Как ускорить создание большого словаря

Question

У меня есть большой файл (около 1 ГБ), который я читал так, чтобы создать словарь отсортированных списков. Мне нужны списки для сортировки, чтобы я мог их искать позже. Это будут запросы предшественника (в которых индекс имеет наибольшее значение, меньшее x), поэтому я не могу использовать наборы.

A = defaultdict(list) 
B = defaultdict(list) 
filename = sys.argv[1] 

with open(filename) as fin: 
    lines = list(fin) 

for line in lines: 
    vals=line.split() 
    vals[2] = int(vals[2]) 
    bisect.insort_left(A[vals[1]],vals[2]] 
    bisect.insort_left(B[vals[0]],vals[2]] 

К сожалению, это слишком медленно.

Профилирование Я вижу, что почти все время тратится на звонок bisect.insort_left.

Есть ли способ ускорить это?

Стоит ли добавлять несортированные элементы, а затем сортировать их потом? Если да, то как вы можете отсортировать все списки в словаре списков?

Answer 1

Я хотел бы попробовать 1) не читает весь файл в одновременно, и 2) сортировка после завершения чтения. Например:

A = defaultdict(list) 
B = defaultdict(list) 
filename = sys.argv[1] 

with open(filename) as fin: 
    for line in fin: 
     vals = line.split() 
     vals[2] = int(vals[2]) 
     A[vals[1]].append(vals[2]) 
     B[vals[0]].append(vals[2]) 

for v in A.itervalues(): 
    v.sort(); 
for v in B.itervalues(): 
    v.sort() 

Answer 2

Try итерация без составления списка первого

with open(filename) as f: 
    for line in f: 
    vals=line.split() 
    vals[2] = int(vals[2]) 
    bisect.insort_left(A[vals[1]],vals[2]] 
    bisect.insort_left(B[vals[0]],vals[2]] 

другой идея заключается в том, чтобы разобраться после того, как все вставки сделаны