4

javascript初学者です。どうかよろしくお願いします。

下記コードなんですが、クイックソートを視覚化しようと思い、処理の途中にawaitをいれて再帰関数を作りました。
さらにその再帰関数をpromiseオブジェクトにして、ソートが完了した時点でresolveさせようと思ったのですが、どういう条件でresolveすればいいのかがわかりません。

var arr=[3,6,21,32,43,54,6,57,88,0,4,32,5,8,6];

async function qsort(array,left,right,resolve){
    var  i,j;
    var pivot; 
    i=left; 
    j=right; 
    pivot=array[Math.floor((left+right)/2)];

    while(1){
        while(array[i]<pivot){ 
            await new Promise((resolve)=>{setTimeout(()=>{resolve()},10)})
            i++;
        }
        while(pivot<array[j]){ 
           await new Promise((resolve)=>{setTimeout(()=>{resolve()},10)})
            j--;   
        }
        if(i>=j) break; 
          await new Promise((resolve)=>{setTimeout(()=>{resolve()},10)})
          Swap(array,i,j); 
          i++;j--; 
    }  
    if(left<i-1){  
    qsort(array,left,i-1,resolve);   
    } 

    if(j+1<right){ 
      qsort(array,j+1,right,resolve)   
    }  
    if(left>=i-1&&j+1>=right){return resolve();}
}

function Swap(array,i,j){
     var temp=array[i];
     array[i]=array[j];
     array[j]=temp;
 }

async function sortTest(){
    await new Promise((resolve)=>{qsort(arr,0,arr.length-1,resolve);})//ソートが終わるまで待つ
    console.log(arr)//ソート完了後のarrを表示したい
}

sortTest();

1 件の回答 1

4

async / await は非同期処理(Promise)の完了待ちを明示するための仕組みです
通常、quicksort は同期的に処理できるので、同期的に処理すればよいと思います

quicksort の処理が順に進む様子を確認するためには、generatorを使うのがよいと思います
以下の例は「quicksort を1段階進めるたび、500ms sleepする」という例です

{
  async function wait(ms) {
    console.info(`wait for ${ms}ms...`);
    return new Promise(resolve => setTimeout(resolve, ms));
  }

  function* qsort(arr, left, right) {
    if (left < right) {
      const pivot = arr[left + (right - left) / 2 | 0];
      let i = left;
      let j = right;
      while (true) {
        while (arr[i] < pivot) {i++;}
        while (pivot < arr[j]) {j--;}
        if (i >= j) {break;}


        [arr[i], arr[j]] = [arr[j], arr[i]];
        yield arr;
        i++;
        j--;
      }
      yield* qsort(arr, left, i - 1);
      yield* qsort(arr, j + 1, right);
    }

  }

  (async function() {
    const arr = [7, 6, 3, 4, 8, 1, 9, 5, 2];
    for (let value of qsort(arr, 0, arr.length - 1)) {
      await wait(500);
      console.info(value.join(','));
    }
    console.info(`sort finished: ${arr.join(',')}`);
  })();
}

quicksort が非同期処理なら、async / await を利用すると便利です
以下の例は「quicksort は1段階進むたび、500ms sleepする」という例です

{
  async function wait(ms) {
    console.info(`wait for ${ms}ms...`);
    return new Promise(resolve => setTimeout(resolve, ms));
  }

  async function qsort(arr, left, right) {
    if (left < right) {
      const pivot = arr[left + (right - left) / 2 | 0];
      let i = left;
      let j = right;
      while (true) {
        while (arr[i] < pivot) {i++;}
        while (pivot < arr[j]) {j--;}
        if (i >= j) {break;}

        await wait(500); // asynchronous
        [arr[i], arr[j]] = [arr[j], arr[i]];
        console.info(arr.join(','));
        i++;
        j--;
      }
      await qsort(arr, left, i - 1);
      await qsort(arr, j + 1, right);
    }
    return arr;
  }

  const arr = [7, 6, 3, 4, 8, 1, 9, 5, 2];
  qsort(arr, 0, arr.length - 1).then(
    result => {
      console.info(`sort finished: ${result.join(',')}`)
    },
    err => {
      console.error(`error occured: ${err}`);
    }
  );
}

