|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Здравствуйте. Прошу помощи в решении задачи с математическим уклоном. Дано: A – последовательность значений, N – количество. Найти: все группы из N элементов последовательности A; порядок элементов в группе должен совпадать c последовательностью A. Например: A = (1, 2, 3, 4), N = 3. Ответ – 4 группы: 123, 234, 124, 134. Решение нашел, но медленное. Сделал перебор всех вариантов через двоичные числа. Скорость никакая, если значений много. Например, если в последовательности 1000 элементов, а N = 10, то очень медленно. Надеюсь, математики подскажут правильный подход. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 01:29 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Сын вождяНапример, если в последовательности 1000 элементов, а N = 10, то очень медленно.Ну да, всего-то ~3*10^23 вариантов. И чё оно тормозит, непонятно... ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 09:10 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Даже больше, =ПЕРЕСТ(1000;10) дает 9,56E+29. А перебор обычно рекурсией делается. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 09:29 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Akina...всего-то ~3*10^23 вариантов... Я как раз об этом :( Мой алгоритм, кроме искомых вариантов, перебирает кучу мусорных. Это тормозит еще больше. Ломаю голову, как перебирать только искомые варианты. Если это невозможно, то придется менять концепцию. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 09:34 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Казанский=ПЕРЕСТ =ПЕРЕСТ(4; 3) выдает 24. Что неверно, для моей задачи. Правильный ответ - 4 варианта. Не пользовался функцией ПЕРЕСТ. В ее описании сказано, что учитывается порядок. Не понял как. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 09:51 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
КазанскийДаже большеУ него не перестановки, а сочетания - требуется сохранять относительное местоположение элементов. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 10:04 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Да, я ошибся, это ЧИСЛКОМБ(4;3)=4, а ЧИСЛКОМБ(100;10)=1,73E+13 ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 10:08 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Сын вождякак перебирать только искомые варианты Имхо наиболее разумный вариант - рекурсивный. Схематично где-то так: Код: vbnet 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 10:12 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
КазанскийДа, я ошибся, это ЧИСЛКОМБ(4;3)=4, а ЧИСЛКОМБ(100;10)=1,73E+13У него не 100, а 1000. Так что ещё 10 порядков добавь... ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 10:14 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Да... чет не мой день сегодня... пойду домашние дела делать ) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 10:18 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Akina...где-то так... Благодарю. Буду разбираться... Akina...не 100, а 1000. Так что ещё 10 порядков добавь... По жизни, число элементов в группе будет близко к общему числу элементов. Для 1000 - от 900, для 100 - от 80... ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 10:25 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
О скорости. Вот тест-код: Код: vbnet 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30.
Среда - Excel 2007, проц Е2160 (1,8ГГц). И вывод: cnt i dTime 11 10 0 12 10 0 13 10 3.90625E-03 14 10 0.0078125 15 10 0.015625 16 10 2.734375E-02 17 10 5.078125E-02 18 10 0.09375 19 10 0.1601563 20 10 0.28125 21 10 0.4726563 22 10 0.7695313 23 10 1.25 24 10 1.972656 25 10 3.082031 26 10 4.707031 27 10 7.089844 28 10 10.48047 29 10 15.42969 30 10 22.19531 Так что 100,10, а тем более 1000,10 я бы запускать не стал... ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 10:31 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Да и 100,80 - тоже... тем более 1000,900. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 10:32 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
AkinaДа и 100,80 - тоже... тем более 1000,900. Да, я уже глянул число комбинаций :( Оптимизация этого алгоритма - почти глухой номер. Благодарю, просветили :) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 10:44 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Сын вождяДа, я уже глянул число комбинаций :( Оптимизация этого алгоритма - почти глухой номер. Это говорит о неправильном подходе. Не проведён предварительный анализ и не определены дополнительные условия отсечения. Перебор же (любой!) - это тупик, тогда как при правильных доп. ограничениях и бОльшие количества обрабатываются за вменяемое время. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2015, 10:49 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Какова конечная задача? Может найдутся другие алгоритмы, а не полный перебор всех сочетаний? ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2015, 22:54 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Задача: найти похожие параграфы в Word. Видел готовые решения для сравнения строк. Правда адаптации для Word не встречал. Изучил предлагаемые алгоритмы. Но интересно же сделать самому :) Да и в Word и в его макросах есть своя специфика. Планировал этот алгоритм использовать для побуквенного сравнения. Но так даже два параграфа не сравнить :) Попробую сделать через отсев, ну и сравнивать надо без перебора - одним проходом. ... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2015, 05:48 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Сын вождяЗадача: найти похожие параграфы в Word. Видел готовые решения для сравнения строк. Правда адаптации для Word не встречал. Изучил предлагаемые алгоритмы. Но интересно же сделать самому :) Да и в Word и в его макросах есть своя специфика. Планировал этот алгоритм использовать для побуквенного сравнения. Но так даже два параграфа не сравнить :) Попробую сделать через отсев, ну и сравнивать надо без перебора - одним проходом. А каковы критерии похожести? С этого надо ИМХО начинать решение задачи:). И в качестве бредовой идеи в рамках мозгового штурма - брать два параграфа, переводить в один регистр, убирать знаки препинания, обеспечить разделение слов одиночными пробелами, выгружать в текстовые файлы, обрабатывать эти файлы встроенной shell'овской утилитой fc (file compare) и затем анализировать результаты ее работы. ... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2015, 09:45 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
uuxА каковы критерии похожести? С этого надо ИМХО начинать решение задачи:) Я и не ставил сразу такую задачу :) Похожими считаем строки, которые отличаются определенным числом знаков. То есть: одни знаки заменены другими, вставлены лишние знаки, удалены отдельные знаки. uux...брать два параграфа, переводить в один регистр, убирать знаки препинания, обеспечить разделение слов одиночными пробелами... Это уже реализовал. Сейчас пытаюсь оптимизировать сравнение двух строк. uux...выгружать в текстовые файлы, обрабатывать эти файлы встроенной shell'овской утилитой fc (file compare) и затем анализировать результаты ее работы. Почитал про Diff. Алгоритм как раз такой, какой нужен. Только задача найти похожие абзацы для каждого абзаца документа. Значит, придется в цикле обрабатывать связку: файл1 - все абзацы документа, очищенные от мусора; файл2 - текущий проверяемый абзац, размноженный до количества абзацев в файл1, чтобы сравнить его со всеми. ... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2015, 10:39 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Если по науке, то хочу написать макрос вычисления наибольшей общей подпоследовательности для двух строк. ... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2015, 10:58 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Этап полного перебора уже прошел :) Перешел к методу динамического программирования :) ... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2015, 11:01 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Сын вождяПохожими считаем строки, которые отличаются определенным числом знаковя в свое время делал такой алгоритм сравнения строк (искал в прайс-листе совпадающие товары, написанные иначе, в том числе с перестановкой слов): сравниваемые строки сжимались (удалялись пробелы и спецсимволы, в случае литературного текста имеет смысл удалить знаки препинания или вообще только буквы оставить) исходная строка разбивалась на перекрывающиеся тройки символов, то есть для строки Код: plaintext
Код: plaintext
каждая тройка искалась во второй строке вычислялся коэффициент попадания (полностью одинаковые строки давали 1, отсутствие совпадений троек - 0) алгоритм не очень быстрый, но скорости хватало ... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2015, 11:05 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Идея с триграммами правильная. Возможно для абзацев стоит делать триграмы по словам. Далее триграмы нужно прохешировать и построить минхеши чтобы вычислить похожесть. ... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2015, 13:19 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
fixxerИдея с триграммами правильнаяспасибо, это была полностью моя собственная идея зеленого еще программиста, в изучение существующих математические методов я тогда не полез, да и интернет был еще молод ))) ... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2015, 13:24 |
|
Быстрый алгоритм для математической задачи
|
|||
---|---|---|---|
#18+
Пока остановился на таком алгоритме: 1. Первый этап - ищу пару абзацев с похожими наборами знаков. Например, "1234" и "4321". 2. Второй этап - для найденной пары, вычисляю максимальную общую последовательность знаков. Наример, для "1234" и "4123" это "123". Довольно быстро работает, по сровнению с начальным вариантом :) ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2015, 10:35 |
|
|
start [/forum/topic.php?fid=60&msg=38924585&tid=2155985]: |
0ms |
get settings: |
8ms |
get forum list: |
13ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
40ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
53ms |
get tp. blocked users: |
1ms |
others: | 15ms |
total: | 146ms |
0 / 0 |