Re[17]: Резюме
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 29.10.05 20:18
Оценка:
Здравствуйте, Dmi_3

Приношу свои извинения, если мое обращение на "ты" (которое является вполне легальным на данном форуме) оскорбило вас. Я здесь со всеми на ты, и даже если ко мне обращаются на "вы", то сразу предлагаю перейти на "ты", т.к. это гораздо более удобно.

D_>Вы правы. Если хэш-функция выдаёт мало разных значений, то ничто не поможет. А о том, что же показывает именно эта оценка см. ниже.

D_>Далее. (//комментарии мои)

К комментариям. Давайте вернемся на несколько шагов назад: Re[10]: Compile-time вычисления: а оно вообще надо?
Автор: eao197
Дата: 27.10.05


Прогонял его на одном и том же log-файле с разными значениями capacity. Оказалось, что capacity, который является степенью двойки, дает наихудший результат (причем намного худший):
2049: 750
2053: 741 # Простое число.
2048: 1920


А на вчетверо больших значениях еще страшнее:
8192: 7680
8209: 3610 # Простое число.
8193: 3612


а так же на код программы, которую я приводил в том же письме. Я считываю из входного потока capacity элементов. Поэтому в первой последовательности я считывал 2049, 2053 и 2048 не пустых строк. Затем решил проверить ситуацию на вчетверо больших объемах. Отсюда и вторая последовательность: 8192, 8209 и 8193 строки соответственно. Видя такое плохое распределение для capacity, которое является степенью двойки, я решил проверить, насколько хорошие хэши генерирует функция hash_pjw из ACE. Чуть модифицировал программу и получил результат 6802 для 8209 строк. Но далее вы продолжаете считать, что в моих тестах всегда присутствуют 8209 строк. Это не так. Посмотрите еще раз на тексты моих программ здесь
Автор: eao197
Дата: 27.10.05
и здесь
Автор: eao197
Дата: 29.10.05
и вы увидете, что capacity как раз и есть количество прочитанных строк.

Поэтому я и считаю, что если хэш функция выбрана удачно и у capacity хорошее значение, то количество пустых элементов в таблице должно стремиться к нулю. Т.к. размер таблицы достаточен для сохранения всех прочитанных значений. Но, если для наиболее равномерного заполнения хэш-таблицы требуется вчетверо больше данных, чем размер таблицы, то может быть об этом можно было просто сказать? Раз уж для вас настолько очевидна моя некомпетентность в данном вопросе. Я ведь здесь не один такой, несведующий. Вместо упражнений в острословии устроили бы здесь маленький ликбез -- глядишь, некомпетенции бы вокруг поубавилось.

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


Напомню, что я предлагал делать такой STATIC_ASSERT только если очень захочется.

D_>Должно быть не STATIC_ASSERT( ( size & 2 ) == 0 );

D_>а STATIC_ASSERT( ( size & 1 ) != 0 );
D_>или STATIC_ASSERT( ( size % 2 ) != 0 );

Да, здесь я ошибся -- вот, что значит приводить код, который никогда не компилировался и не тестировался.

D_>Например, (stupid по Вашему мнению) Юрий Жмеренецкий.


Приведите, пожалуйста точную цитату, где я обозвал Юрия словом stupid.
Чтобы вам проще было искать, сделаю наводку: Re[2]: Compile-time вычисления: а оно вообще надо?
Автор: eao197
Дата: 26.10.05

В общем, уважаемые коллеги по C++ цеху, давайте не будем stupid, и будет пытаться "Keep it simple"


Прошу так же принять во внимание, что я говорил во множественном числе, обращась ко всем коллегам по C++ (имея при этом в виду и себя). А так же наличие смайлика и знака

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

А вот вас я попрошу либо привести точную цитату того, что по моему мнению к Юрию относится термин stupid. Либо публично забрать свои слова обратно.

E_>> Не вижу никаких преимуществ от выбора простых чисел для ограничения размерности.

D_>То есть лично Вы всегда можете найти великолепную хэш-функцию?
D_>Поздравляю! Обычно мне и моим коллегам это не удаётся. Но постойте… Как же это соотнести с ранее высказанным Вами:
E_>> Какая была, такую и использовал. Не всегда есть время изучать Кнута и выбирать оптимальную хэш-функцию, приходится брать то, что есть.
E_>> Кроме-то на этих данных лога выпадает такое распределение. Со временем характер данных в логе может поменяться.
D_>Неувязочка получается.

Никакой неувязочки. Я не специалист в хэшировании, поэтому если мне по каким-то причинам потребуется воспользоваться хэш-функция, то я вряд ли буду осваивать Кнута или другую научную литературу. А воспользуюсь какой-либо готовой реализаций. Из ACE, Ruby или Berkeley DB, т.к. надеюсь, что их разработчики понимают в этом деле больше меня. Что я и попробовал сделать. И, как ни странно, получил результаты, которые ожидал.

E_>> Главное -- это качество хэш функции.

D_>Так я же говорил:
D_>> ОЧЕНЬ ответственно относитесь к выбору хэш-функций, исследуя типичные данные для Вашего случая. Хеширование идентификаторов и путей к файлам – две большие разницы.

Ну в этом мы не противоречим друг другу. Расхождения начинаются в том, что я считают навороты вокруг простых чисел в этом случае уже излишними. А вы -- нет. Что по-моему и является излишним переусложнением.

D_>> Если какое-то требование к использованию кода можно выразить явно в программе – выразите. Это будет дополнительной гарантией. Разве все внимательно читают документацию?

E_>> Что выразить? Что пользователь твоего кода должен искать сам простые числа?
D_>Если задача этого требует то да (cм. RSA-криптосистема с открытыми ключами).

По-вашему, простые числа (для 2048-битовых или 4096-битовых ключей) можно искать в compile-time?

D_>Но Вы опять не поняли. Я для того и завёл массив capacity, что-бы пользователи могли поменьше заботиться и об этом и о чрезмерном использовании памяти и о идеальной функции хеширования. Ведь у них есть свои проблемы и негоже заставлять изучать всех тонкости организации хэшей. А требованием к коду в данном случае являются размеры буферов возрастающие примерно в «золотой» пропорции(в частности для экономии памяти) и являющиеся простыми числами(для снижения требований к качеству хэш-функции). Если бы я просто задал их числами то во время сопровождения программы мой коллега из добрых побуждений не поняв(как Вы) почему они именно такие изменил бы их например на степени двойки.


А с чего бы ему это потребовалось бы делать? Если приложение работает нормально, то зачем его менять? А если работает не правильно, то зачем эти навороты с числами Фибоначчи и ближайшими к ним значениями?

D_> И при изменении структуры и\или вероятностей распределения ключей его алгоритм превратился бы из O(1) в O(N) а его realtime 24x7 приложение «упало»\«зависло» бы не успев обработать socket. А если вы про пример «тупого» хэша говорите, то прочтите комментарий к нему.

D_>// Не ругайтесь. Это только пример.

Ok. Пример, так пример.

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

E_>> Значит меня бы уволили.
D_>Наверно да. Правда в реальности там ещё русский комментарий стоял, на случай если кто плохо знает английский. Но даже комментарий не поможет, если человек не знает таких «академических» понятий как «инкапсуляция» и «абстрагирование», если ему не достаточно интерфейса

Отличный пример иронии, не достигшей своей цели. В баталиях с таким одиозным персонажем RSDN, как VladD2, я уже столько услышал в свой адрес, что меня на форумах RSDN сложно вывести из себя или хотя бы уколоть подобными выпадами.

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

D_>И учитесь абстрагироваться.


Ok. Форумы RSDN как раз очень хороши тем, что здесь есто чему научиться. И я, тот год, что участвую на RSDN многому научился.

Вам же могу посоветовать больше внимания оформлению своего кода. Его очень тяжело читать.

D_>> 59,89,149,233,379,613,991,1597,2591,4201,6779,10949,17713,28657,46381,75029,121403,196429,317827,514229,832063,1346273,2178313,3524603,5702897

E_>> мне бы самом понять, что это такое.
D_>Это размеры хэш-буферов которые автоматически выбираются при создании и\или рехешировании. Именно эти числа находятся в массиве capacity и получаются из выражений near_prime<fibonachchi<N>::result>::result

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

E_>>А от своих студентов я больше требую, чтобы они писали простой, аккуратно оформленный и задокументированный код. Этому, поверь, научится гораздо сложнее, чем решению задач на сообразительность. Особенно, когда срок реализации проекта -- вчера.

D_>Простите, но я сомневаюсь, что самое время этому учиться, когда пропущены сроки реализации проекта. Хотя если проект «завален» то есть время и подучиться.

А кто сказал про пропущенность сроков или завал проекта? Имхо, выражение "срок сдачи -- вчера" является вполне устоявшимся выражением, которое означает, что на реализацию проекта отведен слишком малый срок. В Москве такие проекты сплошь и рядом, если вообще не 100%.

D_> Вот только наряду с обучением грамотному использованию синтаксиса C++ хорошо бы учить и базовым принципам преодоления сложности построения программ.


Например, отказ от использования в коде неоправдано сложных конструкций.

D_>P.S. (offtopic)

D_>После всего выше приведенного, совет «…вообще забей на хэширование, если ничего в нем не понимаешь.» я скорее буду относить к Вам а не к себе.

А этот совет ко мне и относился.

D_> Хотя мне трудно представить разработчика компиляторов пусть даже скриптовых языков не использующего hash и слабо разбирающегося в рекурсии. Как Вы ассоциируете атрибуты с именем идентификатора без hash? Ищете в неупорядоченном списке? Как разбираете БНФ или просто выражения со скобками без рекурсии? Ручками стеки заводите?


Ой, а откуда следовало, что я плохо разбираюсь в рекурсии?

БНФ я не разбирал сам. Это вместо меня yacc делал. А еще я реализовал (4fun, как говорил Юрий Жмеренецкий) собственный аналог yacc, но в виде LR(1) парсера на основании "правил подстановки Флойда", которые нам отчитали в свое время во время обучения.

А идентификаторы я храню в обычном map-е. Может не так эффективно, как в hash, но и проблем с производительностью не было.

D_> И уж совсем невозможно представить 7x24 приложение отказоустойчивость которого базируется на:

E_>> Указал пользователь четное значение -- сам дурак

Очень, кстати, удобно. Делать систему, которая эффективно ведет себя при правильном использовании. А при неправильном -- сразу падает, но не пытается самостоятельно "выровнять" ситуацию.

D_>То, что сделал Юрий Жмеренецкий вызывает если не восхищение то глубокое уважение. А Вы (см. «Собачье сердце») позволяете себе давать советы Космического масштаба и Космической же глупости. Вот это уже можете считать моей оценкой.


Мою оценку работе Юрия вы можете увидеть в списке оценок сообщения Compile-time template library
Автор: Юрий Жмеренецкий
Дата: 22.10.05
или Re: Compile-time вычисления: а оно вообще надо?
Автор: Юрий Жмеренецкий
Дата: 26.10.05
. Я и завел отдельную тему чтобы определить границы полезности использования сложных шаблонных конструкций в реальных проектах (которые будут развиваться не год, не два, и которые будут сопровождаться программистами с разным опытом, квалификацией, энтузиазмом и мотивацией), чтобы не бросать тень или как-то порочить работу Юрия. В крайнем случае модераторы просто вынесут эту тему в Священные воины, а топик Юрия все равно останется здесь.

D_>Впрочем я сам виноват не надо было связываться с таким человеком:

D_>Цитата из Вашей домашней странички:
D_>
D_>... Иностранными языками не владею, на русском пишу с ошибками. Сам себя могу охарактеризовать как системного программиста-камикадзе и патологического изобретателя велосипедов. Системного -- потому, что систематически умудряюсь встревать в безнадежные проекты (фактически все проекты, в которых я участвовал, можно назвать безнадежными). А изобретатель велосипедов -- потому, что меня хлебом не корми, дай что-нибудь свое придумать. Но это уже на генетическом уровне и не лечится.
D_>

D_>Конец цитаты.
D_>Мне добавить нечего!

Кстати спасибо, что так хорошо меня прорекламировали. Жаль только, что ссылку на мою страничку about не привели
Замечательно сказано в Законах Паркинсона:

Если же подумать, увидишь, что идеальное объявление привлечет одного
человека, и того именно, кто нужен. Начнем с предельного случая:

"Требуется акробат, который может пройти по проволоке на высоте 200 м
над бушующим пламенем. Ходить придется дважды в день, по субботам —
трижды. Плата — 25 фунтов в неделю. Ни пенсии, ни компенсации за увечье не
будет. Явиться лично в цирк "Дикий Кот" от 9 до 10".

Может как раз кто-то такого патологического изобретателя велосипедов и разыскивает
... << RSDN@Home 1.1.4 stable rev. 510>>


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[15]: Простота?
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 29.10.05 21:18
Оценка:
Здравствуйте, Dmi_3, Вы писали:

D_>Когда я реализовывал hash то там было что-то такое:

D_>
D_>size_t const capacity[]={
D_>  near_prime<fibonachchi<10>::result>::result,
D_>  near_prime<fibonachchi<11>::result>::result,
D_>  near_prime<fibonachchi<12>::result>::result,
D_>  near_prime<fibonachchi<13>::result>::result,
D_>  near_prime<fibonachchi<14>::result>::result,
D_>…..
D_>  near_prime<fibonachchi<44>::result>::result,
D_>  near_prime<fibonachchi<45>::result>::result,
D_>  near_prime<fibonachchi<46>::result>::result,
D_>};
D_>


D_>А эту последовательность далеко не каждый сумеет понять. Можете дать своим студентам в качестве упражнения на сообразительность.

D_>59,89,149,233,379,613,991,1597,2591,4201,6779,10949,17713,28657,46381,75029,121403,196429,317827,514229,832063,1346273,2178313,3524603,5702897

Если приведенный выше фрагмент в конце-концов сводится к указанной последовательности чисел, то почему нельзя было записать так:
/*! \note Это последовательность простых чисел, ближайших к числам Фибоначчи. */
size_t const capacity[]={
    59, 89, 149, 233, 379, 613, 991, 1597,
    2591, 4201, 6779, 10949, 17713, 28657,
    46381, 75029, 121403, 196429, 317827,
    514229, 832063, 1346273, 2178313,
    3524603, 5702897
};



И что будет с вашим кодом на 64-х битовой платформе, где емкость контейнера в 6 миллионов экземляров -- это мелочь (да и на 32-х битовой платформе это не будет проблемой)?
... << RSDN@Home 1.1.4 stable rev. 510>>


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[16]: Простота?
От: Dmi_3 Россия  
Дата: 30.10.05 10:43
Оценка: +1
Здравствуйте, eao197


D_>>Когда я реализовывал hash то там было что-то такое:

D_>>
D_>>size_t const capacity[]={
D_>>  near_prime<fibonachchi<10>::result>::result,
D_>>  near_prime<fibonachchi<11>::result>::result,
D_>>  near_prime<fibonachchi<12>::result>::result,
D_>>  near_prime<fibonachchi<13>::result>::result,
D_>>  near_prime<fibonachchi<14>::result>::result,
D_>>…..
D_>>  near_prime<fibonachchi<44>::result>::result,
D_>>  near_prime<fibonachchi<45>::result>::result,
D_>>  near_prime<fibonachchi<46>::result>::result,
D_>>};
D_>>


D_>>А эту последовательность далеко не каждый сумеет понять.

D_>>Можете дать своим студентам в качестве упражнения на сообразительность.
D_>>59,89,149,233,379,613,991,1597,2591,

E>Если приведенный выше фрагмент в конце-концов сводится к указанной последовательности чисел,

E>то почему нельзя было записать так:
E>
E>/*! \note Это последовательность простых чисел, ближайших к числам Фибоначчи. */
E>size_t const capacity[]={
E>    59, 89, 149, 233, 379, 613, 991, 1597,
E>    2591, 4201, 6779, 10949, 17713, 28657,
E>    46381, 75029, 121403, 196429, 317827,
E>    514229, 832063, 1346273, 2178313,
E>    3524603, 5702897
E>};
E>

E>

Конечно, написать было можно. Но это только часть последовательности.
near_prime<fibbonachchi<46>::result>::result == 1836311951
near_prime<fibbonachchi<47>::result>::result == 2971215073
И, допустим, что я в 20-том числе допустил ошибку. Это легко, памятуя о двух "опечатках"
в исчезнувшем STATIC_ASSERT((size&2)==0);
Контр-вопрос: Сколько времени Вы проведёте в отладчике, прежде чем найдёте несоответствие комментария
и действительности учитывая, что на маленьких тестовых примерах всё OK да и на больших всё работает
но сильно тормозит?
Е_>ИМХО. Я быстрее найду другую библиотеку.
Ну и наконец:
E_>Было бы круто, если бы .... реализация сама бы подобрала бы ближайшее «БЫ» сверху простое число.
Я тоже человек. Мне не интереееесно всё это вычислять!

Предвидя Ваши возражения про кодогенератор скажу следующее.
1. Выражение типа {@"%$ near_prime_fibonachchi @#16} ничем не лучше моего.
2. Я немогу совсем абстрагироваться от реализации т.к. должен помнить по крайней мере эти "интерфейсные" @"%$ @#.
Это и к документатору относится !\note
В моём случае программа самодокументирована, вероятность ошибки набора минимальна,
сама ошибка легко визуально обнаружима и моя бедная голова свободна от @"%$ @#.
А в другой фирме от @#$%#$%^&^
Что такие последовательности символов означают, Вы знаете.
Расплатой за все прелести является "навороченный" код в пол экрана.
Написание (и разбор с пониманием) которого способствует моему росту как программиста C++,
лучшему пониманию рекурсии и т.д.
А если кому-то он кажется сложным, то можно и абстрагироваться. (это не "наезд").

E>И что будет с вашим кодом на 64-х битовой платформе, где емкость контейнера в 6 миллионов экземляров -- это мелочь (да и на 32-х битовой платформе это не будет проблемой)?

Кажется я уже нечаянно ответил.
Но если Вы имеете ввиду, что is_prime<N64>::result не может быть вычислена
т.к. придётся перебрать в CT слишком много делителей, то скажу
что там алгоритм вообще не ищет делителей.
Есть очень эффективные методы определения простоты числа именно без получения его делителей.
Они и с 256 битным по идее в CT должны справиться.
Как там это сделано прошу не спрашивать, но см. тест Миллера-Рабина.
С его помощью в CT можно искать почти простые числа.
Re[17]: Простота?
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 30.10.05 11:53
Оценка:
Здравствуйте, Dmi_3, Вы писали:

D_>Конечно, написать было можно. Но это только часть последовательности.

D_>near_prime<fibbonachchi<46>::result>::result == 1836311951
D_>near_prime<fibbonachchi<47>::result>::result == 2971215073
D_>И, допустим, что я в 20-том числе допустил ошибку. Это легко, памятуя о двух "опечатках"
D_>в исчезнувшем STATIC_ASSERT((size&2)==0);
D_>Контр-вопрос: Сколько времени Вы проведёте в отладчике, прежде чем найдёте несоответствие комментария
D_>и действительности учитывая, что на маленьких тестовых примерах всё OK да и на больших всё работает
D_>но сильно тормозит?

Не согласен. Если вы последовательность значений для чисел Фибоначчи вводили вручную, то могли написать так:
near_prime<fibbonachchi<46>::result>::result,
near_prime<fibbonachchi<47>::result>::result,
near_prime<fibbonachchi<47>::result>::result,
near_prime<fibbonachchi<49>::result>::result,


А потом бы долго искали подобную ошибку.

А для вставки числовой последовательности в код совсем не нужно делать кодогенератор. Достаточно один раз сделать скрипт или простую программу на С++ для генерации последовательности и:
— либо скопипастить результат ее работы в текст программы;
— либо подключить результат ее работы через #include.

Все.

E>>И что будет с вашим кодом на 64-х битовой платформе, где емкость контейнера в 6 миллионов экземляров -- это мелочь (да и на 32-х битовой платформе это не будет проблемой)?

D_>Кажется я уже нечаянно ответил.

Нет, я имею в виду, что ваш код придется явно портировать на 64-х битовую платформу, т.к. придется расширять исходную последовательность новыми значениями. А если бы в хеш-контейне применялось простое удвоение объема буфера без предварительно вычисленных размеров, то код легко бы портировался с 16-ти битовой на 32-х битовую, на 64-х битовую и на любую другую платформу.

Немного в оффтопик: если вам интересно какое-то решение потому, что оно повысило ваш уровень знания C++, то это еще не повод использовать данное решение в промышленном коде. Занятие самообразованием за счет заказчика -- это довольно опасная затея, хотя и заманчивая.
... << RSDN@Home 1.1.4 stable rev. 510>>


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[18]: Hash & CT
От: Dmi_3 Россия  
Дата: 30.10.05 11:56
Оценка: -1
Здравствуйте, eao197, Вы писали:

Извинения принимаются. Проехали?

E>А вот вас я попрошу либо привести точную цитату того, что по моему мнению к Юрию относится термин stupid. Либо публично забрать свои слова обратно.

После загадочного исчезновения Вашей ошибки со STATIC_ASSERT((size&2)==0);
Я считаю странной эту просьбу.
1. Эти слова могли оказаться там же где и ASSERT
2. Вы сами можете их убрать а заодно добавить мои "восхищённые" восклицания по поводу модерирования.
3. Предлагаю ввести электронные подписи сообщений во избежание подобных инцидентов.

Тем не менее:
class Dmi_3
WORD (*phrase)[];
public://Вы просили публично.
  get_to_back(){delete phrase; phrase=0;}
};
Dmi_3 the_Dmi_3;
int main(){
  the_Dmi_3.get_to_back();
}

Я рад, что ошибся в Вашем отношении к коллегам вообще и к Юрию в частности.
НЕ БОЛЕЕ ТОГО.

Далее без дипломати.

E_>>> Что выразить? Что пользователь твоего кода должен искать сам простые числа?

D_>>Если задача этого требует то да (cм. RSA-криптосистема с открытыми ключами).

E>По-вашему, простые числа (для 2048-битовых или 4096-битовых ключей) можно искать в compile-time?

Нет. Но я этого и не говорил.

E>А с чего бы ему это потребовалось менять числа если приложение работает нормально?

Иногда может попасться хэш-функция
unsigned long
hash_fun( const char * p, std::size_t len ){
  unsigned long key = 0;
  while (len--) {
    enum{mul=89};
    STATIC_ASSERT(is_prime<mul>::result);//Это иногда делает hash_fun хорошей.
    key = key*mul + *p;
    p++;
  }
  key = key + (key>>5);
  return key;
}

где mul совпадёт с текущим размером hash. Последствия могут быть плачевны.
Пользователь, обнаружив это, решит переиначить «магические» числа размеров буферов.

E>Вам же могу посоветовать больше внимания оформлению своего кода. Его очень тяжело читать.

С этого места поподробней please.

E>Ой, а откуда следовало, что я плохо разбираюсь в рекурсии?

Приведённые мною template ну очень похожи на рекурсивные функции runtime.
Если их легко понять то и template легко.
int fibo(int n,int a=0,int b=1){//template<N,A=0,B=1>struct FIBO
  if(n==0) return a; // Аналог частичной специализации для N=0 enum{result=A};
  return fibo(n-1,b,a+b);// enum{result=FIBO<N-1,B,A+B>::result};
}
Re[18]: Простота?
От: ruslan_abdikeev Россия http://aruslan.nm.ru
Дата: 30.10.05 12:51
Оценка:
E>Занятие самообразованием за счет заказчика -- это довольно опасная затея, хотя и заманчивая.
Занятия самообразованием за счёт заказчика в данном конкретном случае — действительно очень-очень опасная затея.
Re[19]: Hash & CT
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 30.10.05 14:54
Оценка:
Здравствуйте, Dmi_3, Вы писали:

D_>Извинения принимаются. Проехали?


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

E>>А вот вас я попрошу либо привести точную цитату того, что по моему мнению к Юрию относится термин stupid. Либо публично забрать свои слова обратно.

D_>После загадочного исчезновения Вашей ошибки со STATIC_ASSERT((size&2)==0);
D_>Я считаю странной эту просьбу.
D_>1. Эти слова могли оказаться там же где и ASSERT
D_>2. Вы сами можете их убрать а заодно добавить мои "восхищённые" восклицания по поводу модерирования.
D_>3. Предлагаю ввести электронные подписи сообщений во избежание подобных инцидентов.

В данной ветке пока следов модерирования я не заметил, все сообщения остались на своих местах. В частности, ошибка со STATIC_ASSERT находится здесь: Re[13]: Простота, эффективность и usabillity
Автор: eao197
Дата: 28.10.05
. Поэтому упрекая меня в негативном отношении к коллегам, вы делаете тоже самое по отношению к модераторам. Не красиво, однако.

E>>По-вашему, простые числа (для 2048-битовых или 4096-битовых ключей) можно искать в compile-time?

D_>Нет. Но я этого и не говорил.

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

E>>А с чего бы ему это потребовалось менять числа если приложение работает нормально?

D_>Иногда может попасться хэш-функция
D_>
D_>unsigned long
D_>hash_fun( const char * p, std::size_t len ){
D_>  unsigned long key = 0;
D_>  while (len--) {
D_>    enum{mul=89};
D_>    STATIC_ASSERT(is_prime<mul>::result);//Это иногда делает hash_fun хорошей.
D_>    key = key*mul + *p;
D_>    p++;
D_>  }
D_>  key = key + (key>>5);
D_>  return key;
D_>}
D_>

D_>где mul совпадёт с текущим размером hash. Последствия могут быть плачевны.
D_>Пользователь, обнаружив это, решит переиначить «магические» числа размеров буферов.

Знаете, Dmi_3, у меня сложилось впечатление, что слаборазбирающийся в вопросах хеширования человек (вроде меня), никогда не поймет, что эпизодические падения производительности будут связаны с тем, что текущий размер хеш-таблицы совпадает со значением mul в hash_fun. К тому же, насколько я могу судить, простого совпадения все равно не достаточно. Для этого еще нужно специальное значение в *p. Так что, человек, который сможет продиагностировать подобные проблемы, сможет подобрать подходящее значение для mul. И не факт, что это значение должно будет быть простым.

E>>Ой, а откуда следовало, что я плохо разбираюсь в рекурсии?

D_>Приведённые мною template ну очень похожи на рекурсивные функции runtime.
D_>Если их легко понять то и template легко.

Ну не скажите, обычная рекурсия в run-time и рекурсия определения шаблонов -- это две довольно большие разницы.
... << RSDN@Home 1.1.4 stable rev. 510>>


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[19]: О стиле
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 30.10.05 14:54
Оценка:
Здравствуйте, Dmi_3, Вы писали:

E>>Вам же могу посоветовать больше внимания оформлению своего кода. Его очень тяжело читать.

D_>С этого места поподробней please.

Ok. Возьмем ваш аккумулированный код из Re[13]: Простота, эффективность и usabillity
Автор: eao197
Дата: 28.10.05
:

template<unsigned int N>
class is_prime{
  template<unsigned int K>
  struct ask{
    enum{
      tmp=(N<K*K),//Временных переменных никто не отменял :-)
      answer=tmp|ask<(K+6u)*(!tmp&&(N%K)&&(N%(K+2u))&&(N%(K+4u)))>::answer
    };
  };
  template<>struct ask<0u>{enum{answer=0u};};//Признак окончания разбора.
public:
  enum{result=ask<3u*(N&1u)>::answer};
};
template<>class is_prime<1u>{public:enum{result=0u};};
template<>class is_prime<2u>{public:enum{result=1u};};

template<unsigned int N>
class get_near_prime_number{
  template<unsigned int K>
  struct ask{
    enum{
      tmp=is_prime<K>::result,
      answer=tmp?K:ask<(K+2u)*!tmp>::answer
    };
  };
  template<>struct ask<0u>{enum{answer=0u};};
public:
  enum{result=ask<N|1u>::answer};
};


Позволю себе просто разбавить его пробелами:
template< unsigned int N >
class is_prime
    {
        template< unsigned int K >
        struct ask
            {
                enum
                    {
                        // Временных переменных никто не отменял :-)
                        tmp = ( N < K*K ),
                        
                        // Здесь бы не помешал какой-то осмысленный комментарий.
                        answer = tmp |
                            ask< ( K + 6u ) *
                                ( !tmp && (N%K) && (N % (K+2u) ) && ( N % (K+4u) ) ) >::answer
                    };
            };
            
        template<>
        struct ask< 0u >
            {
                enum
                    {
                        // Признак окончания разбора.
                        answer = 0u
                    };
            };
    public:
        enum
            {
                // Здесь бы не помешал какой-то осмысленный комментарий.
                result = ask< 3u * (N & 1u) >::answer
            };
    };
    
template<>
class is_prime< 1u >
    {
    public:
        enum { result = 0u };
    };

template<>
class is_prime< 2u >
    {
    public:
        enum { result = 1u };
    };

template< unsigned int N >
class get_near_prime_number
    {
        template<unsigned int K>
        struct ask
            {
                enum
                    {
                        tmp= is_prime< K >::result,
                        // Здесь бы не помешал какой-то осмысленный комментарий.
                        answer = tmp ?
                                K :
                                ask< ( K + 2u ) * !tmp >::answer
                    };
            };
            
        template<>
        struct ask< 0u >
            {
                enum { answer = 0u };
            };
            
    public:
        enum
            {
                result= ask< N | 1u >::answer
            };
    };
... << RSDN@Home 1.1.4 stable rev. 510>>


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[19]: Hash & CT
От: _Winnie Россия C++.freerun
Дата: 30.10.05 16:16
Оценка:
Здравствуйте, Dmi_3, Вы писали:

Ничего не понимаю. Если hash-функция подобрана нормально, то ей пофиг по модулю чего ее брать. Если на каких-то она модулях сбоит, значит писавшему её надо кое-что оторвать.
Правильно работающая программа — просто частный случай Undefined Behavior
Re[20]: Hash & CT
От: _Winnie Россия C++.freerun
Дата: 30.10.05 16:23
Оценка: :)
Здравствуйте, _Winnie, Вы писали:

