Как улучшить производительность этой счетной программы? - PullRequest
Новая
       24

Как улучшить производительность этой счетной программы?

7 голосов
/ 06 декабря 2011

Учитывая, что файл выглядит так: 

1440927 1
1727557 3
1440927 2
9917156 4

Первое поле - это идентификатор, in range(0, 200000000). Второе поле представляет тип, который является in range(1, 5). И тип 1, и тип 2 относятся к общей категории S1, а тип 3 и тип 4 относятся к S2. Один идентификатор может иметь несколько записей разного типа. Размер файла составляет около 200 МБ.

Проблема заключается в подсчете количества идентификаторов, имеющих запись типа 1 или 2, и количества идентификаторов, имеющих запись типа 3 или 4.

Мой код: 

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()

Хотя он дает ответ, я думаю, что он работает немного медленно. Что я должен сделать, чтобы он работал быстрее?

EDIT: В файле есть дублированные записи. И мне нужно только различать S1 (тип 1 и тип 2) и S2 (тип 3 и тип 4). Например, 1440927 1 и 1440927 2 учитываются только один раз, но не дважды, потому что они принадлежат S1. Поэтому я должен хранить идентификаторы.

Ответы [ 3 ]

3 голосов
/ 06 декабря 2011

Вы используете итератор для файла, это означает, что вы одновременно буферизуете только несколько строк.Каждый раз, когда буфер пуст, диск должен искать, а ваша программа должна ждать.

200 МБ легко умещается в вашей памяти, поэтому ускорение всех строк ускоряет процесс: 

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)
2 голосов
/ 06 декабря 2011

Если памяти достаточно, вы можете использовать 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 , чтобы узнать, где находится ваше узкое место.

2 голосов
/ 06 декабря 2011

Вы привязаны к 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

Эти две команды подсчитывают количество вхождений ("1" или "2") и ("3" или "4") в концекаждой строки в вашем filename.txt при игнорировании повторяющихся первых полей.

Возможно, быстрее, чем Python ...

...