2

我必须在内存（RAM）中存储 500M 两位 unicode 字符。

我使用的数据结构应该有：

Worst Case Space Complexity: O(n)
Worst Case Time Complexity: O(1) <-- insertion, read, update, deletion

我正在考虑选择 dict ，它是 python 中哈希的实现，但问题是它仅在平均情况下确保所需操作的 O(1) 时间复杂度，而不是最坏情况。

我听说如果知道条目的数量，在最坏的情况下可以实现 O(1) 的时间复杂度。

怎么做？

万一这在 python 中是不可能的，我可以直接在我的 python 代码中访问内存地址和数据吗？如果是，那么如何？

4

3 回答 3

4

大多数情况下，性能损失（通常发生在碰撞中）会在所有调用中摊销。因此，对于最实际的使用，您不会O(n)每次通话都收到。事实上，唯一会导致O(n)每次调用都受到打击的情况是每个键的哈希与现有键的哈希值冲突的病态情况（即哈希表的最坏可能（或最不幸）的使用）。

例如，如果您事先知道您的一组键，并且您知道它们不会发生散列冲突（即它们的所有散列都是唯一的），那么您将不会遇到冲突情况。另一个主要O(n)操作是哈希表调整大小，但这种操作的频率取决于实现（扩展因子/哈希函数/冲突解决方案等），并且它也会根据输入集在运行之间变化。

在任何一种情况下，如果您可以使用所有键预先填充字典，您都可以避免突然的运行时减速。这些值可以设置为无，然后用它们的实际值填充。当最初用键“启动”字典时，这应该会导致唯一明显的性能损失，并且未来的值插入应该是恒定的时间。

一个完全不同的问题是您打算如何读取/查询结构？您是否需要附加单独的值并通过密钥访问它们？应该订购吗？也许 aset可能比 a 更合适dict，因为您实际上并不需要key:value映射。

更新：

根据您在评论中的描述，即使您正在使用临时集，这听起来更像是数据库要做的工作。您可以使用内存中的关系数据库（例如使用 SQLite）。此外，您可以使用像 SQLAlchemy 这样的 ORM 以更 Python 的方式与数据库交互，而无需编写 SQL。

甚至听起来您可能一开始就从数据库中读取数据，所以也许您可以进一步利用它？

存储/查询/更新大量唯一键入的记录正是 RDBMS 经过数十年的开发和研究专门从事的工作。使用预先存在的关系数据库（例如 SQLite 的）的内存版本可能是更实用和可持续的选择。

尝试使用 python 的内置模块并通过在构建时提供 db 文件路径来sqlite3尝试内存版本：":memory:"

con = sqlite3.connect(":memory:")
于 2013-03-03T23:14:24.847 回答
2

从技术上讲，字典的最坏情况是 O(n)，但它极不可能发生，而且在你的情况下也可能不会发生。我会尝试使用 Dictionary 并且仅在这不足以满足您的需求时才切换到不同的实现。

这是关于该主题的有用线程

于 2013-03-03T23:07:46.597 回答
2

您是否有理由关心最坏情况下的性能而不是平均性能？任何合理的哈希表都会给你 O(N) 的平均性能。

如果您真的想要 O(1) 的最坏情况性能，这里有两种可能的方法：

  1. 有一个max(charCode)-min(charCode)条目向量，并直接从 unicode 字符代码中查找您想要的值。如果您的键位于足够紧凑的范围内，您可以将其放入 RAM 中，这将很有效。

  2. 使用蛮力方法来选择散列函数或字典大小（使用字典的自定义实现，让你控制它），并不断尝试新的函数和/或大小，直到你得到一个没有冲突的函数和/或大小。预计这需要很长时间。 我不推荐这个。

编辑：

假设您知道您将看到的最小字符代码是 1234，而您将看到的最大字符代码是 98765。进一步假设您有足够的 RAM 来容纳 98765-1234 个元素。我还将假设您愿意使用该numpy库或其他一些有效的数组实现。在这种情况下，您可以像这样将值存储在向量中：

# configuration info
max_value = 98765 # replace with your number
min_value = 1234  # replace with your number
spread = (max_value - min_value)
dtype = object # replace with a primitive type if you want to store something simpler

# create the big vector
my_data = numpy.empty((spread,), dtype=dtype)

# insert elements
my_char_code              = ...
my_value_for_my_char_code = ...

assert min_value <= my_char_code < max_value
my_data[my_char_code - min_value] = my_value_for_my_char_code

# extract elements
my_char_code              = ...
assert min_value <= my_char_code < max_value
my_value_for_my_char_code = my_data[my_char_code - min_value]

这是 O(1)，因为查找是使用指针算法实现的，并且不依赖于存储在数组中的元素数量。

如果您实际要存储的元素数量远小于spread. 例如，如果spread是 40 亿（全部 UTF32），那么my_data仅此一项就将消耗至少 40 亿 * 8 字节/指针 = 32 GB 的 RAM（可能更多；我不知道 Python 引用有多大）。另一方面，如果min_value是 30 亿 和max_value = min_value + 100，那么内存使用量会很小。

于 2013-03-04T00:35:56.330 回答