_W>Здравствуйте, Dmi_3, Вы писали:


_W>Ничего не понимаю. Если hash-функция подобрана нормально, то ей пофиг по модулю чего ее брать. Если на каких-то она модулях сбоит, значит писавшему её надо кое-что оторвать.


И, кстати, деление на простое число — это в 12 раз медленней, чем побитовая операция &.
Ф топку такую "оптимизацию", лучше заставить пользователя выбрать нормальную хеш-функцию.
Правильно работающая программа — просто частный случай Undefined Behavior
Re[3]: Compile-time вычисления: а оно вообще надо?
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 16.11.05 20:25
Оценка:
Здравствуйте, eao197, Вы писали:

E>
E>#ifdef MXX_RU_INPLACE_CODEGEN

E>    require 'mxx_ru/cpp/inplace_codegen'

E>    class Config < CppValueIncapsulator
E>        cpp_name "cfg_t"
E>        hpp { :where => :here }
E>        cpp { :where => :file, :file_name => "../cfg.impl.cpp" }
E>        attr_prefix "m_"
E>        setter_prefix "set_"

E>        attr :listening_mbox, "std::string"

E>...

E>    end

E>#endif
E>


E>Вот это я понимаю, вот это метапрограммирование!

E>На шаблонах еще попробовать это сделать нужно

