1

重複の可能性：
JavaScriptハッシュ（コード/テーブル）の優れた実装はありますか？

O（1）でキーをクエリし、要素をかなり迅速に削除し、O（1）からランダムサンプルを取得できるデータ構造が必要です。

辞書（キークエリ用）と配列（サンプリング用）を組み合わせて考えました。しかし、2つの間に（ポインタ）を接続する方法はありますか？

例：キーを指定してエントリを削除したい。辞書から簡単に削除できますが、辞書を使用して配列からスプライスするにはどうすればよいですか？

編集：

var dict = {key1: "val1",key2:"val2"};

キーでアイテムを取得する：

getKey = function(key){ return dict[key]; }

インデックスでアイテムを取得する（変更したい）

getIndex = function(ind) { return dict.values()[ind] }

getIndex関数の問題は、.values（）がすべてのディクショナリを調べて、それを配列に配置することです。辞書が大きい場合は非常に高価です。

更新： この質問を忘れて、その間に解決したので、解決策は次のとおりです。
辞書と配列を使用できます：配列は辞書のすべてのキーを保持します辞書はキーとしてキーを保持します値の代わりに、indexが配列内のこの要素のキーのインデックスであるタプル（並べ替えの配列へのポインター）。
したがって、このように、配列はディクショナリを指し、ディクショナリはアレイを指します。

これで、dsの操作は次のようになります。

Insert（key、value）：
配列に新しいキーをプッシュしてタプルを作成しますキー'key'を使用してタプルを辞書に挿入します

get（key）：
return dictionary.get（key）

remove（key）：
辞書からelemを削除し、配列の最後のキーとキー（キーへのポインターがあります）を切り替えます。辞書のポインターを最後のキーに更新し、キーを削除します。配列から

randomSample（sampler）：サンプラー
で配列をサンプリングします（たとえば、均一なサンプリングにすることができます）。すべてのサンプルを反復処理し、辞書からキーに対応する値を返します

クラスの完全なソースコードが利用可能です：https ：//gist.github.com/shacharz/9807577

4

2 に答える 2

0

ランダムサンプルで何を達成したいのかよくわかりません。しかし、私が理解したことから、あなたは基本的に値のリストを手に入れることができる地図を探していますか？

これを見つけました：https ：//stackoverflow.com/a/868728/715236

于 2012-09-15T22:26:04.680 に答える
0

正直なところ、このソリューションがパフォーマンスの基準を満たしているかどうかはわかりませんが、ここでは.アイデアの核心は、同じディクショナリを使用してこれらの両方を保存することです。削除によって生成されるインデックスの穴など、明らかな欠点がいくつかあります。ルックアップは非常に高速である必要があり、これにより、ランダム データの適切なソースを使用する場合に、非常に優れたランダム ルックアップが可能になります。

ケーキを持って食べるのも難しい。これに対する他のソリューションに間違いなく興味があります。

var dict = {key1: "val1", 0:"key1", key2:"val2", 1:"key2"};
var COUNT = 1;

// inserts
function insertValue(dictionary, key, value) {
    if (typeof dictionary[key] === 'undefined') {    
        COUNT++;
        dict[key] = value;
        dict[COUNT] = key;
    } else {
        return false;
    }
    return;
}

// return an item by index
var index = 20;
var itemByIndex = dict[dict[index]];

// updates by index
dict[dict[index]] = newValue;

// return a "random" element
function getRandomItem (dictionary, maxIndex) {
    var randomNumber = Math.floor(Math.rand() * maxIndex);
    var randomValue = dictionary[randomNumber];
    if (typeof randomValue === 'undefined') {
        return getRandomItem(dictionary, maxIndex);
    }
    return randomValue;
}

// deletes item by index
function deleteItemByIndex(dictionary, index) {
    delete dictionary[dictionary[index]];
    delete dictionary[index];
}
于 2012-09-16T02:00:27.843 に答える