Skip to main content
 首页 » 编程设计

python之具有大对象的 Memcached(NetworkX 图)

2024年12月31日9zhenyulu

我有一个 NetworkX 图 (g),它有大约 25k 个节点和 125k 个边。我想使用 memcached 缓存 g 但 g 太大了。我最多可以将每个项目的 memcached 限制增加到 32MB,但这是行不通的。

  1. 我是否应该尝试让它与 memcached 一起工作?

  2. 如果我希望能够存储最多具有 1m 个节点和 10m 个边的 networkx 图,我还有哪些其他选择?

  3. 在 (a) 对图一无所知,以及 (b) 以导致最小性能下降的方式将图 block 重新组合在一起的情况下,我如何对图进行分块以使其更小。

    <

我正在使用 python。附上创建图表的示例代码。

import sys 
import pickle 
import random 
import networkx as nx 
from django.core.cache import cache 
 
def randstring(x=3): 
    return ''.join([chr(random.randrange(65, 91)) for _ in range(x)]) 
 
class Qux(object): 
    def __init__(self, foo, bar): 
        self.foo = foo 
        self.bar = bar 
 
for n, v in {1: 500, 2: 5000, 3: 50000}.items(): 
    g = nx.Graph() 
    nodes = [Qux(randstring(), randstring()) for _ in range(v)] 
    g.add_nodes_from(nodes) 
    for node in g.nodes: 
        num = random.randrange(25) 
        edges = [(node, random.choice(nodes)) for _ in range(num)] 
        g.add_edges_from(edges) 
 
    print len(g.nodes), sys.getsizeof(pickle.dumps(g)) 
    cache.set('{}/graph'.format(n), g, 3600) 

Memcached 控制台输出(memcached -I 32M -vv)

<20 new auto-negotiating client connection 
20: Client using the ascii protocol 
<20 set :1:1/graph 1 3600 130678  
>20 STORED 
<20 delete :1:2/graph 
>20 NOT_FOUND 
<20 delete :1:3/graph 
>20 NOT_FOUND 

请您参考如下方法:

如果您查看 NetworkX 的代码,就会发现图形只不过是 python 指令。如果您需要的唯一功能是访问节点和边,那么使用字典构建图形并将文件转换为 JSON 可以让您缓存图形。 向无向加权图添加边的代码本质上是这样的:

G_New = {} 
for edge in edges: 
    try: 
        G_New[edge['node1'].update({edge['node2']: edge['weight']}) 
    except KeyError: 
        G_New[edge['node1']] = {edge['node2']: edge['weight']} 
    try: 
        G_New[edge['node2']].update({edge['node1']: edge['weight']}) 
    except KeyError: 
        G_New[edge['node2']] = {edge['node1']: edge['weight']} 

之后是一个简单的json.dumps(G_New)。对于较大的图形,您可以将 dict 拆分为较小的组件并将每个组件托管在内存缓存上。因此 How to split dictionary into multiple dictionaries fast