現在的實現是把地圖中所有可以放置物品的點讀到伺服器上的list中,然後隨機。
現在list中一共要存儲幾十萬個點,想問下有什麼更好的實現方式嗎,謝謝。
假設可放置物品的位置為 的二值圖像,當中像素為1表示可放置,而需求是要均勻地採樣像素為 1 的坐標。
現時題主的方法是把可放置的坐標存儲為列表,然後均勻採樣。每個坐標需用 個比特存儲,所以最壞的空間複雜度應為
,而採樣的時間複雜度為
。例如
的地圖,用 32 位整數存儲坐標,那麼最壞情況需要 64MB 存儲空間。
那麼問題是,能否降低空間複雜度的同時,不會增加太多時間複雜度?
我想到一個方法是,先統計每行中像素為 1 的出現次數,然後做成直方圖,再離散採樣這個分佈。常用的離散採樣方法是別名方法(alias method),它採用 的空間存儲預計算的數據,然後可用
時間採樣。
選擇到某一行之後,可以即時從二值圖像生成列表,這需 時間和
空間。那麼,在空間上,這個方法只需用
存儲二值圖像、
的別名方法預計算表及
的時列表,整體空間為
,而運行時時間複雜度為
。同樣對於
地圖,最大的存儲空間是二值圖像,只需 2MB 空間。
如果可放置物品的位置都是比較連續的,那麼我們可以把每行的表示方法改為區間列表,在每行再用別名方法去抽取區間。如果每列最多有 個區間,那麼空間複雜度為
,時間複雜度為
。假設
地圖中每行平均有 16 個區間,而別名方法每項需用 16 位元組,那麼大約只需 1MB 空間,又能達到
時間。