В поисках лучшего алгоритма или структуры данных для улучшения преобразования подключения от идентификаторов к индексам

Question

Я работаю с Python 3.6.2 и NumPy.

Я пишу код для визуализации модели конечных элементов и результатов.

Код визуализации требует, чтобы узлы и элементы сетки конечных элементов идентифицировались с помощью индексов (начиная с нуля, без пробелов), но входные модели основаны на идентификаторах и могут иметь очень большие промежутки в пространстве идентификаторов.

Поэтому я обрабатываю все узлы и элементы и изменяю их, чтобы использовать индексы вместо идентификаторов.

Узлы

Первым шагом является обработка массива узлов и координат узлов. Это приходит ко мне отсортированным, поэтому мне не нужно ничего делать с координатами - я просто использую индексы массива узловых координат. Но мне нужно переопределить связность элементов, чтобы они были индексными, а не ID.

Для этого я создаю словарь, перебирая массив идентификаторов узлов и добавляя каждый узел в словарь, используя его идентификатор в качестве ключа и его индекс в качестве значения.

В следующем фрагменте кода

1. model.nodes - это словарь, содержащий все объекты Node, идентифицированные по их идентификатору

2. nodeCoords - это предварительно выделенный массив NumPy, в котором я храню узловые координаты для последующего использования в визуализации. Именно индексы этого массива я должен использовать позже, чтобы переопределить мои элементы

3. nodeIdIndexMap - это словарь, который я заполняю, используя идентификатор узла в качестве ключа и индекс nodeCoords в качестве значения

Код:

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

Затем я перебираю все элементы, просматривая идентификатор каждого элемента элемента в словаре, получая индекс и заменяя идентификатор на индекс.

В следующем фрагменте кода

1. tet4Elements - это словарь, содержащий все элементы типа tet4, которые вводятся с использованием идентификатора элемента
2. n1, n2, n3 и n4 - это заранее выделенные массивы, которые содержат узлы элементов
3. element.nodes[n].nid получает идентификатор узла элемента
4. n1[tet4Index] = nodeIdIndexMap[element.nodes[0].nid ищет идентификатор узла элемента в словаре, созданном в предыдущем фрагменте, возвращает соответствующий индекс и сохраняет его в массиве 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 500000 элементов tet4 занимает около 16 секунд (каждый элемент tet4 имеет четыре узла, каждый идентификатор узла должен быть найден в словаре, так что это 26 миллионов поисков в словаре в словарь с 1 600000 записей.

Так что вопрос в том, как сделать это быстрее? В какой-то момент я перейду на C++, но сейчас я пытаюсь улучшить производительность в Python.

Буду благодарен за любые идеи по улучшению производительности.

Спасибо,

Doug

Answer 1

С цифрами, которые вы цитируете, и разумным аппаратным обеспечением (8 ГБ оперативной памяти) сопоставление может быть выполнено менее чем за секунду Плохая новость заключается в том, что извлечение данных из исходных указаний объектов занимает в 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)