Страницы: 1 2 3 След.
RSS
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Мое почтение, джентльмены.
Хочу понять будет ли профит и какой.
Давайте для начала рассмотрим какое либо простое решение на VBA, что бы я переложил в XLL и сравним результаты.
Если результат порадует, можно будет переложить в XLL что-то нужное для всех. Будет копилочка быстрых решений для форума (если будет время и интерес).
«Бритва Оккама» или «Принцип Калашникова»?
 
Виталий, привет.
О каких задачах комбинаторики речь?
Будут ли задействованы потоки при решении задач, нужно ли прописывать потоки алгоритмически или можно использовать встроенные оптимизаторы?

Мне интересно переложить на C++ и прикрутить решение к VBA:
Задачу линейного раскроя, алгоритмы перебора и линейное программирование
Задачу коммивояжера, особенно интересует как прикрутить k-opt оптимизацию, или LKH алгоритм
Реализовать Алгоритм Дейкстры (или другой алгоритм для нахождения кратчайших путей в графе), на сколько будет быстрее решать

Все реализации на VBA у меня есть

На форуме были задачки по кластеризации (k-means), Было бы интересно посмотреть скорость решения через XLL.

Из простого, можно начать с: сочетания, перестановки, размещения
Изменено: MCH - 04.12.2020 16:43:47
 
Михаил, привет!
Думал начать с подбора слагаемых под нужную сумму. Где-то даже использовал твое решение от 2013 года (методом brute force). Вроде как полезная вещь.
Начать с простого алгоритма, но ресурсоемкого.
Потоки можно подключить на втором этапе, потому как будет нечестное сравнение с VBA (но обязательно используем в итоге).
Пока не знаю, нужно ли прописывать потоки алгоритмически. Думаю да, если это не циклические операции друг от друга не зависящие. Запустим в разных потоках сами, без изменения алгоритма.
Цитата
MCH написал:
Задачу коммивояжера, особенно интересует как прикрутить k-opt оптимизацию, или  LKH алгоритм Реализовать Алгоритм Дейкстры
сознаюсь честно, далек от этого, потому и попросил спецов помочь с выбором.
Алгоритмы серьезные, разве нет уже готовых библиотек (что бы велик не изобретать)? Даже я о них уже не раз слышал (не вникая в суть).
Т.е. вижу 2 пути:
1.Создать что-то свое, чего еще нет по каким либо причинам (мелкий масштаб проблемы)
2.Использовать сторонние наработки/библиотеки

В итоге может получится и третий вариант - смешанный.

Начнем с 1го?

Цитата
MCH написал:
Из простого, можно начать с:  сочетания, перестановки, размещения
протестировал, у меня работает настолько быстро, что нет целесообразности переходить на С++ :) Надо что-то вычислительноемкое.
Есть алгоритм просто полного перебора слагаемых под нужную сумму, без отсечения заведомо нереализуемых вариантов и т.д. просто в лоб, что бы поменьше перекодировать (для простоты - по целым числам)?
Изменено: bedvit - 04.12.2020 18:06:18
«Бритва Оккама» или «Принцип Калашникова»?
 
Доброе время суток
Цитата
bedvit написал:
без отсечения заведомо нереализуемых вариантов и т.д. просто в лоб
Виталий, а смыл такой реализовывать? Чем обычный алгоритм рюкзака не подходит? Всяко разно N*M, где N сумма в целых числах, а M - количество слагаемых. Если ограничиться любой первой комбинацией, то по памяти будет всего N элементов массива.
 
Андрей привет! Согласен. Просто хотел начать с коротких алгоритмов, что бы не перекладывать алгоритм днями (сам знаешь времени нет свободного). Интересно просто. Можно и задачу о рюкзаке подключить. Просто подбор слагаемых в чем интерес - сам сталкивался с такой необходимостью, на больших количествах VBA не вытягивал
«Бритва Оккама» или «Принцип Калашникова»?
 
bedvit, если нужен частный случай, то есть задача "Раскрой арматуры"
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Цитата
Jack Famous написал:
есть задача " Раскрой арматуры "
Есть еще более глобальная задача - распил бюджета, но с ней справляются без С++, VBA и думаю , без Excel и без нас.
По вопросам из тем форума, личку не читаю.
 
