Создайте миллионы предметов из большого файла Python быстро

Question

Я пытаюсь собрать несколько наборов int-пар из огромного файла. Каждый набор в типичном файле содержит около нескольких миллионов строк для анализа и построения одного набора. Я создал следующий код, но он занимает> 36 часов только для одного набора из 2 миллионов строк !!

Входной файл (несколько миллионов строк вроде этого): начинается с

*|NET 2 0.000295965PF
... //unwanted sections
R2_42 2:1 2:2 3.43756e-05 $a=2.909040 $lvl=99 $llx=15.449 $lly=9.679 $urx=17.309 $ury=11.243
R2_43 2:2 2:3 0.805627 $l=0.180 $w=1.564 $lvl=71 $llx=16.199 $lly=9.679 $urx=16.379 $ury=11.243 $dir=0
R2_44 2:2 2:4 4.16241 $l=0.930 $w=1.564 $lvl=71 $llx=16.379 $lly=9.679 $urx=17.309 $ury=11.243 $dir=0
R2_45 2:3 2:5 0.568889 $a=0.360000 $lvl=96 $llx=15.899 $lly=10.185 $urx=16.499 $ury=10.785
R2_46 2:3 2:6 3.35678 $l=0.750 $w=1.564 $lvl=71 $llx=15.449 $lly=9.679 $urx=16.199 $ury=11.243 $dir=0
R2_47 2:5 2:7 0.0381267 $l=0.301 $w=0.600 $lvl=8 $llx=16.199 $lly=10.200 $urx=16.500 $ury=10.800 $dir=0
R2_48 2:5 2:8 0.0378733 $l=0.299 $w=0.600 $lvl=8 $llx=15.900 $lly=10.200 $urx=16.199 $ury=10.800 $dir=0

*|NET OUT 0.000895965PF
...etc

Наконец, мне нужно построить набор целочисленных пар из приведенного выше, где целые числа являются индексами списка, составленного из столбца 2 и столбца 3 файла. [(2: 1,2: 2), (2: 2,2: 3), (2: 2,2: 4), (2: 3,2: 5), (2: 3,2: 6) , (2: 5,2: 7), (2: 5,2: 8)] становится [(0,1), (1,2), (1,3), (2,4), (2,5), (4,6), (4,7)]

Я закодировал это:

if __name__ == '__main__':
    with open('myspf') as infile, open('tmp','w') as outfile:
        copy = False
        allspf = []
        for line in infile:
            if line.startswith("*|NET 2"):
                copy = True
            elif line.strip() == "":
                copy = False
            elif copy:
                #capture col2 and col3
                if line.startswith("R"):
                    allspf.extend(re.findall(r'^R.*?\s(.*?)\s(.*?)\s', line))
        final = f6(list(itertools.chain(*allspf))) //to get unique list 
        #build the finalpairs again by index: I've found this was the bottleneck
        for x in allspf:
            left,right = x
            outfile.write("({},{}),".format(final.index(left),final.index(right)))
    pair = []
    f = open('tmp')
    pair = list(ast.literal_eval(f.read()))
    f.close()

    fopen = open('hopespringseternal.txt','w')
    fopen.write((json.dumps(construct_trees_by_TingYu(pair), indent=1)))
    fopen.close()

def f6(seq):
    # Not order preserving    
    myset = set(seq)
    return list(myset)

Узкое место находится в цикле 'for x in allspf', и самой процедуре construct_trees_by_TingYu также не хватило памяти после того, как я дал ей набор миллионов элементов. Процедура от этого парня требует всего набора сразу: http://xahlee.info/python/python_construct_tree_from_edge.html

Окончательный вывод - это дерево от родителя к потомку:

{
"3": {
 "1": {
  "0": {}
 }
},
"5": {
 "2": {
  "1": {
   "0": {}
  }
 }
},
"6": {
 "4": {
  "2": {
   "1": {
    "0": {}
   }
  }
 }
},
"7": {
 "4": {
  "2": {
   "1": {
    "0": {}
   }
  }
 }
}
}

Answer 1

Построение набора всегда O (n) . Вам нужно пройти весь список, чтобы добавить каждый элемент в ваш набор.

Однако, похоже, что вы даже не используете операцию set в приведенном выше фрагменте кода.

Если вам не хватает памяти, вы, вероятно, захотите перебрать огромный набор, а не ждать, пока будет создан весь набор, и затем передать его в construct_trees_by_TingYu (я, кстати, понятия не имею, что это такое). Кроме того, вы можете создать генератор , чтобы получить каждый элемент из набора , что уменьшит ваш объем памяти. Будет ли 'construct_trees_by_TingYu' обрабатывать переданный ему генератор, я не знаю.