11

Java で GapBuffer リストを実装しましたが、パフォーマンスが低下する理由がわかりません。C# で記述された同様のコードは期待どおりに動作します。リストの中間への挿入は、C# の List の実装よりもはるかに高速です。しかし、Java 版の動作がおかしくなっています。

ベンチマーク情報は次のとおりです。

Adding/removing 10,000,000 items @ the end of the dynamic array...
ArrayList: 683 milliseconds
GapBufferList: 416 milliseconds

Adding/removing 100,000 items @ a random spot in the dynamic array...
  - ArrayList add: 721 milliseconds
  - ArrayList remove: 612 milliseconds
ArrayList: 1333 milliseconds
  - GapBufferList add: 1293 milliseconds
  - GapBufferList remove: 2775 milliseconds
GapBufferList: 4068 milliseconds

Adding/removing 100,000 items @ the beginning of the dynamic array...
ArrayList: 2422 milliseconds
GapBufferList: 13 milliseconds

Clearly, the GapBufferList is the better option.

ご覧のとおり、リストの先頭に挿入すると、ギャップ バッファーは期待どおりに動作します。これは、ArrayList よりも何倍も何倍も優れています。ただし、リスト内のランダムな場所で挿入および削除する場合、ギャップ バッファーには説明できない奇妙なパフォーマンス ペナルティがあります。さらに奇妙なのは、GapBufferList からアイテムを削除するのは、アイテムを追加するよりも遅いという事実です。それらのコードはほとんど同じです:

@Override
public void add(int index, T t)
{
    if (index < 0 || index > back.length - gapSize) throw new IndexOutOfBoundsException();
    if (gapPos > index)
    {
        int diff = gapPos - index;
        for (int q = 1; q <= diff; q++)
            back[gapPos - q + gapSize] = back[gapPos - q];
    }
    else if (index > gapPos)
    {
        int diff = gapPos - index;
        for (int q = 0; q < diff; q++)
            back[gapPos + q] = back[gapPos + gapSize + q];
    }
    gapPos = index;
    if (gapSize == 0) increaseSize();
    back[gapPos++] = t; gapSize--;
}
@Override
public T remove(int index)
{
    if (index < 0 || index >= back.length - gapSize) throw new IndexOutOfBoundsException();
    if (gapPos > index + 1)
    {
        int diff = gapPos - (index + 1);
        for (int q = 1; q <= diff; q++)
            back[gapPos - q + gapSize] = back[gapPos - q];
    }
    else
    {
        int diff = (index + 1) - gapPos;
        for (int q = 0; q < diff; q++)
            back[gapPos + q] = back[gapPos + gapSize + q];
    }
    gapSize++;
    return back[gapPos = index];
}

ギャップ バッファーのコードはこちらから、ベンチマーク エントリポイントのコードはこちらからご覧いただけます。Flow.***Exception(への参照をに置き換えることができますRuntimeException。)

4

2 に答える 2

0 
 public E remove(int index) {

     rangeCheck(index);

     modCount++;

     E oldValue = elementData(index);

     int numMoved = size - index - 1;

     if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);

     elementData[--size] = null; // Let gc do its work

     return oldValue;

 }

それが ArrayList の remove メソッドのソースです。それはSystem.arraycopy（非常に巧妙に）使用していて、ループを使用しているため、ArrayList はスコアを付けます。同様のものを実装してみてください。同様のパフォーマンスが得られます。

于 2013-04-09T14:31:55.327 に答える