4

の内容がわからないハッシュテーブルがあります。

ここで、そこから 1 つのキーと値を取得したいと考えています。

ハッシュテーブルのコンテンツが4,500,000 KeyValuePairを超えているため、速度のためにハッシュテーブルを使用するため、GetEnumeratorを使用してプログラム速度を低下させることはできません

4

6 に答える 6

6

を使用しますList<TKey>：

Dictionary<string, string> dict = ... your hashtable which could be huge

List<string> keys = new List<string>(dict.Keys);
int size = dict.Count;
Random rand = new Random();
string randomKey = keys[rand.Next(size)];

要素がハッシュテーブルのキーと同じメモリ内の場所を指している を作成し、List<TKey>このリストからランダムな要素を選択します。

ハッシュテーブルからランダムな要素の値を取得したい場合は、ランダムなキーがあれば非常に簡単です。

string randomeElement = dict[randomKey];
于 2012-08-14T21:28:03.277 に答える
4

GetEnumerator を使用してプログラム速度を下げることはできません」

それは問題です。すべてのエントリを反復し、キーを新しいリストにコピーする回答を受け入れたので、その要件を放棄したかどうかは明確ではありません。

確実にメモリ効率が向上し、潜在的に速度も向上するアプローチは、ディクショナリ全体を反復処理することですが、任意の時点でランダムな要素を保持し、カウントを安価に取得できるコレクションを最適化します。.NET のジェネリック シーケンスに対してそれを行う拡張メソッドを次に示します。

public static T RandomElement<T>(this IEnumerable<T> source,
                                 Random rng)
{
    // Optimize for the "known count" case.
    ICollection<T> collection = source as ICollection<T>;
    if (collection != null)
    {
        // ElementAt will optimize further for the IList<T> case
        return source.ElementAt(rng.Next(collection.Count));
    }

    T current = default(T);
    int count = 0;
    foreach (T element in source)
    {
        count++;
        if (rng.Next(count) == 0)
        {
            current = element;
        }            
    }
    if (count == 0)
    {
        throw new InvalidOperationException("Sequence was empty");
    }
    return current;
}

したがって、 a のDictionary<TKey, TValue>場合はKeyValuePair<TKey, TValue>そのようになります-または、最初に射影することができますKeys:

var key = dictionary.Keys.RandomElement(rng);

（その辺の落とし穴については、私の記事を参照してください。）Random

単なる任意のキーではなく、純粋に疑似乱数のキーが必要な場合は、O(n) よりもうまくできるとは思いません(シーケンスの最初のキーを取得することで取得できます)。別の場所で述べられています）。

もちろん、Darinの回答のようにキーをリストにコピーすると、複数のランダムな要素をより効率的に取得できることに注意してください。それはすべてあなたの要件に依存します。

于 2012-08-23T07:28:32.940 に答える
2

with Linq you can do:

Dictionary<string, string> dicto = new Dictionary<string, string>();

Random rand = new Random();

int size = dicto.Count;

int randNum = rand.Next(0, size);

KeyValuePair<string, string> randomPair = dicto.ElementAt( randNum );

string randomVal = randomPair.Value;

For instance, 

string tmp = dicto.ElementAt( 30 ).Value;

Would copy the value of the thirtieth item in the Dicto to the string tmp.

Internally, I think it walks through the keypairs one at a time, till it gets to the thirtieth, instead of copying them all, so you don't need to load all the elements into memory.

I'm not sure what you meant by not knowing what the content is.

You don't know the types in the KeyValuePair of the dicto? Or just don't know what values will be in the dicto?

于 2012-08-15T00:12:01.623 に答える
2

ランダムキーはどのくらいランダムでなければなりませんか?

ハッシュ テーブルでは、アイテムを格納する順序が定義されていないため、最初のアイテムだけを取得できます。ランダムではありませんが、挿入順でもソート順でもありません。それは十分にランダムでしょうか？

Dictionary<string, string> dict = GetYourHugeHashTable();

KeyValuePair<string, string> randomItem = dict.First();
DoAComputation(randomItem.Key, randomItem.Value);
dict.Remove(randomItem.Key);
于 2012-08-14T21:50:31.250 に答える
1

Hashtable.Keysは、キーの内部リストへのポインターを提供します。それはスピーディーです。また、ハッシュテーブルからアイテムを削除するのはO（1）操作であるため、アイテムが大量にある場合でも、これも迅速になります。

このようなループを実行できます（質問でランダムを使用する理由はありません）。

var k = Hashtable.Keys(); // Will reflect actual contents, even if changes occur

while (k.Count > 0 )
{
 var i = Keys.First();
 {
       Process(i);
       Hashtable.Remove(i)  
 }
}
于 2012-08-15T13:20:48.300 に答える
0

対象とする .NET BCL のバージョンがわかっている場合 (つまり、修正されている場合) は、いつでも の内部をDictionary<TKey, TValue>調べて、キーをプライベートに格納する方法を見つけ出し、それを使用してランダムなキーを取り出すことができます。

たとえば、仕事用のラップトップに現在インストールされている Mono のバージョンを使用すると、Dictionary<TKey, TValue>タイプにプライベート フィールドという名前が付けられていることがわかりkeySlotsます (Windows を使用している場合は、これが異なると思います)。この知識を使用して、次のような関数を実装できます。

static readonly Dictionary<Type, FieldInfo> KeySlotsFields = new Dictionary<Type, FieldInfo>();

public static KeyValuePair<TKey, TValue> GetRandomKeyValuePair<TKey, TValue>(this Random random, Dictionary<TKey, TValue> dictionary, Random random = null)
{
    // Here's where you'd get the FieldInfo that you've identified
    // for your target version of the BCL.
    FieldInfo keySlotsField = GetKeySlotsField<TKey, TValue>();

    var keySlots = (TKey[])keySlotsField.GetValue(dictionary);

    var key = (TKey)keySlots[random.Next(keySlots.Length)];

    // The keySlots field references an array with some empty slots,
    // so we need to loop until we come across an existing key.
    while (key == null)
    {
        key = (TKey)keySlots[random.Next(keySlots.Length)];
    }

    return new KeyValuePair<TKey, TValue>(key, dictionary[key]);
}

// This happens to work for me on Mono; you'd almost certainly need to
// rewrite it for different platforms.
public FieldInfo GetKeySlotsField<TKey, TValue>()
{
    Type keyType = typeof(TKey);

    FieldInfo keySlotsField;
    if (!KeySlotsFields.TryGetValue(keyType, out keySlotsField))
    {
        KeySlotsFields[keyType] = keySlotsField = typeof(Dictionary<TKey, TValue>).GetField("keySlots", BindingFlags.Instance | BindingFlags.NonPublic);
    }

    return keySlotsField;
}

これはあなたのケースでは適切な解決策かもしれませんし、恐ろしい考えかもしれません。その呼び出しを行うのに十分なコンテキストを持っているのはあなただけです。

上記のメソッドの例について: 個人的には、Randomランダム性を含む機能のクラスに拡張メソッドを追加するのが好きです。それは私の選択です。明らかに、別のルートに進むことができます。

于 2012-08-15T01:06:34.737 に答える