Я просто хочу найти функцию fastest set bits в php.
Например, 0010101 => 3, 00011110 => 4
Я видел, что есть хороший алгоритм, который можно реализовать в c ++. Как подсчитать количество заданных битов в 32-битовом целое?
Есть ли встроенная функция php или самая быстрая пользовательская функция?
Вы можете попробовать применить маску с двоичным И, и использовать сдвиг для тестирования бит один за другим, используя цикл, который будет повторяться 32 раза.
function getBitCount($value) { $count = 0; while($value) { $count += ($value & 1); $value = $value >> 1; } return $count; }вfunction getBitCount($value) { $count = 0; while($value) { $count += ($value & 1); $value = $value >> 1; } return $count; }
Вы также можете легко разместить свою функцию в стиле PHP
function NumberOfSetBits($v) { $c = $v - (($v >> 1) & 0x55555555); $c = (($c >> 2) & 0x33333333) + ($c & 0x33333333); $c = (($c >> 4) + $c) & 0x0F0F0F0F; $c = (($c >> 8) + $c) & 0x00FF00FF; $c = (($c >> 16) + $c) & 0x0000FFFF; return $c; }
Мой контрольный код
start_benchmark(); for ($i = 0; $i < 1000000; $i++) { getBitCount($i); } end_benchmark(); start_benchmark(); for ($i = 0; $i < 1000000; $i++) { NumberOfSetBits($i); } end_benchmark(); start_benchmark(); for ($i = 0; $i < 1000000; $i++) { substr_count(decbin($i), '1'); } end_benchmark();
Результат бенчмаркинга:
benchmark (NumberOfSetBits ()): 1.429042 миллисекунды
benchmark (substr_count ()): 1.672635 миллисекунды
benchmark (getBitCount ()): 10.464981 миллисекунды
Я думаю, что NumberOfSetBits () и substr_count () являются лучшими. Благодарю.
Я мог бы выяснить несколько способов, но не уверен, какой из них был бы самым быстрым:
PS: если вы начинаете с целого числа, эти примеры будут связаны с использованием функции decbin ().
Существует множество других способов; но для десятичного 32-битного целого числа, NumberOfSetBits , безусловно, самый быстрый.
Недавно я наткнулся на алгоритм Брайана Кернигана , который имеет O(log(n)) а не большинство других, имеющих O(n) . Я не знаю, почему здесь не так быстро. но он по-прежнему имеет измеримое преимущество перед всеми другими неспецифическими функциями.
Конечно, ничто не может бить NumberOfSetBits с помощью O(1) .
мои контрольные показатели:
function getBitCount($value) { $count = 0; while($value) { $count += ($value & 1); $value = $value >> 1; } return $count; } function getBitCount2($value) { $count = 0; while($value) { if ($value & 1)$count++; $value >>= 1; } return $count; } // if() instead of +=; >>=1 instead of assignment: sometimes slower, sometimes faster function getBitCount2a($value) { for($count = 0;$value;$value >>= 1) if($value & 1)$count ++; return $count; } // for instead of while: sometimes slower, sometimes faster function getBitCount3($value) { for($i=1,$count=0;$i;$i<<=1) if($value&$i)$count++; return $count; } // shifting the mask: incredibly slow (always shifts all bits) function getBitCount3a($value) { for($i=1,$count=0;$i;$i<<=1) !($value&$i) ?: $count++; return $count; } // with ternary instead of if: even slower function NumberOfSetBits($v) { // longest (in source code bytes), but fastest $c = $v - (($v >> 1) & 0x55555555); $c = (($c >> 2) & 0x33333333) + ($c & 0x33333333); $c = (($c >> 4) + $c) & 0x0F0F0F0F; $c = (($c >> 8) + $c) & 0x00FF00FF; $c = (($c >> 16) + $c) & 0x0000FFFF; return $c; } function bitsByPregReplace($n) { return strlen(preg_replace('_0_','',decbin($n))); } function bitsByNegPregReplace($n) { return strlen(preg_replace('/[^1]/','',decbin($n))); } function bitsByPregMatchAll($n) { return preg_match_all('/1/',decbin($n)); } function bitsBySubstr($i) { return substr_count(decbin($i), '1'); } function bitsBySubstrInt($i) { return substr_count(decbin($i), 1); } // shortest (in source code bytes) function bitsByCountChars($n){ return count_chars(decbin($n))[49]; } // slowest by far function bitsByCountChars1($n) { return count_chars(decbin($n),1)[49]; } // throws a notice for $n=0 function Kernighan($n) { for(;$n;$c++)$n&=$n-1;return$c; } // Brian Kernighan's Algorithm function benchmark($function) { gc_collect_cycles(); $t0=microtime(); for($i=1e6;$i--;) $function($i); $t1=microtime(); $t0=explode(' ', $t0); $t1=explode(' ', $t1); echo ($t1[0]-$t0[0])+($t1[1]-$t0[1]), " s\t$function\n"; } benchmark('getBitCount'); benchmark('getBitCount2'); benchmark('getBitCount2a'); benchmark('getBitCount3'); benchmark('getBitCount3a'); benchmark('NumberOfSetBits'); benchmark('bitsBySubstr'); benchmark('bitsBySubstrInt'); benchmark('bitsByPregReplace'); benchmark('bitsByPregMatchAll'); benchmark('bitsByCountChars'); benchmark('bitsByCountChars1'); benchmark('decbin');
Результаты banchmark (отсортировано)
> php count-bits.php 2.286831 s decbin 1.364934 s NumberOfSetBits 3.241821 s Kernighan 3.498779 s bitsBySubstr* 3.582412 s getBitCount2a 3.614841 s getBitCount2 3.751102 s getBitCount 3.769621 s bitsBySubstrInt* 5.806785 s bitsByPregMatchAll* 5.748319 s bitsByCountChars1* 6.350801 s bitsByNegPregReplace* 6.615289 s bitsByPregReplace* 13.863838 s getBitCount3 16.39626 s getBitCount3a 19.304038 s bitsByCountChars*
Это числа из одного из моих запусков (с PHP 7.0.22); другие показывали разные порядки в группе за 3,5 секунды. Я могу сказать, что на моей машине четыре из этих пяти довольно равны, а bitsBySubstrInt всегда немного медленнее из-за типов.
Для большинства других способов требуется decbin (который в основном занимает больше времени, чем фактический подсчет, я отметил их * в результатах тестов); только BitsBySubstr бы к победителю без этой ножки гемми.
Мне кажется, что вы можете сделать count_chars 3 раза быстрее, ограничив его только существующими символами. Кажется, что индексирование массива требует довольно много времени.
редактировать:
preg_replace версия preg_replace preg_match_all