2維網格的不同隨機點

我有一個很大的2維網格，比如說10000 X 10000.從這些網格我需要選擇1000個隨機點，但是我也需要注意兩點都不是一樣。我想到的標準方法是，在選擇每一點之後，我應該檢查所有以前的條目以查看該點是否已被選中，但對於大型網格和大量點似乎這將變得低效。有沒有更好的方法來做到這一點？我使用C++2維網格的不同隨機點

來源

2012-05-25 lovespeed

@nim：我甚至會建議在這裏使用'std :: unordered_set'，因爲這些值不需要進行排序。查找將是'O（1）'而不是'O（logN）'。 –

@LucTouraille，當然，不確定OP是否可以訪問C++ 11，否則boost是我猜的一個很好的替代品。 – Nim

隨機選取的任何一點，然後如果存在將其丟棄在選定點名單不應是無效率的，只要你有選定點良好有序集合，你也可以很容易地插入。另外，根據點的定義方式（即它們是否與您定義的類或結構相關聯），您可以向點對象添加一個布爾變量，名爲Selected。選擇一個點後，檢查它是否已被標記爲Selected。如果沒有，請將其添加到您的列表中並將Selected值更改爲TRUE。否則，繼續選擇隨機點。

來源

2012-05-25 12:33:05 RLH

您可能不想創建10000 X 10000個對象（每個點對應一個），特別是如果只選擇1000個對象 – Attila

您的意思是在第一句中寫「高效」？ –

@Luc：謝謝，你是對的。 – RLH

您可以實現這樣的算法：

創建通過哈希來分一個空映射如果散列

選擇隨機點

計算哈希

映射，轉到1

保存哈希&點
個
如果不夠分呢，轉到1

來源

2012-05-25 12:29:22 Wesley

對不起，我不明白「哈希」，請你詳細說明一下嗎？ – lovespeed

哈希是單向的'加密';見http：//en.wikipedia。org/wiki/Hash_function的詳細描述 – Wesley

如果可用，最好使用現有的散列圖 – Attila

似乎對大電網和大量的點，這將成爲低效

不一定。有兩種潛在的低效率來源：

拒絕採樣（即不得不繼續嘗試直到找到尚未選定的點）導致開銷。考慮到你選擇0.001％的積分，隨機選擇兩次相同點的機率非常小。因此，重新嘗試的成本應該可以忽略不計。
檢查隨機選擇的點是否已被選中的開銷。如果將所有以前選擇的點存儲在合適的數據結構中，則可以在O(1)時間內完成。爲此，std::unordered_set將是一個很好的候選人。該集合的大小將隨着您需要選擇的元素數量線性增長，並且將完全獨立於網格大小。

來源

2012-05-25 12:32:56 NPE

只有當你不關心偶爾發生散列衝突時忽略一些點，散列集才能起作用 – Attila

@Attila：請原諒你的赦免？我基本上談論'std :: unordered_set'。 – NPE

與任何散列函數一樣，如果存在比散列值更多的可能性，則會有衝突。我指出，如果存在_is_碰撞，那麼可以排除一些其他有效的點（當它們的哈希與哈希集中已經存在的不同點相沖突時） – Attila

2維網格的不同隨機點

回答

相關問題