все понятно, ты в последних формулах использовал логарифм с основанием 2, хотя по HyperLogLog там просто log, и методом проб между основаниями 10 и e, правильные ответы дает с основанием e if (E <= 5/2 * m)
{
var V = 0; for (var i = 0; i < m; ++i) if (M[i] == 0) ++V;
if (V > 0) E = m * Math.log(m / V);
}
else if (E > 1/30 * pow_2_32) E = -pow_2_32 * Math.log(1 - E / pow_2_32);
а откуда такие формулы? может в них ошибка?
и еще, по ссылке «мэд скилзы» стандартная ошибка определена через 1.3, а не 1.04, и даже с какими-то коррекциями 1.05. И еще смущает подсчет alpha_m.
хочется разобраться, ибо мне помог бы этот алгоритм
Еще не забываем, что выкидывать исключение надо в действительно исключительной ситуации для обработки ошибок, а не просто ради быстрого выхода из кучи вложенностей
есть 2 вида реализации работы с исключениями:
— zero cost, по предгенеренным таблицам, большинство нынешних компиляторов по умолчанию использует этот вариант
— динамический
все performance issue исследованы и описаны в «Technical Report on C++ Performance» public.research.att.com/~bs/performanceTR.pdf
можно прочитать и побороть свою throwФобию
Да зря вы смеетесь над циклом для достижения Дао, я почти так делаю (я еще добавляю присвоение в некую переменную через xor, который возвращается из функции, чтобы компилятор не убрал код совсем) для прогрева данных после мапирования их из диска, т.к. таких областей я мапирую много, а последовательное чтение по диску лучше чем хаотичное, когда все эти области начнут считываться.
Тот же код может применяться для прогрева кеша определенной областью данных из памяти.
установка _SECURE_SCL в 0, affinity на то или иное ядро на разных прогонах немного снизил расхождения, но они не исчезли.
размер контейнеров = 10000 элементов (чтобы меньше влияли кешмисы и пейджфолты), 100000 прокруток прохода по контейнеру.
пример тяжелого итератора, где лучше писать префиксный: у меня есть код итерации слиянием по множеству отсортированных массивов уникальных элементов сразу, и итератор на каждом шаге дает перечень индексов идентичных элементов в различных массивах, и его копирование будет сложностью O(m) где m — ичсло массивов на входе.
Андрей, я специально протестировал для других видов контейнеров для константных и неконстантных итераторов, постфиксный и префиксный итераторы. И результаты показывают, что разницы почти нет, кроме постфиксного ++ у константного итератора: std::list на 1-2% больше, std::map на 5-6% больше,.
Удивительные результаты показывает std::multimap — префиксный на 12-13% больше постфиксного! Неожиданно? Да!
Идем дальше: std::set показывает, что постфиксные++ для двух видов итераторов константный и некостантный на 15-16% и 10% дороже чем префиксный, соответственно. Для std::multiset постфиксный ++ константного итератора проигрывает на 2-3%, и для неконстантного, наоборот, префиксный проигрывает на 11%.
Но нельзя забывать, что помимо стандартных контейнорв, разработчики которых постарались на славу, и хвала писателям компиляторов, которые много что оптимизируют, остается некоторая ниша, где могут появиться деградация производительности. Где-то оно мало проявляется (map, set), а где-то может проявиться больше, если объект итератора будет сложным и объемным в памяти.
Как говорится, преждевременная оптимизация это зло.
Но большее зло писать код, который не говорит сам за себя, что оно делает, что составляет некоторую культуру написания кода. Там где нет нужды в постфиксном ++, стоит писать префиксный, что дает знание читающему чужой код понимание, для чего этот кусок был написан (просьба не сводить к простому примеру с for). Эт также важно, как и важно применять правильные *_cast вместо C-like кастинга, что дает понимание, что хотел сделать программист.
Да, с этой точки зрения в вашем продукте нет нужды делать такие проверки, и не потому, что в основных итераторах нет разницы, а в некоторых творятся чудеса. А потому, что культура кода вещь немного из другой области, хоть и может проверяться статическими анализаторами.
>> P.S. Еще раз хочу поблагодарить всех кто принял участие в обсуждении топика «Собираю страшненькое от программистов» и поделился примерами. Многое со временем войдет в PVS-Studio. Спасибо!
а в связи с этим, бесплатный community edition будет??))
2. у меня 3 ящика — на мейле (9лет), яндексе (6лет), гмейле(3года). из них самой большой объем спама на гмейле. и при этом нормальные письма частенько неправильно распознаются спамом. потом мейл, и чище яндекс
if (E <= 5/2 * m)
{
var V = 0; for (var i = 0; i < m; ++i) if (M[i] == 0) ++V;
if (V > 0) E = m * Math.log(m / V);
}
else if (E > 1/30 * pow_2_32) E = -pow_2_32 * Math.log(1 - E / pow_2_32);
и еще, по ссылке «мэд скилзы» стандартная ошибка определена через 1.3, а не 1.04, и даже с какими-то коррекциями 1.05. И еще смущает подсчет alpha_m.
хочется разобраться, ибо мне помог бы этот алгоритм
var log_log = HyperLogLog(0.01);
var log_log = HyperLogLog(0.001);
упорно получаю ошибку 44%
чем это объясняется?
www.open-std.org/jtc1/sc22/wg21/docs/18015.html
— zero cost, по предгенеренным таблицам, большинство нынешних компиляторов по умолчанию использует этот вариант
— динамический
все performance issue исследованы и описаны в «Technical Report on C++ Performance»
public.research.att.com/~bs/performanceTR.pdf
можно прочитать и побороть свою throwФобию
Тот же код может применяться для прогрева кеша определенной областью данных из памяти.
размер контейнеров = 10000 элементов (чтобы меньше влияли кешмисы и пейджфолты), 100000 прокруток прохода по контейнеру.
пример тяжелого итератора, где лучше писать префиксный: у меня есть код итерации слиянием по множеству отсортированных массивов уникальных элементов сразу, и итератор на каждом шаге дает перечень индексов идентичных элементов в различных массивах, и его копирование будет сложностью O(m) где m — ичсло массивов на входе.
Удивительные результаты показывает std::multimap — префиксный на 12-13% больше постфиксного! Неожиданно? Да!
Идем дальше: std::set показывает, что постфиксные++ для двух видов итераторов константный и некостантный на 15-16% и 10% дороже чем префиксный, соответственно. Для std::multiset постфиксный ++ константного итератора проигрывает на 2-3%, и для неконстантного, наоборот, префиксный проигрывает на 11%.
Но нельзя забывать, что помимо стандартных контейнорв, разработчики которых постарались на славу, и хвала писателям компиляторов, которые много что оптимизируют, остается некоторая ниша, где могут появиться деградация производительности. Где-то оно мало проявляется (map, set), а где-то может проявиться больше, если объект итератора будет сложным и объемным в памяти.
Как говорится, преждевременная оптимизация это зло.
Но большее зло писать код, который не говорит сам за себя, что оно делает, что составляет некоторую культуру написания кода. Там где нет нужды в постфиксном ++, стоит писать префиксный, что дает знание читающему чужой код понимание, для чего этот кусок был написан (просьба не сводить к простому примеру с for). Эт также важно, как и важно применять правильные *_cast вместо C-like кастинга, что дает понимание, что хотел сделать программист.
Да, с этой точки зрения в вашем продукте нет нужды делать такие проверки, и не потому, что в основных итераторах нет разницы, а в некоторых творятся чудеса. А потому, что культура кода вещь немного из другой области, хоть и может проверяться статическими анализаторами.
а в связи с этим, бесплатный community edition будет??))
for(unsigned char i=0; i<256; i++)
{
//…
}
{
for(int i=0; i<count; i++) printf("%s\n", names[i]);
}
…
char names[32][32], *names_p[32];
for(int i=0; i<32; i++)
{
sprintf(names[i], "%d", i);
names_p[i] = names[i];
}
func(names, 32); // упадет
func(names_p, 32); // не упадет