為此，我使用坐標變換 (x,y)-> 1000*x y 來提高效率。
了解代碼在做什么并不是很重要，但對于這個問題： https ://oeis.org/A337663
這只是將它們添加到板上，然后將它們作為性能指標洗掉：
##################
#1###1###1###1###1#
##################
并跟蹤觸摸板上數字的鄰居的總和
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
using namespace std;
//I Know this is bad practice, but just for readability for now
void add_update_edges_and_used(int spot, unordered_map<int, unordered_set<int> > &edge_sums_to_locations, unordered_map<int, int> &edge_locations_to_sums,
unordered_set<int> &used_locations, int current_number) {
used_locations.insert(spot);
vector<int> neighbors { spot 1000,spot-1000,
spot 1,spot-1,
spot 1000 1,spot-1000 1,
spot 1000-1,spot-1000-1 };
for (int neighbor : neighbors) {
if (used_locations.count(neighbor) == 0) {
if (edge_locations_to_sums.count(neighbor)) {
edge_sums_to_locations.at(edge_locations_to_sums.at(neighbor)).erase(neighbor);
edge_locations_to_sums.at(neighbor) = current_number;
} else {
edge_locations_to_sums.insert({neighbor, current_number});
}
int new_neighbor_sum = edge_locations_to_sums[neighbor];
if (edge_sums_to_locations.count(new_neighbor_sum)) {
edge_sums_to_locations.at(new_neighbor_sum).insert(neighbor);
} else {
unordered_set<int> new_edge_sum_locations;
new_edge_sum_locations.insert(neighbor);
edge_sums_to_locations.insert({new_neighbor_sum, new_edge_sum_locations});
}
}
}
}
int main() {
std::clock_t start_time = std::clock();
unordered_map<int, unordered_set<int> > edge_sums_to_locations;
unordered_map<int, int> edge_locations_to_sums;
unordered_set<int> used_locations;
for (int q=0; q<1000; q ) {
edge_sums_to_locations.clear();
edge_locations_to_sums.clear();
used_locations.clear();
for (int i=0; i<100; i ) {
add_update_edges_and_used(i*4, edge_sums_to_locations, edge_locations_to_sums,
used_locations, 1);
}
}
std::clock_t tot_time = std::clock() - start_time;
std::cout << "Time: "
<< ((double) tot_time) / (double) CLOCKS_PER_SEC
<< " seconds" << std::endl;
return 0;
}
大約需要 1 秒
import time
def add_update_edges_and_used(spot, edge_sums_to_locations, edge_locations_to_sums,
used_locations, current_number):
used_locations.add(spot)
neighbors = {spot 1000,spot-1000,
spot 1,spot-1,
spot 1000 1,spot-1000 1,
spot 1000-1,spot-1000-1}
unused_neighbors = neighbors.difference(used_locations)
for neighbor in unused_neighbors:
if neighbor in edge_locations_to_sums.keys():
edge_sums_to_locations[edge_locations_to_sums[neighbor]].remove(neighbor)
edge_locations_to_sums[neighbor] = current_number
else:
edge_locations_to_sums[neighbor] = current_number
new_neighbor_sum = edge_locations_to_sums[neighbor]
if new_neighbor_sum in edge_sums_to_locations.keys():
edge_sums_to_locations[new_neighbor_sum].add(neighbor)
else:
edge_sums_to_locations[new_neighbor_sum] = {neighbor}
start_time = time.time()
start_cpu_time = time.clock()
for q in range(1000):
edge_sums_to_locations = {} #unordered map of ints to unordered set of ints
edge_locations_to_sums = {} #unordered map of ints to ints
used_locations = set() #unordered set of ints
for i in range(100):
add_update_edges_and_used(i*4, edge_sums_to_locations, edge_locations_to_sums,
used_locations, 1)
print(f'CPU time {time.clock() - start_cpu_time}')
print(f'Wall time {time.time() - start_time}')
大約需要 0.4 秒
這個問題在放大后仍然存在并且與擦除功能無關，而是基于分析的插入和洗掉。
我一直聽說 C 通常更快，所以我希望通過從 python 轉換為 C 來提高這個函式的速度。
uj5u.com熱心網友回復：
大部分執行時間應該花在快取未命中、分配和容器實作的開銷上（即低級細節）。這就是為什么啟用優化應該產生很小的影響（如果甚至可以忽略不計）。編譯器不能輕易地優化散串列容器。CPython 和目標 C STL 實作之間的差距來自于容器的不同實作。
C unordered_map和unordered_set實作對 hash-table 使用單獨的鏈接方法。這是由于 C 標準中的幾個限制（如提供的答案中所述）。簡而言之，該實作基本上是一桶鏈表（即。vector<list<pair<Key,Value>>>），眾所周知，這是非常低效的。此外，一些實作還使用模數將散列轉換為桶中的索引，并且已知此操作在大多數平臺上非常慢。
3.6 CPython 實作使用不斷增長的整數索引陣列來參考包含條目的不斷增長的陣列。每個條目基本上是一個包含散列、鍵和相關值的元組。有關這方面的更多資訊，請參見此處。CPython 使用開放尋址方法，更具體地說是二次探測，只要負載因子特別小并且沒有太多沖突（否則表需要很小），它就非常有效。
讓我們比較兩個實作。在 C 實作中，每個桶可能非常大，因為它通常包含一個指向條目（即鍵值對）的指標，并且指標在主流 64 位平臺上占用 8 個位元組。在 CPython 實作中，索引陣列包含可變大小的整數：從 1 位元組到 8 位元組，與字典中的專案數有關。這是有效的，因為表在記憶體中可以更加緊湊，并且還降低了導致快取未命中的風險（因為當每個專案使用 1 個位元組時，表可以包含在少數快取行中）。條目陣列要大得多，但它的好處是可以打包在記憶體中（并有序）。最后，（最近的）CPython 實作的資料區域性往往優于 C 實作之一。
請嘗試替代 C 哈希映射實作。您可以在 Internet 上找到使用開放尋址的非常有效的非標準 C 哈希映射實作。例如，Tessil 的robin-map和hopscotch -map以及ankerl::unordered_dense::map特別有效且設計得非常好（請注意，還應調整散列以使用一些散列獲得正確的性能-map 實作）。您可以在這里、這里和那里找到一些很棒的基準。請注意，沒有一個哈希映射來統治它們：它們每個都有優點和缺點（關于用例的可變速度和記憶體占用）。盡管如此，在大多數用例中，它們中的許多通常可以顯著優于其中一種 STL 實作。關于基準和您的特定用例，我建議您嘗試emhash7::HashMap使用mumx散列函式。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/529660.html
標籤：PythonC 表现
上一篇：IIS性能-首次加載aspx頁面