Какъв е правилният формат на разредена матрица на SciPy за инкрементално сумиране

В моя код в момента повтарям и създавам три списъка:

data, row, col

Има голямо повторение на (row, col) двойки и в моята крайна разредена матрица M бих искал стойността на M[row, col] да бъде сумата от всички съответни елементи в data. От прочита на документацията coo_matrix форматът изглежда идеален и за малки примери работи добре.

Проблемът, който имам, е, че когато увелича размера на проблема си, изглежда, че междинните списъци data, row, col използват цялата ми (8 gb) памет и пространството за суап и моят скрипт автоматично се унищожава.

Та въпросът ми е:

Има ли подходящ формат или ефективен начин за постепенно изграждане на моята сумирана матрица, така че да не се налага да съхранявам пълните междинни списъци/numpy масиви?

Моята програма преминава през решетка, създавайки local_data, local_row, local_col списъци във всяка точка, чиито елементи след това се добавят към data, row, col, така че възможността за актуализиране на разредената матрица със списъци според конструкторите на разредени матрици би била идеалният случай.


python numpy scipy sparse-matrix scientific-computing
person YXD    schedule 23.09.2013    source източник

Отговори (1)


arrow_upward
3
arrow_downward

Има две неща, които може да ви убиват: дубликатите или режийните разходи на списък над масив. И в двата случая вероятно правилното нещо, което трябва да направите, е да увеличите списъка си толкова много, преди да го изхвърлите в coo_matrix и да го добавите към общия си брой. Взех няколко тайминга:

rows = list(np.random.randint(100, size=(10000,)))
cols = list(np.random.randint(100, size=(10000,)))
values = list(np.random.rand(10000))

%timeit sps.coo_matrix((values, (rows, cols)))
100 loops, best of 3: 4.03 ms per loop

%timeit (sps.coo_matrix((values[:5000], (rows[:5000], cols[:5000]))) +
         sps.coo_matrix((values[5000:], (rows[5000:], cols[5000:]))))
100 loops, best of 3: 5.24 ms per loop

%timeit sps.coo_matrix((values[:5000], (rows[:5000], cols[:5000])))
100 loops, best of 3: 2.16 ms per loop

Така че има около 25% излишък при разделянето на списъците на две, преобразуването на всеки в coo_matrix и след това добавянето им заедно. И изглежда, че не е толкова лошо, ако правите повече разделяния:

%timeit (sps.coo_matrix((values[:2500], (rows[:2500], cols[:2500]))) +   
         sps.coo_matrix((values[2500:5000], (rows[2500:5000], cols[2500:5000]))) +  
         sps.coo_matrix((values[5000:7500], (rows[5000:7500], cols[5000:7500]))) + 
         sps.coo_matrix((values[7500:], (rows[7500:], cols[7500:]))))
100 loops, best of 3: 5.76 ms per loop
person Jaime    schedule 23.09.2013
comment
Jaime - благодаря още веднъж. Сега използвам подхода за нарастване на списъка само толкова голям и (поне тази част) кодът ми работи за разумно време, без да се срива. - person YXD; 23.09.2013