Можно что-нибудь и по проще, например, просто подбор суммы минимумом слагаемых один вариант. В 365 стало удобно, можно Udf-функцию, возвращающую массив, вводить только в одну ячейку, Excel сам динамически её распространяет.
 
Задача по генерации оптимальных схем раскроя
Здесь и подбор слагаемых и перебор и ограничение ненужных вариантов. При этом кода не очень много
Для ускорения отключил вывод результата на лист, оставил только генерацию и подсчет количества вариантов

Например, со всеми простыми тестами VBA справляется достаточно хорошо, кроме последнего, где генерируется более 5 млн вариантов и времени требуется значительно больше.
Можно конечно перенести во FreeBasic, считать будет не намного медленнее, чем С++, но преимущество XLL подкупает.

Если получится максимально перенести вычислительные процессы в XLL, то можно реализовать достаточно быстрый алгоритм раскроя, а Excel будет только оболочкой для ввода/вывода информации.
 
Андрей, Михаил спасибо, попробуем перенести в XLL. 365 офиса нет, жаль не могу посмотреть, но могу сделать формулу массива, протестируем. Вариант с формулой массива тоже интересен, но теперь я не привязан к udf, научился пользоваться СОМ-интерфейсом Excel из XLL. Теперь могу просто выгрузить на лист данные. Могу конечно и udf - формулой массива. Что будет удобнее под задачу.
«Бритва Оккама» или «Принцип Калашникова»?
 
Появилось немного времени, перевел пока решения Андрея на С++
код на VBA
Скрытый текст

Код на С++
Скрытый текст


Файл пример прилагаю.
тест для VBA - кнопка в файле
тест для XLL - открываем XLL - кнопка "XLL Find Summands " на панели "Надстройки" (так же при первом активном листе - перезаписывает столбец "С")

Результаты:
VBA - 1325 миллисекунд
XLL - 50 миллисекунд

Быстрее в 26 раз на одном и том же алгоритме.
Прошу протестировать, каков результату вас?

XLL как всегда здесь.
Изменено: bedvit - 07.12.2020 13:49:11
«Бритва Оккама» или «Принцип Калашникова»?
 
Андрей, посмотри пример (прилагаю). Алгоритм явно неправильно отрабатывает. Ищу сумму "53263", а получаю "50653".

Цитата
MCH написал:
или  LKH алгоритм
Михаил, скачал исходники, глянул. Много кода, много модулей, если есть примеры, как использовать, можно подключить к решению наших задач.
Посмотрел "Генератор схем раскроя2" - там несколько листов. Нужно начать с тех областей, где VBA плохо справляется. Здесь посложнее для перевода, чем код от Андрея, т.к. есть собственные типы данных/переменных и Excel - функции, которые надо будет чет-то заменить (если будут аналоги в С++)
Уникальные особенности языка, функции, конвертация типов т.к. в другом может не быть, что сложнее к переводу.
Изменено: bedvit - 07.12.2020 14:25:40
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
bedvit написал:
Алгоритм явно неправильно отрабатывает. Ищу сумму "53263", а получаю "50653"
Сделал свою функция поиска слагаемых
на вход даем массив слагаемых, а также минимальную и максимальную требуемую сумму, на выходе формирует массив индексов слагаемых, и возвращает полученную сумму
Если удается найти сумму от МИН до МАКС, то возвращает первую найденную сумму из диапазона, если не удается найти - то ближайший найденный результат.
Изменено: MCH - 07.12.2020 15:36:07
 
Михаил, переношу в XLL или будут еще тесты и оптимизация?
Видел реализацию для чисел с плавающей точкой, с задаваемой погрешностью/точностью.
Но это всего лишь умножение на нужную величину и опять можно считать в целых. Или я упускаю и лучше считать с плавающей точкой?
Вообщем, главное мы определили - профит есть!, а т.к. времени мало и хочется использовать и для себя и для форума наиболее оптимальный алгоритм подбора/поиска слагаемых, без тестирования разных алгоритмов в xll (накладно это по времени переноса кода) - хочу перенести победителя зрительских симпатий и тайминга :)

Пользовался когда-то таким, твоим:
Скрытый текст

Вообщем, если народу будет интересно, готов нарисовать форму на winapi, где можно будет задать несколько параметров под алгоритм, если такой функционал не нужен, сделаю простой - через InputBox (диапазон, сумма), с точностью до копеек (умножим на 100)
Изменено: bedvit - 07.12.2020 18:19:38
«Бритва Оккама» или «Принцип Калашникова»?
 