E>А вот на Ruby, как мне представляется, реализация будет не столь сложной....


Действительно, реализация оказалась не такой уж и сложной Но и не совсем такой (пока?), как я здесь показал. Вот, что получилось: [Ruby,C++] RuCodeGen -- простой фреймворк для кодогенерации
Автор: eao197
Дата: 16.11.05
... << RSDN@Home 1.1.4 stable rev. 510>>


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re: Compile-time вычисления: а оно вообще надо?
От: CrystaX Россия https://crystax.me/
Дата: 20.11.05 22:23
Оценка:
Евгений, вот тебе та самая ситуация, когда compile-time вычисления действительно полезны — Обеспечение семантического контроля над размерностями стандартными средствами C++
Автор: CrystaX
Дата: 21.11.05
.
У меня наконец дошли руки причесать эти исходники и выложить на всеобщее обозрение. Именно об этих исходниках также шла речь в небезызвестной тебе ветке Что толку в Ада если Ариан 5 все равно упал
Автор: eao197
Дата: 05.06.05
. С Арианом-то дело уже прошлое, но я смею надеяться, что использование моего кода (с compile time вычислениями) не позволит упасть многим другим программам.
... << RSDN@Home 1.1.4 stable rev. 510>>
Re[2]: Compile-time вычисления: а оно вообще надо?
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 21.11.05 08:02
Оценка:
Здравствуйте, CrystaX, Вы писали:

