Поиск  Пользователи  Правила 
Закрыть
Логин:
Пароль:
Забыли свой пароль?
Регистрация
Войти
 
Выбрать дату в календареВыбрать дату в календаре

Страницы: 1 2 3 4 5 6 7 8 9 10 11 ... 124 След.
Алгоритмы. Игры. Сортировка объектов по контейнерам
 
Какие ограничения в игре?
Чему равно N? сколько всего колб максимально? сколько различных цветов?
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Все таки C++ обгоняет FB, если в 32bit это не так заметно, то в 64bit разница ярко выражена, может быть разница в компиляторах и оптимизации кода
Разбить число на количество единиц.
 
Код
=ЛЕВСИМВ(ПОВТОР("1;";A1);A1*2-1)

Код
=ПОВТОР("1;";A1-1)&1
Изменено: MCH - 24 дек 2020 14:26:07
Количество контейнеров каждого типа для размещения набора деталей
 
Рабочая демоверсия есть здесь: http://www.excelworld.ru/forum/3-21304-1
Количество контейнеров каждого типа для размещения набора деталей
 
Одно из решений
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Интересен результат.
XLL 32бит - 9,9 сек
XLL 64бит - не запускается т.к. система 64, Excel 32
FB 32 бит - 10,5 сек 8,9 сек
FB 64 бит - 4,9 сек 3,9 сек

Виталий, протестируй код на FreeBasic на своем компьютере, сопоставима будет скорость с C++? Я немного скорректировал код.
Изменено: MCH - 12 дек 2020 09:42:40
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Вариант на FreeBasic
Все данные находятся в txt файле, после решения результат сохраняется также в txt
У меня версия 64бит считает 5 секунд 3-4 сек
XLL не тестировал, не разобрался еще как это сделать

UPD: файл обновил
Изменено: MCH - 12 дек 2020 09:39:17
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
На тестовом стенде (ранее выложенный файл) - 2 сек
У меня FreeBasic считает значительно дольше 2х секунд
Выложить реализацию на FreeBasic в 1 поток для теста?
Изменено: MCH - 11 дек 2020 16:13:13
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Пока с потоками не получается сделать, видимо сама концепция разделения на параллельные вычисления не правильная, подумаю еще
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Михаил, что быстрее стек или предыдущее изменения?
У меня получается стек немного быстрее и он не требует сокращения на НОД, но нужно выделять больше памяти

Цитата
bedvit написал:
Я так понимаю со стеком  - это под вопросом (важна очередность)?
Стек разделять на потоки наверное сложнее, т.к. потоки должны работать с одним и тем же стеком, будут конфликты между потоками

Цитата
bedvit написал:
На freebasic не получилось с потоками сделать? у меня здесь вопросы есть.
Пока нет времени, может вечером получится набросать

Хочу немного изменить ввод и вывод данных
на входе размер слагаемого и кол-во (по умолчанию кол-во = 1)
на выходе порядковый номер слагаемого и их кол-во, можно выводит как в сжатом виде так и полный перечень всех слагаемых с нулевым количеством (если слагаемое не используется)
Это пригодится например в задаче раскроя
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Пока не пойму куда это нужно добавить.
Решение через очередь/стек - небольшой прирост производительности на поиске больших сумм

UPD: При использовании очереди уже нет такой острой необходимости по сокращению значений на НОД, исключительно только для сокращения выделяемой памяти, на скорость решения не должно сильно влиять.
Изменено: MCH - 10 дек 2020 15:38:57
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
не взлетает, наверное  есть и другие зависимопотоковые данные, например переменная "К"?
ну k в каждом потоке должна быть локальной, а при нахождении решения присваиваем ее значение глобальной переменной
Попробую на freebasic сделать с потоками
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Виталий, внеси небольшие правки в код на VBA, ну и на C++
см. строки 41-46 и 51
Скрытый текст

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

