3

私は、Scala のハッシュ関数が大きなハッシュ テーブル (数十億のエントリを含む、たとえば、特定の DNA のビットが出現する頻度を格納するため) に対してどれだけうまくスケールするかを調べようとしています。

ただし、興味深いことに、HashMap と OpenHashMap の両方が、初期サイズを指定するパラメーターを無視しているようです (2.9.2. および 2.10.0、最新ビルド)。

これは、最初の 800.000 前後以降、新しい要素の追加が非常に遅くなるためだと思います。

挿入される文字列のエントロピーを増やしてみましたが (以下のコードの文字 ACGT のみ)、効果はありません。

この特定の問題に関するアドバイスはありますか？また、数十億のエントリを持つハッシュ テーブルに Scala の組み込み型を使用することが適切かどうかについて、ご意見をお聞かせいただければ幸いです。

import scala.collection.mutable.{ HashMap, OpenHashMap }    
import scala.util.Random

object HelloWorld {
    def main(args: Array[String]) {


        val h = new collection.mutable.HashMap[String, Int] {
            override def initialSize = 8388608
        }

        // val h = new scala.collection.mutable.OpenHashMap[Int,Int](8388608); 



        for (i <- 0 until 10000000) {
            val kMer = genkMer()

            if(! h.contains(kMer))
            {
                h(kMer) = 0;
            }
            h(kMer) = h(kMer) + 1;

            if(i % 100000 == 0)
            {
                println(h.size);
            }
        }

        println("Exit. Hashmap size:\n");
        println(h.size);

    }

    def genkMer() : String =
    {
        val nucs = "A" :: "C" :: "G" :: "T" :: Nil

        var s:String = "";
        val r = new scala.util.Random
        val nums = for(i <- 1 to 55 toList) yield r.nextInt(4) 
        for (i <- 0 until 55) {
            s = s + nucs(nums(i))
        }
        s
    }
}
4

3 に答える 3

3

何十億ものエントリのマップを管理するために Java データ構造を使用するつもりはありません。理由:

  • Java HashMap の最大バケットは 2^30 (~1B) なので、
    • デフォルトの負荷係数では、マップが 750 M エントリの後にサイズ変更しようとすると失敗します
    • 負荷係数 > 1 を使用する必要があります (たとえば、5 の場合、理論的には 50 億のアイテムが得られます)。
    • 負荷率が高いと、多くのハッシュ衝突が発生し、読み取りと書き込みの両方のパフォーマンスが大幅に低下し始めます。
    • 実際に Integer.MAX_INTEGER 値を超えると、どのような問題が存在するのかわかりません-マップ上の .size() は、たとえば、実際のカウントを返すことができません
  • Java で 256 GB ヒープを実行することについては非常に心配です。完全な GC にヒットした場合、古い世代の数十億のオブジェクトをチェックするために長い間世界をロックすることになります。

それが私だったら、オフヒープ ソリューション、つまりある種のデータベースを検討するでしょう。（ハッシュコード、カウント）を保存するだけの場合は、多くのキー値ストアの1つが機能する可能性があります。最大のハードルは、数十億のレコードをサポートできるものを見つけることです (2^32 で最大になるものもあります)。

ある程度の誤差を許容できるのであれば、確率論的方法を検討する価値があるかもしれません。私はここの専門家ではありませんが、ここにリストされている内容は関連しているように思えます。

于 2012-11-01T15:46:33.533 に答える
2

まず、initialSizeをオーバーライドすることはできません。これは、HashTableでプライベートなパッケージであるため、scalaを使用できると思います。

private[collection] final def initialSize: Int = 16

次に、初期サイズを設定する場合は、必要な初期サイズのHashTableを指定する必要があります。したがって、16から始めずにこのマップを作成する良い方法はありませんが、2の累乗で大きくなるため、サイズを変更するたびに改善されるはずです。

第三に、scalaコレクションは比較的遅いので、代わりにjava / guava/etcコレクションをお勧めします。

最後に、ほとんどのハードウェアでは数十億のエントリが少し多いため、メモリが不足する可能性があります。ほとんどの場合、メモリマップトファイルを使用する必要があります。これが良い例です（ただしハッシュはありません）。

https://github.com/peter-lawrey/Java-Chronicle

UPDATE1Java コレクションの代わりに次のようなものがあります。

https://github.com/boundary/high-scale-lib

UPDATE 2 コードを実行すると、約800,000エントリの速度が低下しましたが、Javaヒープサイズを大きくすると、正常に実行されました。jvmには次のようなものを使用してみてください。

-Xmx2G

または、メモリの最後のビットをすべて使用する場合は、次のようにします。

-Xmx256G
于 2012-11-01T02:09:24.380 に答える
2

これらは間違ったデータ構造です。RAM の制限にかなり早く到達します (100 GB を超える場合を除き、それでも非常に速く制限に到達します)。

適切なデータ構造が scala に存在するかどうかはわかりませんが、おそらく誰かが Java で何かを行っているでしょう。

于 2012-10-31T22:25:31.210 に答える