双方向キーの適切なデータ構造<-> valルックアップテーブル

Question

Rのキー（文字）< - >ハッシュ（整数）の関連付けがあります。これらの関連付けを私はキーとハッシュのペアでキー/ハッシュペアを参照する。

ように可変dbで

"hello" <-> 1234 

のようなもの。

そして持つアクセス、それを（っぽい、この正確なアクセス構文である必要はありません）：

db["hello"] -> 1234 
db[1234] -> "hello" 

私は鍵をデータフレームを使用して、そしてrownamesを命名しようとしました。しかし、私はハッシュ整数で行を参照することはできません。 rownamesとしてハッシュ整数を使用すると、キー名などで参照することができません。

私の現在の解決策は、2つのデータフレームを2つのデータフレームとして保持することです。 1つはrownamesとしてハッシュを持ち、もう1つはrownamesのようなキーを持っています。これはうまくいきますが、2つの同一のデータフレーム（rownames以外）を保持するのは少し厄介で反復しているようです。

私は両方向で超高速になりたいと思っています:)。私は文字方向のO（log（n））、整数方向のO（1）を意味すると思いますが、私はデータ構造/アルゴリズムの専門家ではありません。 O（log（n））はおそらくOKですが、どちらの方向にもO（n）（dbソリューション全体をトラバースする必要があります）が物事を重すぎると考えています。

dbも全容です。つまり、各キーはちょうど1つの値にマップされ、各値はちょうど1つのキーにマッピングされます。

EDIT：これまでの記事をお寄せいただきありがとうございます：

いくつかのテストを実行し、一致技術は鍵付きdata.tableより確実に遅くなります。 Martinが指摘しているように、これは、鍵付きテーブルを作成するために必要な時間だけが原因です。つまり、一致し、キー付きのdata.tableはバイナリ検索を実行して値を検索します。しかし、1つの値を返すときは、私のニーズに合わせてマッチが遅すぎます。だから、私はdata.tableのソリューションをコーディングして投稿します。

> system.time(match(1,x)) 
    user system elapsed 
    0.742 0.054 0.792 
> system.time(match(1,x)) 
    user system elapsed 
    0.748 0.064 0.806 
> system.time(match(1e7,x)) 
    user system elapsed 
    0.747 0.067 0.808 
> system.time(x.table[1]) 
    user system elapsed 
     0  0  0 
> system.time(x.table[1e7]) 
    user system elapsed 
    0.001 0.001 0.000 
> system.time(x.table[1e7]) 
    user system elapsed 
    0.005 0.000 0.005 
> system.time(x.table[1]) 
    user system elapsed 
    0.001 0.000 0.000 
> system.time(x.table[1]) 
    user system elapsed 
    0.020 0.001 0.038 

EDIT2：

私はFMATCHソリューションと名付けベクターで行きました。私はマッチアプローチのシンプルさが気に入っていましたが、私はデータベースのルックアップを繰り返していますので、マッチするたびにハッシュテーブルを再作成するとパフォーマンスが低下しました。

fmatchは同じ名前のベクトルデータ型などで動作します。作成されたハッシュテーブルをキャッシュ/メモするだけで、名前付きベクトルの後続の呼び出しでハッシュ検索を実行するだけです。これらはすべて呼び出し元から抽象化されているので、fmatchは単に一致するためのドロップインです。

双方向のルックアップのための簡単なラッパーコード：

getChunkHashes = function(chunks, db) { 
     return(db[fmatch(chunks, names(db))]) 
} 

getChunks = function(chunkHashes, db) { 
     return(names(db[fmatch(chunkHashes, db)])) 
} 

Answer 1

は考える：

デシベルも全単射です。つまり、各キーはちょうど1つの値にマップされ、各値はちょうど1つのキーにマッピングされます。

それから私は、（例えばhash package）fastmatch package、またはdata.table::chmatchをハッシュ・ソリューションをお勧めしたいです。 data.tableのキー付き結合は、の複数列のキーおよび/またはグループ化されたデータを対象としています。実際には問題はありません。

Answer 2

ベースのアプローチは、名前のベクトルを使用することです：使用、値（複数可）にキー（S）から移動するには

db <- c(hello = 1234, hi = 123, hey = 321) 

を[：キー（複数可）に値（S）から行くために

db[c("hello", "hey")] 
# hello hey 
# 1234 321 

は少しトリッキーです：

names(db)[match(c(321, 123), db)] 
# [1] "hey" "hi" 

（match(x, y)がyでxの最初マッチのインデックスを返しますので、あなたのマップが単射である場合は、このアプローチが唯一うまく機能、あなたがあなたの質問に明確にしていなかった何かことに注意してください。）

最後の使用量が多すぎると「重い」場合は、間違いなく独自の関数を記述できます。

注：指摘したように、このアプローチはキーの方向の価値が低下する可能性があるため、大規模なマップの繰り返し双方向アクセスには理想的ではありません。防衛のために、それは実装が簡単で、base以外のパッケージを必要とせず、99％の人々のニーズに対して非常にまともな仕事をします。何もない場合は、より高速な代替案に対するベンチマークとしてここで使用できます。

Answer 3

@claytonstanleyさんが@flodelの反応について心配していることの詳細。 matchは、その引数のうちの1つのハッシュを作成し、次に他のものを検索します。コストは、ハッシュの作成ではなく、ルックアップ

> n = 1e7; x = seq_len(n) 
> system.time(match(1, x)) 
    user system elapsed 
    1.156 0.064 1.222 
> system.time(match(n, x)) 
    user system elapsed 
    1.152 0.068 1.221 

であり、それはルックアップの数で償却だ

> y = sample(x) 
> system.time(match(y, x)) 
    user system elapsed 
    2.112 0.052 2.167 

を行っので、あなたは間違いなく、ルックアップは、「ベクトル化になりたいです'