Ускорить создание графика из 2.92M точек данных

Question

У меня есть 2.92M точки данных в CSV-файле 3.0GB, и мне нужно пропустить его дважды, чтобы создать график, который я хочу загрузить в NetworkX. По текущему курсу мне понадобится несколько дней, чтобы создать этот график. Как я могу ускорить это?

similarity = 8 

graph = {} 
topic_pages = {} 

CSV.foreach("topic_page_node_and_edge.csv") do |row| 
       topic_pages[row[0]] = row[1..-1] 
end 

CSV.open("generate_graph.csv", "wb") do |csv| 
     i = 0 
     topic_pages.each do |row| 
       i+=1 
       row = row.flatten 
       topic_pages_attributes = row[1..-1] 
       graph[row[0]] = [] 
       topic_pages.to_a[i..-1].each do |row2| 
         row2 = row2.flatten 
         topic_pages_attributes2 = row2[1..-1] 
         num_matching_attributes = (topic_pages_attributes2 & topic_pages_attributes).count 
         if num_matching_attributes >= similarity or num_matching_attributes == topic_pages_attributes2.count or num_matching_attributes == topic_pages_attributes.count 
           graph[row[0]].push(row2[0]) 
         end 
       end 
       csv << [row[0], graph[row[0]]].flatten 
     end 
end 

Answer 1

Больше всего времени затрачено на загрузку данных с диска i belive. Параллелизируйте данные чтения в несколько потоков/процессов, а затем создайте граф.

Также вы могли бы создать графики подмножества на разных машинах и объединить их позже.

Answer 2

1. тест. Например, используя cProfile, который поставляется с Python. В вашем коде легко получить некоторые неэффективные показатели эффективности, и они могут легко получить 10-процентную производительность в интенсивных приложениях.

   Довольно код, такой как

   (topic_pages_attributes2 & topic_pages_attributes).count 
   

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

2. Используйте более эффективный язык. Например, в benchmarksgame.alioth, по ряду интенсивных проблем, самый быстрый Программа Python 3 находится в медиане 63 раза медленнее, чем самая быстрая программа на C (Ruby - 67x, JRuby - 33x). Да, разрыв в производительности может быть большим, даже с хорошо оптимизированным кодом Python. Но если вы не оптимизировали свой код, он может быть еще больше; и вы сможете получить ускорение 100x-1000x, используя более эффективный язык и тщательно оптимизируя свой код.

3. Рассмотрите более умные формулировки своей проблемы. Например, вместо повторения по каждому узлу итерации на каждом краю один раз. В вашем случае это, вероятно, означает создание инвертированного индекса, темы -> страниц. Это очень похоже на то, как работают текстовые поисковые системы, и популярный способ вычислить такие операции над кластерами: отдельные темы можно разделить на отдельные узлы. В ваших данных этот подход выгоден от разрешений. Это может резко сократить время выполнения вашего алгоритма.

   У вас есть около 3 документов Mio. Судя по вашему общему размеру данных, они, вероятно, имеют менее 100 тем в среднем? Для вашего подхода с совместным сравнением требуется 3mio^2 сравнения, вот что вам мешает. Если более популярные темы используются только по 30 000 документов, вы можете уйти с вычислением всего 30 тыс.^2 * тем. Предполагая, что у вас есть 100 таких очень популярных тем (редкие темы не имеют большого значения), это будет 100-кратное ускорение.

4. Упростите вашу проблему. Например, first объединить все документы, которые имеют ровно тем же темам, сортируя. Чтобы сделать это более эффективным, также устраните все темы, которые происходят ровно один раз. Но, вероятно, есть только около 10.000-100.000 различных комплектов документов. Этот шаг можно легко решить, используя сортировку, и сделает вашу проблему примерно в 900-90000 раз проще (если предположить, что диапазон значений выше).

Некоторые из этих номеров может быть слишком оптимистичным - например, IO не был принят во внимание на всех, и если ваша проблема I/O связанного с использованием C/Java не поможет. Могут быть некоторые очень популярные темы, которые могут повредить подходы, обсуждаемые в C. Для D) вам нужно время O (n log n) для сортировки ваших данных; но есть очень хорошие реализации для этого. Но это определенно упрощение, которое вы должны сделать. Эти документы также будут формировать полностью связанные клики в ваших окончательных данных, что, вероятно, повредит и другим анализам.