эффективно строить разреженную матрицу biadjacency в Numpy

Question

Я пытаюсь загрузить файл этого CSV в разреженную матрицу Numpy, которая будет представлять biadjacency матрицу этого пользователь-subreddit двудольного графа: http://figshare.com/articles/reddit_user_posting_behavior/874101

Вот пример:

603,politics,trees,pics 
604,Metal,AskReddit,tattoos,redditguild,WTF,cocktails,pics,funny,gaming,Fitness,mcservers,TeraOnline,GetMotivated,itookapicture,Paleo,trackers,Minecraft,gainit 
605,politics,IAmA,AdviceAnimals,movies,smallbusiness,Republican,todayilearned,AskReddit,WTF,IWantOut,pics,funny,DIY,Frugal,relationships,atheism,Jeep,Music,grandrapids,reddit.com,videos,yoga,GetMotivated,bestof,ShitRedditSays,gifs,technology,aww 

Есть 876,961 линии (по одному на каждый пользователь) и 15,122 subreddits и в общей сложности 8,495,597 пользователя-subreddit ассоциаций.

Вот код, который я прямо сейчас, и который занимает 20 минут, чтобы работать на моем MacBook Pro:

import numpy as np 
from scipy.sparse import csr_matrix 

row_list = [] 
entry_count = 0 
all_reddits = set() 
with open("reddit_user_posting_behavior.csv", 'r') as f: 
    for x in f: 
     pieces = x.rstrip().split(",") 
     user = pieces[0] 
     reddits = pieces[1:] 
     entry_count += len(reddits) 
     for r in reddits: all_reddits.add(r) 
     row_list.append(np.array(reddits)) 

reddits_list = np.array(list(all_reddits)) 

# 5s to get this far 

rows = np.zeros((entry_count,)) 
cols = np.zeros((entry_count,)) 
data = np.ones((entry_count,)) 
i=0 
user_idx = 0 
for row in row_list: 
    for reddit_idx in np.nonzero(np.in1d(reddits_list,row))[0]: 
     cols[i] = user_idx 
     rows[i] = reddit_idx 
     i+=1 
    user_idx+=1 
adj = csr_matrix((data,(rows,cols)), shape=(len(reddits_list), len(row_list))) 

Кажется, трудно поверить, что это так быстро, как это может пойти ... Загрузка 82MB-файл в список списков занимает 5 секунд, но построение разреженной матрицы занимает в 200 раз больше. Что я могу сделать, чтобы ускорить это? Есть ли какой-то формат файла, который я могу преобразовать в этот CSV менее чем за 20 минут, которые будут импортироваться быстрее? Есть ли какая-то явно дорогая операция, которую я здесь делаю, это не хорошо? Я попытался создать плотную матрицу, и я попытался создать lil_matrix и dok_matrix и назначить 1 по одному, и это не быстрее.

Answer 1

не мог спать, попробовал одну вещь ... Я был в состоянии получить его до 10 секунд таким образом, в конце концов:

import numpy as np 
from scipy.sparse import csr_matrix 

user_ids = [] 
subreddit_ids = [] 
subreddits = {} 
i=0 
with open("reddit_user_posting_behavior.csv", 'r') as f: 
    for line in f: 
     for sr in line.rstrip().split(",")[1:]: 
      if sr not in subreddits: 
       subreddits[sr] = len(subreddits) 
      user_ids.append(i) 
      subreddit_ids.append(subreddits[sr]) 
     i+=1 

adj = csr_matrix( 
    (np.ones((len(userids),)), (np.array(subreddit_ids),np.array(user_ids))), 
    shape=(len(subreddits), i)) 

Answer 2

Для начала вы могли бы заменить во внутреннем for что-то вроде:

reddit_idx = np.nonzero(np.in1d(reddits_list,row))[0] 
sl = slice(i,i+len(reddit_idx)) 
cols[sl] = user_idx 
rows[sl] = reddit_idx 
i = sl.stop 

Использование nonzero(in1d()) для поиска совпадений выглядит хорошо, но я не исследовал альтернативы. Альтернативой назначению с помощью срезов является список extend, но это, вероятно, медленнее, особенно со многими строками.

Построить ряды, cols на сегодняшний день является самой медленной частью. Вызов csr_matrix является незначительным.

Поскольку существует намного больше рядов (пользователей), чем подзадач, возможно, стоит собрать для каждого субредакта список идентификаторов пользователей. Вы уже собираете субредады в наборе. Вместо этого вы можете собирать их в словаре по умолчанию и строить из этого матрицу. При тестировании на 3-мя линиях, реплицируемых 100000 раз, это заметно быстрее.

from collections import defaultdict 
red_dict = defaultdict(list) 
user_idx = 0 
with open("reddit_user_posting_behavior.csv", 'r') as f: 
    for x in f: 
     pieces = x.rstrip().split(",") 
     user = pieces[0] 
     reddits = pieces[1:] 
     for r in reddits: 
      red_dict[r] += [user_idx] 
     user_idx += 1 

print 'done 2nd' 
x = red_dict.values() 
adj1 = sparse.lil_matrix((len(x), user_idx), dtype=int) 
for i,j in enumerate(x): 
    adj1[i,j] = 1