Главное меню
Мы солидарны с Украиной. Узнайте здесь, как можно поддержать Украину.

Ответ

Обратите внимание: данное сообщение не будет отображаться, пока модератор не одобрит его.
Ограничения: максимум вложений в сообщении — 3 (3 осталось), максимальный размер всех файлов — 300 КБ, максимальный размер одного файла — 100 КБ
Снимите пометку с вложений, которые необходимо удалить
Перетащите файлы сюда или используйте кнопку для добавления файлов
(Удалить вложения)
Вложения и другие параметры
Проверка:
Оставьте это поле пустым:
Наберите символы, которые изображены на картинке
Прослушать / Запросить другое изображение

Наберите символы, которые изображены на картинке:

√36:
ALT+S — отправить
ALT+P — предварительный просмотр

Сообщения в этой теме

Автор myst
 - ноября 27, 2010, 14:56
Цитата: GaLL от ноября 27, 2010, 14:38
Я сделал специальную оговорку:
Эта оговорка и показывает бессмысленность сей затеи.

Цитата: GaLL от ноября 27, 2010, 14:38
Мне неоднократно доводилось писать самопальный хэш, и ничего близкого к человекочасам не возникало: уж очень прост алгоритм хэширования строк.
Кроме хэширования строк ничего не надо, да? :eat:

Цитата: GaLL от ноября 27, 2010, 14:38
Не будет выделение память под подстроку. Если хэш самопальный, то и копировать эту подстроку необязательно.
А как сами сочетания в результат выводить?

Цитата: GaLL от ноября 27, 2010, 14:38
За время, ушедшее на обсуждение этой темы участниками - ещё больше раз.
Это время тоже часть решения задачи? :o

