0

我有一些来自各种来源的意见。输入是键值对形式。键的类型为“abc”形式。来自不同来源的键可以相同，在这种情况下，我必须执行一组所有值。

我需要对数据结构做的事情：

  • 我应该能够检索特定源 ID 的所有键和值
  • 给定一个键，我应该能够找出与之关联的所有值，而不管源 ID 是什么。

我想要一个或多个节省空间的数据结构，我可以使用它来实现这一点。我最初想保留 2 个映射：一个用于源 id 与键，另一个用于键与值。但是在这里，我将源 ID 丢失为值映射。

速度/空间要求：获取每个键值列表的速度很重要；维护这些数据结构所需的内存也是如此。构建此数据结构和源 ID 到键/值检索速度所花费的时间并不重要。

有什么建议么？

4

1 回答 1

0

您可以稍微修改您的想法：保留一个字典将源与（键，值）对相关联，另一个将键与值集相关联。这应该可以快速构建/更新（添加一个条目需要两个字典查找和一个列表/集合插入），并且不需要太多的内存开销。然后，您想要的两个查找操作中的每一个只需要一个字典命中。

请注意，这只会使指向实际数据的指针数量增加一倍；如果值很大，那么内存使用量将远少于两倍。但是，如果这是一个问题，并且您不介意使源 id 到键值查找的速度慢得多，那么您可以只存储从键到（源，值）对的字典。然后您可以通过以下方式获取给定键的所有值

vals_for_key = [val for source, val in the_dict[key]]

以及来自给定来源的键值对

keyvals_for_source = [(key, val)
                      for key, items in the_dict.iteritems()
                      for src, val in items
                      if src == source]
于 2013-04-04T00:47:39.417 回答