替代嵌套數組（6維），保留O（1）的存儲空間訪問權限

我正在讀取運行具有不同配置的程序的統計數據。假設有6種配置（a,b，...，f）。配置可能不會線性變化，所以如果您將測量結果視爲表格，表格中可能存在空白。問題在於關於在存儲器中構造這些統計數據。替代嵌套數組（6維），保留O（1）的存儲空間訪問權限

，想到的第一件事是看這些配置動態分配的6深或多個陣列：

struct data ******measurements;

現在能正常工作。你只有很少的內存開銷（只有實際分配數據的配置），訪問時間爲O(1)。

除了大多數人不喜歡******指針這個事實，它的缺點是添加配置意味着向數組添加維度，除非讀寫數組被封裝在函數中，否則可能會變得很難看。（必要時Write已經被封裝來處理分配，所以這實際上並不是什麼大不了的事）。

想到的另一個想法是使用AVL樹或東西（我already have所以沒有實現間接費用）使用地圖struct config到struct data。這解決了擴展配置參數的問題，但將訪問時間減少到O(log(n))。

對於O(log(n))來說，測試次數可能會相當大。

我的問題是：在這裏使用6深層嵌套數組是否合理？或者有更好的方法來做到這一點？

來源

2012-06-11 Shahbaz

爲什麼不使用一臺單維數組，做你自己的指數計算，而不是讓編譯器做呢？ –

擁有n維數組將增加緩存未命中的可能性，並可能導致代碼的性能很差。採用智能數據結構將帶來更好的性能。如果你的數據集是標稱恆定，你可以打造擁有近O（1）與唯一的缺點好的哈希函數查找是你必須首先構建它的哈希表... – Mosby

這不是6D數組，但只有一個仿效它。 C具有內置的n維數組，不需要指針開銷。 –

真正的性能瓶頸（除了浪費內存）不是計算，而是你會遇到的間接和緩存未命中的數量。這些可以支配數百到數千的計算指數和類似的東西。所以你最好的選擇是減少間接的數量，並花一點時間進行計算。據我所見，這最好通過散列6個索引來完成。這樣可以將你的indirections減少到兩個，首先查找存儲在散列表中的值（可能是一個指針），然後直接獲取你感興趣的數據。

來源

2012-06-12 08:15:45

請注意，您當前的設置不是O（1），它是O（k），其中k是維數。有了平衡樹，無論如何它都會到達O（log 2^k）== O（k）（我假設每個維度都有兩個選擇，但沒關係......這裏只是一個常數）。儘管如此，您可能會也可能不會期望在實現均衡樹方面帶來更大的開銷。你可以做的就是嘗試用typedefs和getter/setter函數（最好是inlineable）抽象接口，然後使用你想要的任何實現。那麼你不必處理那麼多的指針，而仍然使用裏面的任何結構。

來源

2012-06-11 17:14:58 liori

是的，它是'O（k）'，'k'是配置的數量。儘管並非所有可能的值都被記錄，但每個配置可以是任何整數（比如小於65k）。假設一個配置可能需要200個可能的值，另一個配置不同的數字。如果你有'xi'配置'i'的值，你總共有'n = x1 * x2 * x3 * ... * x6'測量值。在平衡樹的情況下，這變成'O（log（n））'，這與'k'完全無關。 – Shahbaz

使用6D陣列其實很簡單，你只需要'write_to'和'read_from'（在線）即採取6個索引功能。你只是確認我應該和陣列一起去呢？ – Shahbaz

我只是說如果你抽象接口，你可以測試你的特定情況下哪種方法實際上是最快的，而不需要改變其他人的代碼。 – liori

X-trees是高效存儲和查找高維數據的常用選擇。鏈接的維基百科文章只是一個存根，但它指向一個更權威的來源。

它們基本上是R-Tree的改進版本，爲最小化的重疊進行了優化。

我不知道手邊有一個c實現。

來源

2012-06-11 17:47:35 dmckee

這非常有趣。我還閱讀了R-樹。但在我看來，鑑於我的數據的表格性質，這將減少爲數組和樹方法的混合。例如，前四個配置中的平衡樹和每個組內的二維數組。你怎麼看？ – Shahbaz

替代嵌套數組（6維），保留O（1）的存儲空間訪問權限

回答

相關問題