1

我有一个包含 2000 万人位置的数据集。在近乎实时的情况下，我想知道我收到的查询是否在这个集合中，如果是，实际位置。本质上，我想要一个大哈希表。由于数量（每秒数千个查询），为 Redis/Memcached 支付网络往返费用是不可能的。

是否有可以提供非常快速的成员资格测试和数据检索的数据结构？少量错误是可以接受的。

有些地点比其他地点更受欢迎。例如，“美国，纽约，纽约”比“美国，阿拉斯加，安克雷奇”出现的频率要高得多。

4

5 回答 5

1

“2000 万”——“我想要一个大哈希表”——听起来你已经有了答案。包含 2000 万个项目的哈希映射很容易放入单个机器上单个进程使用的内存中。

  • C++：std::unordered_map<Key, Value>
  • C＃：System.Collections.Generic.Dictionary<Key, Value>
  • 爪哇：java.util.HashMap<Key, Value>
  • 斯卡拉：HashMap[Key, Value]

如果您告诉我们您使用的是什么语言，我们可以为您指出该语言的确切类型。

此外-尽管我认为这可能有点矫枉过正-您可以使用辅助Bloom过滤器（rampion的想法-不是我的-只是为了完整性而将其包括在此处）以在给定人（密钥）不在的情况下可能加快成员资格测试哈希映射。

于 2013-05-22T02:03:39.497 回答
1

您可以使用Bloomier 过滤器：

布隆过滤器[...]是一种节省空间的概率数据结构，用于测试元素是否是集合的成员。假阳性检索结果是可能的，但假阴性是不可能的；即查询返回“在集合内（可能是错误的）”或“绝对不在集合内”。元素可以添加到集合中，但不能删除（尽管这可以通过计数过滤器解决）。添加到集合中的元素越多，误报的概率就越大。

[...]

Chazelle 等人。(2004) 设计了一个泛化的布隆过滤器，它可以将一个值与每个插入的元素相关联，实现一个关联数组。像布隆过滤器一样，这些结构通过接受小概率的误报来实现小空间开销。在“Bloomier 过滤器”的情况下，误报被定义为当键不在映射中时返回结果。地图永远不会为地图中的键返回错误的值。

于 2013-05-22T02:03:57.003 回答
0

一种选择是使用简单明了的地图：

// Scala
val locations: Map[String, Geo] = Map.empty
def location(id: String): Option[Geo] = locations.get(id)

但这会消耗大量内存。

于 2013-05-22T02:00:21.930 回答
0

使用排序数组并进行二进制搜索是另一种选择：

val ids: Array[Long] = new Array(30000000)
val values: Array[Int] = new Array(30000000)
var lookups = Map.empty[String, Int]

// populate ids with sorted array read from disk
Source.fromFile("sorted.csv").map(_.split("\t")).zipWithIndex.foreach {
    case (Array(id, value), index) =>
        ids[index] = id.toLong
        values[index] = lookups.get(value) match {
            case Some(valueIndex) => valueIndex
            case None =>
              val valueIndex = values.size + 1
              lookups = lookups.updated(value, valueIndex)
              valueIndex
        }
}

// Flip lookups around: value becomes key, key becomes value
val realLookup = lookups.foldLeft(Map.empty[Int, String]) {
    case (memo, (value, index)) => memo.updated(index, value)
}

// Usage:
Source.fromFile("ids.csv").foreach {
    idStr =>
        val id = idStr.toLong
        val index = java.util.Arrays.binarySearch(ids, id)
        if (index < 0) {
            // Unknown -- check javadoc
            println(idStr)
        } else {
            // Known
            println(id + "\t" + realLookup(values(index))
        }
}
于 2013-05-31T15:33:38.357 回答
0

朱迪阵列

是一种具有高性能、低内存使用并实现关联数组的数据结构。

Judy 数组显然压缩得很好，而且速度很快。

于 2013-05-22T15:39:29.353 回答