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

Question

我正在使用 Python 3.6.2 和 numpy。

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

可视化代码要求有限元网格节点和元素由索引标识（从零开始，没有间隙）但输入模型基于 ID，并且 ID 中可能有非常大的间隙 space.

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

节点是

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

为此，我创建了一个字典，方法是遍历节点 ID 数组并将每个节点添加到字典中，使用它的 ID 作为键并将其索引作为值

在下面的代码片段中，

model.nodes 是一个包含所有 Node 对象的字典，由它们的 id
nodeCoords 是一个预分配的 numpy 数组，我在其中存储节点坐标以供以后在可视化中使用。这是我稍后需要使用的这个数组的索引来重新定义我的元素
nodeIdIndexMap 是我使用节点 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 替换为索引。

在下面的代码片段中，

tet4Elements 是一个包含所有 tet4 类型元素的字典，使用元素 id
n1、n2、n3 和 n4 是预先分配的 numpy 数组，用于保存元素节点
element.nodes[n].nid 获取元素节点ID
n1[tet4Index] = nodeIdIndexMap[element.nodes[0].nid在上一个片段创建的字典中查找元素节点ID，returns对应索引存入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都得查字典，所以在包含 1,600,000 个条目的字典中进行 2600 万次字典查找。

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

的性能

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

谢谢，

道格

Answer 1

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

# extract 29.2821946144104 map 0.4702422618865967

但也许您可以找到一些批量查询节点和四元组的方法？

代码：

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)

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

Looking for a better algorithm or data structure to improve conversion of connectivity from ID's to indices

python

numpy

dictionary

finite-element-analysis