33167


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

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

[code]

    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();
    
[/code]


CC BY-SA 3.0
2017-03-07T01:49:21.687
33154
2019-07-28T11:08:05.503
2019-07-28T11:08:05.503
32986
20956
question
javascript promise
クイックソートの処理をawaitで制御したい


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

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

[code]

    {
      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(',')}`);
      })();
    }
[/code]

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

[code]

    {
      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}`);
        }
      );
    }
[/code]

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

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

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

* * *

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

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

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

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

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

[code]

    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
    
[/code]

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 に代入

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


CC BY-SA 3.0
2017-03-07T11:30:01.757
33167
2017-03-08T07:45:47.247
2017-03-08T07:45:47.247
9796
9796
33154
answer