r - 双向 key<->val 查找表的正确数据结构

Question

我在 R 中有一组键(字符)<-> 哈希(整数)关联。我想将这些关联存储在一个结构中，允许我通过键和哈希来引用键/哈希对。

所以像

"hello" <-> 1234

在变量 db .

并使用(ish；不必是这种确切的访问语法)访问它:

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

我尝试使用数据框，并将行名命名为键。但是我不能通过哈希整数引用一行。如果我使用哈希整数作为行名，那么我不能通过键名等引用。

我目前的解决方案是将两个数据库保留为两个数据框。一个将哈希作为行名，另一个将键作为行名。这可行，但保留两个相同的数据帧(除了它们的行名)似乎有点尴尬和重复。

我希望它在两个方向上都 super 快:)。我认为这意味着字符方向为 O(log(n))，整数方向为 O(1)，但我不是数据结构/算法专家。整数方向上的 O(log(n)) 可能没问题，但我认为任一方向上的 O(n) (需要遍历整个 db 解决方案)都会使事情变得过于沉重。

db 也是双射的。也就是说，每个键都映射到一个值，每个值都映射到一个键。

编辑:感谢到目前为止的帖子:

运行一些测试，匹配技术肯定比 keyed data.table 慢。正如 Martin 所指出的，这完全是由于匹配创建键控表所需的时间。也就是说，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 

编辑2:

我选择了 fmatch 解决方案和一个命名向量。我喜欢 match 方法的简单性，但我在 db 上重复查找，因此在每次调用 match 时重新创建哈希表的性能影响太大了。

fmatch 与 match 具有相同的接口(interface)，适用于相同的命名向量数据类型等。它只是缓存/内存创建的哈希表，因此对命名向量的后续调用只需执行哈希查找。所有这些都是从调用者抽象出来的，所以 fmatch 只是 match 的一个 dropin。

双向查找的简单包装代码:

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

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

Answer 1

一种基本方法是使用命名向量:

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"

(注意 match(x, y) 返回 x 中 y 的第一个匹配项的索引，因此这种方法仅在您的 map 是单射的情况下才有效，您在问题中没有明确说明。)

如果你觉得最后一个用法有点“重”，你绝对可以编写自己的函数。

备注 :正如所指出的，这种方法在 value-to-key 方向上可能会很慢，因此对于大型 map 的重复双向访问可能并不理想。对于它的防御，它很容易实现，不需要 base以外的任何包, 并且会为 99% 的人的需求做一个非常体面的工作。如果没有，它可以在这里用作更快替代方案的基准。