Кстати, почему-то никто не обратил внимание на алгоритмическую "дебильность" CalcNumOfBits.
Сущесвует множество методов быстрого решения этой проблемы — как для общих случаев, так и для разреженных слов. Понятно, что "вживую" вспоминать эти алгоритмы заставлять по меньшей мере глупо (хотя ничего сложного там нет — обычное групповое сложение, в самом просто варианте), но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.
Здравствуйте, Andrew S, Вы писали:
AS>Кстати, почему-то никто не обратил внимание на алгоритмическую "дебильность" CalcNumOfBits. AS>Сущесвует множество методов быстрого решения этой проблемы — как для общих случаев, так и для разреженных слов. Понятно, что "вживую" вспоминать эти алгоритмы заставлять по меньшей мере глупо (хотя ничего сложного там нет — обычное групповое сложение, в самом просто варианте), но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.
AS>>Кстати, почему-то никто не обратил внимание на алгоритмическую "дебильность" CalcNumOfBits. AS>>Сущесвует множество методов быстрого решения этой проблемы — как для общих случаев, так и для разреженных слов. Понятно, что "вживую" вспоминать эти алгоритмы заставлять по меньшей мере глупо (хотя ничего сложного там нет — обычное групповое сложение, в самом просто варианте), но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.
А>не нужно слов — покажите на примере!
Генри Уоррен Младший, страницы 75-76. Учите матчасть.
int pop (unsigned X)
{
X = X - ( (X >> 1) & 0x55555555);
X = (X & 0x33333333) + ((X >> 2) & 0x33333333);
X = (X + (X >> 4)) & 0x0F0F0F0F;
X = X + (X >> 8) ;
X = X + (X>> 16) ;
return X & 0x0000003F;
}
Здравствуйте, Andrew S, Вы писали:
AS>но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.
ИМХО глупо требовать от кандидата писать всякую хрнеь в комментах.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
AS>>но вот в комментах написать, что это просто набросок и настоящая реализация так не должна работать, имхо, стОило.
E>ИМХО глупо требовать от кандидата писать всякую хрнеь в комментах.
Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно.
В общем, понятно, опять адеквата не увидим.
Этот код как минмум не быстрее приведенного мной. Например, на моем А64 — в 2 раза медленее.
LONGLONG l = QueryPerformanceCounter();
for (unsigned i = 0; i < 1024*1024;++i)
{
pop(i);
}
LONGLONG l1 = QueryPerformanceCounter() - l;
l = QueryPerformanceCounter();
for (unsigned j = 0; j < 1024*1024;++j)
{
countOnes(j);
}
LONGLONG l2 = QueryPerformanceCounter() - l;
cout << (unsigned)l1 << endl;
cout << (unsigned)l2 << endl;
// output
23065
42916
Не говоря уже требовании наличия инициализированного не нулями массива (что как минимум увеличивает размер бинарника). Ваш код можно ускорить, если выбирать не char, а unsigned, примерно в 1.5 раза. Но и в этом случае лучше приведенного мной варианта он не стант, а памяти потребует еще больше.
В общем, не стОит считать себя умнее людей, которые алгоритмами оптимизации занимаются профессионально (я имею в виду указанного выше автора, ессно). А почитать указанную книгу как минимум не вредно, а на самом деле — очень полезно.
AS>int pop (unsigned X)
AS>{
AS> X = X - ( (X >> 1) & 0x55555555);
AS> X = (X & 0x33333333) + ((X >> 2) & 0x33333333);
AS> X = (X + (X >> 4)) & 0x0F0F0F0F;
AS> X = X + (X >> 8) ;
AS> X = X + (X>> 16) ;
AS> return X & 0x0000003F;
AS>}
AS>
и что, действительно будет быстрее чем обычный цикл вроде
template <typename T>
unsigned int Bits(T value)
{
unsigned int bits = 0;
for (; value > 0; value >>= 1)
bits += (value & 0x1);
return bits;
}
?
... причем в котором нет привязки к размерности числа
преждевременная оптимизация — корень всех зла... а приведенный мной пример ну НИКАК не тянет на преждевременную пессимизацию %)
AS>>int pop (unsigned X)
AS>>{
AS>> X = X - ( (X >> 1) & 0x55555555);
AS>> X = (X & 0x33333333) + ((X >> 2) & 0x33333333);
AS>> X = (X + (X >> 4)) & 0x0F0F0F0F;
AS>> X = X + (X >> 8) ;
AS>> X = X + (X>> 16) ;
AS>> return X & 0x0000003F;
AS>>}
AS>>
А>и что, действительно будет быстрее чем обычный цикл вроде А>
А>template <typename T>
А>unsigned int Bits(T value)
А>{
А> unsigned int bits = 0;
А> for (; value > 0; value >>= 1)
А> bits += (value & 0x1);
А> return bits;
А>}
А>
А>?
Да. В 5 раз, для unsigned 32 bit.
22866 // pop
42549 // countones
106870 // bits
А>... причем в котором нет привязки к размерности числа
Из указанного примера можно при желании сделать безразмерный вариант при помощи шаблонов — там вся мысль заключается в групповом сложении. Причем, сложность будет логарифмическая, т.е. если, например, размерность будет больше в 2 раза, вычисление не будет выполняться в 2 раза дольше в отличие от 2-х приведенных тут вариантов.
А>преждевременная оптимизация — корень всех зла... а приведенный мной пример ну НИКАК не тянет на преждевременную пессимизацию %)
Да-да, это любимая фраза всех лентяев и бездельников В данном случае существует уже _готовые_ алгоритмы, которые надо просто применить — т.е. стоимость r&d == 0. Так что это именно преждевременная пессимизация.
Здравствуйте, Andrew S, Вы писали:
AS>Этот код как минмум не быстрее приведенного мной. Например, на моем А64 — в 2 раза медленее.
ICC 10
P4 630
Колво циклов увеличил до 1024^3 — бо выполняется слишком быстро
15318209580
8983055617
AS>В общем, не стОит считать себя умнее людей, которые алгоритмами оптимизации занимаются профессионально (я имею в виду указанного выше автора, ессно). А почитать указанную книгу как минимум не вредно, а на самом деле — очень полезно.
pop
00031 8b ee mov ebp, esi ;.\test.cpp:39.6
00033 d1 ed shr ebp, 1 ;.\test.cpp:39.6
00035 81 e5 55 55 55
55 and ebp, 1431655765 ;.\test.cpp:39.6
$LN9:
0003b f7 dd neg ebp ;.\test.cpp:39.10
0003d 03 ee add ebp, esi ;.\test.cpp:39.10
$LN11:
0003f 8b c5 mov eax, ebp ;.\test.cpp:39.6
00041 25 33 33 33 33 and eax, 858993459 ;.\test.cpp:39.6
00046 c1 ed 02 shr ebp, 2 ;.\test.cpp:39.6
00049 81 e5 33 33 33
33 and ebp, 858993459 ;.\test.cpp:39.6
0004f 03 c5 add eax, ebp ;.\test.cpp:39.6
00051 8b f8 mov edi, eax ;.\test.cpp:39.6
00053 c1 ef 04 shr edi, 4 ;.\test.cpp:39.6
00056 03 c7 add eax, edi ;.\test.cpp:39.6
00058 25 0f 0f 0f 0f and eax, 252645135 ;.\test.cpp:39.6
0005d 8b e8 mov ebp, eax ;.\test.cpp:39.6
0005f c1 ed 08 shr ebp, 8 ;.\test.cpp:39.6
00062 03 c5 add eax, ebp ;.\test.cpp:39.6
00064 8b e8 mov ebp, eax ;.\test.cpp:39.6
00066 c1 ed 10 shr ebp, 16 ;.\test.cpp:39.6
00069 03 c5 add eax, ebp ;.\test.cpp:39.6
0006b 83 e0 3f and eax, 63 ;.\test.cpp:39.6
AS>Из указанного примера можно при желании сделать безразмерный вариант при помощи шаблонов — там вся мысль заключается в групповом сложении. Причем, сложность будет логарифмическая, т.е. если, например, размерность будет больше в 2 раза, вычисление не будет выполняться в 2 раза дольше в отличие от 2-х приведенных тут вариантов.
AS>>Этот код как минмум не быстрее приведенного мной. Например, на моем А64 — в 2 раза медленее.
CC>ICC 10 CC>P4 630
CC>Колво циклов увеличил до 1024^3 — бо выполняется слишком быстро
CC>15318209580 CC>8983055617
AS>>В общем, не стОит считать себя умнее людей, которые алгоритмами оптимизации занимаются профессионально (я имею в виду указанного выше автора, ессно). А почитать указанную книгу как минимум не вредно, а на самом деле — очень полезно. CC>
Да пожалуйста, тоже увеличил.
VC6
23384774
43100993
VC7.1
17996589
20148363
Итого — у меня мой варианта _всегда_ быстрее. Вариант Романа, к сожалению, имеет довольно мало средств для оптимизации — тут практически не могут спариваться команды, да и выборка из памяти дело тормознутое.
Но как собственно VC7 смог так улучшить вариант 2? Посмотрим.
Как мы видим, тут просто развернули цикл (пачками по 4). Полагаю, IC сделал примерно то же, поскольку больше увеличить производительность в данном варианте нечем (только работать с 32-х битным массивом, но там прибавка не будет большой).
Т.о., сравнение в данном случае получается не слишком некорректным (а точнее, вообще некорретным) — в реальном применении цикл гораздо сложнее и развернуть его таким образом не получится. Правильнее всего в смысле теста поступает VC6 — он тупо компилит то, что ему написали
AS>>Из указанного примера можно при желании сделать безразмерный вариант при помощи шаблонов — там вся мысль заключается в групповом сложении. Причем, сложность будет логарифмическая, т.е. если, например, размерность будет больше в 2 раза, вычисление не будет выполняться в 2 раза дольше в отличие от 2-х приведенных тут вариантов.
А>будьте любезны — уж очень хочется заценить
Что за народ пошел — все только просят привести решение, а подумать самим лень
В общем, даже и не собираюсь — у меня полно других дел, помимо изобретательств никому не нужных шаблонов. Если вам действительно требуется такая функциональность — вы и делайте, где взять алгоритм и объяснение его работы я уже сказал. Из алгоритма возможность его реализации для любых 2^n битных значений вытекает очень явно
Здравствуйте, Andrew S, Вы писали:
AS>Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно.
1) ИМХО, не важно знает ли кандидат такой алгоритм или нет. Мне лично было бы вполне достаточно, если бы на вопрос "А как это ускорить" он бы ответил что-то вроде: "Вообще-то можно по индексируемой байтом таблице суммировать, или может стоит поискать эффективный алгоритм в интернете. Если это действительно надо ускорять"
2) В любом случе ожидать, что кандидат напишет к своему коду коммент: "можно и быстрее, но я забыл точно как именно" по крайней мере странно...
AS>В общем, понятно, опять адеквата не увидим.
В цело м перед собеседованием всё-таки стоит задаться вопросом чего ты хочешь узнать о кандидате в результате собеседорвания, и вообще чего именно ты от него хочешь...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Andrew S, Вы писали:
AS>>>Генри Уоррен Младший, страницы 75-76. Учите матчасть. RO>>Ужас. AS>Нет. Ужас то, что привели вы, почему — см. ниже. Хотя даже если был бы приведен такой вариант — уже значительно лучше цикла. RO>>unsigned char const ones[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, . . . };
AS>Этот код как минмум не быстрее приведенного мной. Например, на моем А64 — в 2 раза медленее.
AS>// output AS>23065 AS>42916 AS>Не говоря уже требовании наличия инициализированного не нулями массива (что как минимум увеличивает размер бинарника). Ваш код можно ускорить, если выбирать не char, а unsigned, примерно в 1.5 раза. Но и в этом случае лучше приведенного мной варианта он не стант, а памяти потребует еще больше. AS>В общем, не стОит считать себя умнее людей, которые алгоритмами оптимизации занимаются профессионально (я имею в виду указанного выше автора, ессно). А почитать указанную книгу как минимум не вредно, а на самом деле — очень полезно.
О ужас! 256 байт.
Мой код имеет премущество совсем в другом. По нему понятно, что он делает. Если допустить ошибку в твоем, то можно доолго ее искать. Ну, и premature optimization…
По поводу того, что мой код якобы не имеет возможностей для оптимизации компилятором:
unsigned countOnesSmartly(unsigned X)
{
X = X - ( (X >> 1) & 0x55555555);
X = (X & 0x33333333) + ((X >> 2) & 0x33333333);
X = (X + (X >> 4)) & 0x0F0F0F0F;
X = X + (X >> 8) ;
X = X + (X>> 16) ;
return X & 0x0000003F;
}
unsigned countOnesLamely(unsigned x)
{
unsigned res = 0;
while(x)
{
x &= x - 1;
++res;
}
return res;
}
class OnesCounter
{
public:
OnesCounter()
{
for(unsigned i = 0; i < 65536; ++i)
{
table[i] = countOnesLamely(i);
}
}
unsigned operator()(unsigned x) const
{
return table[x & 0xFFFF] + table[x >> 16];
}
private:
unsigned table[65536];
};
template <class F>
inline LONGLONG getLargeInt(F func)
{
LARGE_INTEGER tmp;
func(&tmp);
return tmp.QuadPart;
}
template <class It, class F>
LONGLONG benchmark(It first, It last, F f, unsigned& dummy)
{
LONGLONG const t1 = getLargeInt(QueryPerformanceCounter);
while(first != last)
{
dummy += f(*first++);
}
LONGLONG const t2 = getLargeInt(QueryPerformanceCounter);
return t2 - t1;
}
int main()
{
unsigned const sampleSize = 0x08000000;
std::vector<unsigned> data(sampleSize);
// Ваши с CreatorCray варианты дают мне поблажку, позволяя менеджеру кеша загружать таблицу по частям.
std::generate(data.begin(), data.end(), boost::bind(boost::uniform_int<unsigned>(0u, 0xFFFFFFFFu), boost::mt19937()));
unsigned dummy = 0;
LONGLONG const tLame = benchmark(data.begin(), data.end(), countOnesLamely, dummy);
LONGLONG const tSmart = benchmark(data.begin(), data.end(), countOnesSmartly, dummy);
LONGLONG const tTable = benchmark(data.begin(), data.end(), OnesCounter(), dummy);
std::cout << tLame << std::endl;
std::cout << tSmart << std::endl;
std::cout << tTable << std::endl;
std::cout << (dummy == 42 ? ' ' : '\t') << std::endl;
}
Ага, и так на каждый чих? Ну да, верно, поэтому и получаем то, что получаем — гигантские и на 99% бесполезные исполняемые модули...
RO>Мой код имеет премущество совсем в другом. По нему понятно, что он делает. Если допустить ошибку в твоем, то можно доолго ее искать. Ну, и premature optimization…
Тут я согласен. Для этих целей надо просто привести начальный (т.е. цикл со сдвигом) код в комментах функции, либо краткое описание алгоритма — он действительно очень прост.
А сампл.. Ну да, действительно, тут получалась последовательная выборка из таблица, что VC 71 заметил и "наоптимизировал".
RO>По поводу того, что мой код якобы не имеет возможностей для оптимизации компилятором:
\code skipped\
Ну, это уже совсем не весело — 256 кб пустоты для такой мелкой функции. Почему бы тогда уж 4 гб таблицу не сделать?
А по поводу результатов — для начала надо убедиться, что в данном случае сам инструмент измерений не вносит большой погрешности, как в моем варианте с VC71, когда раскручивался цикл. Т.е. смотреть нативный код — надо добиваться, чтобы _всем_ вариантам были предоставлены одинаковые условия. Например, для меня совсем не очевидно, что 256 кб таблица будет быстрее 1 кб — тут уже проблемы с кешем даже второго уровня начнутся.
А нативного кода я тут не приметил
Впрочем, я посмотрел и сам — ну и конечно, там оно и есть, ведь Роман для своего случая передает не просто указатель на функцию (который, ессно, не встраивается), а функтор (который, как раз наоборот, встраивается почти всегда).
Хотелось бы думать, что это было сделано непреднамеренно, хотя использование функтора _только_ для своего случая — странно.
Или VC8 для всех случае генерит идентичный код? Если нет — тогда ценность этих измерений == 0...
AS>>Речь идет о знании алгоритмов (не их реализации, а вообще существовании), а не "хрени в комментах". Из моего сообщения это очевидно. E>1) ИМХО, не важно знает ли кандидат такой алгоритм или нет. Мне лично было бы вполне достаточно, если бы на вопрос "А как это ускорить" он бы ответил что-то вроде: "Вообще-то можно по индексируемой байтом таблице суммировать, или может стоит поискать эффективный алгоритм в интернете. Если это действительно надо ускорять"
Опять передергиваете. Перечитайте то, на что отвечаете, нужное выделено.
E>2) В любом случе ожидать, что кандидат напишет к своему коду коммент: "можно и быстрее, но я забыл точно как именно" по крайней мере странно...
Да при чем тут комменты — смысл в том, что надо понимать, что это далеко не оптимальная реализация. Судя по коду (то, что например, это шаблонная функция), кандидат об этом не задумывался.
AS>>В общем, понятно, опять адеквата не увидим. E>В цело м перед собеседованием всё-таки стоит задаться вопросом чего ты хочешь узнать о кандидате в результате собеседорвания, и вообще чего именно ты от него хочешь...
Это вопрос не ко мне, а к топиккастеру. Хотя за ту сумму, что он озвучил, откомментировав ее как "средняя по городу вообще (а не для IT)" — думаю, вполне нормально. Хотя, конечно, задания таковы, что по ним определнно сказать что-либо сложно.
Здравствуйте, Andrew S, Вы писали:
AS>Впрочем, я посмотрел и сам — ну и конечно, там оно и есть, ведь Роман для своего случая передает не просто указатель на функцию (который, ессно, не встраивается), а функтор (который, как раз наоборот, встраивается почти всегда).
Почему компиляторы не всегда встраивают вызовы функций по одному и тому же указателю — неясно. Надеюсь, исправятся.
AS>Хотелось бы думать, что это было сделано непреднамеренно, хотя использование функтора _только_ для своего случая — странно. AS>Или VC8 для всех случае генерит идентичный код? Если нет — тогда ценность этих измерений == 0...
Там потому функтор, что он же должен таблицу проинициализировать.
А вообще, засунул бы функции в классы и проверил бы сам.
Вывод: твою функцию в топку, мою функцию в топку, использовать std::bitset::count, пока не выяснится, что программа проводит в ней непристойно много времени.
Перекуём баги на фичи!
