Python中大数据结构的性能分析

Question

我正在寻找一些帮助来理解Python中大列表、dict或数组的性能特征。我有大约100万个键值对需要临时存储（明年可能会增加到1000万个）。它们的键是从0到大约1.1M（有一些间隙）的数据库id，值是浮动的。在

我在计算pagerank，所以我的过程是用值1初始化每个ID，然后在内存中查找并更新大约10次，然后将其保存回数据库。在

1. 我的理论是，如果我使用数据库ID作为数组/列表的索引，那么列表或数组将是最快的。这将创建一个gappy数据结构，但我不知道查找或更新的速度有多快。我还不知道使用arrays而不是列表是否有很大的好处。

2. 使用dict是非常自然的，使用键值对，但是我得到的印象是，第一次构建dict会非常慢，而且随着dict的增长可以容纳所有的条目，这会占用大量的内存。

3. 我还读到，使用:memory:标志的SQLite可能是一个很好的解决方案，但是我还没有深入研究过。

不管怎样，我只是在这里寻求一些指导。如果有任何想法，我将不胜感激。在

Answer 1

好吧，一般来说，如果你有太多的数据要保存在内存中，你需要使用某种外部存储器；如果你所有的数据都能放入内存，你就不需要做任何花哨的事情。在

您可能遇到的最大问题是，如果您的数据超过了操作系统在单个进程映像中所允许的数量；在这种情况下，您将再次需要外部存储。在

在这两种情况下，这都归结为：使用一个数据库，不管是sql还是no。如果是sql数据库，您可能希望使用ORM来简化这一过程。在

但是，在遇到这个问题之前，只需将所有内容存储在内存中，然后序列化到磁盘。我建议使用cPickle或ORM+sqlite。在

Answer 2

由于内置的hashing键，在字典中查找数据花费了O（1）时间。当然，对于大量的数据，会有collisions需要线性时间来解决，但是包含10万个项目的dict应该可以正常工作。不要在长列表中搜索数据，因为这需要线性（O（n））时间。在

但是，根据您计划如何处理数据，可以考虑使用numpy。dicts只用于存储和检索，它是完美的，但是使用numpy的vectorization instead of using loops可以大大加快对大量数据的计算。在

当您需要执行更复杂的查询（搜索多个键或定义要匹配的条件）时，就会出现SQL。对于一个简单的键值对，SQL似乎有点过头了。在

Answer 3

从字典开始吧。Even if you are running on WinXP1000万个密钥应该不是问题。但我希望你不是：）

一个字典将更容易编写代码，并且可能更快地构建和更新，尤其是当您以随机顺序更新值时。在

通常最好开始编写一个原型并使用它来识别性能问题。您的瓶颈很可能是从哪里请求数据。没有从字典中输入或检索。在