7

给定一个文件如下所示：

1440927 1
1727557 3
1440927 2
9917156 4

第一个字段是一个 ID，即in range(0, 200000000). 第二个字段表示一个类型，即in range(1, 5). 并且类型1和类型2属于一个共同的范畴S1，而类型3和类型4属于S2。一个 ID 可能有多个不同类型的记录。该文件大小约为 200MB。

问题是计算具有类型 1 或 2 记录的 ID 数量，以及具有类型 3 或 4 记录的 ID 数量。

我的代码：

def gen(path):
    line_count = 0
    for line in open(path):
        tmp = line.split()
        id = int(tmp[0])
        yield id, int(tmp[1])

max_id = 200000000
S1 = bitarray.bitarray(max_id)
S2 = bitarray.bitarray(max_id)
for id, type in gen(path):
    if type != 3 and type != 4:
        S1[id] = True
    else:
        S2[id] = True

print S1.count(), S2.count()

虽然它给出了答案，但我认为它运行得有点慢。我应该怎么做才能让它运行得更快？

编辑： 文件中有重复的记录。而我只需要区分S1（类型1和类型2）和S2（类型3和类型4）。例如，1440927 1and1440927 2只计算一次，而不是两次，因为它们属于 S1。所以我必须存储ID。

4

3 回答 3

3

您正在对文件使用迭代器，这意味着您一次只缓冲几行。每次缓冲区为空时，磁盘都需要查找，您的程序必须等待。

200MB 可以轻松放入您的内存中，因此获取所有行会加快速度：

def gen(path):
    # load all the lines, 
    lines = open(path).readlines() 
    split = (line.split() for line in lines)
    return ((int(x), int(y)) for x,y in split)
于 2011-12-06T09:56:12.680 回答
2

你被 Python 捆绑了吗？

egrep -e "[12]$" filename.txt | cut -d " " -f 1 | sort -u | wc -l

egrep -e "[34]$" filename.txt | cut -d " " -f 1 | sort -u | wc -l

这两个命令会计算 filename.txt 中每一行末尾出现 ("1" or "2") 和 ("3" or "4") 的次数，同时忽略重复的第一个字段。

可能比 Python 快……</p>

于 2011-12-06T09:51:30.040 回答
2

如果有足够的内存，您可以使用dict而不是bitarray.bitarray. 它可能会更快：

S1, S2 = {}, {} # dicts are slightly faster than `set()`
with open(path) as f:
     for i, line in enumerate(f, 1):
         id, sep, type = line.partition(" ")
         if type == "1" or type == "2":
            S1[id] = True
         elif type == "3" or type == "4":
            S2[id] = True
         else:
            print "WARNING: unknown type: %r in line %d: %r" % (type, i, line)
print len(S1), len(S2)

或者您可以尝试先对行进行排序：

def gettype(line):
    return line[-1]

S1, S2 = 0, 0
with open(path) as f:
     lines = f.read().splitlines()

lines.sort(key=gettype)
for type, group in itertools.groupby(lines, gettype):
    ids = (line.partition(" ")[0] for line in group)
    if type == "1" or type == "2":
       S1 += len(set(ids))
    elif type == "3" or type == "4":
       S2 += len(set(ids))
    else:
       assert 0, (type, list(ids))

print S1, S2

第二种方法的渐近复杂度更差。

您可以使用line_profiler找出瓶颈所在。

于 2011-12-06T10:07:43.243 回答