什麼時候應該小心使用bitset代替布爾數組？

我正在研究移動電話應用程序，並且看到了提升性能的潛在機會。在整個代碼中，我使用bool數組來跟蹤哪些對象處於活動狀態。例如，我會檢查，看看是否第i個MyObject的是做着積極的以下內容：什麼時候應該小心使用bitset代替布爾數組？

if(activeMyObjects[i]){ // it's active so do something... }

因爲我的對象的最大數量範圍爲[5,20]我想我可以代替activeMyObjects布爾具有單個整數「activeMyObjects」形式的bitset的數組。切換到位集時，實際上可能會降低性能

// check if ith object is active 
if(activeMyObjects & (1 << i)){ // it's active... } 

// activate the ith object 
activeMyObjects |= (1 << i); 

// reset all myObjects to inactive 
activeMyObjects = 0; 

// and so on...

有隨時：那我可以做以下？我使用的語言是c。還要注意這個代碼經常被調用（頻率在30 - 60 Hz範圍內）。

編輯： 另一條信息：該位集有我可以輕鬆地告訴我們，如果任何對象都是活躍在所有的另一個優勢。所以我可以跳過一個循環，通過首先檢查是否（activeMyObjects）來檢查每個項目是否處於活動狀態。當我使用數組時，這是棘手的...我的方法是有一個額外的計數器int，每當MyObject被激活時遞增，每當MyObject被停用時遞減...這種方式我只是檢查是否（activeMyObjectsCount> 0）在我檢查每一個循環之前。

來源

2009-12-07 MrDatabase

根據多久分配一次位組，您可以很容易地最終佔用更多內存與bitset版本。

訪問某個特定位的代碼比訪問完整字節內存的代碼大得多 - 如果只有少數這些數組會被訪問，但它會經常訪問，則會留下更小的空間它喜歡它。

來源

2009-12-07 03:10:12

在程序開始時，位組在堆棧上分配一次。他們訪問非常頻繁。 bitset上的操作是：設置第i位，檢查第i位是否置位，取消第i位，取消所有位。鑑於這個信息，你會建議使用數組或位集？ – MrDatabase 2009-12-07 03:35:04

你真的只需要自己測試一下。我知道它吸收開發時間到一個不確定的價值的東西，但這是非常依賴實施。這真的可以去任何一個方面。這取決於編譯器優化，本地芯片組命令，緩存結構以及CPU /緩存/數據的相對速度。我真的很驚訝，如果這裏有人能夠爲你作出權威的回答，尤其是因爲你沒有列出任何這些變量。 – 2009-12-07 03:49:05

如果它們被分配一次並且經常訪問，它將使用較少的內存來堅持陣列。裝載那一個布爾值就是一條指令 - 而在一個位集的時候，你正在查看三個（加載，移位，掩碼）。在性能方面，您需要對目標硬件上的每個選項進行基準測試，以便了解結果。 – 2009-12-07 03:59:10

沒有。在一天結束時，這是一個簡單的整數移位，與所有賬戶的數組訪問相比，這種移位成本更低。只要保持謹慎，即將bitset轉換爲第三級（可能是active，inactive和undefined），或試圖向每個條目添加數據現在都無需重構。

來源

2009-12-07 03:04:12 BrainCore

此外，如果你曾經有過32個對象，你需要擴大你的位集是一個int數組。在這種情況下，您仍然可以訪問數組條目，但它會節省空間。 – BrainCore 2009-12-07 03:05:50

在大多數平臺上，您不會獲得任何性能。你將節省的是內存佔用。

來源

2009-12-07 03:04:24 jfclavette

如果速度比內存佔用更重要（因爲這是整個移動應用程序），那麼您可以將遮罩存儲在一個數組中，並將它們作爲activeMyObjects遮罩[i]訪問。

來源

2009-12-07 03:21:57 user226080

如果速度很關鍵，那麼使用命名常量而不是掩碼陣列會更好。 – 2009-12-07 03:29:39

我聽說一些PowerPC芯片（不知道它們是否全部是這樣 - 例如參見this question）在執行可變長度的位移時速度很慢，因爲您正在處理(1 << i)指令。所以在這些芯片上，bitset似乎很可能比bool陣列運行速度慢得多。

這很可能不是你的問題，但它是一個有趣的小案例:)

來源

2009-12-07 03:51:44 Peter

什麼時候應該小心使用bitset代替布爾數組？

回答

相關問題