4

リストをループして手動でチェックするList<String> 代わりに、binarySearchを使用してこれを実行したいのですが、その方法がわかりません。

古い方法：

for(String s : list) {
  if(s.startsWith("contact.")
     return true;
}

代わりに私はこのようなものが欲しいです：

Collections.sort(list);
Collections.binarySearch(list, FindContactComparator());

誰かが私がこのコンパレータを書くのを手伝ってもらえますか？
binarySearchを使用する代わりにこれを行うためのより良い方法はありますか？

4

5 に答える 5

3

これは機能するはずです：

        Comparator<String> startsWithComparator = new Comparator<String>() {
            public int compare(String currentItem, String key) {
                if(currentItem.startsWith(key)) {
                    return 0;
                }
                return currentItem.compareTo(key);
            }
        };

int index = Collections.binarySearch(items, "contact.", startsWithComparator);

ただし、並べ替えとその後のバイナリ検索は、シングルパスの反復よりも効率的ではありません。

補遺：

上記の答えはあなたを助けますが、ここに別の方法があります（Scala、Googleコレクションからインスピレーションを得ています）：

List<String> items = Arrays.asList("one", "two", "three", "four", "five", "six");
int index = find(items, startsWithPredicate("th"));
System.out.println(index);


public static Predicate<String> startsWithPredicate(final String key) {
    return new Predicate<String>(){
        @Override
        public boolean apply(String item) {
            return item.startsWith(key); 
        }
    };
}

public static <T> int find(Collection<T> items, Predicate<T> predicate) {
    int index = 0;
    for(T item: items) {
        if(predicate.apply(item)) {
            return index;
        }
        index++;
    }
    return -1;
}

interface Predicate<T> {
    boolean apply(T item);
}

ここで重要なのは、find（）メソッドが「マッチング」ロジックに関連付けられていないことです。述語を満たす要素を見つけるだけです。したがって、たとえば、述語の別の実装を渡すことができます。'endsWith'をチェックしてfind（）メソッドを実行すると、特定の文字列で終わる見つかったアイテムが返されます。さらに、find（）メソッドは、あらゆるタイプのコレクションに対して機能します。必要なのは、コレクション要素タイプの要素をブール値に変換する述語だけです。単純なロジックに関するこの複数行のコードは、Javaがファーストクラス関数をサポートしていないことも示しています。

于 2010-08-11T09:48:45.917 に答える
1

問題は、二分探索が決して振り返らないことです。私はこれを解決するために、バイナリ検索を使用して最初に一致する要素を見つけ、次に逆方向にループしてこの部分文字列の最初の出現を見つけ、続いてすべての一致する要素を収集するループを見つけました。

于 2010-08-11T09:00:29.393 に答える
1

あなたが今これをしている方法は、実際にはパフォーマンスの観点から最良の方法だと思います。ソート自体は、ソートされていないリストを単純に繰り返すよりもおそらくコストがかかります。ただし、いくつかのテストを実行する必要があることを確認してください（ただし、JITコンパイルのために聞こえるほど簡単ではありません）。

あなたが探している基準は常に「で始まる」ですか？あなたの質問では、正規表現について話しているからです。

これを実装したい場合は、少なくともComparator検索と同じものを並べ替えに使用する必要があります。コンパレータ自体は非常に単純です。基準に一致するものすべてを、一致しないものすべての前に置くものを書くだけです。しばらくJavaを実行していないため、構文が完全に正しくない可能性があります。

public class MyComparator<string> implements Comparator<string> {
    private string prefix;
    public MyComparator(string prefix) {
        this.prefix = prefix;
    }
    public int compare(string s0, string s1) {
        if (s0.startsWith(prefix) && s1.startsWith(prefix)) {
            return 0;
        }
        else if (s0.startsWith(prefix)) {
            return -1;
        }
        else if (s1.startsWith(prefix)) {
            return 1;
        }
        return 0;
    }
    public bool equals(object comp) {
        return true;
    }
}
于 2010-08-11T09:34:34.810 に答える
1

リスト自体の並べ替えには、リストの線形スキャンよりも時間がかかります。（比較ベースのソートには、 n （log n）に比例する時間がかかります。nはリストの長さです。）

ほとんどの場合、リストが完全に並べ替えられている場合でも、並べ替えアルゴリズムは、これを確認するために少なくともリストを反復処理する必要があります。

基本的に、並べ替えアルゴリズムをどのように実装しても、アルゴリズムは（最良の場合でも）少なくともすべての要素を調べる必要があります。したがって、「concat」の線形検索は、おそらくここでの最良のオプションです。

より複雑な解決策は、文字列を含むリストをサブクラス化し、「concat」の最初の出現のインデックスを維持することです。

文字列は不変であるため、追加、削除などをオーバーライドし、それに応じてインデックスを更新するだけです。

于 2010-08-11T09:48:34.123 に答える
1

ちょうど別のコンパレータ（正規表現付き）：

Comparator<String> comparator = new Comparator<String>() {

    private final Pattern containsPattern = Pattern.compile(searchTerm,Pattern.CASE_INSENSITIVE);

    public int compare(String o1, String o2) {

        Matcher contains1 = containsPattern.matcher(o1);
        Matcher contains2 = containsPattern.matcher(o2);
        boolean find1 = contains1.find();
        boolean find2 = contains2.find();

        if(find1 && find2){
            int compareContains = contains1.end() - contains2.end();
            if (compareContains == 0) {
                return o1.compareTo(o2);
            } else {
                return compareContains;
            }
        }else if(find1){
            return -1;
        }else if(find2){
            return 1;
        }else{
            return o1.compareTo(o2);
        } 
    } 
};

Input ArrayList (search term: dog):

「yxcv」、「dogb」、「doga」、「abcd」、「aDog」

Output(sorted) ArrayList:

「doga」、「dogb」、「a Dog」、「abcd」、「yxcv」

于 2012-08-23T22:23:31.980 に答える