CX>Евгений, вот тебе та самая ситуация, когда compile-time вычисления действительно полезны — Обеспечение семантического контроля над размерностями стандартными средствами C++
Автор: CrystaX
Дата: 21.11.05
.


Интересно, Дмитрий. Вот за что мне нравится C++, так это за возможность сотворить что-нибудь такое-эдакое:
// Сила
si::force f1(10);      // 10 Н
cgs::force f2 = f1*2;  // 10 Н * 2 = 2000000 дин

si::force f3 = m1*l2/(t1*t1); // 1 г * 1 м / (1 с * 1 с) = 0.001 Н

Я в свое время так и не смог на Java программировать из-за того, что там этого хоть убейся, а не сделаешь.

C++ forever!

Тем не менее, я думаю, что как раз compile-time там не так уж и много. Имхо, это практически обобщенное и метапрограммирование в чистом виде. Хотя строгую классификацию я бы не стал делать.
... << RSDN@Home 1.1.4 stable rev. 510>>


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[3]: Compile-time вычисления: а оно вообще надо?
От: CrystaX Россия https://crystax.me/
Дата: 21.11.05 08:36
Оценка:
Здравствуйте, eao197, Вы писали:

E>Я в свое время так и не смог на Java программировать из-за того, что там этого хоть убейся, а не сделаешь.


