2

約 10^7 という巨大なサイズのキーと値のペアのマップがあり、その内容を更新するために 1 秒間に 15 回ループする必要があります。適切な複雑さを提供し、必要な時間を短縮するクラスまたは構造はありますか?ループする？

現在、私はTreeMapを使用していますが、contains、put、get、removeの複雑さはlog nだけです。要素をループするのは複雑です

構造を知っていますか、またはn 以下の複雑さを減らす可能性のあるアイデアはありますか?

4

2 に答える 2

5

コレクション全体を任意にループする必要がある場合、n よりもうまくいきません。コレクション全体をループする必要がある場合は、単純な ArrayList を使用できます。ただし、キーを使用してコレクション内の特定のデータにアクセスする必要がある場合は、TreeMap で問題ありません。

于 2011-08-01T20:09:33.260 に答える
0

問題が O(n) 値のすべてを調べるだけの場合、シーケンシャル (または有限並列) コンピューターで O(n) バウンドを打ち負かすことはできません。

有限並列マシンがあり、要素を更新する方法によっては、高速化を達成できます。たとえば、CUDA と GPU、または OpenMP/MPI とクラスター/マルチコア ワークステーションを使用すると、A[i] = A[i]^3 などを高速に計算できます。もちろん、コミュニケーションの問題もありますが、これは注目すべき点かもしれません。

于 2011-08-01T20:21:06.213 に答える