現在的實現是把地圖中所有可以放置物品的點讀到伺服器上的list中，然後隨機。

現在list中一共要存儲幾十萬個點，想問下有什麼更好的實現方式嗎，謝謝。

假設可放置物品的位置為 的二值圖像，當中像素為1表示可放置，而需求是要均勻地採樣像素為 1 的坐標。

現時題主的方法是把可放置的坐標存儲為列表，然後均勻採樣。每個坐標需用 個比特存儲，所以最壞的空間複雜度應為 ，而採樣的時間複雜度為 。例如 的地圖，用 32 位整數存儲坐標，那麼最壞情況需要 64MB 存儲空間。

那麼問題是，能否降低空間複雜度的同時，不會增加太多時間複雜度？

我想到一個方法是，先統計每行中像素為 1 的出現次數，然後做成直方圖，再離散採樣這個分佈。常用的離散採樣方法是別名方法（alias method），它採用 的空間存儲預計算的數據，然後可用 時間採樣。

選擇到某一行之後，可以即時從二值圖像生成列表，這需 時間和 空間。那麼，在空間上，這個方法只需用 存儲二值圖像、 的別名方法預計算表及 的時列表，整體空間為 ，而運行時時間複雜度為 。同樣對於 地圖，最大的存儲空間是二值圖像，只需 2MB 空間。

如果可放置物品的位置都是比較連續的，那麼我們可以把每行的表示方法改為區間列表，在每行再用別名方法去抽取區間。如果每列最多有 個區間，那麼空間複雜度為 ，時間複雜度為 。假設 地圖中每行平均有 16 個區間，而別名方法每項需用 16 位元組，那麼大約只需 1MB 空間，又能達到 時間。