7

Rにキー（文字）<->ハッシュ（整数）の関連付けのセットがあります。これらの関連付けを単一の構造に格納して、キーとハッシュのペアをキーごと、およびハッシュごとに参照できるようにします。

だから何かのような

"hello" <-> 1234

変数でdb。

そして、それにアクセスします（ish;この正確なアクセス構文である必要はありません）：

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

データフレームを使用して、行名にキーの名前を付けてみました。しかし、ハッシュ整数で行を参照することはできません。行名としてハッシュ整数を使用すると、キー名などで参照できなくなります。

私の現在の解決策は、2つのデータベースを2つのデータフレームとして保持することです。1つは行名としてハッシュを持ち、もう1つは行名としてキーを持ちます。これは機能しますが、2つの同一のデータフレーム（行名を除く）を保持するのは少し厄介で繰り返しのようです。

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

dbも全単射です。つまり、各キーは正確に1つの値にマップされ、各値は正確に1つのキーにマップされます。

編集：これまでの投稿に感謝します：

いくつかのテストを実行すると、一致手法はキー付きのdata.tableよりも明らかに遅くなります。マーティンが指摘したように、これはキー付きテーブルを作成するための一致に必要な時間のみによるものです。つまり、matchとkeyed data.tableの両方が、値を見つけるためにバイナリ検索を実行します。しかし、それにもかかわらず、単一の値を返す場合、一致は私のニーズには遅すぎます。そこで、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は、matchと同じインターフェイスを持ち、同じ名前付きベクトルデータ型などで機能します。作成されたハッシュテーブルをキャッシュ/記憶するだけなので、名前付きベクトルに対する後続の呼び出しでハッシュルックアップを実行するだけで済みます。これらはすべて呼び出し元から抽象化されているため、fmatchは単に一致のドロップインです。

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

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

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

3 に答える 3

4

基本的なアプローチは、名前付きベクトルを使用することです。

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

キーから値に移動するには、次を使用します[。

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

値からキーに移動するのは少し注意が必要です。

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

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

最後の使用法が少し「重すぎる」と感じた場合は、間違いなく独自の関数を作成できます。

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

于 2012-10-08T00:19:33.457 に答える
3

与えられた：

dbも全単射です。つまり、各キーは正確に1つの値にマップされ、各値は正確に1つのキーにマップされます。

次に、ハッシュソリューション（ハッシュパッケージなど）、fastmatchパッケージ、またはを提案しますdata.table::chmatch。キー付き結合はdata.table、順序付けられた複数列のキーやグループ化されたデータを対象としていますが、実際には問題にはなりません。

于 2012-10-08T08:35:15.913 に答える
2

@flodelの応答に関する@claytonstanleyの懸念についての詳細。match引数の1つをハッシュしてから、もう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

したがって、ルックアップを「ベクトル化」する必要があります。

于 2012-10-08T03:17:07.207 に答える