Самый быстрый способ получить поразрядный средний байт?

Question

Учитывая, что у меня есть большой набор из n байтов, что является самым быстрым способом генерации байта, который является «средним» или, возможно, «бит-мудрым медианом» этого набора?

В частности, я хочу получить результирующий байт, где каждый бит установлен, если большая часть байтов имеет этот бит.

Пример (с грызет)

Bytes: 
1000 
1111 
1010 

Result: 
1010 

Я уверен, что есть какая-то немного вертел магия, которая поможет мне сделать это, но я не смог найти его до сих пор. До сих пор мои единственные идеи были наивным. Есть идеи?

EDIT: В случае, когда число вхождений бит равно, бит может быть задан произвольно.

EDIT 2: Я использовал байты для примера. Предпочтительно предложенный метод должен содержать байтовые векторы длиной до ~ 128 байтов.

Answer 1

Байт всего 8 бит. Поскольку это достаточно маленькое, вы можете использовать нисходящее базисный вид (LSB первый) стратегия:

// this assumes 0 based indexing with LSB at index 0 
for i := 0 to 7 
    initialize bucket 0 and 1 with 0 
    for j := 0 to N - 1 
    increment bucket[bit i of byte j] 
    bit i of resulting byte = max(bucket[0],bucket[1]) ? 0 : 1 

, что O (8 * N) = O (N) время сложности, которая должна быть быстрой.

P.S .: Вы не указано, что должно произойти, если оба 0 и 1 вхождений равны

Answer 2

Существует немного-вертел так, но это не значит, что довольно (и не особенно быстро). Но я все равно объясню, так как вы спросили, и это интересно.

Идея состоит в том, что вместо того, чтобы удерживать счетчик для каждой позиции бита в целочисленном размере, удерживайте биты счетчиков целыми числами. Поэтому, если вы рассматриваете счетчики как логическую матрицу, каждая строка которой является счетчиком, сохраните столбцы в целых числах. Таким образом, ввод чисел - это странный вид сложения, а не «столько приращений, сколько бит». Как это (не проверено) (добавление в c)

for (int i = 0; i < counter_bits; i++) { 
    counter[i] ^= c; 
    c &= ~counter[i]; // counter & c == ~(counter^c) & c 
} 

А теперь самое интересное: что такое медиана? Ну, если n (количество элементов) - это мощность двух минус одна, а counter - это массив, который достаточно длинный, чтобы выразить n «по вертикали», тогда медиана - это точно значение счетчика «верхнего бита» (там 1 будет появляться всякий раз, когда бит был замечен как минимум (n + 1)/2 раза).

Более интересный случай «в противном случае». Он по-прежнему фиксируется, все, что необходимо, чтобы заставить его работать хорошо, - это инициализировать счетчики с предубеждением, так что самый старший бит будет установлен точно в нужный момент. Например, если n = 5, то счетчики должны быть инициализированы до 1 (по вертикали 1, поэтому счетчик [0] = -1, все остальные счетчики равны 0), поэтому при добавлении 3 единиц он переходит в 4, что является верхним битом в этом случае. Другой пример: если n = 17, то верхний бит должен иметь вес 16, но 9 достаточно, чтобы установить бит в медиане, поэтому счетчики должны быть инициализированы до 7 (так, счетчик [0] = счетчик [1] = счетчик [2] = -1, остальное 0).

Этот подход, очевидно, обобщается на более широкие битвекторы простым способом, поскольку все операции над вещами, которые становятся шире, являются потоковыми битовыми операциями.

---

Пример (только в случае, если кто-то спутать о том, что происходит в этом алгоритме)

Вход:

1000 
1111 
1010 

3 пунктов, 2 необходимы для большинства, мы рассчитываем до 3 макс, поэтому в счете есть только 2 бита (веса 1 и 2), и никакого смещения не требуется.

init: counter = { 0000, 0000 } 
put in 1000 
counter = { 1000, 0000 } 
put in 1111 
counter = { 0111, 1000 } (the leftmost bit carried into the high counter) 
put in 1010 
counter = { 1101, 1010 } (the second bit from the right carried into the high counter) 
result: the upper counter, so 1010 

---

Теперь, в реальном мире, это не так, как я бы это сделать. В зависимости от обстоятельств я мог бы сделать это следующим образом:

У вас есть таблица (или pdep, если она у вас есть), которая отображает байты в «разложенную» версию, например 10010101b -> 0x10010101, и добавляет их (с нормальной дополнение), затем извлечение конечного результата из высоких бит полубайтов (pext, если он у вас есть, в противном случае это сложнее). Уловка смещения все еще работает. Недостаток: работает только для n < 16. Несмотря на этот огромный недостаток, я все еще использовал это в реальной жизни (для двоичных головоломок, чтобы обрезать пространство поиска). Конечно, это все еще работает с «более распространенным», что дает вам более высокий максимум n (например, если положить 8 счетчиков в uin64, то дает n < 256, положив 4 в uint64, дает n < 65536 и т. Д.). Это действительно изоморфно использованию массива, как в ответе LeleDumbo, за исключением того, что массив находится в одном int (фактически, если вы включите распространение до одиннадцати, он станет точно таким же). Это может также масштабироваться до очень больших векторов (просто используйте несколько из этих счетчиков в массиве).

Или: используйте надлежащий SIMD, вместо этого поддельного SIMD. Делает извлечение бит проще (поскольку маска всех верхних бит может быть извлечена). Это даже не требует трюка смещения, потому что вы можете сравнить SIMD. Это также упрощает распространение, так как это не нужно делать с помощью таблицы поиска - транслировать элемент на все полосы, маскировать соответствующий бит в каждой полосе (это удобно игнорирует некоторые детали), сравнивать, а затем вычесть это из count (потому что теперь это -1, когда true, а не 1). Например (не проверено)

vpbroadcastb xmm0, [item] ; put 8bit item in all lanes 
vpand xmm0, [lane_bit_mask] ; { 1, 2, 4, 8, ... 
vpcmpeqb xmm0, [lane_bit_mask] ; -1 if the bit is set 
vpsubb xmm1, xmm0   ; subtract from total 

Это немного расточительно, используя только 8 из 16 (или 32) полос, но она показывает основную идею. Требуется еще несколько усилий для распаковки бит при использовании большего количества дорожек.