从两个被比较的字典中的一个字典的键创建一个新字典，Python。

Question

我有两个带有坐标的字典：

vertex_coordinates = {0: [x0,y0,z0], 1: [x1,y1,z1], 2: [x2,y2,z2] ...}
element_coordinates = {0: [X0,Y0,Z0], 2: [X2,Y2,Z2], 7: [X3,Y3,Z3] ...}

第一个字典的键名是0:N，而第二个字典的键名是排序过的，但不一定是连续的。第二个字典实际上比第一个字典要大得多，因此有一个特殊情况

len(vertex_coordinates) = 729
len(element_coordinates) = 58752

我需要的是一个字典，其中键表示第一个字典的键，与此键相关联的值是来自第二个字典的键列表，这些键的坐标相等。例如，让我们假设有两个字典:

vertex_coordinates = {0: [1.0,1.0,1.0], 1: [0.0,0.0,0.0], 2: [3.0,4.0,5.0], 3: [3.0, 6.0, 7.0]}
element_coordinates = {0: [0.0,0.0,0.0], 1: [3.0,4.0,5.0], 3: [3.0,6.0,7.0], \
   4: [1.0,1.0,1.0], 6: [0.0,0.0,0.0], 7: [3.0,4.0,5.0], 8:[1.0,1.0,1.0] \
   10: [3.0,6.0,7.0]}

然后，所需的字典是：

element_to_vertex = {0: [4,8], 1: [0,6], 2: [1,7], 3: [3,10]}

这可能很重要，也可能不重要，但我的数据结构是这样的，这个过程中字典2中没有键会留下来，它们都将最终进入结果字典，即字典2的值集合等于字典1的值集合。

我实现的方式是：

for vertex in vertex_coordinates:
  temp = []
  for elem in element_coordinates:
    if(near(element_coordinates[elem][0], vertex_coordinates[vertex][0])):
      if(near(element_coordinates[elem][1], vertex_coordinates[vertex][1])):
        if(near(element_coordinates[elem][2], vertex_coordinates[vertex][2])):
          temp.append(elem)

  element_to_vertex[vertex] = temp

虽然这个方法可以正常工作，但速度非常慢：在字典长度分别为729和58752的示例中，运行时间大约需要25秒，而我感兴趣的长度并不是最大的。请问是否可能加快速度或者我应该考虑其他解决方法？ 谢谢。

- Pukki

---

dof 是从哪里来的？ - Bob Dylan

我的错，已经编辑了。应该是“elem”。 - Pukki

Answer 1

目前你正在每个vertex_coordinates条目中迭代element_coordinates。这样做速度非常慢。

为什么不创建一个与element_coordinates相反的新字典：{(1.0,1.0,1.0):[4, 8], ...}。这样，您只需要迭代一次并进行快速查找。

但是，有一个问题（感谢@Lukas Graf）。浮点数不总是正确比较，这可能行不通。如果计算坐标，则可能存在四舍五入误差，查找将无法按预期工作。这就是为什么您在问题中使用near方法的原因。您可以查看bigdecimal，以获取潜在的修复方法。如果数据相对干净或已设置，应该没有问题。

用这种方式，您只需一次迭代每个字典。它从O(n^2)变成了O(n)。这种方式使用更多的内存，但您必须选择其中之一。

你可以像这样做：

from collections import defaultdict
vertex_coordinates = {0: [1.0,1.0,1.0], 1: [0.0,0.0,0.0], 2: [3.0,4.0,5.0], 3: [3.0, 6.0, 7.0]}
element_coordinates = {0: [0.0,0.0,0.0], 1: [3.0,4.0,5.0], 3: [3.0,6.0,7.0], 4: [1.0,1.0,1.0], 6: [0.0,0.0,0.0], 7: [3.0,4.0,5.0], 8:[1.0,1.0,1.0], 10: [3.0,6.0,7.0]}

inv_el_coords = defaultdict(list)

for k, v in element_coordinates.items():
    inv_el_coords[tuple(v)].append(k)

element_to_vertex = {k:inv_el_coords[tuple(v)] for k,v in vertex_coordinates.items()}

