Сравните две матрицы разных размеров, чтобы сделать одну большую матрицу - Улучшения скорости?

Question

У меня есть две матрицы, которые мне нужно использовать, чтобы создать большую матрицу. Каждая матрица представляет собой просто текстовый файл с разделителями табуляции, который читается. Каждая матрица имеет 48 столбцов с одинаковыми идентификаторами на матрицу с разным количеством строк. Первая матрица - 108887x48, вторая - 55482x48. Записи в каждой позиции для каждой матрицы могут быть 0 или 1, поэтому двоичные. Конечный результат должен содержать первые идентификаторы строк матрицы в виде строк, а вторая строка матрицы - как столбцы, поэтому итоговая матрица равна 55482x10887.

Что должно произойти здесь, так это то, что для каждого pos в каждой строке в первой матрице для каждой строки во второй матрице, если pos (col) для каждой матрицы равно 1, тогда счетчик окончательной матрицы будет расти 1. Наибольшим значением любой pos в финальной матрице может быть 48, и ожидается, что осталось 0.

Пример:

mat1 
    A B C D 
1id1 0 1 0 1 
1id2 1 1 0 0 
1id3 1 1 1 1 
1id4 0 0 1 0 

mat2 
    A B C D 
2id1 1 1 0 0 
2id2 0 1 1 0 
2id3 1 1 1 1 
2id4 1 0 1 0 

final 
    2id1 2id2 2id3 2id4 
1id1 1 1 2 0 
1id2 2 1 2 1 
1id3 2 2 4 2 
1id4 0 1 1 1 

У меня есть код, чтобы сделать это, однако это крайне медленно, что, где я в основном с просьбой о помощи. Я попытался максимально ускорить алгоритм. Он работает 24 часа и составляет всего около 25% пути. Я разрешил ему работать до и окончательный выходной файл составляет 20 ГБ. Я не имею опыта с базами данных и могу реализовать его здесь, если osomeone может помочь мне в том, как это сделать, с учетом фрагмента кода ниже.

#!/usr/bin/env python 

import sys 

mat1in = sys.argv[1] 
mat2in = sys.argv[2] 

print '\n######################################################################################' 
print 'Generating matrix by counts from smaller matrices.' 
print '########################################################################################\n' 

with open(mat1in, 'r') as f: 
     cols = [''] + next(f).strip().split('\t')    # First line of matrix is composed of 48 cols 
     mat1 = [line.strip().split('\t') for line in f]   # Each line in matrix = 'ID': 0 or 1 per col id 

with open(mat2in, 'r') as f: 
     next(f)             # Skip first row, col IDs are taken from mat1 
     mat2 = [line.strip().split('\t') for line in f]   # Each line in matrix = 'ID': 0 or 1 per col id 

out = open('final_matrix.txt', 'w')        # Output file 

#matrix = [] 
header = []              # Final matrix header 
header.append('')            # Add blank as first char in large matrix header 
for i in mat2: 
     header.append(i[0])          # Composed of all mat2 row ids 
#matrix.append(header) 

print >> out, '\t'.join(header)         # First print header to output file 

print '\nTotal mat1 rows: ' + str(len(mat1))     # Get total mat1 rows 
print 'Total mat2 rows: ' + str(len(mat2)), '\n'    # Get total mat2 rows 
print 'Progress: '            # Progress updated as each mat1 id is read 

length = len(header)           # Length of header, i.e. total number of mat2 ids 
totmat1 = len(mat1)            # Length of rows (-header), i.e. total number of mat1 ids 

total = 0              # Running total - for progress meter 
for h in mat1:             # Loop through all mat1 ids - each row in the HC matrix 
     row = []            # Empty list for new row for large matrix 
     row.append(h[0])          # Append mat1 id, as first item in each row 
     for i in xrange(length-1):        # For length of large matrix header (add 0 to each row) - header -1 for first '\t' 
       row.extend('0') 
     for n in xrange(1,49):         # Loop through each col id 
       for k in mat2:         # For every row in mat2 
         if int(h[n]) == 1 and int(k[n]) == 1: # If the pos (count for that particular col id) is 1 from mat1 and mat2 matrix; 
           pos = header.index(k[0])  # Get the position of the mat2 id 
           row[pos] = str(int(row[pos]) + 1)  # Add 1 to current position in row - [i][j] = [mat1_id][mat2_id] 
     print >> out, '\t'.join(row)       # When row is completed (All columns are compared from both mat1 and mat2 matrices; print final row to large matrix 
     total += 1            # Update running total 
     sys.stdout.write('\r\t' + str(total) + '/' + str(tvh)) # Print progress to screen 
     sys.stdout.flush() 