Немного доработал макрос поиска слагаемых:
Может работать с копейками, все числа умножаются на 100 и округляется до целых чисел
Для ускорения работы затем все числа делятся на НОД (наибольший общий делитель)

На VBA большие числа уже заметно долго считает
 
Михаил, посмотрел, здорово! немного подредактировал макрос, для возможности понять, какие позиции попали в выборку, иногда это очень важно, к примеру отгрузка по штрихкодам и отобрать нужные.
Скрытый текст

Для чего функция "GCD"? Почему бы просто не умножить на 100, зачем НОД, в чем профит такого действия?
Изменено: bedvit - 08.12.2020 12:58:52
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
bedvit написал:
Для чего функция "GCD"? Почему бы просто не умножить на 100, зачем НОД, в чем профит такого действия?
функция GCD  это и есть НОД алгоритмом Евклида

Сложность алгоритма нахождения слагаемых под нужную сумму динамическим программированием - N*M, где N -кол-во слагаемых, M - искомая сумма, и памяти выделяем M
Если все числа умножить на 100, то мы сразу замедляем алгоритм в 100 раз, поэтому, если все полученные числа кратны какому нибудь числу (2, 5, 10, 100 и т.п.), то нужно сократить их на наибольший общий делитель, тем самым в ряде случаев может получится более быстрое решение.
Так для целых чисел, после умножения их на 100, обратно сокращаем на те же 100, и скорость решения остается без изменения
Изменено: MCH - 08.12.2020 13:30:45
 
Цитата
MCH написал:
100, то мы сразу замедляем алгоритм в 100 раз,
вот здесь не понял, разве для ЦП есть разница складывать 100 или 10000? Все равно арифметика идет с машинным словом, это 64 бита. Нет?
«Бритва Оккама» или «Принцип Калашникова»?
 
Сам алгоритм суммы подмножеств/рюкзака динамическим программированием основан на создании массива размерностью равной искомой сумме и его перебору по всем слагаемым, отсюда и ограничения: целочисленность данных и ограничение в размере искомой суммы (ограничено возможной выделяемой памятью).
Если решать грубой силой (переборами), то разницы нет, целые числа или дробные, большие или маленькие, ограничение в решении связано с вариативностью и нехваткой времени на перебор всех вариантов.
 
Если перебором по отсортированном у массиву, с отсечением не быстрее будет на больших суммах? Какие ограничения у этих двух алгоритмов? Что целесообразнее?
Увеличил все суммы на 10 тыс.руб., поиск увеличился с 7 сек до 156.
Хорошобы понять, где "алгоритм суммы подмножеств/рюкзака динамическим программированием" пересекается с перебором по отсортированному списку с отсечением (возможно есть более оптимальные варианты перебора). Коллеги, что скажите?
Изменено: bedvit - 08.12.2020 15:08:24
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
bedvit написал:
Какие ограничения у этих двух алгоритмов? Что целесообразнее?
Если искомая сумма мала - до 10 000 (или до 1 млн) то динамическое программирование будет быстро находить решение при большом количестве слагаемых.
Если слагаемых несколько десятков и сумма может быть найдена в пределах десятка слагаемых - то перебором с МВиГ (метод ветвей и границ)

Предпочтительно начинать с динамического программирования, если искомая сумма большая, то пытаемся перебором, но ограничиваем решение по времени с выводом наилучшего найденного результата.
Либо эвристические алгоритмы типа "жадного" с различными его вариациями, с добавлением переборов.
 
Ок, начну тогда с динамического. Сможешь в одну процедуру все внести, по функциям неудобно разбивать при переводе. Одним блоком проще. И думаю сделать для целых (не будем перемножать, раз так скорость падает), кому нужно умножат на 100 или 10000 (какую точность захотят), или оставим с копейками? какие соображения?
Изменено: bedvit - 08.12.2020 15:39:47
«Бритва Оккама» или «Принцип Калашникова»?
 
