9

Java では、文字列である Name という名前のメンバーを持つ TestClass という名前のクラスがあります。このタイプの ArrayList もあり、名前のアルファベット順に並べ替えられています。私がやりたいことは、TestClass の新しいインスタンスを配置するのに最適なインデックスを見つけることです。これまでに思いついた最善のアプローチは次のとおりです。

public static int findBestIndex(char entry, ArrayList<TestClass> list){
    int desiredIndex = -1;
    int oldPivot = list.size();
    int pivot = list.size()/2;
    do
    {
        char test = list.get(pivot).Name.charAt(0);
        if (test == entry)
        {
            desiredIndex = pivot;
        }
        else if (Math.abs(oldPivot - pivot) <= 1)
        {
            if (test < entry)
            {
                desiredIndex = pivot + 1;
            }
            else
            {
                desiredIndex = pivot - 1;
            }
        }
        else if (test < entry)
        {
            int tempPiv = pivot;
            pivot = oldPivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }
        else
        {
            int tempPiv = pivot;
            pivot = pivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }

    } while (desiredIndex < 0);

    return desiredIndex;
}

基本的に、配列を半分に分割し、値がその時点の前、後、またはその時点にあるかどうかを確認します。後である場合は、配列の前半を確認します。それ以外の場合は、後半を確認してください。次に、繰り返します。この方法は最初の文字でのみテストすることを理解していますが、それは簡単に修正でき、私の主な問題には関係ありません。一部のシナリオでは、この方法で十分に機能します。ほとんどの場合、それは恐ろしく機能します。新しいピボット ポイントが適切に検出されていないと思います。その場合、どうすれば修正できますか?

編集：明確にするために、これを在庫システムに使用しているため、LinkedListが適切かどうかわかりません。私が ArrayList を使用しているのは、それらの方が私には馴染みがあり、必要に応じて別の言語に翻訳しやすいためです (現時点では、C# に移行している可能性があります)。C# にない場合は完全に書き直さなければならないため、 Comparable のようなものは避けようとしています。

一部の編集 Duex: 私が間違っていたことを理解しました。以前のピボット ポイントを使用する代わりに、チェックしている領域の境界を設定および変更し、それに基づいて新しいピボットを作成する必要がありました。

4

6 に答える 6

5

すでに指摘したように、これを自分で実装する理由はありません。単純なコード例:



    class FooBar implements Comparable<FooBar> {

        String name;

        @Override
        public int compareTo(FooBar other) {
           return name.compareTo(other.name);
        }
    }

    TreeSet<FooBar> foobarSet = new TreeSet<>();
    FooBar f1;
    foobarSet.add(new FooBar("2"));
    foobarSet.add(f1 = new FooBar("1"));

    int index = foobarSet.headSet(f1).size();

( TreeSet 内の要素のインデックスを見つける方法に基づく)

于 2013-05-26T22:49:58.457 に答える
1

ツリー、優先キューなど、リストの代わりに使用できる他のデータ構造があります。

于 2013-05-26T22:26:10.597 に答える
1

問題は次のコードにあると思います。

else if (test < entry)
{
    int tempPiv = pivot;
    pivot = oldPivot - (oldPivot - pivot)/2;
    oldPivot = tempPiv;
}
else
{
    int tempPiv = pivot;
    pivot = pivot - (oldPivot - pivot)/2;
    oldPivot = tempPiv;
}

test < entry または wether test > entry と同じアクションを実行しています。これにより、検索しているアイテムが配列の先頭にある場合に線形検索が行われます。

私は（低と高）のように使用することを好みます

high = list.size();
low = 0;

do {
   pivot = (high + low) / 2;
   if (test < entry) {
      low = pivot;
   } else if (test > entry) {
      high = pivot
   } else {
      ....
   }
} while ...;
于 2013-05-27T01:37:35.203 に答える