print '\n######################################################################################' 
print 'Matrix complete.' 
print '########################################################################################\n' 

Вот что профилирование первых 30 итераций для ид в MAT1:

###################################################################################### 
Generating matrix by counts from smaller matrices. 
######################################################################################## 


Total mat1 rows: 108887 
Total mat2 rows: 55482 

Progress: 
     30/108887^C   2140074 function calls in 101.234 seconds 

    Ordered by: standard name 

    ncalls tottime percall cumtime percall filename:lineno(function) 
     1 70.176 70.176 101.234 101.234 build_matrix.py:3(<module>) 
     4 0.000 0.000 0.000 0.000 {len} 
    55514 0.006 0.000 0.006 0.000 {method 'append' of 'list' objects} 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
    1719942 1.056 0.000 1.056 0.000 {method 'extend' of 'list' objects} 
     30 0.000 0.000 0.000 0.000 {method 'flush' of 'file' objects} 
    35776 29.332 0.001 29.332 0.001 {method 'index' of 'list' objects} 
     31 0.037 0.001 0.037 0.001 {method 'join' of 'str' objects} 
    164370 0.589 0.000 0.589 0.000 {method 'split' of 'str' objects} 
    164370 0.033 0.000 0.033 0.000 {method 'strip' of 'str' objects} 
     30 0.000 0.000 0.000 0.000 {method 'write' of 'file' objects} 
     2 0.000 0.000 0.000 0.000 {next} 
     3 0.004 0.001 0.004 0.001 {open} 

Я также приуроченный каждую итерацию, которая занимает около 2.5-3s на MAT1 идентификатору, и если я правильное заняло бы около 90 часов, чтобы завершить все это. Это о том, что нужно для полного запуска всего скрипта.

Я отредактировал некоторые из основных бит, чтобы удалить строки, добавив и xrange, чтобы сделать список за один шаг, умножив '0' на длину заголовков. Кроме того, я сделал словарь в MAT2 идентификаторах с индексом в качестве значений, думая Dict поиска будет быстрее, чем индекс ..

headdict = {} 
for k,v in enumerate(header): 
     headdict[v] = k 

total = 0              # Running total - for progress meter 
for h in mat1:             # Loop through all mat1 ids - each row in the HC matrix 
     timestart = time.clock() 
     row = [h[0]] + ['0']*(length-1)     # Empty list for new row for large matrix 
     #row.append(h[0])          # Append mat1 id, as first item in each row 
     #for i in xrange(length-1):        # For length of large matrix header (add 0 to each row) - header -1 for first '\t' 
     #  row.append('0') 
     for n in xrange(1,49):         # Loop through each col id 
       for k in mat2:         # For every row in mat2 
         if int(h[n]) == 1 and int(k[n]) == 1: # If the pos (count for that particular col id) is 1 from mat1 and mat2 matrix; 
           pos = headdict[k[0]] #header.index(k[0])  # Get the position of the mat2 id 
           row[pos] = str(int(row[pos]) + 1)  # Add 1 to current position in row - [i][j] = [mat1_id][mat2_id] 
     print >> out, '\t'.join(row)       # When row is completed (All columns are compared from both mat1 and mat2 matrices; print final row to large matrix 
     total += 1            # Update running total 
     sys.stdout.write('\r\t' + str(total) + '/' + str(totmat1)) # Print progress to screen 
     #sys.stdout.flush() 
     timeend = time.clock() 
     print timestart - timeend 

Answer 1

Это всего лишь матричное умножение. Вы хотите умножить первую матрицу на транспонирование второй. Для эффективных операций с матрицами получите NumPy.

Если вы читаете ваши два входных матриц в NumPy массивы DTYPE numpy.int8, то вычисление просто

m1.dot(m2.T) 

Это займет пару минут, топы.

Answer 2

Я не совсем понимаю, что делает этот код (единственная буква имен переменных Безразлично 't помочь).

Мое предложение: попробуйте уменьшить количество операций, выполняемых в самых внутренних циклах. Например, вам нужно пересчитать pos на внутреннем уровне?

pos = header.index(k[0]) 

Если это возможно, чтобы изменить порядок вложенных циклов k, h и n, вы можете быть в состоянии сократить дорогостоящие list.index, который является O (п) операции.