有效地迭代和存儲數以千計/數百萬個對象

我正在開發一個模擬器，我需要能夠處理數千個潛在數百萬個更新每個循環的對象。所有對象都需要具有稱爲（AI）的邏輯功能。但取決於對象的位置決定了邏輯的詳細程度。例如：有效地迭代和存儲數以千計/數百萬個對象

[100個對象合作，以保持它的簡單]

所有對象都有一個位置（x，y）的
20對象是500點遠離從'的景點位置。
50對象是500點從20對象（1000點的距離）。
30對象內的興趣點100個點。

現在說這是一個詳細的城市仿真的對象是虛擬的公民。在下午6點，每個人都應該從工作中回家睡覺。

所以我們遍歷所有的公民，但我想讓他們做不同的事情。

更遠離物體（50）回到家中從他們的工作和睡覺直到早晨。
較近的物體（20）從他們的工作回家，有一個咬吃，然後睡覺，直到早晨。
最接近的對象（30）去從他們的工作家，得一口一口吃，刷牙然後睡覺，直到早上。

正如你可以看到他們是接近的興趣點的更詳細的邏輯變。

我正在努力研究什麼是最好和最有效的方式來遍歷所有對象將是。這將是一個相對容易的手充滿對象，但因爲這需要處理至少500,000對象有效，我需要一些建議。

而且我不知道我是否應該通過所有對象的每一個循環迭代或者它會更好地迭代通過最近的物體的每一個循環，但每10個循環只有itereate通過漸行漸遠的對象？

與需要的對象與其它對象之間的互動接近他們的附加要求，我一直在想這樣做可能是組織他們在四叉樹的最佳方式，但我不知道。看起來好像四叉樹對於靜態內容更多，但我所處理的對象具有一個位置，並且需要移動到其他位置。我是否正在思考的正確軌道？或者，還有更好的方法？

我也在C++中工作，如果有人認爲它的相關。

任何意見，將不勝感激。

注：

的興趣變化點定期，認爲它是一個攝像頭視圖。
對象是動態創建和

來源

2013-02-14 xyz

摧毀如果你想從特定的點一定半徑快速選擇的對象，那麼四叉樹或只是簡單的方形網格會有所幫助。

如果你的問題是如何存儲數以百萬計的對象來有效地迭代它們，那麼你可能可以使用基於列的技術，而不是每個擁有5個字段的100萬個對象時，有5個包含100萬個元素的數組每。在這種情況下，每個對象只是在範圍0 999999因此，舉例來說，要存儲以下結構的百萬對象的索引..：

struct resident 
{ 
    int x; 
    int y; 
    int flags; 
    int age; 
    int health; // This is computer game, right? 
}

然後，不是宣告resident residents [1000000]聲明5個陣列：

int resident_x [1000000]; 
int resident_y [1000000]; 
int resident_flags [1000000]; 
int resident_age [1000000]; 
int resident_health [1000000];

那麼，而是說：而且，residents [n].x使用resident_x [n]。當您需要遍歷相同類型的所有對象並對每個對象中的幾個字段（每個對象中具有相同的一組字段）執行某些操作時，存儲對象的這種方式可能會更快。

來源

2013-02-14 21:02:58

因此，第一個數組最接近點，第二個數組接近第二個數組......然後在數組之間移動對象，取決於對象與點的距離如何？我忘記提及的唯一問題是感興趣的點會改變，所以會有很多數組交換。 – xyz 2013-02-14 21:06:49

@xyz號只需添加更多細節。 – 2013-02-14 21:25:39

對不起，我想知道。謝謝你爲我清理這個。 – xyz 2013-02-14 21:27:50

您需要將問題分解爲「類」，就像在現實世界中一樣。每個人的課程都是從距離計算的。所以低階層的人遠離上流社會。或者更準確地說是「遠距離課堂」，近距離課堂和「這裏上課」，或者任何你想要給他們命名的東西。

1）爲每個類創建一個插槽。該插槽將保存該班級中每個人的「鏈接列表」。當一個階級轉換者（社會登山者），那麼將這個對象轉移到另一個列表是非常迅速的。

2）因此，把每個人都放到適當的類中，只迭代接近你的類。在適當的場景中，有些對象需要遠離關心，因此您可以將這些對象放回到磁盤上，並在距離較近時重新加載。

來源

2013-02-14 21:13:01

我不知道計算時間是否會有好處？由於每個循環都需要檢查所有對象類的關聯，以確保它們仍然屬於正確的類，並且不會改變它們的類。如果（citizen [i] - > class == far && citizen [i] - > distance> = 1000）繼續，則爲（i = 0; i xyz 2013-02-15 02:30:30

當分配距離或類時，班級是否改變。不在循環中。所以當你設置距離時，或者類創建一個名爲update class的函數並在那裏檢查它。因爲列表鏈接交換類是快速的。 – 2013-02-15 13:57:50

是的，使用鏈表，沒有for循環與我整數。使用鏈表來循環它。它必須是一個鏈表，以便類可以快速更改。 – 2013-02-15 13:58:33

有幾個問題嵌入在那裏： - 如何處理大量的對象？如果有固定數量的固定對象，只要有足夠的內存，就可以簡單地創建它們的數組。如果您需要動態創建並銷燬它們，那麼您將自己置於內存泄漏的風險之中，無需仔細處理被破壞的對象。在某個時候，您可能會問自己，使用其他應用程序（如數據庫）來存儲對象，並只執行C++代碼中的邏輯更好。數據庫將提供我將強調的其他功能。

- 如何找到與他人給定距離的物體。這是地理信息系統（GIS）的經典問題;這聽起來像是你想要操作一個簡單的GIS來存儲你的對象和屬性，所以它是適用的。它需要計算能力來測試每個點上的SQRT（（X-x）^ 2 +（Y-y）^ 2）距離公式。相反，通常使用'窗口函數'來提取包含所有想要的點的正方形，然後在其中搜索以找到特定位於給定半徑內的點。一些數據庫經過優化以執行各種GIS功能，包括返回給定半徑內的點，或返回其他幾何圖形（如多邊形）內的點。否則，你必須自己編寫這個功能。

- 對象的存儲。這可以提高速度，但是如果物體不斷移動，你就會進行權衡，其中樹必須經常重構。這一切都取決於事情多久發生一次，以及你想多久進行一次計算。

-AI代碼。如果您想要對數百萬個對象執行AI，這可能是您最大的性能使用，而不是用於存儲和搜索對象的方法。對於遠離點的較簡單的代碼會提高性能，正如對較遠點執行邏輯的次數較少一樣。有時使用Monte Carlo分析來處理這個問題，在任何給定的迭代中，邏輯將在隨機子集上執行，並且隨着距興趣點距離的增加，執行概率可能會降低。

來源

2013-02-14 21:13:19

我會考慮使用帶莫頓編碼/ Z順序索引的線性四叉樹。您可以通過使用位陣列來表示包含數據的節點並快速執行計算，從而進一步優化此結構。

我已經在使用Javascript的瀏覽器中非常高效地完成了這項工作，並且我可以在亞秒內遍歷6700萬個節點。一旦我將其縮小到感興趣的區域，我就會以不同的結構查看數據。所有這些仍然以毫秒爲單位。我正在使用這個空間矢量動畫。

來源

2014-04-05 19:00:13 theoutlander

有效地迭代和存儲數以千計/數百萬個對象

回答

相關問題