查找陣列中指定索引之前最近使用過的索引（快速）

Question

此問題與Array of pairs of 3 bit elements
此數組有52對（約40字節），我想在指定的一對之前找到第一對，它的值不同於0（使用對）。 顯而易見的解決方案是檢查每對<而不是這個（從右到左掃描），但如果有很多未使用的對（設置爲0），這看起來效率很低。

該圖像可以更好地解釋的情況：

雙人0,1和51被使用。
我想在51之前找到第一個使用的對（這裏是1）。

我嘗試的技巧，比如

if(*((int *)&array[arrayPos]) == 0) { 
    arrayPos -= sizeof(int); 
    pairPos -= ??? 
} 

這裏的問題是，從pairPos減去並非如此簡單，因爲6位/對的，所以我有一個查找表結束基於之間的一些關係pairPos and arrayPos，所有這些使得解決方案的表現像微不足道。

有什麼方法可以使查找速度更快？另一個問題是，只有1個未使用的字節...也許我可以爲另外4個空間創建空間。如果至少有7個我可以使用該數組的位圖，並且跳過未使用的對會快得多。

Answer 1

我發現最好的解決辦法是：
1.使項目1個字節（不超過6位前） - 感謝Skizz
2.使用位圖，看看哪些項目是最近的左側。這要比用djna描述的技術快得多。

速度的改進是令人印象深刻：
在一個測試用例 ，從13S現在6.5s
是在一個又一個，從7.4S到3.6s
性能已經翻了一番：d再次

感謝你的答案！

Answer 2

存在針對搜索位數組的處理器特定指令。這些可以作爲編譯器內部函數提供。許多Linux文件系統廣泛使用這些文件系統。

__builtin_ffs（）是GCC中的一個。

ffsll（）可能是POSIX，儘管直到現在我還沒有聽說過。

Answer 3

你能說一下表示空對的相鄰字節值嗎？

我想建議看看字節而不是位。

任何給定的字節，如果它是一對空的6位字符的左手貢獻者，必須適合一個特定的位掩碼，其值取決於他的位置。 ?? ?? 00 00還是?? 00 00 00或其他。您可以將每個字節依次視爲最左邊的字節。可以使用哪個掩碼的簡單查找表。

因此，我們實際上並沒有在考慮它們之前拔出6位字符。

我們可以做得更好嗎，丟棄了一個字節作爲候選人，我們現在可以跳過一個離開嗎？

在我們的掩碼是00 00 00 00的情況下，如果失敗了，那麼我們的鄰居在左邊，如果第一位被設置，是。

這是否真的讓事情更快？

Answer 4

按組處理6位值。

您可以在32位字中使用5個值的組，這會浪費2位或大約7％的空間。如果一個單詞中的所有值都是0，那麼這個單詞是零，因此找到一個非空單詞很快，然後檢查該單詞中的5個值。

如果你不能忍受一點浪費的空間，使用96位組，其中96是6和32的最小公倍數。將16位16位值分成三個32位字。