0

ソートされたリスト クラスに新しい要素を追加するための簡単な方法を作成しました。コードは Dart にありますが、すべての C のような言語で何が起こっているかはかなり明白なはずです。いくつかの簡単な単体テストを実行しました。新しい要素を正しい順序で追加しているようですが、私の質問は、完全な証拠ですか? それはより効率的でしょうか？バイナリ検索を使用して、挿入する適切なインデックスを見つけようとしています。また、新しいオブジェクトが挿入されたインデックスを返します。

int add(T obj){

  int loIdx = 0;
  int upIdx = list.length - 1;
  int i;

  while(loIdx <= upIdx){

    i = loIdx + ((upIdx - loIdx) >> 1);

    switch(_compare(obj, list[i])){

      case 0:

        loIdx = i;

        upIdx = i - 1;

        break;

      case -1:

        upIdx = i - 1;

        if(loIdx == upIdx){

          if(_compare(obj, list[loIdx]) == 1){

            loIdx++;

          }

        }

        break;

      case 1:

        loIdx = i + 1;

        break;

    }

  }

  list.insert(loIdx, obj);

  return loIdx;

}

完全を期すために、実際に機能することを示すために私が使用している単体テストの1つを次に示します。

test('Order',(){

  SortedList<int> intList = new SortedList<int>((int a, int b) => a.compareTo(b));

  intList.add(5);
  intList.add(7);
  intList.add(0);
  intList.add(3);
  intList.add(6);
  intList.add(9);
  intList.add(1);
  intList.add(2);
  intList.add(8);
  intList.add(5);
  intList.add(4);

  expect(intList.list, orderedEquals([0,1,2,3,4,5,5,6,7,8,9]));

});
4

1 に答える 1

2

Dart を使ったことはありませんが、次の行があります。

i = loIdx + ((upIdx - loIdx) % 2);

本当に奇妙に見えます。通常、次のようなものが表示されると予想されます。

i = loIdx + ((upIdx - loIdx) >> 1);

また

i = loIdx + ((upIdx - loIdx) / 2);
于 2013-10-27T22:32:49.213 に答える