Аналогично.

E>C++ forever!


+1

E>Тем не менее, я думаю, что как раз compile-time там не так уж и много. Имхо, это практически обобщенное и метапрограммирование в чистом виде. Хотя строгую классификацию я бы не стал делать.


Как раз compile-time там довольно много, просто не торчит наружу. Вся система выведения коэффициентов, новых типов и т.д. основана на boost::mpl, а уж boost::mpl — это просто квинтэссенция compile time вычислений. А вот если туда еще и CT итерирование прикрутить...
... << RSDN@Home 1.1.4 stable rev. 510>>
Re[2]: Compile-time вычисления: а оно вообще надо?
От: Erop Россия  
Дата: 21.11.05 10:38
Оценка: 12 (1)
Здравствуйте, CrystaX, Вы писали:

CX>Евгений, вот тебе та самая ситуация, когда compile-time вычисления действительно полезны — Обеспечение семантического контроля над размерностями стандартными средствами C++
Автор: CrystaX
Дата: 21.11.05
.

CX>У меня наконец дошли руки причесать эти исходники и выложить на всеобщее обозрение. Именно об этих исходниках также шла речь в небезызвестной тебе ветке [url=http://rsdn.ru/forum/Message.aspx?mid=1206899&amp;only=1
Автор: eao197
Дата: 05.06.05
]


