將二維空間中的物體映射到內存中

Question

我有許多通過其二維座標標識的項目（有符號的短程）。每個項目都是包含64KB數據的類。任何時候都有大約500-1500件物品。項目通常在一個點附近以〜20爲一組。我的問題是，我應該如何映射它們，以便它不會佔用過多的內存。項目將被緩慢地添加/刪除（每秒1-10次），並且會經常提取，因此從列表中獲取元素（指向較大結構的指針）應該儘可能快。

我想到的是，會有一些gridContainer類，讓我們說它會存儲64x64指針的矩形。我會有主網格容器，它將存儲其他gridContainer，並且此嵌套的gridContainer將存儲我想要映射的實際項目（這將允許4096x4096個實際項目）。爲了訪問一個特定的項目，例如[260,130]，我將它除以64，並取商以查找父代gridContainer位置和其餘部分以找到嵌套的gridContainer位置。所以對於[270,145]我會有[4,2]和[14,17]。

我也在考慮使用stl的地圖，但我不知道它的內部結構，我不知道應該從中期望的性能。

對我的方法有任何建議，或者有沒有更好的方法來做到這一點？

Answer 1

您可以使用已經建議的std :: map，它只是一個b樹容器，或者您可以使用哈希表，它可能會更快。四叉樹也是一種選擇，與前兩種選擇相比，它將涉及更多，但會提供更早的選項。

具有最小負載的散列表很有可能成爲O（1）查找，但是存在最壞情況的O（n），當n =項目存在時。如果你可以將負載保持在10％以下，那麼你必須有一個非常糟糕的哈希函數來比O（1）更壞。這顯然咀嚼了很多額外的記憶，但它有可能成爲最快的選擇。哈希表的比較類型非常複雜。你有一個hasher函數，它接受鍵類型的輸入，在這種情況下是一對短褲，並返回一個索引。該索引對應於半固定對象陣列上的位置。如果那裏有一個物體，碰撞必須被解決，這可能導致有害的運行時間，所以稀疏越好。

四叉樹的最佳返回時間爲O（1），但僅適用於空單元格，而如果存在項目，則其查找時間爲O（log n），其中n是期望的領域。除非你有很少的對象，否則這有可能比散列表佔用更多的內存，但是如上所述，你會得到一個體面的運行時間，並且不會產生結果的查找可以以相對速度結束。四叉樹的比較類型通常只是一個級聯布爾檢查。

std :: map有一個不變的查找時間O（log n），其中n是地圖中的元素。這是最高效的內存選項，但對於任何查找都有保證的運行時間。 std :: map的比較類型是級聯的小於操作，在int（short1）的情況下，它的速度也很快。

對您可能使用的容器有很好的概述。你應該使用一個取決於你期望你的桌子是如何加載下來的。只有幾個對象（< 500），std :: map可能是您最好的選擇。對於500到5000，你應該使用四叉樹。除此之外，您將開始爲樹使用大量內存，並且可能應該使用散列表。

Answer 2

您可以隨時使用std::map<std::pair<short, short>, *item>這將允許檢索和log(n)時間增加，但對於更精確的答案，我們必須知道你需要什麼樣的操作要快

Answer 3

一個Quad Tree似乎是你在找什麼對於。