А еще можно что то типа очереди или стека придумать (добавив еще один массив) и тогда должно еще быстрее считать, т.к. будут пропускаться часть операций по проверке массива
Изменено: MCH - 10 дек 2020 14:11:16
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Идеи для ускорения алгоритма поиска слагаемых:
1. Думаю, что алгоритм легко разбить на потоки, в каждом потоке делаем цикл по слагаемым:
Код
For i = НомерПотока To n Step Кол-воПотоков

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

2. Разбить алгоритм поиска слагаемых на два алгоритма:
Тот что есть - поиск слагаемых для суммы не превышающих исходную
и другой - поиск слагаемых не менее искомой суммы
В данном случае если искомая сумма больше половины суммы всех слагаемых, то лучше найти те числа, который нужно исключить из общего списка, это может дать значительное ускорение при поиске больших сумм (существенно больших половины суммы всех слагаемых).
Изменено: MCH - 10 дек 2020 09:47:46
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Какие ограничения у этих двух алгоритмов? Что целесообразнее?
Если искомая сумма мала - до 10 000 (или до 1 млн) то динамическое программирование будет быстро находить решение при большом количестве слагаемых.
Если слагаемых несколько десятков и сумма может быть найдена в пределах десятка слагаемых - то перебором с МВиГ (метод ветвей и границ)

Предпочтительно начинать с динамического программирования, если искомая сумма большая, то пытаемся перебором, но ограничиваем решение по времени с выводом наилучшего найденного результата.
Либо эвристические алгоритмы типа "жадного" с различными его вариациями, с добавлением переборов.
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Сам алгоритм суммы подмножеств/рюкзака динамическим программированием основан на создании массива размерностью равной искомой сумме и его перебору по всем слагаемым, отсюда и ограничения: целочисленность данных и ограничение в размере искомой суммы (ограничено возможной выделяемой памятью).
Если решать грубой силой (переборами), то разницы нет, целые числа или дробные, большие или маленькие, ограничение в решении связано с вариативностью и нехваткой времени на перебор всех вариантов.
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Для чего функция "GCD"? Почему бы просто не умножить на 100, зачем НОД, в чем профит такого действия?
функция GCD  это и есть НОД алгоритмом Евклида

Сложность алгоритма нахождения слагаемых под нужную сумму динамическим программированием - N*M, где N -кол-во слагаемых, M - искомая сумма, и памяти выделяем M
Если все числа умножить на 100, то мы сразу замедляем алгоритм в 100 раз, поэтому, если все полученные числа кратны какому нибудь числу (2, 5, 10, 100 и т.п.), то нужно сократить их на наибольший общий делитель, тем самым в ряде случаев может получится более быстрое решение.
Так для целых чисел, после умножения их на 100, обратно сокращаем на те же 100, и скорость решения остается без изменения
Изменено: MCH - 8 дек 2020 13:30:45
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Немного доработал макрос поиска слагаемых:
Может работать с копейками, все числа умножаются на 100 и округляется до целых чисел
Для ускорения работы затем все числа делятся на НОД (наибольший общий делитель)

На VBA большие числа уже заметно долго считает
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Алгоритм явно неправильно отрабатывает. Ищу сумму "53263", а получаю "50653"
Сделал свою функция поиска слагаемых
на вход даем массив слагаемых, а также минимальную и максимальную требуемую сумму, на выходе формирует массив индексов слагаемых, и возвращает полученную сумму
Если удается найти сумму от МИН до МАКС, то возвращает первую найденную сумму из диапазона, если не удается найти - то ближайший найденный результат.
Изменено: MCH - 7 дек 2020 15:36:07
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Задача по генерации оптимальных схем раскроя
Здесь и подбор слагаемых и перебор и ограничение ненужных вариантов. При этом кода не очень много
Для ускорения отключил вывод результата на лист, оставил только генерацию и подсчет количества вариантов

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

Если получится максимально перенести вычислительные процессы в XLL, то можно реализовать достаточно быстрый алгоритм раскроя, а Excel будет только оболочкой для ввода/вывода информации.
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Виталий, привет.
О каких задачах комбинаторики речь?
Будут ли задействованы потоки при решении задач, нужно ли прописывать потоки алгоритмически или можно использовать встроенные оптимизаторы?

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

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

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

