11

他のリストにない子を持つことができるように、2つのArrayListを減算したいと思います。

私はそれをこのようにします：

removeIDs=(ArrayList<Integer>) storedIDs.clone();
removeIDs.removeAll(downloadedIDs);

downloadIDs=(ArrayList<Integer>) downloadedIDs.clone();
downloadIDs.removeAll(storedIDs);

問題は、両方のリストに5000の子が含まれていて、私のandroidphoneではほぼ4秒かかることです。

これを行うための迅速な方法はありますか？セットをより速く使用していますか？（リストに重複する値はありません）

私はAndroidアプリを開発しています

4

5 に答える 5

7

順序を維持する必要がない限り、ArrayListの代わりにHashSetを使用してください。

要素を削除するには、リストの実装のために完全なリストをスキャンする必要があります。比較すると、HashSetは、ハッシュコードを計算してから、ターゲットバケットを特定するだけです。

于 2013-03-12T20:36:17.833 に答える
1

セットはもっと速くなければなりません。現在、基本的にn^2ループを実行しています。removeIDsのすべての要素をループし、そのIDがdownloadedIDsにあるかどうかを確認します。これには、リスト全体を検索する必要があります。ダウンロードしたIDが、HashSetなどの検索用のより高速なものに格納されている場合、これははるかに高速になり、O（n ^ 2）ではなくO（n）になります。また、Collections APIにはもっと高速なものがあるかもしれませんが、私にはわかりません。

順序を保持する必要がある場合は、通常のHashSetの代わりにLinkedHashSetを使用できますが、要素の挿入/削除でメモリが多少追加され、パフォーマンスが少し低下します。

于 2013-03-12T20:37:53.480 に答える
1

整数IDが比較的狭い範囲に収まらない限り、HashSetの推奨事項に同意します。その場合、HashSetとBitSetのそれぞれを使用してベンチマークを行い、実際には、環境内のデータに対してどちらか速い方を使用します。

于 2013-03-12T20:39:43.930 に答える
1

まず第一に、私は長い答えをお詫びします。私が間違っている場合は、いつでも私を訂正してください。ここでは、ソリューションを解決するためのいくつかのオプションを比較しています

オプション1<ArrayList>：

あなたのコードでは、ArrayList.removeAllメソッドを使用して、removeAllのコードを調べます。

removeAllのソースコード

public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false);
    }

batchRemoveだから、メソッドに何があるかを知る必要があります。こちらがリンクです。あなたが見ることができるならここで重要な部分

for (; r < size; r++)
         if (c.contains(elementData[r]) == complement)
                 elementData[w++] = elementData[r];

contains次に、メソッドの単なるラッパーであるメソッドを調べてみましょうindexOf。リンク。indexOfメソッドには、O（n）操作があります。（ここでは一部に注意してください）

 for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                    return i;

だから全体的にそれは

O（n ^ 2）

での操作removeAll

オプション2<HashSet>： 以前、ここに何かを書きましたが、ある時点で間違っていたようですので、これを削除します。ハッシュセットに関する専門家からの提案を参考にしてください。あなたの場合、ハッシュマップがより良い解決策になるかどうかはわかりません。だから私は別の解決策を提案しています

オプション3<私の提案あなたが試すことができます>：

ステップ1：データがソートされている場合、このステップは必要ありません。それ以外の場合は、減算するリストをソートします（2番目のリスト）

ステップ2：ソートされていないリストのすべての要素について、2番目のリストでバイナリ検索を実行します

ステップ3：一致するものが見つからない場合は別の結果リストに保存しますが、一致するものが見つかった場合は追加しないでください

ステップ4：結果リストが最終的な答えです

オプション3のコスト：

ステップ1：ソートされてO(nlogn)いない場合

ステップ2： O(nlogn)時間

ステップ3： O(n)スペース

****

したがって、全体的なO（nlogn）時間とO（n）スペース

****

于 2013-03-13T04:09:31.407 に答える
0

リストが必要な場合は、 LinkedListを選択できます。あなたの場合、@ Chrisが言ったように、ArrayList実装は各削除のすべての要素を移動します。

LinkedListを使用すると、ランダムな追加/削除のパフォーマンスが大幅に向上します。この投稿を参照してください。

于 2013-03-12T21:13:20.437 に答える