入れ子ループのよりよい代替方法

私は現在、Damerau levenshteinアルゴリズムと同様の文字列をArrayList of ArrayListの文字列と比較する必要があるプログラムを作成しています。今、私はこれをやっている方法は、ネストされたコードのループを介してである：入れ子ループのよりよい代替方法

Damerau d = new Damerau(); 

for(int i = 0;i<outer.size();i++) { 
    System.out.println(i); 
    String cstring = outer.get(i).get(5); 
    for(ArrayList<String> current : outer) { 
     if(d.distance(cstring , current.get(5)) < 30){ 
      //System.out.println(cstring); 
      outer.get(i).set(0, current.get(0)); 
      break; 
     } 
    } 
}

しかし、ArrayListには33000の文字列の配列リストで構成されていて、これは本当に遅いです。

出典

2017-11-02 cheese sells

データベースからデータを読み取っている場合、すべてのデータを取得するのではなく、必要なデータだけを取得します。 SQL問合せは、行ごとの比較よりも比較的高速です。あなたがRDBMSを使用していない場合は、少なくともsqliteのデータをダンプし、クエリを使用してデータを取得することをお勧めします。もう一つは、プロファイラツールを使用して、どのラインが正確に時間を消費しているかを特定することです。可能であれば、小さなリストと独立したスレッドでデータを分割してみてください。 –

あなたのコードをベンチマークして、最も多くの時間が費やされた場所を確認しましたか？ 1つの最適化は、内側のループの繰り返しごとにフェッチするのではなく、外側のループ内で 'outer.get（i） 'を1回だけフェッチすることです。 – Turing85

既にチェックした値にタグを付けてスキップするとどうなりますか？ 'out.get（i）'だけを設定するのではなく、もし一致すれば 'current 'も更新することができます。 – AxelH

私が正しくあなたのコードを理解するのであれば、あなたはこの線に沿って何かの操作を行います。

 
for each outer as cstring : 
    for each outer as current: 
     levenshtein(cstring, current)

あなたが不要な比較のトンを作る意味。文字列が[a, b, c]のリストがあると仮定すると、テストする組み合わせは[aa, ab, ac, ba, bb, bc, ca, cb, cc]です。これには、常に0である自分自身（aa, bb, cc）との比較、およびスワップされたパラメータ（ab,ba,ac,ca,bc,cb）を持つlevenshtein関数への呼び出しが含まれます。これらは常に同じです。したがって、同じペアと自己テストをスキップする場合は、組み合わせをテストする必要があります。ab,ac,bc i + 1の内部ループを開始することで、コード内で簡単にこれを実現できます。

出典

2017-11-02 15:06:23

入れ子ループのよりよい代替方法

答えて

関連する問題