Переборыч
|
Сообщение #1355
27 октября 2017 в 00:48
|
Клавомеханик-Организатор событий
55 |
ТОМА-АТОМНАЯ писал(а): это видимо ну очень сложно Сложность равна O(длина отрывка ^2). Если кто знает как на php уменьшить сложность вычисления расстояния Левенштейна, то черкните, пожалуйста, мне, - починим квалу. Сейчас, например, Лигурия требует 700М памяти и 200 сек. времени, но не думаю, что хорошим решением было бы настолько увеличивать лимиты, лучше оптимизировать алгоритм. Последний раз отредактировано 27 октября 2017 в 00:54 модератором Переборыч
|
MMMAAANNN
|
Сообщение #1356
28 октября 2017 в 19:15
|
Супермен
36 |
Переборыч, для того чтобы оптимизировать алгоритм, нужно видеть его текущую реализацию. Можешь показать? У меня есть пару идей. Например, можно попробовать вычислять не для всего текста целиком, а разбивать на куски (скажем, по 100 символов), а стыки кусков обрабатывать как-то иначе, например перекрывающимися фрагментами. P. S. Кроме того, в реальности квалификация юзабельна только в случае безошибочного набора или с очень малым количеством ошибок - для больших текстов, наверное, до 2. Иначе потери времени на исправление ошибок после набора в текущей реализации квалификации фактически делают ее бесполезной. Поэтому можно попробовать вычислять нижнюю границу расстояния Левенштайна - и если она ниже выше определенного значения (например, заданного пользователем) - просто не вычислять расстояние полностью, тем самым экономя ресурсы. P. P. S. А еще есть вариант сделать квалификацию для больших текстов платной и предупреждать пользователя, что ее вычисление займет некоторое время + придется сделать взнос в очках. P. P. P. S. Еще идея - вычислять расстояние Левенштайна не побуквенно, а по словам. То есть за отдельный элемент взять слово (определив его как то, что находится между двух пробелов либо между началом строки и пробелом, либо между пробелом и концом строки). А потом уже можно сравнивать конкретные найденные различающиеся слова, так сказать вторым этапом. Последний раз отредактировано 28 октября 2017 в 20:30 пользователем MMMAAANNN
|
un4given
|
Сообщение #1357
28 октября 2017 в 21:19
|
Клавокодер
122 |
Предлагаю решить проблему комплексно, переформулировав задачу\перекроив саму идею квалы: 1) вместо бесполезного «вы допустили Н ошибок в тексте» (и предложения исправить (которое, согласитесь, совершенно ни о чём)) предлагаю определить ДОПУСТИМЫЙ ПРОЦЕНТ ОШИБОК 2) сравнивать тексты не через ф-цию Левенштайна, а посредством штатной функции similar_text, причём первым параметром подать набранный юзером текст, а вторым − исходный текст. я сильно долго не мудрил, получилось так: скрытый текст… <pre> <?
$source_text="В четверг четвертого числа в четыре с четвертью часа лигурийский регулировщик регулировал в Лигурии, но тридцать три корабля лавировали, лавировали, да так и не вылавировали, и потом протокол про протокол протоколом запротоколировал, как интервьюером интервьюируемый лигурийский регулировщик речисто, да не чисто рапортовал, да не дорапортовал, дорапортовывал, да так зарапортовался про размокропогодившуюся погоду, что дабы инцидент не стал претендентом на судебный прецедент, лигурийский регулировщик акклиматизировался в неконституционном Константинополе, где хохлатые хохотушки хохотом хохотали и кричали турке, который начерно обкурен трубкой: не кури, турка, трубку, купи лучше кипу пик, лучше пик кипу купи, а то придет бомбардир из Бранденбурга — бомбами забомбардирует за то, что некто чернорылый у него полдвора рылом изрыл, вырыл и подрыл; но на самом деле турка не был в деле, да и Клара-краля в то время кралась к ларю, пока Карл у Клары крал кораллы, за что Клара у Карла украла кларнет, а потом на дворе деготниковой вдовы Варвары два этих вора дрова воровали; но грех — не смех — не уложить в орех: о Кларе с Карлом во мраке все раки шумели в драке, — вот и не до бомбардира ворам было, но и не до деготниковой вдовы, и не до деготниковых детей; зато рассердившаяся вдова убрала в сарай дрова: раз дрова, два дрова, три дрова — не вместились все дрова, и два дровосека, два дровокола-дроворуба для расчувствовавшейся Варвары выдворили дрова вширь двора обратно на дровяной двор, где цапля чахла, цапля сохла, цапля сдохла; цыпленок же цапли цепко цеплялся за цепь; молодец против овец, а против молодца сам овца, которой носит Сеня сено в сани, потом везет Сенька Соньку с Санькой на санках: санки — скок, Сеньку — в бок, Соньку — в лоб, все — в сугроб, а Сашка только шапкой шишки сшиб, затем по шоссе Саша пошел, саше на шоссе Саша нашел; Сонька же — Сашкина подружка шла по шоссе и сосала сушку, да притом у Соньки-вертушки во рту еще и три ватрушки — аккурат в медовик, но ей не до медовика — Сонька и с ватрушками во рту пономаря перепономарит, — перевыпономарит: жужжит, как жужелица, жужжит, да кружится: была у Фрола — Фролу на Лавра наврала, пойдет к Лавру на Фрола Лавру наврет, что — вахмистр с вахмистршей, ротмистр с ротмистршей, у ужа — ужата, у ежа — ежата, а у него высокопоставленный гость унес трость, и вскоре опять пять ребят съели пять опят с полчетвертью четверика чечевицы без червоточины, да тысячу шестьсот шестьдесят шесть пирогов с творогом из сыворотки из-под простокваши, — о всем о том около кола колокола звоном раззванивали, да так, что даже Константин — зальцбуржский бесперспективняк из-под бронетранспортера констатировал: как все колокола не переколоколовать, не перевыколоколовать, так и всех скороговорок не перескороговорить, не перевыскороговорить; но попытка — не пытка.";
$typed_text="В четверг четвертого числа в тыре с чтвертью часа лигурийский регулировщик регулировал в Лигурии, но тридцать три корабля лавировали, лавировали, да так и не вылавировали, и потом протокол про протокол протоколом запротоколировал, как интервьюером интервьюируемый лигурийский регулировщик речисто, да не чисто рапортовал, да не дорапортовал, дорапортовывал, да так зарапортовался про размокропогодившуюся погоду, что дабы инцидент не стал претендентом на судебный прецедент, лигурийский регулировщик акклиматизировался в неконституционном Константинополе, где хохлатые хохотушки хохотом хохотали и кричали турке, который начерно обкурен трубкой: не кури, турка, трубку, купи лучше кипу пик, лучше пик кипу купи, а то придет бомбардир из Бранденбурга — бомбами забомбардирует за то, что некто чернорылый у него полдвора рылом изрыл, вырыл и подрыл; но на самом деле турка не был в деле, да и Клара-краля в то время кралась к ларю, пока Карл у Клары крал кораллы, за что Клара у Карла украла кларнет, а потом на дворе деготниковой вдовы Варвары два этих вора дрова воровали; но грех — не смех — не уложить в орех: о Кларе с Карлом во мраке все раки шумели в драке, — вот и не до бомбардира ворам было, но и не до деготниковой вдовы, и не до деготниковых детей; зато рассердившаяся вдова убрала в сарай дрова: раз дрова, два дрова, три дрова — не вместились все дрова, и два дровосека, два дровокола-дроворуба для расчувствовавшейся Варвары выдворили дрова вширь двора обратно на дровяной двор, где цапля чахла, цапля сохла, цапля сдохла; цыпленок же цапли цепко цеплялся за цепь; молодец против овец, а против молодца сам овца, которой носит Сеня сено в сани, потом везет Сенька Соньку с Санькой на санках: санки — скок, Сеньку — в бок, Соньку — в лоб, все — в сугроб, а Сашка только шапкой шишки сшиб, затем по шоссе Саша пошел, саше на шоссе Саша нашел; Сонька же — Сашкина подружка шла по шоссе и сосала сушку, да притом у Соньки-вертушки во рту еще и три ватрушки — аккурат в медовик, но ей не до медовика — Сонька и с ватрушками во рту пономаря перепономарит, — перевыпономарит: жужжит, как жужелица, жужжит, да кружится: была у Фрола — Фролу на Лавра наврала, пойдет к Лавру на Фрола Лавру наврет, что — вахмистр с вахмистршей, ротмистр с ротмистршей, у ужа — ужата, у ежа — ежата, а у него высокопоставленный гость унес трость, и вскоре опять пять ребят съели пять опят с полчетвертью четверика чечевицы без червоточины, да тысячу шестьсот шестьдесят шесть пирогов с творогом из сыворотки из-под простокваши, — о всем о том около кола колокола звоном раззванивали, да так, что даже Константин — зальцбуржский бесперспективняк из-под бронетранспортера констатировал: как все колокола не переколоколовать, не перевыколоколовать, так и всех скороговорок не перескороговорить, не перевыскороговорить; но попытка не пытка.";
similar_text($typed_text, $source_text, $diff);
echo $diff."\n"; echo memory_get_usage();
?> результат выполнения: 99.892964873017 345584 где первое число − это похожесть текста в процентах, а второе − объём использованной памяти в байтах.
|
Игрок3
|
Сообщение #1358
28 октября 2017 в 21:22
|
Организатор событий
32 |
un4given писал(а): Предлагаю решить проблему комплексно, переформулировав задачуперекроив саму идею квалы: 1) вместо бесполезного «вы допустили Н ошибок в тексте» (и предложения исправить (которое, согласитесь, совершенно ни о чём)) предлагаю определить ДОПУСТИМЫЙ ПРОЦЕНТ ОШИБОК 2) сравнивать тексты не через ф-цию Левенштайна, а посредством штатной функции similar_text, причём первым параметром подать набранный юзером текст, а вторым − исходный текст. я сильно долго не мудрил, получилось так: скрытый текст… <pre> <?
$source_text="В четверг четвертого числа в четыре с четвертью часа лигурийский регулировщик регулировал в Лигурии, но тридцать три корабля лавировали, лавировали, да так и не вылавировали, и потом протокол про протокол протоколом запротоколировал, как интервьюером интервьюируемый лигурийский регулировщик речисто, да не чисто рапортовал, да не дорапортовал, дорапортовывал, да так зарапортовался про размокропогодившуюся погоду, что дабы инцидент не стал претендентом на судебный прецедент, лигурийский регулировщик акклиматизировался в неконституционном Константинополе, где хохлатые хохотушки хохотом хохотали и кричали турке, который начерно обкурен трубкой: не кури, турка, трубку, купи лучше кипу пик, лучше пик кипу купи, а то придет бомбардир из Бранденбурга — бомбами забомбардирует за то, что некто чернорылый у него полдвора рылом изрыл, вырыл и подрыл; но на самом деле турка не был в деле, да и Клара-краля в то время кралась к ларю, пока Карл у Клары крал кораллы, за что Клара у Карла украла кларнет, а потом на дворе деготниковой вдовы Варвары два этих вора дрова воровали; но грех — не смех — не уложить в орех: о Кларе с Карлом во мраке все раки шумели в драке, — вот и не до бомбардира ворам было, но и не до деготниковой вдовы, и не до деготниковых детей; зато рассердившаяся вдова убрала в сарай дрова: раз дрова, два дрова, три дрова — не вместились все дрова, и два дровосека, два дровокола-дроворуба для расчувствовавшейся Варвары выдворили дрова вширь двора обратно на дровяной двор, где цапля чахла, цапля сохла, цапля сдохла; цыпленок же цапли цепко цеплялся за цепь; молодец против овец, а против молодца сам овца, которой носит Сеня сено в сани, потом везет Сенька Соньку с Санькой на санках: санки — скок, Сеньку — в бок, Соньку — в лоб, все — в сугроб, а Сашка только шапкой шишки сшиб, затем по шоссе Саша пошел, саше на шоссе Саша нашел; Сонька же — Сашкина подружка шла по шоссе и сосала сушку, да притом у Соньки-вертушки во рту еще и три ватрушки — аккурат в медовик, но ей не до медовика — Сонька и с ватрушками во рту пономаря перепономарит, — перевыпономарит: жужжит, как жужелица, жужжит, да кружится: была у Фрола — Фролу на Лавра наврала, пойдет к Лавру на Фрола Лавру наврет, что — вахмистр с вахмистршей, ротмистр с ротмистршей, у ужа — ужата, у ежа — ежата, а у него высокопоставленный гость унес трость, и вскоре опять пять ребят съели пять опят с полчетвертью четверика чечевицы без червоточины, да тысячу шестьсот шестьдесят шесть пирогов с творогом из сыворотки из-под простокваши, — о всем о том около кола колокола звоном раззванивали, да так, что даже Константин — зальцбуржский бесперспективняк из-под бронетранспортера констатировал: как все колокола не переколоколовать, не перевыколоколовать, так и всех скороговорок не перескороговорить, не перевыскороговорить; но попытка — не пытка.";
$typed_text="В четверг четвертого числа в тыре с чтвертью часа лигурийский регулировщик регулировал в Лигурии, но тридцать три корабля лавировали, лавировали, да так и не вылавировали, и потом протокол про протокол протоколом запротоколировал, как интервьюером интервьюируемый лигурийский регулировщик речисто, да не чисто рапортовал, да не дорапортовал, дорапортовывал, да так зарапортовался про размокропогодившуюся погоду, что дабы инцидент не стал претендентом на судебный прецедент, лигурийский регулировщик акклиматизировался в неконституционном Константинополе, где хохлатые хохотушки хохотом хохотали и кричали турке, который начерно обкурен трубкой: не кури, турка, трубку, купи лучше кипу пик, лучше пик кипу купи, а то придет бомбардир из Бранденбурга — бомбами забомбардирует за то, что некто чернорылый у него полдвора рылом изрыл, вырыл и подрыл; но на самом деле турка не был в деле, да и Клара-краля в то время кралась к ларю, пока Карл у Клары крал кораллы, за что Клара у Карла украла кларнет, а потом на дворе деготниковой вдовы Варвары два этих вора дрова воровали; но грех — не смех — не уложить в орех: о Кларе с Карлом во мраке все раки шумели в драке, — вот и не до бомбардира ворам было, но и не до деготниковой вдовы, и не до деготниковых детей; зато рассердившаяся вдова убрала в сарай дрова: раз дрова, два дрова, три дрова — не вместились все дрова, и два дровосека, два дровокола-дроворуба для расчувствовавшейся Варвары выдворили дрова вширь двора обратно на дровяной двор, где цапля чахла, цапля сохла, цапля сдохла; цыпленок же цапли цепко цеплялся за цепь; молодец против овец, а против молодца сам овца, которой носит Сеня сено в сани, потом везет Сенька Соньку с Санькой на санках: санки — скок, Сеньку — в бок, Соньку — в лоб, все — в сугроб, а Сашка только шапкой шишки сшиб, затем по шоссе Саша пошел, саше на шоссе Саша нашел; Сонька же — Сашкина подружка шла по шоссе и сосала сушку, да притом у Соньки-вертушки во рту еще и три ватрушки — аккурат в медовик, но ей не до медовика — Сонька и с ватрушками во рту пономаря перепономарит, — перевыпономарит: жужжит, как жужелица, жужжит, да кружится: была у Фрола — Фролу на Лавра наврала, пойдет к Лавру на Фрола Лавру наврет, что — вахмистр с вахмистршей, ротмистр с ротмистршей, у ужа — ужата, у ежа — ежата, а у него высокопоставленный гость унес трость, и вскоре опять пять ребят съели пять опят с полчетвертью четверика чечевицы без червоточины, да тысячу шестьсот шестьдесят шесть пирогов с творогом из сыворотки из-под простокваши, — о всем о том около кола колокола звоном раззванивали, да так, что даже Константин — зальцбуржский бесперспективняк из-под бронетранспортера констатировал: как все колокола не переколоколовать, не перевыколоколовать, так и всех скороговорок не перескороговорить, не перевыскороговорить; но попытка не пытка.";
similar_text($typed_text, $source_text, $diff);
echo $diff."n"; echo memory_get_usage();
?> результат выполнения: 99.892964873017 345584 где первое число − это похожесть текста в процентах, а второе − объём использованной памяти в байтах. О, назревают серьёзные изменения!
|
Переборыч
|
Сообщение #1359
29 октября 2017 в 14:58
|
Клавомеханик-Организатор событий
55 |
MMMAAANNN писал(а): Переборыч, для того чтобы оптимизировать алгоритм, нужно видеть его текущую реализацию. Можешь показать? У меня есть пару идей... Да, отличные идейки, на следующей неделе подготовлю всё необходимое и забацаю темку, где выложу текущий код, и можно будет обмозговать и потестировать варианты.
|
MMMAAANNN
|
Сообщение #1360
30 октября 2017 в 01:16
|
Супермен
36 |
Я кстати поддерживаю варианты опытного пыхщика унча выше - если проблема решается встроенными средствами, значит нужно их использовать - потому как они практически всегда будут гораздо лучше оптимизированы, чем любой наш наколенный пхпшный код (кстати встроенный левенштайн тоже существует - но там вроде как ограничение 255 символов и это просто левенштайн, а не дамерау-левенштайн, если я правильно понял).
А также неистово плюсую пересмотр самой парадигмы квалификации - в текущей реализации это фактически ни рыба ни мясо. Ее либо надо делать сугубо вспомогательным режимом, который не влияет на статистику напрямую (типа прошлой капчи), либо выделять в отдельный режим - записывать результаты вперемешку с неквалификационными категорически не комильфо, и в этом странном виде оно существует уже много лет, увы. Я бы выделил эту проблему как одну из главных проблем на сайте сегодня - важнее чем машинки и картинки и новые ранги и вот это ваше все.
|
Лень
|
Сообщение #1361
30 октября 2017 в 06:10
|
Кибергонщик
80 |
Переборыч, верни допы! Я предлагаю такой вариант. Допы вернуть, а задачу дня сделать в виде рекомендации. Типа высвечивается "сегодня рекомендуем вам проехать такие-то словари". Будет ок
|
Deda61
|
Сообщение #1362
30 октября 2017 в 08:09
|
Профи
59 |
Не понял, а разве задача дня (для меня самая важная функция клавогонок), не приятный бонус? Хочешь сказать, что это было по уставу? Я просто не знаю, - ни разу не пропускал, так как это помогает ежедневно стимулировать мою отсутствующую мотивацию. А она оказывается была ... обязательной!!! Ну как после этого относиться к энтропии?!!
|
Игрок3
|
Сообщение #1363
30 октября 2017 в 09:36
|
Организатор событий
32 |
ябвдул писал(а): Переборыч, верни допы! Я предлагаю такой вариант. Допы вернуть, а задачу дня сделать в виде рекомендации. Типа высвечивается "сегодня рекомендуем вам проехать такие-то словари". Будет ок Против. Я пришёл на КГ уже после появления ЗД. Меня она устраивает. Здесь будет борьба старожилов и новых игроков!
|
Переборыч
|
Сообщение #1364
30 октября 2017 в 11:54
|
Клавомеханик-Организатор событий
55 |
ябвдул писал(а): Я предлагаю такой вариант. Допы вернуть, а задачу дня сделать в виде рекомендации. 300 за допы + в среднем 600 за задачу = многовато получится. Нужно изобретать и разрабатывать грамотное совмещение. Вариант: альтернативная задача 100 заездов в стандартных режимах засчитывается за прохождение, - интересует? Последний раз отредактировано 30 октября 2017 в 11:55 модератором Переборыч
|
ДядяСаша
|
Сообщение #1365
30 октября 2017 в 12:01
|
Маньяк
48 |
Считаю, что задача дня не должна быть столь продолжительной т.е. 20-40 заездов. Это много! Предлагаю урезать ее максимум до 10 заездов и оставить как есть. Как разминка и реклама словарей отлично катит. По поводу очков, оставить как есть.
|
Novatin
|
Сообщение #1366
30 октября 2017 в 13:01
|
Маньяк
88 |
AlexZP писал(а): Считаю, что задача дня не должна быть столь продолжительной т.е. 20-40 заездов. Это много! Во-во, особенно, как вчерашняя задача"на мели мы налима лениво ловили и меняли налима вы мне на линя о любви не меня ли вы мило молили и в туманы лимана манили меня". В ней 3 варианта и они идентичны! "Не хочешь, не набирай, это всё понятно." Но достижение на 180 дней никто не отменял. Вот я и проехал вчера 3 раза из 40! Мне реально надоело! В той же "Соточке" варианты генерируются, хоть 100 раз можно проехать, а тут безысходно-безудержная ловля налима и обменивание его на линя. Почему задачи не сделать разнообразными? В субботу, если мне не изменяет память - 4-5 книг всегда. Их набирать интересно. Не нравится одна - набирай другую. А в некоторые дни бывают такие словари, что вот хоть упрись, но сиди и делай. И сидишь реально 1 час, или минут 50 набираешь текст. Наберёшь там всякие скобки, цифры или большие "Й" со скоростью 189 знаков, а над тобой ещё подстебутся табличкой - "Пора учиться набирать 10 пальцами, лошара. Что это за смешные 189 знаков?"
|
Novatin
|
Сообщение #1367
30 октября 2017 в 13:05
|
Маньяк
88 |
А каково новичку выполнить 9 или 12, сколько там заездов в безошибке? Он и ехать-то не умеет толком, в кнопках путается. А ему говорят - не больше 1 ошибки.
|
Переборыч
|
Сообщение #1368
30 октября 2017 в 13:51
|
Клавомеханик-Организатор событий
55 |
К Безошибке в задаче всегда предлагается альтернативный словарь. Это делается не конкретно для Новичков, а для кривотыков любого ранга.
|
Novatin
|
Сообщение #1369
30 октября 2017 в 14:02
|
Маньяк
88 |
Переборыч писал(а): К Безошибке в задаче всегда предлагается альтернативный словарь. Я предполагал, что про это кто-то напишет. Конечно же, я знаю про альтернативу. Но альтернатива Безошибке очень часто - это какой-нибудь "налим". Как говорится, хрен редьки не слаще. Как-то в один день была, как сейчас помню, восьмисоточка какая-то убойная. Либо её надо было набирать со скоростью 220-240 знаков (при моей средней грубо в 300), либо Безошибку. Вопрос в целом концептуальный. Немного не в тему. Ещё очень бы хотелось услышать ответ от Клавомехаников на вопрос, поднятый в этом посте про попадание в чужие заезды в книге. Последний раз отредактировано 30 октября 2017 в 14:05 пользователем Novatin
|
Лень
|
Сообщение #1370
30 октября 2017 в 14:08
|
Кибергонщик
80 |
Переборыч писал(а): ябвдул писал(а): Я предлагаю такой вариант. Допы вернуть, а задачу дня сделать в виде рекомендации. 300 за допы + в среднем 600 за задачу = многовато получится. Нужно изобретать и разрабатывать грамотное совмещение. Вариант: альтернативная задача 100 заездов в стандартных режимах засчитывается за прохождение, - интересует? я говорю не допы + очки за задачу, а просто фиксированные допы на день, как раньше было. Например допы до 600 увеличить, а задачу как я и говорил - в виде рекомендации. человек катает то, что хочет - допы добавляются, выполняет задачу - те же допы добавляются. Хочет и то, и другое - те же допы идут. Если кому-то там хочется бесполезных ачивок за непрерывную серию - так они и останутся. Последний раз отредактировано 30 октября 2017 в 14:13 пользователем Лень
|
Переборыч
|
Сообщение #1371
30 октября 2017 в 14:15
|
Клавомеханик-Организатор событий
55 |
ябвдул писал(а): задачу дня сделать в виде рекомендации Рекомендация = задача дня без награды?
|
Лень
|
Сообщение #1372
30 октября 2017 в 14:29
|
Кибергонщик
80 |
наградой будут выкатанные за день допы.
|
Игрок3
|
Сообщение #1373
30 октября 2017 в 14:37
|
Организатор событий
32 |
ябвдул писал(а): наградой будут выкатанные за день допы. Нет, задача дня - особенна. К тому же, она подстегивает интерес к разным мероприятиям. (В пятницу - БО, во время Абра-турнира - абракадабра. Последний раз отредактировано 30 октября 2017 в 14:37 пользователем Игрок3
|
carmero
|
Сообщение #1374
30 октября 2017 в 19:31
|
Маньяк
51 |
Переборыч из вредности не даёт "Обычный in English" по вторникам...
|