适用于双向密钥< - > val查找表的数据结构

Question

我在R中有一组键(字符)< - >哈希(整数)关联.我想将这些关联存储在一个结构中,允许我按键引用键/哈希对,也可以通过哈希引用.

所以像

"hello" <-> 1234

在变量db.

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

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

我尝试使用数据框,并将密钥命名为rownames.但后来我无法通过哈希整数引用一行.如果我使用哈希整数作为rownames,那么我不能通过keyname引用等.

我目前的解决方案是将两个dbs保持为两个数据帧.一个有哈希作为rownames,另一个有键作为rownames.这是有效的,但保持两个相同的数据帧(除了他们的rownames)似乎有点尴尬和重复.

我希望它在两个方向都超级快:).我认为这意味着字符方向为O(log(n)),整数方向为O(1),但我不是数据结构/算法专家.整数方向的O(log(n))可能没问题,但我认为O(n)(需要遍历整个数据库解决方案)在任何一个方向上都会对事情造成太大影响.

数据库也是双射的.也就是说,每个键都映射到一个值,每个值都映射到一个键.

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

运行一些测试,匹配技术肯定比键控data.table慢.正如Martin所指出的,这仅仅是因为匹配创建键控表所需的时间.也就是说,匹配和键控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解决方案和一个命名向量.我喜欢匹配方法的简单性,但是我在db上重复查找,因此在每次调用匹配时重新创建哈希表的性能太高了.

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

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

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

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

Answer 1

鉴于：

db 也是双射的。也就是说，每个键恰好映射到一个值，并且每个值恰好映射到一个键。

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