Ну, не смотря на узкую область применения, классная машинка. Мало того, прикаольно реализовано, ну и вообще хорошо довольно всё сделано. В конце концов идея приписывать размерность через тип переменной и поиск преобразования (Если оно есть) или детектирование того факта, что преобразования нет вещь в принципе верная

Но вот зачем коэффициент в преобразовании вычислять CT я не понимаю. В конце концов его же можно кэшировать. Что за выгоду ловим-то?: )

Ну и CT-вычисления, как мне кажется, её нифига не красят эту хорошую задумку.
Там всё-таки не такая уж и красивая реализация. Одни комментарии вот в этом месте:

// system tags

//               mass    length   time  temperature      light intensity
//                 |        |       |        |                   |
//                 |        |       |        | current strength  |  quantity of substance
//                 |        |       |        |        |          |      |
//                 v        v       v        v        v          v      v
typedef vector<int_<1>, int_<0>, int_<0>, int_<0>, int_<0>, int_<0>, int_<0> > mass_tag;
typedef vector<int_<0>, int_<1>, int_<0>, int_<0>, int_<0>, int_<0>, int_<0> > length_tag;
typedef vector<int_<0>, int_<0>, int_<1>, int_<0>, int_<0>, int_<0>, int_<0> > time_tag;
typedef vector<int_<0>, int_<0>, int_<0>, int_<1>, int_<0>, int_<0>, int_<0> > temperature_tag;
typedef vector<int_<0>, int_<0>, int_<0>, int_<0>, int_<1>, int_<0>, int_<0> > current_strength_tag;
typedef vector<int_<0>, int_<0>, int_<0>, int_<0>, int_<0>, int_<1>, int_<0> > light_intensity_tag;
typedef vector<int_<0>, int_<0>, int_<0>, int_<0>, int_<0>, int_<0>, int_<1> > quantity_of_substance_tag;

