1

データ構造クラス プロジェクトからの誤った検索結果をデバッグしています。この現在のプロジェクトでは、順序付けられた展開されたリンク リストを作成し、コンテンツに対して検索を実行してから、包括的開始点から排他的終了点までのアイテムのサブリストを返す必要がありました。これを行うには、内部配列を検索して開始要素のインデックス ポイントを見つける必要があります。これはバイナリ検索で行いますが、これは最初に見つかった一致のみを返し、その前に他の一致が存在する可能性があるため、最初の真の一致を見つけるために配列に戻る必要があります。私はこれを介して行います

//get first index match, work backwards
int index= binarySearch(node.items, 0, node.numUsed, item, comp);
while (index>0 && comp.compare(node.items[index], item)==0){
    index--;
}

教授は、文字列を分割し、各文字を構造内の項目として追加するテスト コードを提供しました。また、ネストされた StringCmp クラスも含めました。これは、comp上記の二分探索宣言のように参照されます。彼の比較方法は

public int compare(String s1, String s2) {
  cmpCnt++;
  return s1.compareTo(s2);
}

ただし、i から o までのサブリスト メソッドでテストを実行すると、このメソッドは true 値を返し、これにより、作成comp.compare(h,i)==0した検索クラスから開始結果がスローされます。return index++私はもともと、構造テストに合格するのに十分な量で補正しましたが、予想される開始点を 1 つずらしました。

では、明らかに false であるのに、なぜこれが true を返すのでしょうか?

EDITは、i から o まで実行されると予想されるサブリスト メソッドの出力を追加しました

入力テスト文字列=abcdefghijklmnopqrstuvwxyzaeiou サブリストメソッドからの戻り:
チャンク 1 (10 の 4 を使用): [h][i][i][j]
チャンク 2 (10 の 4 を使用): [k][l][m][n ]

h はリストにまったく含まれていないはずですが、comp.compare(node.items[index], item)==0は i == h という true を返しています。これは明らかに false です。

編集 2 プロジェクトの 2 番目の部分では、テキスト ファイルを解析し、Artist、Title、および Lyrics フィールドから Song オブジェクトを作成し、プレフィックスを使用してタイトルを検索する必要があります。ここで発生するバグは一文字検索や複数文字検索では発生しないので、テストの StringCmp ネストクラスに問題があると思います。

4

5 に答える 5

5

何compare()が返ってくるのか知っていますか？一般に、このような関数は、最初の引数が2番目の引数よりも小さい場合は負の値を返し、等しい場合は0を返し、最初の引数が2番目の引数よりも大きい場合は正の値を返します。

また、配列でソートを実行しているのは何ですか？binarySearch()問題がそこにあるかどうかを確認できるように、コードを投稿していただけますか？

于 2010-10-29T13:19:12.430 に答える
2

あなたのwhileループ

while (index>0 && comp.compare(node.items[index], item)==0){
    index--;
}

一致ごとにインデックスをデクリメントしているため、最初の一致を 1 ずつオーバーシュートし、一致しなくなったインデックスのままにします。代わりに index-1 の項目で Comparator を呼び出すと、これが修正されます。

while (index>0 && comp.compare(node.items[index-1], item)==0){
    index--;
}
于 2010-10-29T17:56:29.133 に答える
1

独自のバイナリ検索を実装したので、一致が見つかったらすぐに停止するのではなく、これを使用して配列内で最初に一致する要素を検索する必要があります。

現在のアプローチは不必要な複雑さをもたらし、入力配列がすべて同一の値で構成されている場合、O(log N) アルゴリズムを O(N) アルゴリズムに変更する可能性があります。

現在のアルゴリズムは次のようになっていると思います

int low = 0; 
int high = a.length-1;
while (low <= high) {
    int mid = (low + high) / 2;
    int cmp = comp.compare(a[mid], key);
    if (cmp < 0)
        low = mid + 1;
    else if (cmp > 0)
        high = mid - 1;
    else
        return mid;
}
return -1;

これを以下のコードに置き換えるとうまくいくはずです

int low = 0;
int high = a.length-1;
while (low < high) {
    int mid = (low + high) / 2;
    int cmp = comp.compare(a[mid], key);
    if (cmp < 0)
        low = mid + 1;
    else
        high = mid;
}
if (comp.compare(a[low], key) == 0)
    return low;
else 
    return -1;
于 2010-10-29T15:12:28.070 に答える
0

好奇心から、これはあなたがやろうとしていることのよりインラインではありませんか?

//get first index match, work backwards
int index= binarySearch(node.items, 0, node.numUsed, item, comp);

for (int i = index; i >= 0; i--) {
    if (comp.compare(node.items[index], item)==0))
        index = i;
}
于 2010-10-29T13:53:47.520 に答える
0

compareTo(String) メソッドの公式説明を確認してください

ドキュメントから：

戻り値: 引数文字列がこの文字列と等しい場合は値 0。この文字列が文字列引数より辞書的に小さい場合は 0 より小さい値。この文字列が文字列引数よりも辞書的に大きい場合は、0 より大きい値。

于 2010-10-29T13:35:25.713 に答える