3

x個のキーに制限された連想配列があり、別のキーを追加するために、最も最近アクセスされていないキーを削除したいと思います。mintlでHashAAを見つけましたが、これはD1で仕事をすることができますが、D2では何も見つかりませんでした。これをサポートするものはありますか、それともジョブを実行するために2番目のアレイを維持する必要がありますか？

4

2 に答える 2

3

私には本当の答えはありませんが、数分でそれを実装してみるのは楽しいだろうと思いました（おそらく非常に非効率的でバグがあるかもしれません）：

import std.stdio;
import std.traits;

struct MyHash(AA, size_t Limit)
    if (isAssociativeArray!AA)
{
    alias KeyType!AA Key;
    alias ValueType!AA Value;

    void opIndexAssign(Value value, Key key)
    {
        if (hash.length >= Limit)
        {
            Key leastUsed = leastUsedKey;
            hash.remove(leastUsed);
            counts.remove(leastUsed);
        }

        hash[key] = value;
    }

    Value opIndex(Key key)
    {
        counts[key]++;
        return hash[key];
    }

    Value[Key] hash;
    alias hash this;

private:

    @property Key leastUsedKey()
    {
        Key result;
        size_t maxCount = size_t.max;

        foreach (key; hash.byKey)
        {
            if (auto count = key in counts)
            {
                if (*count < maxCount)
                {
                    maxCount = *count;
                    result = key;
                }
            }
            else
            {
                return key;
            }
        }

        return result;
    }

    size_t[Key] counts;
}

// just to avoid declaring variables in main()
@property void consume(int key) { }

void main()
{
    MyHash!(int[int], 3) hash;

    hash[0] = 0;
    hash[1] = 0;
    hash[2] = 0;

    writeln(hash.keys);

    hash[2].consume;
    hash[5] = 0;

    writeln(hash.keys); // 2 stays, 5 added

    hash.clear();
    hash[0] = 0;
    hash[1] = 0;
    hash[2] = 0;

    hash[0].consume;
    hash[1].consume;
    hash[1].consume;
    hash[2].consume;
    hash[2].consume;
    hash[2].consume;

    hash[5] = 0;
    writeln(hash);  // (0 removed)
}
于 2012-09-30T21:32:21.053 に答える
2

組み込みのAAは、より多くの要素を収めるために必要なときに再ハッシュし、サイズは固定されておらず、要素にアクセスまたは追加した方法を追跡しません。また、言語にはAAが組み込まれているため、代替ハッシュテーブルがあります。実装は比較的まれになります（ほとんどの人は組み込みのAAを使用するだけです）。

したがって、これを自分で行う必要があると確信しています。おそらく、組み込みのAAタイプの周りにラッパーを作成し、ラッパーにすべてのアクセスを追跡させて、どのキーが最もアクセスされていないかを認識できるようにすることです。近々。

いくつかの代替コンテナ実装のdcollectionsをいつでもチェックできます（そしてIIRCにはハッシュテーブルが含まれていますが、それがあなたの望むことをするかどうかは疑わしいです）。個人的には、ハッシュテーブルが思い通りに動作することは聞いたことがないので、探しているものは少なくとも多少異常だと思います。ただし、AAのラッパーを作成して、希望どおりに機能させるのは簡単なはずです。

于 2012-09-30T22:22:34.367 に答える