在一個巨大的位圖

的面試問題，對於第一套位搜索：在一個巨大的位圖

在停車位，可容納萬人的汽車，你需要找到一個免費停車位。在插槽可能的位置沒有條件，即，停車場可以有多個入口並且在入口附近找到一個插槽等等，並不重要。問題是應該使用什麼樣的數據結構以及各種操作的複雜性。

我建議使用一個百萬比特的數組，因爲0/1用於被佔用/空閒的時隙，所以爲了找到空閒的地方，將問題轉換爲尋找第一組比特。不要假設有多少輛汽車等等，即位陣列可能稀疏或密集。

什麼是在一個巨大的位圖中找到一個位的最快方法？作爲方案，我確實建議使用二進制搜索+有效的ffs（）。

來源

2012-07-20 sandeep

如果我們不能假設有關數組內容的任何內容，那麼二分查找在這裏不會有幫助;你將不得不使用線性搜索。 – 2012-07-20 14:59:44

在c中，可以遍歷64位組中的插槽（使用uint64_t），並檢查第一個非零值。 – 2012-07-20 15:00:19

我想在Fenwick樹（二進制索引樹，BIT）上進行二分搜索。更新操作需要O（log n）。搜索第一組位是O（（log n）^ 2） – nhahtdh 2012-07-20 15:01:10

你可以這樣說：

存儲在一個變量的最後一個空閒時隙的索引，然後尋找下一個不掃描從一開始的位圖，但這個值。

如果您需要釋放某個插槽，請將其分配給最後一個索引。

std::vector<bool>可以是你的位陣列，所以你不需要自己處理位（bool的內部被打包成int）。

可以引入一個mip-mapped結構：

``std::vector<bool>`` Bitmap; 
``std::vector<bool>`` Bitmap2; // half-sized 
``std::vector<bool>`` Bitmap4; // 1/4 
``std::vector<bool>`` Bitmap8; // 1/8 
// etc

在上層陣列的free值對應於其中下部水平陣列有任何空閒時隙的情況。您可以使用二進制搜索來遍歷此結構。

來源

2012-07-20 15:17:05

除非您跟蹤填充率或類似情況，否則mip-mapping將非常昂貴。否則，您必須檢查每次傳球時是否更新其他關卡。 – MvG 2012-07-20 16:12:38

Mip-mapping會增加約33％的內存開銷，並允許在線性時間內進行搜索。所以它是一個折衷。 – 2012-07-20 16:14:22

一百萬個32位整數需要大約4MB的內存。所以我會說你保留一個免費插槽列表。每當一輛汽車進入時，你從列表中取出一個項目並分配它。每當一輛汽車離開時，您將釋放的插槽號碼放入列表中。因爲你只能操縱列表的末尾（所以這實際上用作stack或LIFO結構），這可以爲您找到最佳的O（1）性能，既可以找到空閒插槽，也可以返回一個自由狀態的插槽。如果您在原始塊內存的情況下執行此操作，則需要一個指示列表當前結束的指針。找到一個插槽會減少該指針並返回其值。返回一個槽分配給指針並在之後遞增。

如果您稍後決定添加其他要求，您可以對數據進行一些操作，例如，把它變成heap。用0/1位的大地圖，這種擴展是不可能的。

來源

2012-07-20 15:19:06 MvG

嘿，我喜歡這樣的答案。我認爲大多數人 - 包括我自己 - 往往會忘記現代計算機是多麼強大有力。跟蹤幾百萬的整數？呃，我的手機可以做到這一點，甚至沒有註冊負載！ – 2012-07-20 18:18:52

@LexiR，即使在15歲的機器上，這種方法也能很好地工作。大多數列表可能會交換到磁盤，但單個活動端可以隨時在物理內存中使用。您只需要一個比軟盤大的後備存儲和一個能夠交換內存的操作系統。儘管如此，嚴格限制內存的微控制器也許是另一回事。 – MvG 2012-07-20 18:26:22

在一個巨大的位圖

回答

相關問題