Вроде бы простая задача: посчитать количество единичек в числе.
Я знаю четыре способа её решения: "наивный" метод (пробежаться по всем битам), встроенная в Gcc функция __builtin_popcount, предподсчёт для всех чисел < 0xFFFF и метод за log log X.
Написал тестовую программу (с long long'ами): http://pastebin.com/vTUPkK07
Результаты на Core 2 Duo E4500 2.2 GHz (10^7 long long'ов):
__builtin_popcount: 0.211
countPrecalc: 0.129
countLoglog: 0.269
countSimple: 1.240
Самым быстрым оказался способ с предподсчётом - он делает наивный метод в 10 раз, а метод за loglog и встроенную функцию - в два.
Что любопытно, если попытаться сократить количество операций в предподсчёте (не до 2^16, а до 2^22 - чтобы было 3 сложения вместо четырёх), скорость резко падает до 0.6 - т.е. уже её делают в два раза встроенная функция и loglog.
UPD: при замене int cnt[] на char cnt[] и компиляциис -O2 скорость countPrecalc возврастает в два раза. При компиляции с -O3 - еще в два - до 0.048.
Я знаю четыре способа её решения: "наивный" метод (пробежаться по всем битам), встроенная в Gcc функция __builtin_popcount, предподсчёт для всех чисел < 0xFFFF и метод за log log X.
Написал тестовую программу (с long long'ами): http://pastebin.com/vTUPkK07
Результаты на Core 2 Duo E4500 2.2 GHz (10^7 long long'ов):
__builtin_popcount: 0.211
countPrecalc: 0.129
countLoglog: 0.269
countSimple: 1.240
Самым быстрым оказался способ с предподсчётом - он делает наивный метод в 10 раз, а метод за loglog и встроенную функцию - в два.
Что любопытно, если попытаться сократить количество операций в предподсчёте (не до 2^16, а до 2^22 - чтобы было 3 сложения вместо четырёх), скорость резко падает до 0.6 - т.е. уже её делают в два раза встроенная функция и loglog.
UPD: при замене int cnt[] на char cnt[] и компиляциис -O2 скорость countPrecalc возврастает в два раза. При компиляции с -O3 - еще в два - до 0.048.
Просто с -O2 — в полтора.
А -O3 скорость вырастает до 0.048.
Если увеличить размер чисел, то log log n будет укатывать предпросчет.
Вот еще козырный алгоритм, считает за время, равное количеству единиц в числе. То есть в среднем случае за log(n). Идея в том, чтобы сбрасывать последнюю единицу в числе до тех пор, пока оно не станет нулем.
ans = 0;
while( x ) {
++ ans;
x = ( ( x - 1 ) & x );
}
Нет, длинка не подойдет, потому что нам надо, чтобы операции and и rshift выполнялись за константу.
Но, допустим, если бы были 256-ти разрядные машиы, на них мне кажется log log n бы уже обшустрил бы предпросчет, потому что предпросчет бы стал медленнее в четыре раза, а log log n бы медленнее почти не стал.