建立從兩個字典中的一個被比較的密鑰的新詞典，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左側的鍵在這個過程結束時，它們都會以結果字典結束，即dict2的值集合等於dict1的設定值。

我實現它的方式是：

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秒運行，這些長度的例子不是我有興趣使用的最大的。你能告訴我是否有可能加速它，或者我應該想辦法解決這個問題嗎？ 謝謝。

Answer 1

當前您正在對vertex_coordinates中的每個條目遍歷element_coordinates。如你所見，這很慢。

爲什麼不寫一個與element_coordinates：{(1.0,1.0,1.0):[4, 8], ...}相反的新字典。這樣你只需迭代一次，然後快速查找。

有一個與此（謝謝@盧卡斯格拉夫）的漁獲。浮動並不總是正確比較，這可能無法正常工作。如果計算座標，則可能會出現舍入誤差，查找將無法按預期工作。這就是爲什麼你在你的問題中使用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個項目。如果你必須改變一個值，只需要替換整個元組。

Answer 2

我沒有你的數據，所以我不能測試自己的表現，但是如何理解一個大的邪惡列表？像這樣？

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.

Answer 3

您可能希望重新考慮如何存儲數據。你可以使用一個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]} 

這應該會加快你的程序，但是不能知道你的數據的完整結構我可能做出了假設並不一定是正確的。