读入大文件并制作字典
我有一个大文件，我需要阅读并从中制作字典。 我希望这个尽可能快。 但是我在python中的代码太慢了。 这是一个显示问题的最小示例。
首先制作一些假数据
paste <(seq 20000000) largefile.txt 现在这里有一段最小的python代码来读取它并制作一本字典。
import sys from collections import defaultdict fin = open(sys.argv[1]) dict = defaultdict(list) for line in fin: parts = line.split() dict[parts[0]].append(parts[1])
时序：
time ./read.py largefile.txt real 0m55.746s
但是它不是I / O绑定的：
time cut -f1 largefile.txt > /dev/null real 0m1.702s
如果我注释掉dict行，则需要9秒。 似乎几乎所有的时间都花在了dict[parts[0]].append(parts[1]) 。
有什么方法可以加快速度吗？ 我不介意使用cython甚至C，如果这会产生很大的不同。 或者pandas可以在这帮忙吗？
以下是大小为10000000行的文件的配置文件输出。
python -m cProfile read.py test.data 20000009 function calls in 42.494 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 0.000 0.000 bisect.py:1() 1 0.000 0.000 0.001 0.001 collections.py:1() 1 0.000 0.000 0.000 0.000 collections.py:25(OrderedDict) 1 0.000 0.000 0.000 0.000 collections.py:386(Counter) 1 0.000 0.000 0.000 0.000 heapq.py:31() 1 0.000 0.000 0.000 0.000 keyword.py:11() 1 30.727 30.727 42.494 42.494 read.py:2() 10000000 4.855 0.000 4.855 0.000 {method 'append' of 'list' objects} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 10000000 6.912 0.000 6.912 0.000 {method 'split of 'str' objects} 1 0.000 0.000 0.000 0.000 {open}
更新。 我们可以假设parts [1]是一个整数，而parts [0]是一个短的固定长度字符串。
我的假数据不是很好，因为每个键只能获得一个值。 这是一个更好的版本。
perl -E 'say int rand 1e7, $", int rand 1e4 for 1 .. 1e7' > largefile.txt
我要做的唯一操作是查询一个键以返回与之关联的值列表。
如果您想要在评论中说出的内容，那么您可以在pandas中轻松完成：假设您有一个具有相同布局的文件，但条目会重复，因为在您的示例中，您将所有重复项添加到列表中：
1 1 2 2 1 3 3 4 1 5 5 6
然后您可以读取和操作数据：
In [1]: df = pd.read_table('largefile.txt', header=None, index_col=0) In [2]: df.loc[2] Out[2]: 1 2 Name: 2, dtype: int64 In [3]: df.loc[1] Out[3]: 1 0 1 1 1 3 1 5
Pandas将所有内容存储在DataFrames和Series对象中，这些对象都是索引的，因此不需要考虑输出，第一列是索引，第二列是重要的列，它将为您提供所需的数字。
您可以使用pandas做更多事情……例如，您可以按文件中的第一列进行分组并执行聚合：
In [64]: df = pd.read_table('largefile.txt', header=None).groupby(0) In [65]: df.sum() Out[65]: 1 0 1 9 2 2 3 4 5 6 In [66]: df.mean() Out[66]: 1 0 1 3 2 2 3 4 5 6 In [67]: df[0].count() Out[67]: 0 1 3 2 1 3 1 5 1 dtype: int64
我知道这不是如何加快字典速度的答案，但是根据你在评论中提到的内容，这可能是另一种解决方案。
编辑 – 添加时间
与最快的字典解决方案相比，将数据加载到pandas DataFrame中：
test_dict.py
import sys d = {} with open(sys.argv[1]) as fin: for line in fin: parts = line.split(None, 1) d[parts[0]] = d.get(parts[0], []) + [parts[1]]
test_pandas.py
import sys import pandas as pd df = pd.read_table(sys.argv[1], header=None, index_col=0)
在Linux机器上定时：
$ time python test_dict.py largefile.txt real 1m13.794s user 1m10.148s sys 0m3.075s $ time python test_pandas.py largefile.txt real 0m10.937s user 0m9.819s sys 0m0.504s
编辑：用于新的示例文件
In [1]: import pandas as pd In [2]: df = pd.read_table('largefile.txt', header=None, sep=' ', index_col=0).sort_index() In [3]: df.index Out[3]: Int64Index([0, 1, 1, ..., 9999998, 9999999, 9999999], dtype=int64) In [4]: df[1][0] Out[4]: 6301 In [5]: df[1][1].values Out[5]: array([8936, 5983])
以下是我设法获得的一些快速性能改进：
使用普通dict而不是defaultdict ，并改变d[parts[0]].append(parts[1])到d[parts[0]] = d.get(parts[0], []) + [parts[1]] ，将时间减少10％。 我不知道它是否正在消除对Python __missing__函数的所有调用，而不是在原地改变列表，或其他值得信任的东西。
在普通dict而不是defaultdict上使用setdefault也会将时间减少8％，这意味着它是额外的字典工作而不是就地附加。
同时，用split(None, 1)替换split() split(None, 1)有助于9％。
在PyPy 1.9.0而不是CPython 2.7.2中运行时间缩短了52％; PyPy 2.0b增加55％。
如果你不能使用PyPy，CPython 3.3.0的时间缩短了9％。
以32位模式而不是64位运行会将时间增加170％，这意味着如果您使用的是32位，则可能需要切换。
dict占用2GB以上（32位稍微少一点）的事实可能是问题的一个重要部分。 唯一真正的替代方案是将所有内容存储在磁盘上。 （在现实应用中，您可能希望管理内存缓存，但在这里，您只是生成数据并退出，这使事情变得更简单。）这是否有帮助取决于许多因素。 我怀疑在带有SSD而不是RAM的系统上它会加快速度，而在具有5400rpm硬盘和16GB RAM的系统上（就像我目前正在使用的笔记本电脑）它不会……但取决于你的系统的磁盘缓存等，谁知道，没有测试。
没有快速和脏的方法来存储基于磁盘的存储中的字符串列表（ shelve可能会浪费更多的时间来进行酸洗和取消节省），但是将其更改为仅连接字符串而使用gdbm将内存使用量保持在200MB以下并且大约在同一时间完成，并且具有良好的副作用，如果您想要多次使用数据，则必须持久存储它们。 遗憾的是，普通的旧dbm不起作用，因为默认页面大小对于这么多条目来说太小了，并且Python接口没有提供任何覆盖默认值的方法。
切换到一个简单的sqlite3数据库，该数据库只有非唯一的Key和Value列并在以下内容中执行:memory:花费大约80％的时间，而在磁盘上则需要85％的时间。 我怀疑将每个键存储多个值的exception化都无济于事，事实上会使事情变得更糟。 （尽管如此，对于许多现实生活中的使用，这可能是一个更好的解决方案。）
同时，在主循环中包装cProfile ：
40000002 function calls in 31.222 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 21.770 21.770 31.222 31.222 :2() 20000000 2.373 0.000 2.373 0.000 {method 'append' of 'list' objects} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 20000000 7.079 0.000 7.079 0.000 {method 'split' of 'str' objects}
所以，这是你在string.split花费的时间的三分之一，10％花在append ，剩下的花费了cProfile看不到的代码，这里包括迭代文件和defaultdict方法调用。
使用setdefault切换到常规dict （记住，速度稍快一点）显示在setdefault花费了3.774秒，因此大约15％的时间，或者大约20％的defaultdict版本。 预设__setitem__方法不会比setdefault或defaultdict.__getitem__更差。
但是，我们可能没有看到malloc调用的时间，它们可能是性能的一大块。 要测试它，您需要一个C级分析器。 让我们回过头来看看。
同时，至少有一些剩余时间也可能被线分裂所占用，因为它必须与空间分裂的成本相同，对吗？ 但我不知道有什么办法可以显着改善这一点。
最后，一个C级分析器将在这里提供帮助，但是我的系统上的一个运行对你的系统可能没什么帮助，所以我会把它留给你。
我系统上最快的版本取决于我运行的Python，但它是这样的：
d = {} for line in fin: parts = line.split(None, 1) d[parts[0]] = d.get(parts[0], []) + [parts[1]]
或这个：
d = {} for line in fin: parts = line.split(None, 1) d.setdefault(parts[0], []).append(parts[1])
……而且他们彼此非常接近。
gdbm解决方案的速度大致相同，并且具有明显的优缺点，如下所示：
d = gdbm.open(sys.argv[1] + '.db', 'c') for line in fin: parts = line.split(None, 1) d[parts[0]] = d.get(parts[0], '') + ',' + parts[1]
（显然，如果你想能够重复运行它，你需要添加一行来删除任何预先存在的数据库 – 或者，更好的是，如果它适合你的用例，检查它对输入文件的时间戳并跳过整个循环，如果它已经是最新的。）
这是一个有兴趣的人的快速C版本。 我的机器上的标题时间：
Python（> 5Gb内存）
time ./read.py largefile.txt real 0m48.711s user 0m46.911s sys 0m1.783s
C（~1.9Gb内存）
gcc -O3 read.c -o read time ./read largefile.txt real 0m6.250s user 0m5.676s sys 0m0.573s
因此在C.中快7.8倍:)
我应该补充一点，我的seq版本不会创建一个可用的列表而不将命令更改为：
paste <(seq -f "%.0f" 20000000) <(seq -f "%.0f" 2 20000001) > largefile.txt
下面的代码，必须归功于Vijay Mathew，他将C编程语言的6.6节中的dict示例复制到他的示例中（我复制到下面的答案中）： 在C中实现字典的快速方法
======编辑======（2013年8月13日）
根据我的回答评论＃2，我已经将代码更新为代码清单2中的代码，以允许单个密钥的多个值，并且还开始使用更新的perl代码生成测试文件（因此大小的一半）大约半个执行时间）。
标题时间是：
Python（> 5Gb内存）
time ./read.py largefile.txt real 0m25.925s user 0m25.228s sys 0m0.688s
C（~1.9Gb内存）
gcc -O3 read.c -o read time ./read largefile.txt real 0m3.497s (although sub 3 seconds is possible by reducing the hash size?!?!?) user 0m3.183s sys 0m0.315s
因此，虽然pandas可能接近，但C的速度提高了约7.4倍。
但是，关于尺寸的要点很重要。 我可以通过将散列大小减小到一个非常小的数字来“欺骗”，对于多值字典而言，这会以查找为代价增加插入速度。 因此，要真正测试这些实现中的任何一个，您还需要测试查找速度。
代码2（多值字典）
#include #include #include struct nlist { /* table entry: */ struct nlist *next; /* next entry in chain */ char *name; /* defined name */ char *defn; /* replacement text */ }; #define HASHSIZE 10000001 static struct nlist *hashtab[HASHSIZE]; /* pointer table */ /* hash: form hash value for string s */ unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31 * hashval; return hashval % HASHSIZE; } /* lookup: look for s in hashtab */ struct nlist *lookup(char *s) { struct nlist *np; for (np = hashtab[hash(s)]; np != NULL; np = np->next) if (strcmp(s, np->name) == 0) return np; /* found */ return NULL; /* not found */ } struct nlist * lookup_all(char *key) { struct nlist *np, *np2, *ret; unsigned hashval = hash(key); ret = NULL; for (np = hashtab[hashval]; np != NULL; np = np->next) { if (strcmp(key, np->name) == 0) { np2 = malloc(sizeof(*np2)); np2->name = np->name; np2->defn = np->defn; np2->next = ret; ret = np2; } } return ret; /* not found */ } /* install: put (name, defn) in hashtab */ struct nlist *install(char *name, char *defn) { struct nlist *np, *np2; unsigned hashval = hash(name);; //if ((np = lookup(name, hashval)) == NULL) { /* not found */ np = (struct nlist *) malloc(sizeof(*np)); if (np == NULL || (np->name = strdup(name)) == NULL) return NULL; np->next = hashtab[hashval]; hashtab[hashval] = np; if ((np->defn = strdup(defn)) == NULL) return NULL; return np; } #ifdef STRDUP char *strdup(char *s) /* make a duplicate of s */ { char *p; p = (char *) malloc(strlen(s)+1); /* +1 for .\0. */ if (p != NULL) strcpy(p, s); return p; } #endif /* STRDUP */ int main(int argc, char *argv[]) { FILE *fp; char str1[20]; char str2[20]; int size = 0; int progress = 0; struct nlist *result; fp = fopen(argv[1],"r"); if(fp==NULL) {return 1;} fseek(fp, 0, SEEK_END); size = ftell(fp); rewind(fp); while(size != ftell(fp)) { if(0==fscanf(fp, "%s %s",str1,str2)) break; (void)install(str1,str2); } printf("Done\n"); fclose(fp); // Test a lookup to see if we get multiple items back. result = lookup_all("1"); while (result) { printf("Key = %s Value = %s\n",result->name,result->defn); result = result->next; } return 0; }
代码1（单值字典）
#include #include #include struct nlist { /* table entry: */ struct nlist *next; /* next entry in chain */ char *name; /* defined name */ char *defn; /* replacement text */ }; #define HASHSIZE 10000001 static struct nlist *hashtab[HASHSIZE]; /* pointer table */ /* hash: form hash value for string s */ unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31 * hashval; return hashval % HASHSIZE; } /* lookup: look for s in hashtab */ struct nlist *lookup(char *s) { struct nlist *np; for (np = hashtab[hash(s)]; np != NULL; np = np->next) if (strcmp(s, np->name) == 0) return np; /* found */ return NULL; /* not found */ } /* install: put (name, defn) in hashtab */ struct nlist *install(char *name, char *defn) { struct nlist *np; unsigned hashval; if ((np = lookup(name)) == NULL) { /* not found */ np = (struct nlist *) malloc(sizeof(*np)); if (np == NULL || (np->name = strdup(name)) == NULL) return NULL; hashval = hash(name); np->next = hashtab[hashval]; hashtab[hashval] = np; } else /* already there */ free((void *) np->defn); /*free previous defn */ if ((np->defn = strdup(defn)) == NULL) return NULL; return np; } #ifdef STRDUP char *strdup(char *s) /* make a duplicate of s */ { char *p; p = (char *) malloc(strlen(s)+1); /* +1 for .\0. */ if (p != NULL) strcpy(p, s); return p; } #endif /* STRDUP */ int main(int argc, char *argv[]) { FILE *fp; char str1[20]; char str2[20]; int size = 0; int progress = 0; fp = fopen(argv[1],"r"); if(fp==NULL) {return 1;} fseek(fp, 0, SEEK_END); size = ftell(fp); rewind(fp); while(size != ftell(fp)) { if(0==fscanf(fp, "%s %s",str1,str2)) break; //printf(">%s<>%s<\n",str1,str2); (void)install(str1,str2); ++progress; if((progress % 100000)==0) printf("Progress = %d\n",progress); } printf("Done\n"); fclose(fp); return 0; }
您仍然可以在其他优化之上添加额外的优化：
由于您的键是“几乎”连续整数的字符串，因此您可以通过按顺序插入dict中的元素来加速dict的创建。 它将减少字典冲突。 请参阅有关python dict实现的注释
未来的主要细微之处：大多数哈希方案依赖于具有“良好”哈希函数，在模拟随机性的意义上。 Python没有：它最重要的哈希函数（对于字符串和整数）在常见情况下是非常规则的：
map（hash，（0,1,2,3））[0,1,2,3] map（hash，（“namea”，“nameb”，“namec”，“named”））[ – 1658398457， – 1658398460，-1658398459，-1658398462]
这不一定是坏事！ 相反，在大小为2 ** i的表中，将低位i位作为初始表索引是非常快的，并且对于由连续的整数范围索引的dicts，根本没有冲突。 当键是“连续”字符串时，大致相同。 因此，这在常见情况下提供了比随机更好的行为，这是非常理想的。
因此，如果您可以预处理文件以对其进行排序，那么python执行速度会快得多。