大規模な配列全体の類似性

Question

私は非常に大きな配列（32kワード程度）を持っており、配列全体の類似性を効率的にチェックしたいと思っていました。私はそれがパーセントで返されたかった。私はまた、どのくらい多くのスポットが配列に正確にあるのかわかりません。私はこれを行う最も効率的な方法が何であるか分かりません。私の現在の考え方は、配列内の2つの単語の間の類似性をチェックし、その類似性を平均化することです。私はもっ​​と効率的な解決策を探していた。 これは私がこれまで試したものです：

import java.util.*; 
import org.apache.commons.lang3.StringUtils; 
public class Trial2 { 

public static void main(String[] args) { 
    ArrayList<Double> averageValues = new ArrayList<>(); 
    ArrayList<String> temp = new ArrayList<>(); //holds all the words in the list 
    for(int i = 0; i < temp.size() - 1; i++) { 
     double k = StringUtils.getLevenshteinDistance(temp.get(i), temp.get(i + 1)); 
     averageValues.add(k/(double)temp.get(i).length()) 
    } 
    double average; 
    for(int i = 0; i < averageValues.size(); i++) { 
     average += averageValues.get(i); 
    } 
    average = average/averageValues.size(); 
} 
} 

は私の一時リストがすでに満杯であると仮定。このコードの問題は、すでに2つのforloopsに埋め込まれていて、n^3にヒットしたくないということです。この問題を解決する他の方法はありますか？

助けてください。

Answer 1

以下は、個々のエントリ（単語など）の長さが増加しないと仮定します。

あなたのアルゴリズムは、すべてのエントリを次のすべてのエントリだけを比較するため（他のすべてのエントリではないため）、配列のエントリ数でO（n）です。トレードオフは、（それだけで）全体の類似性のヒューリスティックな推定値を提供することです。良い：あなたのアルゴリズムはすべてのエントリーを訪問するので、各エントリーは少なくともヒューリスティックな結果に影響を与えます（しかし、以下の統計情報を参照してください）。

提案：

成長コストを回避するために、あなたはaverageValuesに一時のものに等しい初期サイズを与えることができる（-1あなたがしたい場合）。しかし、あなたが次のことをするなら、これは必要でさえありません。お使いのバージョンではチャンスがあるので、これはより速く実行される可能性

average = sumOfDifferences/temp.size(); 

：ループの後に続いて

sumOfDifferences += k/(double)temp.get(i).length(); 

：あなたが最初のをさせることにより、第2のループを排除することができる

はただ結果を蓄積しますその時点で別のスレッド/プロセスが実行されていた場合、2番目のループが実行されたときにエントリがキャッシュ内で無制限であることを示します。 これにより、averageValuesのArrayListを削除して、成長コストを無制限にすることもできます。

最適化ではなく、考慮する必要があります。(double)temp.get(i).length()で割ることが達成しようとしていることに意味があるかどうかを考えてください。

統計的には、次のエントリと常に比較しているのは面倒かもしれません。例えば。単語がソートされていれば大きな偏りがあります。最初に配列をランダム化する方が良いかどうかを考えてみてください。