Цитата: GaLL от ноября 27, 2010, 14:38
Я просто высказал соображения по поводу возможной оптимизации, решив (вероятно ошибочно), что это действительно имеет отношение к теме и будет кому-то интересно.
Ваши соображения по оптимизации были бы интересны для более общей задачи, где размер сочетания переменный. Если Вы с C++ (точнее с микрософтовской реализацией) хорошо знакомы, то, может, подскажете, как выключить синхронизацию в библиотеке. Они однопоточную библиотеку выкинули зачем-то, а судя по показаниям профилёра, как раз на одной из блокировок съедается куча времени. :(
Автор GaLL
 - ноября 27, 2010, 14:38
Цитировать
А если понадобится другой размер сочетаний или даже диапазон длин, передаваемый как параметр? А если уникод? Как выводить результаты?
Я сделал специальную оговорку:
Цитировать
Если размер алфавита около 100 или меньше
Цитировать
трёхбуквенных сочетаний
Если же число возможных подстрок слишком велико, конечно, надо хэш.

Цитировать
Знаем мы эти программистские 5 минут, плавно превращающиеся в человеко-часы. :green:
За эти пять минут самое медленное искаробочное решение отработает 2 раза.
Мне неоднократно доводилось писать самопальный хэш, и ничего близкого к человекочасам не возникало: уж очень прост алгоритм хэширования строк.

Цитировать
То есть Вы предлагаете вручную выделять массивы символов в куче и копировать в них? И где здесь профит?

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

Цитировать
За эти пять минут самое медленное искаробочное решение отработает 2 раза.
За время, ушедшее на обсуждение этой темы участниками - ещё больше раз.
Я просто высказал соображения по поводу возможной оптимизации, решив (вероятно ошибочно), что это действительно имеет отношение к теме и будет кому-то интересно.
Автор myst
 - ноября 27, 2010, 14:17
Цитата: GaLL от ноября 27, 2010, 13:53
Возможно, мне следовало так выразиться: просто в реализации и эффективнее по времени работы.
А если понадобится другой размер сочетаний или даже диапазон длин, передаваемый как параметр? А если уникод? Как выводить результаты?

Цитата: GaLL от ноября 27, 2010, 13:53
Куда больше пары секунд для таких больших данных.
Из этих 35 секунд половина — чтение данных.

Цитата: GaLL от ноября 27, 2010, 13:53
Не понимаю, чего плохого в реализации тех или иных алгоритмов, если это занимает пять минут и если действительно есть смысл оптимизировать.
Знаем мы эти программистские 5 минут, плавно превращающиеся в человеко-часы. :green:
За эти пять минут самое медленное искаробочное решение отработает 2 раза.

Цитата: GaLL от ноября 27, 2010, 13:53
Я об этом:
Код Выделить
string piece = str.Substring(pos, ngram_size);
Не из какого астрала мы длину строки тут не узнаём, она же равна ngram_size.

То есть Вы предлагаете вручную выделять массивы символов в куче и копировать в них? И где здесь профит?
Автор GaLL
 - ноября 27, 2010, 13:53
Цитировать
Чем проще?
Возможно, мне следовало так выразиться: просто в реализации и эффективнее по времени работы.

Цитировать
Ога, ради экономии пары секунд только самопала и не хватало. И это нечестно по отношению к конкурентам. Там искаробочные решения.
Куда больше пары секунд для таких больших данных. Не понимаю, чего плохого в реализации тех или иных алгоритмов, если это занимает пять минут и если действительно есть смысл оптимизировать.

Цитата: myst от ноября 27, 2010, 13:44
Конечно, не даёт. Мы же длину строки узнаём из астрала, а автоматическое управление памятью — это неудобно.

Я об этом:
Код Выделить

string piece = str.Substring(pos, ngram_size);

Не из какого астрала мы длину строки тут не узнаём, она же равна ngram_size.
Автор myst
 - ноября 27, 2010, 13:44
Цитата: GaLL от ноября 27, 2010, 11:45
Если размер алфавита около 100 или меньше, то для подсчёта числа различных трёхбуквенных сочетаний проще обойтись прямой индексацией, т. е. массивом вида count[C][C][C], C - размер алфавита.
Чем проще?

Цитата: GaLL от ноября 27, 2010, 11:45
Если же нужен хэш, то тогда можно написать несложный самопальный, который будет быстрее hash_map'а.
Ога, ради экономии пары секунд только самопала и не хватало. И это нечестно по отношению к конкурентам. Там искаробочные решения.

Цитата: GaLL от ноября 27, 2010, 11:45
Использование std::string'а в данном случае не даёт особых удобств, поэтому можно (для оптимизации по времени) юзать массив символов фиксированной длины.
Конечно, не даёт. Мы же длину строки узнаём из астрала, а автоматическое управление памятью — это неудобно.
Автор GaLL
 - ноября 27, 2010, 11:45
Если размер алфавита около 100 или меньше, то для подсчёта числа различных трёхбуквенных сочетаний проще обойтись прямой индексацией, т. е. массивом вида count[C][C][C], C - размер алфавита. Если же нужен хэш, то тогда можно написать несложный самопальный, который будет быстрее hash_map'а. Использование std::string'а в данном случае не даёт особых удобств, поэтому можно (для оптимизации по времени) юзать массив символов фиксированной длины.
Автор myst
 - ноября 27, 2010, 10:47
Цитата: myst от ноября 27, 2010, 09:54
С hash_map C++ — 1:10. Максимальное потребление памяти ок. 9 мегабайт.
Очорт! Я забыл отладочный вывод закомментировать. Без него — 0:35. Наконец-то всё встало на свои места. :)
Автор myst
 - ноября 27, 2010, 09:55
Цитата: Алексей Гринь от ноября 27, 2010, 09:43
Дотнет медленнее в два раза серверной версии, зато потребляет ресурсов меньше в 14 раз.
Дык, не в два: 0:53 vs 1:09
Автор myst
 - ноября 27, 2010, 09:54
С hash_map C++ — 1:10. Максимальное потребление памяти ок. 9 мегабайт.
Автор Алексей Гринь
 - ноября 27, 2010, 09:43
Цитата: myst от ноября 27, 2010, 08:51
.NET'овые программы нельзя никак потюнить, чтобы они, когда надо, память не экономили и выдавали максимальную скорость?
Да там есть конфигурационные файлы какие-то, не разбирался.

Цитата: myst от ноября 27, 2010, 08:51
У серверной машины максимум где-то в районе 190 мегов. У клиентской — 35, но она работает полторы минуты.
У дотнетовой программы — 13,5.

В производительность входит количество работы в единицу времени.
Ну вот. Дотнет медленнее в два раза серверной версии, зато потребляет ресурсов меньше в 14 раз. Поэтому он выигрывает.