7

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

所以像

"hello" <-> 1234

在变量中db。

并使用（ish；不必是这种确切的访问语法）访问它：

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

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

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

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

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 具有相同的接口，适用于相同的命名向量数据类型等。它只是缓存/记忆创建的哈希表，因此对命名向量的后续调用只需执行哈希查找。所有这些都是从调用者中抽象出来的，所以 fmatch 只是 match 的一个 dropin。

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

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"

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

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

注意：正如所指出的，这种方法在 value-to-key 方向上可能很慢，因此它可能不适合重复双向访问大地图。对于它的防御来说，它很容易实现，不需要除base. 如果没有，它可以在这里用作更快替代方案的基准。

于 2012-10-08T00:19:33.457 回答
3

给定：

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

然后我会建议散列解决方案（例如散列包）、快速匹配包或data.table::chmatch. 键控联接data.table更适用于有序的多列键和/或分组数据，这并不是您真正遇到的问题。

于 2012-10-08T08:35:15.913 回答
2

更多关于@claytonstanley 对@flodel 回应的关注的详细说明。match对其中一个参数进行哈希处理，然后搜索另一个。成本在于创建哈希而不是查找

> 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 回答