python - 寻找更好的算法或数据结构来改进从 ID 到索引的连接转换

Question

我正在使用 Python 3.6.2 和 numpy。

我正在编写代码来可视化有限元模型和结果。

可视化代码要求有限元网格节点和元素通过索引进行标识(从零开始，没有间隙)，但输入模型基于 ID，并且在 ID 空间中可能有非常大的间隙。

因此，我正在处理所有节点和元素，并将它们更改为使用索引而不是 ID。

节点是

第一步是处理节点数组和节点坐标。这对我来说是排序的，所以我不需要对坐标做任何事情 - 我只使用节点坐标数组的索引。但我确实需要将元素的连接重新定义为基于索引而不是基于 ID。

为此，我通过迭代节点 id 数组并使用其 ID 作为键、索引作为值将每个节点添加到字典中来创建一个字典

在下面的代码片段中，

1. model.nodes 是一个包含所有 Node 对象的字典，以它们的 id 为键

2. nodeCoords 是一个预先分配的 numpy 数组，我在其中存储节点坐标以供以后在可视化中使用。我稍后需要使用这个数组的索引来重新定义我的元素

3. nodeIdIndexMap 是一个字典，我使用 Node ID 作为键、nodeCoords 的索引作为值来填充

代码:

nodeindex=0
node_id_index_map={}
for nid, node in sorted(model.nodes.items()): 
    nodeCoords[nodeIndex] = node.xyz   
    nodeIdIndexMap[nid] = nodeIndex
    nodeIndex+=1 

然后我迭代所有元素，在字典中查找每个元素节点 ID，获取索引并将 ID 替换为索引。

在下面的代码片段中，

1. tet4Elements 是一个包含 tet4 类型的所有元素的字典，使用元素 id 作为键控
2. n1、n2、n3 和 n4 是保存元素节点的预分配 numpy 数组
3. element.nodes[n].nid 获取元素节点ID
4. n1[tet4Index] = nodeIdIndexMap[element.nodes[0].nid 在上一个片段创建的字典中查找元素节点 ID，返回对应索引并将其存储在 numpy 数组中

代码:

tet4Index = 0
for eid, element in tet4Elements.items():
    id[tet4Index] = eid
    n1[tet4Index] = nodeIdIndexMap[element.nodes[0].nid]
    n2[tet4Index] = nodeIdIndexMap[element.nodes[1].nid]
    n3[tet4Index] = nodeIdIndexMap[element.nodes[2].nid]
    n4[tet4Index] = nodeIdIndexMap[element.nodes[3].nid]
    tet4Index+=1 

上面的方法可以，但是很慢……处理 6,500,000 个 tet4 元素大约需要 16 秒(每个 tet4 元素有四个节点，每个节点 ID 都要在字典中查找，所以是 2600 万个)在包含 1,600,000 个条目的字典中进行字典查找。

所以问题是如何更快地做到这一点？在某些时候我会转向 C++，但现在我希望提高 Python 的性能。

如果有任何提高性能的想法，我将不胜感激。

谢谢

道格

Answer 1

根据您引用的数字和合理的硬件(8GB 内存)，映射可以在不到一秒的时间内完成。坏消息是，从对象的原始字典中获取数据至少需要花费 60 倍的时间，至少对于我创建的模拟对象而言。

# extract 29.2821946144104 map 0.4702422618865967

但是也许您可以找到某种批量查询节点和 tets 的方法？

代码:

import numpy as np
from time import time

def mock_data(nn, nt, idf):
    nid = np.cumsum(np.random.randint(1, 2*idf, (nn,)))
    nodes = np.random.random((nn, 3))
    import collections
    node = collections.namedtuple('node', 'nid xyz')
    tet4 = collections.namedtuple('tet4', 'nodes')
    nodes = dict(zip(nid, map(node, nid, nodes)))
    eid = np.cumsum(np.random.randint(1, 2*idf, (nt,)))
    tet4s = nid[np.random.randint(0, nn, (nt, 4))]
    tet4s = dict(zip(eid, map(tet4, map(lambda t: [nodes[ti] for ti in t], tet4s))))
    return nodes, tet4s

def f_extract(nodes, tet4s, limit=15*10**7):
    nid = np.array(list(nodes.keys()))
    from operator import attrgetter
    ncoords = np.array(list(map(attrgetter('xyz'), nodes.values())))
    tid = np.array(list(tet4s.keys()))
    tnodes = np.array([[n.nid for n in v.nodes] for v in tet4s.values()])
    return nid, ncoords, tid, tnodes, limit

def f_lookup(nid, ncoords, tid, tnodes, limit):
    nmx = nid.max()
    if nmx < limit:
        nlookup = np.empty((nmx+1,), dtype=np.uint32)
        nlookup[nid] = np.arange(len(nid), dtype=np.uint32)
        tnodes = nlookup[tnodes]
        del nlookup
    else:
        nidx = np.argsort(nid)
        nid = nid[nidx]
        ncoords = ncoords[nidx]
        tnodes = nid.searchsorted(tnodes)
    tmx = tid.max()
    if tmx < limit:
        tlookup = np.empty((tmx+1,), dtype=np.uint32)
        tlookup[tid] = np.arange(len(tid), dtype=np.uint32)
    else:
        tidx = np.argsort(tid)
        tid = tid[tidx]
        tnodes = tnodes[tidx]
    return nid, ncoords, tid, tnodes

data = mock_data(1_600_000, 6_500_000, 16)
t0 = time()
data = f_extract(*data)
t1 = time()
f_lookup(*data)
t2 = time()
print('extract', t1-t0, 'map', t2-t1)