bedvit, мне всегда целых хватало. Если надо, то самому перемножить не является проблемой. С другой стороны, цикл по всем слагаемым с поверкой на целочисленность и последующим умножением до целочисленного при необходимости, не должна занять много времени
А уж если будет считать долго, так оно в любом случае так будет, но пользователю мороки меньше
Можно сообщение выводить с предупреждением о длительности - в общем, проблем не вижу
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Тест нахождения слагаемых под нужную сумму, по алгоритму динамического программирования.
Поиск 2 тыс. слагаемых на 3 млн. рублей.

Код VBA
Скрытый текст


Код С++
Скрытый текст


Тайминги:
VBA - 137 сек.
XLL - 4 сек.

Более чем в 30 раз быстрее на одном и том же алгоритме.
Тестируйте (xll обновил на ресурсе)

upd:
Поиск 2 тыс. слагаемых на 13 млн. рублей.
VBA - 643,8 сек.
XLL - 19 сек.

В 33 раза быстрее.

Размялись, а теперь можно попробовать распараллелить алгоритм и запустить на 8 ядрах :)
Изменено: bedvit - 09.12.2020 18:00:52
«Бритва Оккама» или «Принцип Калашникова»?
 
Идеи для ускорения алгоритма поиска слагаемых:
1. Думаю, что алгоритм легко разбить на потоки, в каждом потоке делаем цикл по слагаемым:
Код
For i = НомерПотока To n Step Кол-воПотоков

массивы arr(), arrIndex() - глобальные
При нахождения результата в одном из потоков заканчиваем расчеты по флагу во всех других потоках
Соответственно нужно разграничить одновременный доступ к глобальному массиву arrIndex()

2. Разбить алгоритм поиска слагаемых на два алгоритма:
Тот что есть - поиск слагаемых для суммы не превышающих исходную
и другой - поиск слагаемых не менее искомой суммы
В данном случае если искомая сумма больше половины суммы всех слагаемых, то лучше найти те числа, который нужно исключить из общего списка, это может дать значительное ускорение при поиске больших сумм (существенно больших половины суммы всех слагаемых).
Изменено: MCH - 10.12.2020 09:47:46
 
Цитата
MCH написал:
Думаю, что алгоритм легко разбить на потоки, в каждом потоке делаем цикл по слагаемым
не взлетает, наверное  есть и другие зависимопотоковые данные, например переменная "К"? При нескольких потоках она другая. Возможно играет роль очередность заполнения arrIndex
По второй части, не проще ли прибавить к уже найденной сумме, минимальное число из исходного массива?
Изменено: bedvit - 10.12.2020 13:41:31
«Бритва Оккама» или «Принцип Калашникова»?
 
Виталий, внеси небольшие правки в код на VBA, ну и на C++
см. строки 41-46 и 51
Скрытый текст

Сокращение времени расчета при поиске суммы близкой к сумме всех слагаемых более чем в 1,5 раза

А еще можно что то типа очереди или стека придумать (добавив еще один массив) и тогда должно еще быстрее считать, т.к. будут пропускаться часть операций по проверке массива
Изменено: MCH - 10.12.2020 14:11:16
 
Цитата
bedvit написал:
не взлетает, наверное  есть и другие зависимопотоковые данные, например переменная "К"?
ну k в каждом потоке должна быть локальной, а при нахождении решения присваиваем ее значение глобальной переменной
Попробую на freebasic сделать с потоками
 
вот на С++, тестовая версия (с одним потоком работает, с 8 нет)
Скрытый текст

здесь через массив arrK, где каждый поток записывает найденное К, а далее смотрим, найдено ли решение.
И создаю потоки, если данных более 24 строк (настраивается). Зачем затрачивать ресурсы на создание потоков, если данных мало.
Так же добавил, при отсутствии точного решения, вывод найденных слагаемых, меньше задаваемой суммы.

Цитата
MCH написал:
А еще можно что то типа очереди или стека придумать (добавив еще один массив) и тогда должно еще быстрее считать, т.к. будут пропускаться часть операций по проверке массива
Пока не пойму куда это нужно добавить.
Изменено: bedvit - 10.12.2020 14:34:38
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
bedvit написал:
Пока не пойму куда это нужно добавить.
Решение через очередь/стек - небольшой прирост производительности на поиске больших сумм

UPD: При использовании очереди уже нет такой острой необходимости по сокращению значений на НОД, исключительно только для сокращения выделяемой памяти, на скорость решения не должно сильно влиять.
Изменено: MCH - 10.12.2020 15:38:57
Страницы: 1 2 3 След.
Наверх