1

C＃のコンテキストで最良のアイデアは何でしょうか、

  1. C＃では辞書を使用しています。使用するメモリスペースを減らしたい。何が良くなるでしょうか？

    キータイプがである辞書、Uint64またはキータイプがstring？である辞書 どちらの場合も、値は各ディクショナリで同じカスタムクラスです。

    私は辞書を次のように宣言しました、

    private static readonly Dictionary<string, List<Node>> HashTable =
    new Dictionary<string, List<Node>>();

    クラスノードは次のように定義されます。

    public class Node
{
    public UInt64 CurrentIndex { get; set; }
    public string NextHashedString { get; set; }
    public int NextHashPos { get; set; }
}

    文字列のキーは、実際には次のように計算された文字列からのハッシュ値です。文字列の長さは1〜20文字です。

    static UInt64 CalculateHash(string read, bool lowTolerance)
{
    UInt64 hashedValue = 0;
    int i = 0;
    while (i < read.Length)
    {
        hashedValue += read.ElementAt(i) * (UInt64)Math.Pow(31, i);
        if (lowTolerance) i += 2;
        else i++;
    }
    return hashedValue;
}

    ここで、このハッシュ値を辞書のキーとして保存します。何が最良のアイデアになるでしょう。Uint64として使用するか、文字列に変換して文字列を辞書キーとして使用します。私の主な目標は、辞書が最小限のスペースを使用し、キーの検索時間が短縮されることです。

  2. 3571079文字のファイルがあります。ファイル全体を文字列に読み込むことはできますか、それとも高度なデータ構造が必要ですか？

4

1 に答える 1

3

ディクショナリのキーとして文字列 (またはその他の参照型) の代わりに UInt64 を使用すると、実質的にメモリの消費量が少なくなります。文字列のような参照型を使用するには、ディクショナリがキーへの参照を内部データ構造に格納する必要があります。これにより、オブジェクトごとのオーバーヘッドなどを含め、参照されるオブジェクト (文字列) もメモリに保持されます。 UInt64 の場合、(の現在の実装) ディクショナリは、個別のキー オブジェクトを使用せずに、キーへの参照の代わりにキーの値を格納します (ジェネリックが機能する通常の方法の一部として)。

UInt64 キーが文字列よりも高いメモリ使用量を引き起こす可能性があると考えることができる状況は 1 つだけです: プロセスが 32 ビット (x86) の場合、参照は 32 ビットです。ディクショナリが大きいがほとんど空の場合、多くの空のDictionary<K,V>.Entryインスタンスが存在します。UInt64 キーの場合、これらのインスタンスのキー部分は (明示的な値が割り当てられていなくても) 64 ビットになりますが、文字列キーの場合は 32 ビットのみです。したがって、割り当てられたメモリの合計量は、UInt64 キーを持つディクショナリの方が多くなります。しかし、これは非常に理論的な状況です。

したがって、ソフトウェア設計の他の品質を犠牲にすることなく文字列の代わりに UInt64 キーを使用できる場合、それらを使用しても問題はありません。ただし、本当に必要になる前に最適化を開始しないでください。Donald Knuth の言葉を借りれば、「時期尚早の最適化は諸悪の根源である」

更新: UInt64 値の計算方法を示すために投稿を更新したため:

  1. UInt64 値で ToString を呼び出して文字列キーを単純に導出する場合は、最初に UInt64 バージョンを使用する必要があります。どうしても効率が良くなります。

  2. ハッシュをキーとして使用するのはやや難しい場合があります。ハッシュが衝突しないようにする必要があります。あなたのハッシュ関数は一見するとあまりよく見えませんが、もちろんこれはユースケースによって異なります。しかし、これは私が推測するこの質問の範囲外です。

于 2012-03-03T10:55:56.210 に答える