0

テキストファイルで多数の可能性を検索しようとしています。

たとえば、一意の名前を含むテキスト ファイルを検索したいとします。ここで、X という名前が見つかった場合は、X を別のファイルに保存します。

ここでの問題は、1000 を超える一意の名前があり、一意の名前ごとに 1000 回の検索呼び出しと if ステートメントを実行したくありません。

java/javascript/php でそれを行うより良い方法はありますか?

4

1 に答える 1

2

名前のセットがあり、別の名前のセットと一致する名前を見つけたいとします。

Set<String> namesFromFile = readFile(filename);
Set<String> namesToMatch = readFile(matchingNames);
namesToMatch.retainAll(namedFromFile);

これretainAllは O(n) 演算で、nは小さい方のセットのサイズです。Java では、retainAll1000 個の値のセットを取得するのに数ミリ秒かかる場合があります。

Set.retainAll()は次のことを行います

指定されたコレクションに含まれるこのセットの要素のみを保持します (オプションの操作)。つまり、指定されたコレクションに含まれていないすべての要素をこのセットから削除します。指定されたコレクションもセットである場合、この操作はこのセットを効果的に変更し、その値が 2 つのセットの交差になるようにします。

1000 個のセットは非常に小さいため、正確にテストするのは難しいため、このテストでは 10 倍大きいもの、つまり 100,000 個の要素のセットに対して 10,000 個の要素をテストします。

public static void main(String... args) {
    Set<String> names1 = generateStrings(100000, 2);
    Set<String> names2 = generateStrings(10000, 3);
    for (int i = 0; i < 10; i++) {
        long start = System.nanoTime();
        Set<String> intersect= new HashSet<String>(names2);
        intersect.retainAll(names1);
        long time = System.nanoTime() - start;
        System.out.printf("The intersect of %,d and %,d elements has %,d and took %.3f ms%n",
                names1.size(), names2.size(), intersect.size(), time / 1e6);
    }
}

private static Set<String> generateStrings(int number, int multiple) {
    Set<String> set = new HashSet<String>();
    for (int i = 0; i < number; i++)
        set.add(Integer.toBinaryString(i * multiple));
    return set;
}

版画

The intersect of 100,000 and 10,000 elements has 5,000 and took 21.173 ms
The intersect of 100,000 and 10,000 elements has 5,000 and took 10.785 ms
The intersect of 100,000 and 10,000 elements has 5,000 and took 9.597 ms
The intersect of 100,000 and 10,000 elements has 5,000 and took 3.414 ms
The intersect of 100,000 and 10,000 elements has 5,000 and took 2.791 ms
The intersect of 100,000 and 10,000 elements has 5,000 and took 2.629 ms
The intersect of 100,000 and 10,000 elements has 5,000 and took 2.689 ms
The intersect of 100,000 and 10,000 elements has 5,000 and took 2.753 ms
The intersect of 100,000 and 10,000 elements has 5,000 and took 2.704 ms
The intersect of 100,000 and 10,000 elements has 5,000 and took 2.645 ms
于 2012-11-22T18:31:23.677 に答える