generator と async / await は似たような記述になります
(async / await は内部で generator を利用しています)

  • 1つも非同期処理が含まないなら generator
    • generator は途中の値が手に入る
  • 1つ以上非同期処理を含むなら async / await
    • async / await は途中の値が手に入らず、最終的な値だけが手に入る

という特徴があるので、使い分けるとよいと思います


以下、コメントへの回答です

generator は「総要素数が不明なループ」で利用するととても強力です
(今回のquicksortの中間状態の総数も不明ですね)
例えば、リモートにあるデータを順番に取得する場合などは、generatorを利用するのが望ましいです

全部取得してから処理するようにしてしまうと、全データ取得するまで何もしないので非効率 & メモリ負荷が大きい、という問題があります
逐次処理にすることで、取得が完了したデータを非同期処理に回せる & メモリ負荷低減 が狙えます

ただ、プログラムの見通しや可用性は 全部処理 >> 逐次処理 なので、予想される負荷に応じて generator と 通常のループ を使い分けたいですね

yield * someIteratorという記述は、someIterator を順に yield する、という記述です

const gen = function* () {
  yield* [1,2]; // use Array.prototype[Symbol.iterator]
  yield* '34'; // use String.prototype[Symbol.iterator]
  yield* new Set([5, 6]); // use Set.prototype[Symbol.iterator]
  yield* new Map([['key1', 7], ['key2', 8]]); // use Map.prototype[Symbol.iterator]
  // yield* {key3: 9, key4: 10} // 仕様策定中...まだ使えない
};
const iter = gen();
console.info(iter.next()); // {value: 1, done: false}
console.info(iter.next()); // {value: 2, done: false}
console.info(iter.next()); // {value: '3', done: false}
console.info(iter.next()); // {value: '4', done: false}
console.info(iter.next()); // {value: 5, done: false}
console.info(iter.next()); // {value: 6, done: false}
console.info(iter.next()); // {value: ['key1', 7], done: false}
console.info(iter.next()); // {value: ['key2', 8], done: false}
console.info(iter.next()); // {value: undefined, done: true}

console.info(iter.next === iter[Symbol.iterator]().next); // true

for (let yieldValue of someIterator) { ... } は

  • for ... of が someIterator[Symbol.iterator]().next() を呼び出す
  • someIterator は直前の実行位置から再開、次の yield まで進んで
    {value: (yieldの右側の値), done: (yield行ならfalse, return行ならtrue)} を返却
  • for ... of が done の値を使ってループ終了判定
  • for ... of が value の値を yieldValue に代入

という面倒な処理を一気にしてくれる、便利アイテムです

4
  • generatorについてよくわからなかったので大変勉強になりました!iやjの値が変わったときに処理を挟みたいときはyieldでiやjを一旦返せばいいのですね。 ところでyield* qsort(arr, left, i - 1)の部分なんですが、新しく引数を変えたgeneratorを作って、そこで次のyieldまで処理してその返り値が下のforof文のvalueに収まり、そのyieldからまた再開するという感じなんでしょうか。むむむ、難しい…
    – 1年生
    Commented 2017年3月7日 16:56
  • コメントでいただいた質問に回答しました
    – gocho
    Commented 2017年3月8日 7:37
  • 2度にわたり詳細な解説ありがとうございます!なるほど逐次処理によるメリットは大きいのですね。for ... ofはgenerator関数をyield行が尽きるかまたはreturnに当たるまでyieldを区切りに逐次実行しその返り値に対し逐次何らかの処理していくということですね。なんとなくgeneratorのイメージがわいてきました。考えてみれば自分の失敗作では2又に再帰してルートが枝分かれしているのに、1本道で行って帰ってきて寄り道する間もなく速攻で未完成品を渡されていたのですねw。
    – 1年生
    Commented 2017年3月8日 18:53
  • generatorであれば*yeildの先に2本の道があるか行き止まりかですべてのルート探索後にforof文のdoneがtrueになってソートされた配列が渡される。async/awaitの場合はawaitとreturnを例のように配置することですべてのルートでreturnを踏むことでthenチェーンにつながるということでしょうか。
    – 1年生
    Commented 2017年3月8日 19:26

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。