print(element_to_vertex)

顺便提一下，如果一开始就能将数据存储在元组中，那么将有助于提高速度，因为不需要将它们转换为元组。据我所见，这不应该是一个问题，因为值列表始终只有3个项目。如果你需要更改其中一个值，请直接替换整个元组。

- Kassym Dorsel

---

虽然查找表通常是解决此类问题的理想方法，但这种解决方案存在一个问题：OP正在处理浮点数（三维空间中的坐标）。由于表示问题和舍入误差，浮点数不幸地不能始终相等，尽管它们在所有意义上都是相等的。这就是为什么它们通常使用公差epsilon进行比较 - 我假设这就是OP的“near（）”函数所做的。 - Lukas Graf

所以，除非有某种保证，表中的坐标不是某些算术操作的结果，否则 inv_el_coords[tuple(v)] 查找可能会失败。例如，hash(0.2 + 0.1) != hash(0.3)。 - Lukas Graf

你是正确的。我不应该假设所有数字都是圆滑完美的。 - Kassym Dorsel

Answer 2

你可能需要重新考虑如何存储数据。你可以使用numpy数组来存储顶点坐标，使用scipy稀疏矩阵来存储元素坐标。这样你既可以保持空间效率，又可以获得高效的操作数据的方法。

from scipy.sparse import coo_matrix
from itertools import chain
import numpy as np

# input as specified
vertex_coordinates = {0: [1.0,1.0,1.0], 1: [0.0,0.0,0.0], 2: [3.0,4.0,5.0], 3: [3.0, 6.0, 7.0]}
element_coordinates = {0: [0.0,0.0,0.00000001], 1: [3.0,4.0,5.0], 3: [3.0,6.0,7.0], \
   4: [1.0,1.0,1.0], 6: [0.0,0.0,0.0], 7: [3.0,4.0,5.0], 8:[1.0,1.0,1.0], \
   10: [3.0,6.0,7.0]}

# conversion to numpy array and sparse array
vertex_coordinates = np.array(list(vertex_coordinates.values()), dtype=float)
rows = list(chain.from_iterable([i] * 3 for i in element_coordinates))
cols = list(range(3)) * len(element_coordinates)
data = list(chain.from_iterable(element_coordinates.values()))
element_coordinates = coo_matrix((data, (rows, cols)))
del rows, cols, data

# create output
num_cols = vertex_coordinates.shape[1] # 3
num_rows = len(element_coordinates.row) // num_cols # 8 in this case
shape = num_rows, num_cols

element_to_vertex = {}
# data and row are flat arrays, reshape array to have 3 columns
data_view = element_coordinates.data.reshape(shape)
row_indices = element_coordinates.row[::num_cols]
for i, row in enumerate(vertex_coordinates):
    # compare each row in element_coordinates to see if there is any match
    matches = np.isclose(row, data_view)
    # keep only the rows that completely matched
    row_matches = matches.all(axis=1)
    if row_matches.any():
        # if at least one row matched then get their indices 
        indices = row_indices[row_matches]
        element_to_vertex[i] = indices.tolist()

print(element_to_vertex)
# prints {0: [4, 8], 1: [0, 6], 2: [1, 7], 3: [3, 10]}

这应该能加速您的程序，但是由于无法了解您数据的完整结构，我可能会做出并不一定正确的假设。

- Dunes

Answer 3

我没有你的数据，所以无法自行测试性能，但是怎么样使用一个大而邪恶的列表推导式呢？就像这样：

element_to_vertex = {}
for vertex in vertex_coordinates:
    temp = []
    element_to_vertex[vertex] = [elem for elem in element_coordinates if(near(element_coordinates[elem][0], vertex_coordinates[vertex][0])) and if(near(element_coordinates[elem][1], vertex_coordinates[vertex][1])) and if(near(element_coordinates[elem][2], vertex_coordinates[vertex][2]))]

你可能不会注意到速度上的巨大改善，但是也许会有一些，因为它不必每次查找append()方法。为了获得更好的性能，请考虑使用C语言。

- Bob Dylan