Из простого, можно начать с: сочетания, перестановки, размещения
Изменено: MCH - 4 дек 2020 16:43:47
Рассчитать усреднение по курсу валют
 
Цитата
Ирина Тихонова написал:
как посчитать средний курс с 20 числа предыдущего месяца по 19 число настоящего?
Можно использовать две методологии:
1. Брать средние значения фактически устанавливаемых курсов по торгам, публикуемые на cbr.ru, при этом среднее берется не за 30/31 день, а меньше, т.к. курс на воскресение и понедельники не устанавливается (т.к. нет торгов на бирже)
2. Брать среднее значение всех курсов, действующие на каждую дату (даже если нет торгов)

Пример во вложении.
На работе применяется вариант 1, для формульного ценообразования на сырье.
Изменено: MCH - 30 ноя 2020 13:55:28
Разнесение и подсчёт количества серий из цифр в строке, количества цифр и их сумм в заданном диапазоне
 
Цитата
Peet написал:
т.е. если в строке идёт 24245 6 7 24 - то 1 серия сумма 53 и 3 числа сумма 47
у меня получается 6 + 7 + 24 = 37, а не 47

В принципе, моя функция так и считает
Изменено: MCH - 24 ноя 2020 17:15:46
Разнесение и подсчёт количества серий из цифр в строке, количества цифр и их сумм в заданном диапазоне
 
Реализовал как понял:
Если подряд сумма часов превышает 24, то считаем ее как вариант 1, если не превышает, то как вариант2
поэтому подряд 2+2 или 3+3 это одна серия, но суммарно менее 24, возможно нужно как то иначе реализовать
Максимальные расстояния между одинаковыми знаками строки
 
Цитата
БМВ написал:
только так не лучше?
Можно еще на пару символов сократить:
Код
=МАКС(МУМНОЖ(ЕСЛИОШИБКА(ПОИСК(C$1;{0;""}&$B2;СТРОКА($2:$99)););{-1:1}))
Максимальные расстояния между одинаковыми знаками строки
 
Цитата
БМВ написал:
только так не лучше?
Наверно лучше, немного не дожал
Максимальные расстояния между одинаковыми знаками строки
 
Цитата
БМВ написал:
если не извлекать символ искомый из заголовка то естесвенно короче
да, не извлекал, а прописал в заголовках. Соответственно короче, сделал еще немного короче за счет МУМНОЖ:
Код
=МАКС(МУМНОЖ(ЕСЛИОШИБКА(ПОИСК(C$1;$B2;СТРОКА($1:$98)+{0;1})+{1;0};);{-1:1}))
Изменено: MCH - 20 ноя 2020 18:32:07
Максимальные расстояния между одинаковыми знаками строки
 
Есть 76, вскрываемся или в избушку перенести вопрос?
Как разделить разные суммы между n людей так, чтоб у всех было поровну?, надо узнать кто кому сколько передает
 
В продолжении решения задачи макросом, для сокращения количества транзакций, можно отсортировать исходный массив данных случайным образам, запустить решение несколько раз и выбрать лучшее решение (с наименьшим количеством транзакций).
Каждый раз макрос подберет решение с наименьшей суммой транзакций, пытаясь сократить их количество, тем самым можно немного улучшить решение, если это возможно.

Например, для задачи про машины уже находится не 29, а 28 транзакций - это наименее возможное для этой задачи
Также на приложенных случайных данных в задачах на 100 и 200 значений получается немного их уменьшить
Изменено: MCH - 20 ноя 2020 11:59:16
Максимальные расстояния между одинаковыми знаками строки
 
Цитата
БМВ написал:
Краюшки обрезает? Если да то можно посмотреть.
У меня полное соответствие результатов UDF и формулы
Страницы: 1 2 3 4 5 6 7 8 9 10 11 ... 124 След.
Наверх