memory-management - 在 Sage 中使用 nauty_geng 的内存错误
问题描述
我试图让 Sage 生成具有 11 个顶点、30 条边和 4 号集团的所有图。我输入了以下内容:
g11=[g for g in graphs.nauty_geng('11 30') if g.clique_number()==4]
过了一会儿,我看到以下消息:
MemoryError Traceback (most recent call last)
<ipython-input-6-1ec9660b8e07> in <module>()
----> 1 g11=[g for g in graphs.nauty_geng('11 30') if g.clique_number()==Integer(4)]
/opt/sagemath-8.6/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in clique_number(self, algorithm, cliques, solver, verbose)
6072 self._scream_if_not_simple(allow_loops=False)
6073 if algorithm == "Cliquer":
-> 6074 from sage.graphs.cliquer import clique_number
6075 return clique_number(self)
6076 elif algorithm == "networkx":
我的 RAM 中似乎没有足够的内存来要求 Sage 为我执行此操作。有没有办法让 Sage 将这些信息存储在其他地方?Sage 是否只需要使用 RAM 内存?我有 1 TB 的可用存储空间。
如果这是不可能的,那么我该如何解决这个问题?先感谢您!
解决方案
上市前清点
有时将感兴趣的数学对象存储在列表中过于雄心勃勃,因为这会占用太多内存。
第一步可能是计算有多少这样的图,以及在尝试存储它们之前迭代它们需要多长时间。
下面的时间是在一台特定的机器上;它们在其他机器上可能会有所不同。
计算 11 个顶点、30 条边、团数为 4 的图大约需要两个小时。
sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: %time nb_g_11_30_c4 = sum(1 for g in g_11_30_c4)
CPU times: user 2h 12min 9s, sys: 1min 9s, total: 2h 13min 18s
Wall time: 2h 13min 18s
sage: nb_cg_11_30_c4
58211868
仅计算连接的那些花费的时间大致相同。
sage: cg_11_30 = graphs.nauty_geng('11 30:30 -c')
sage: cg_11_30_c4 = (g for g in cg_11_30 if g.clique_number() == 4)
sage: %time nb_cg_11_30_c4 = sum(1 for g in cg_11_30_c4)
CPU times: user 2h 13min 27s, sys: 1min 11s, total: 2h 14min 38s
Wall time: 2h 14min 39s
sage: nb_cg_11_30_c4
58182054
我们看到在 11 个顶点上大约有 5820 万个图,有 30 条边和 4 个团,其中大多数是连接的——只有 29814 个没有连接。如果我们只关心未连接的那些,那就大不相同了!
迭代而不是列出
如果存储这些图不可行,我们知道每次想了解它们时,我们可以在两个小时内完成它们。
了解迭代与列表的一种好方法是 阅读 SageMath 的理解教程。
例如,取集合中的第一个图并检查它的边和它的graph6 字符串 (更多关于 graph6 格式):
sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: g = next(g_11_30_c4)
sage: print(g.edges(labels=False))
[(0, 7), (0, 8), (0, 9), (0, 10), (1, 7), (1, 8), (1, 9), (1, 10),
(2, 7), (2, 8), (2, 9), (2, 10), (3, 7), (3, 8), (3, 9), (3, 10),
(4, 8), (4, 9), (4, 10), (5, 8), (5, 9), (5, 10), (6, 8), (6, 9),
(6, 10), (7, 9), (7, 10), (8, 9), (8, 10), (9, 10)]
sage: g.graph6_string()
'J???Fb}~~~_'
第二个:
sage: g = next(g_11_30_c4)
sage: print(g.edges(labels=False))
[(0, 7), (0, 8), (0, 9), (0, 10), (1, 7), (1, 8), (1, 9), (1, 10),
(2, 7), (2, 8), (2, 9), (2, 10), (3, 7), (3, 8), (3, 9), (3, 10),
(4, 8), (4, 9), (4, 10), (5, 8), (5, 9), (5, 10), (6, 8), (6, 9),
(6, 10), (7, 8), (7, 9), (7, 10), (8, 10), (9, 10)]
sage: g.graph6_string()
'J???Fb~~v~_'
等等。
存储较小的等效数据
如果图本身太多而无法存储在列表中,也许我们可以使用这些图的更紧凑的表示,这将占用更少的内存。例如,边列表让我们可以轻松地重构图;非常紧凑的“graph6 字符串”也是如此。
为了给我们一个想法,让我们将前一万个图列表的文件大小作为 Sage 对象,将它们的图边列表列表作为 Sage 对象,将它们的 graph6 字符串作为文本文件:
sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: graphs = [next(g_11_30_c4) for _ in range(10^4)]
sage: save(graphs, "g_11_30_c4_1e4_graph_bare")
sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: edges = [next(g_11_30_c4).edges(labels=False) for _ in range(10^4)]
sage: save(edges, "g_11_30_c4_1e4_graph_edges")
sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: s = '\n'.join(next(g_11_30_c4).graph6_string() for _ in range(10^4))
sage: with open('g_11_30_c4_graph_graph6.txt', 'w') as f:
....: f.write(s)
....:
119999
比较相应的文件大小:
g_11_30_c4_1e4_graph_bare.sobj
: 971Kg_11_30_c4_1e4_graph_edges.sobj
: 775Kg_11_30_c4_1e4_graph_graph6.txt
: 117K
显然,graph6 格式胜出,以这种格式将所有 5820 万个图形存储在一个文本文件中需要 ~ 5820 * 117K,即 ~ 680M。
我们还可以将其存储在编号为 0 到 99 的 100 个文件中,如下所示:
sage: n = 100
sage: for k in range(N):
....: gk = graphs.nauty_geng('11 30:30 {}/{}'.format(k, n))
....: ggk = (g for g in gk if g.clique_number() == 4)
....: s = '\n'.join(g.graph6_string() for g in ggk)
....: with open('g_11_30_c4_graph_graph6_file_{}_of_{}.txt'
....: .format(k, n - 1), 'w') as f:
....: f.write(s)
这将让我们在几个会话中研究这些图表,而无需每次都让 nauty 工作两个小时。
推荐阅读,取决于您的 Sage 所基于的 Python 版本:
推荐阅读
- spring-boot - JPA双向关系父为空
- perl - 防止编译器执行 BEGIN / UNITCHECK / CHECK / INIT 块
- c++ - Rust 中不止一个运算符重载
- python - 了解我的 while 循环中断的原因
- python - MQTT paho 上课时收不到消息
- sublimetext3 - 项目设置中的崇高主题
- excel - 在 powershell 特殊变量中不起作用
- c# - C# 使用来自授权端点 (crv, x, y) 的值验证 JWT 令牌
- google-apps-script - 当项目被附加并发布时,我想了解 GAS 的 SpreadsheetTriggerBuilder
- javascript - 如何修复 API 调用 nodeJS 上的 Cors 错误消息