typedef vector<int_<0>, int_<2>, int_<0>, int_<0>, int_<0>, int_<0>, int_<0> > area_tag;
typedef vector<int_<0>, int_<3>, int_<0>, int_<0>, int_<0>, int_<0>, int_<0> > volume_tag;
typedef vector<int_<0>, int_<1>, int_<-1>, int_<0>, int_<0>, int_<0>, int_<0> > velocity_tag;
typedef vector<int_<0>, int_<1>, int_<-2>, int_<0>, int_<0>, int_<0>, int_<0> > acceleration_tag;

Уже наводят на мысли что тут что-то не так.

А вообще вот надо мне завести ещё одну размерность. Там, скажем, очарованность. Вот что мне делать дальше?
Ну ладно, положим очарованность нужна маньякам, они твой код разберут, перепишут и добавят. Но вот что делать челу, которому как раз люмены с канделами по фигу, а не пофигу СГСэ и СГСм? Или там, скажем, надо часто переводить мили в час в футы в секунду. Что ему делать со всей этой мощью CT-вычислений?

Таки лучше бы всю мощь шаблонов направить на расширяемость и редактируемость, а не на CT. Ну а вычислять коэффициенты и сдвиги можно и RT всё-таки кажедый коэффициент нужно вычислять один раз, и не так уж их и много вообще.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[2]: Ссылка на реализацию
От: Erop Россия  
Дата: 21.11.05 10:41
Оценка:
Дмитрий выложил и реализацию своего прекрасного продукта, кому неудобно искать, вот ссылка
Автор: CrystaX
Дата: 21.11.05
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[3]: Compile-time вычисления: а оно вообще надо?
От: Cyberax Марс  
Дата: 21.11.05 11:23
Оценка: +2
Erop wrote:

