python - 加快从 292 万个数据点创建图表的速度

我在 3.0GB CSV 文件中有 2.92M 数据点，我需要循环遍历它两次以创建一个我想加载到 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

最佳答案

基准 。例如，使用 Python 附带的 cProfile。在您的代码中很容易出现一些代价高昂的低效率，并且在密集型应用程序中很容易导致 10 倍的性能成本。

漂亮的代码，例如

(topic_pages_attributes2 & topic_pages_attributes).count

可能会成为运行时的主要因素，可以通过使用更传统的代码轻松减少。

使用更高效的语言。例如在 benchmarksgame.alioth 中，在许多密集问题上，最快的 Python 3 程序比最快的 C 程序慢 63 倍(Ruby 是 67 倍，JRuby 是 33 倍)。是的，即使使用经过良好优化的 Python 代码，性能差距也可能很大。但是如果你没有优化你的代码，它可能会更大；通过使用更高效的语言并仔细优化代码，您可能可以获得 100 倍到 1000 倍的加速。

考虑更聪明的问题表述。例如，不是迭代每个节点，而是迭代每个边一次。在您的情况下，这可能意味着构建倒排索引，主题 -> 页面。这与文本搜索引擎的工作方式非常相似，也是一种在集群上计算此类操作的流行方式:可以在单独的节点上拆分各个主题。这种方法受益于数据的稀疏性。
这会大大缩短算法的运行时间。

您有大约 3 个 Mio 文档。从你的总数据量来看，他们可能平均不到 100 个主题？您的成对比较方法需要 3mio^2 次比较，这对您造成了伤害。如果每个更流行的主题仅用于 30.000 个文档，您可能只计算 30k^2 * 主题数。假设您有 100 个此类非常受欢迎的主题(稀有主题无关紧要)，这将是 100 倍的加速。

简化您的问题。例如，首先通过排序合并所有具有完全相同主题的文档。为了使这更有效，还要消除所有恰好出现一次的主题。但可能只有 10.000-100.000 组不同的文档。使用排序可以轻松解决此步骤，并使您的问题轻松 900-90000 倍(假设上述值范围)。

其中一些数字可能过于乐观——例如，根本没有考虑 IO，如果您的问题是 I/O 限制，使用 C/Java 可能没有多大帮助。可能有一些非常受欢迎的主题可能会受到 C 中讨论的方法的影响。对于 D)，您需要 O(n log n) 时间来排序数据；但是有非常好的实现可用。但这绝对是您应该做的简化。这些文档还将在您的最终数据中形成完全连接的派系，这也可能会损害其他分析。

关于python - 加快从 292 万个数据点创建图表的速度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25818246/