未定義索引的默認值最快的數據結構？

Question

我想創建一個2d數組，其中，當我訪問索引時，將返回值。但是，如果訪問未定義的索引，它將調用回調並用該值填充索引，然後返回該值。

該數組也將具有負指數，但我可以通過使用4個數組（每個象限圍繞0,0）來克服這個問題。

Answer 1

您可以創建依賴於元組和字典中的Matrix類，具有下列行爲：

from collections import namedtuple 
2DMatrixEntry = namedtuple("2DMatrixEntry", "x", "y", "value") 
matrix = new dict() 
defaultValue = 0 

# add entry at 0;1 
matrix[2DMatrixEntry(0,1)] = 10.0 

# get value at 0;1 
key = 2DMatrixEntry(0,1) 
value = {defaultValue,matrix[key]}[key in matrix] 

乾杯

Answer 2

這個問題可能是計算器過於寬泛。 - 沒有一種通用的「一刀切」解決方案，結果取決於所使用的語言（和標準庫）。

這個問題有幾個問題。首先讓我們考慮一個二維數組，我們說這已經是該語言的一部分，並且這種數組在訪問時動態增長。如果情況並非如此，那麼這個問題就會變得與語言有關。

現在經常在分配內存時，語言自動初始化點（語言取決於這是怎麼回事，最好的方法是什麼，看看RAII）。雖然我可以預見，具體細胞的實際計算可能是昂貴的（與分配相比）。在這種情況下，一個有趣的事情可能就是所謂的「兩階段建設」。該數組必須填充元組/對象。對象的默認構造將bit/boolean設置爲false - 表示該值未準備就緒。然後在acces上（即一個get()方法或一個operator() - 語言相關），如果這個位是假的，它會構造，否則它只是讀取。

---

另一種方法是使用字典/鍵值映射。關鍵是座標和價值。這具有的優點是訪問構造的問題繼承了數據結構（儘管語言依賴）。然而，使用映射的缺點是值的查找速度從O（1）變爲O（logn）。 （雖然實際時間根據語言而有很大差異）。

---

最後，我希望你明白，如何做到這一點取決於更具體的要求，你所使用的語言和其他庫。最後，每種語言只有一個數據結構：未分配值的長序列。任何比這更先進的東西都取決於語言。