> А вообще вот надо мне завести ещё одну размерность. Там, скажем,

> очарованность. Вот что мне делать дальше?
> Ну ладно, положим очарованность нужна маньякам, они твой код разберут,
> перепишут и добавят. Но вот что делать челу, которому как раз люмены с
> канделами по фигу, а не пофигу СГСэ и СГСм? Или там, скажем, надо
> часто переводить мили в час в футы в секунду. Что ему делать со всей
> этой мощью CT-вычислений?

Мили имеют размерность расстояния, furlongs per fornight —
расстояние/время (т.е. скорость). Пишешь трансляторы — и вперед.

--
С уважением,
Alex Besogonov (alexy@izh.com)
Posted via RSDN NNTP Server 1.9
Sapienti sat!
Re[3]: Compile-time вычисления: а оно вообще надо?
От: CrystaX Россия https://crystax.me/
Дата: 21.11.05 11:33
Оценка:
Здравствуйте, Erop, Вы писали:

E>Ну, не смотря на узкую область применения, классная машинка. Мало того, прикаольно реализовано, ну и вообще хорошо довольно всё сделано. В конце концов идея приписывать размерность через тип переменной и поиск преобразования (Если оно есть) или детектирование того факта, что преобразования нет вещь в принципе верная


E>Но вот зачем коэффициент в преобразовании вычислять CT я не понимаю. В конце концов его же можно кэшировать. Что за выгоду ловим-то?: )


Самая главная причина — посмотреть, а вот можно ли? Оказалось, можно. Мелочь, а приятно.

[skip]

E>Таки лучше бы всю мощь шаблонов направить на расширяемость и редактируемость, а не на CT. Ну а вычислять коэффициенты и сдвиги можно и RT всё-таки кажедый коэффициент нужно вычислять один раз, и не так уж их и много вообще.


Если почитаешь дальше (Направления дальнейшего развития
Автор: CrystaX
Дата: 21.11.05
), то увидишь, что я над этим как раз сейчас думаю. Ничего страшного нет, сделаю CT итерирование — можно будет наворачивать любые базовые единицы. В том числе очарованность.
Просто подожди немного.
... << RSDN@Home 1.1.4 stable rev. 510>>
Re[4]: Compile-time вычисления: а оно вообще надо?
От: Erop Россия  
Дата: 21.11.05 11:42
Оценка:
Здравствуйте, CrystaX, Вы писали:

CX>Если почитаешь дальше (Направления дальнейшего развития
Автор: CrystaX
Дата: 21.11.05
), то увидишь, что я над этим как раз сейчас думаю. Ничего страшного нет, сделаю CT итерирование — можно будет наворачивать любые базовые единицы. В том числе очарованность.

CX>Просто подожди немного.

Я уже прочитал.
Я не про то пишу, что совсем совсем не удастся реализовать это всё. Я про то, что трудно будет воспользоваться, если запрос немного нестандартный. Не в последнюю очередь и из-за CT
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[5]: Compile-time вычисления: а оно вообще надо?
От: CrystaX Россия https://crystax.me/
Дата: 21.11.05 11:47
Оценка:
Здравствуйте, Erop, Вы писали:

CX>>Если почитаешь дальше (Направления дальнейшего развития
Автор: CrystaX
Дата: 21.11.05
), то увидишь, что я над этим как раз сейчас думаю. Ничего страшного нет, сделаю CT итерирование — можно будет наворачивать любые базовые единицы. В том числе очарованность.

CX>>Просто подожди немного.

E>Я уже прочитал.

E>Я не про то пишу, что совсем совсем не удастся реализовать это всё. Я про то, что трудно будет воспользоваться, если запрос немного нестандартный. Не в последнюю очередь и из-за CT

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

Я хочу сделать некую универсальную библиотеку для работы с любыми размерностями. Физические величины — это просто самый наглядный пример, не более того.
Удобство использования — один из важнейших критериев. Если есть что по этому поводу сказать — жду с нетерпением.
... << RSDN@Home 1.1.4 stable rev. 510>>
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.