Почему моя реализация Shaker Sort-а такая медленная?

Timur, Возможно в пузырьке оптимизация: если ничего не свапнули ни разу, то можно из внешнего цикла выходить.

Потом, может это проблема бенчмарка. Вы как меряли? Запускали 1000 раз и брали среднее? Игнорировали ли вы самые медленные и самые быстрые запуски? Вы уверены, что у вас там JIT не дает задержки, которой нет у стандартной реализации пузырька?

Грамотно померять скорость работы, собственно, реализации - довольно сложная задача.

Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

alex_agaphe , я смотрю вы вопрос поменяли и код добавили.

Вы делаете не то, что я вам ответил. Вы берете для всех состояний {i, w, w} и смотрите куда может пойти i-ая гирька. Но так нельзя делать, потому что эти состояния независимы. ДП же говорит, можно ли собрать вот такие веса и куда класть последнюю гирю при этом. Но оно не говорит, что все эти состояния должны быть вместе. Каждое из них говорит о каком-то решении, но эти решения могут быть исключающими: одно требует первую гирю во в первую кучу класть, другое - в третью.
Более того, вот если у вас i=0 - вы пытаетесь понять, куда класть первую гирю. Но вы одной гирей никак веса w+w в двух кучах не наберете никогда. Т.е. у вас часть этих состояний еще и невозможны.

Вот в dp[n-1][w/3][w/3] у вас лежит правильное значение - куда класть последнюю гирю. Вот это вы знаете. Отметьте ее в нужную кучу. Если там было 0, то гиря лежит в третьей куче. Если ее выбросить из рассмотрения, то получится, что у вас осталось n-1 гиря, с теми же весами. И вы в dp[n-2][w/3][w/3] знаете, где лежит предпоследняяг гиря. Если же dp[n-1][w/3][w/3] == 1, то последняя гиря должна быть в первой куче, а значит, после ее выкидывания вам надо смотреть на dp[n-2][w/3-a[-1]][w/3] чтобы понять, где лежит предпоследняя гиря.

В итоге вам надо написать цикл по i от N-1 до 0, завести 2 переменные для текущих весов (начать с w/3, w/3, а не w,w). Вы по dp[i][w1][w2] понимаете, куда класть i-ую гирю, и вычитаете ее из веса нужной кучки: w1, если в dp был 1, w2, если там был 2.

Как написать свой фреймворк?

Вова, Хочу добавить - это будет не фреймворк, а библиотечка для рисования на экране элементов GUI. До фреймворка ей расти и расти еще много лет.

Как написать свой фреймворк?

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

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

Для обработки нажатий алгоритм простой - компонент сначала запускает проверку в детях, потом проверяет сам, было ли событие по его области ответственности, и если да - то вызывает callback. Самый верхний - корневой компонент должен принимать события о клике от системы. Не знаю, как тач в адруинке работает, возможно у вас как в игре будет цикл обработки событий, где вы опрашиваете устройства на предмет нажатий и передаете это в корневой объект GUI.

Как написать свой фреймворк?

Вова, Но на arduino нет никакого GUI же? Это микроконтроллер же. Какой вы там ГУИ в 8мгц запихнете?

Как написать свой фреймворк?

Очень странная затея. Зачем вам писать свой собственный фереймворк? Особенно декстопный? Какая перед вами задача стоит?

Вам хочется написать GUI приложение без всяких сторонних фреймворков? Допустим, потому что они тяжелые? В этом случае вам не стоит упарываться в создание фреймворка и просто написать свое GUI приложение используя напрямую функции операционной системы - winAPI (GDI или DirectX) или wayland/x, в зависимости от того, под что вы пишите. Да, под каждую платфорому вам придется писать практически весь GUI отдельно.

Даже если вы планируете писать несколько приложений, у вас разработка фреймворка не окупится никак, быстрее и легче будет написать каждое с нуля, возможно копируя какие-то куски кода.

Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

floppa322,

а хотелось написать C(n,k)/C~(n,k)

Тогда задача нужна что-то вроде "есть шляпа, где 28 шаров, по 7 каждого из 4 цветов. Вы тянете оттуда 4 шара. Какова вероятность, что они все разноцветные?"

Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

floppa322, Почему на 7^4 будет а не C(10, 4), потому что у вас могут быть исходы {3,3,4,7} и {3,4,7,3}, если у вас 4 события могут произойти независимо в один из 7 дней. Два события могут выпасть на среду, но это могут быть первое и второе, а могут быть первое и четвертое. Это разные исходы. Порядок элементов важен. А, если у вас сочетание с повторениями, то порядок был бы не важен.

Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

floppa322,

Так это же как раз то, что я пытаюсь избежать. Если я правильно понял о чём речь

В алгоритме случайного перемешивания же у вас выплняется swap i-ого значения с j = RandInt()%(i+1). Можно не делать swap, если вам важны только первые k элементов. Сгенерировали j, если j
> Ну просто все возможные исходы это все наборы из 7 элементов по 4 элемента, но с повторениями, то есть не только {3, 1, 7, 2}, а ещё и {7, 2, 3, 3}, например. А благоприятные наборы это то же самое, но без повторов, например {2, 1, 7, 6}

Все равно не понял, как вы счаете вероятность через генерацию случайного объекта. По идее вам надо сгенерировать любые возможные объекты (в задаче из условия у вас не сочетания с повторениями, а просто 7^4 всех слов из алфавита с 7 буквами длины 4). Проверять их на "хорошесть" и увеличивать на 1 счетчик хороших исходов. И всегда увеличивать счетчик попыток. Ответ - счетчик хороших делить на количество попыток. Генерировать при этом хорошие исходы уметь вам совсем не надо.

Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

floppa322, перечитал ваш вопрос, понял. У вас формула неправильная. Всего вариантов 7^4. Каждый независимый эксперимент может выпасть на любой день недели. Хороших же вариантов 4! С(7,4) - выбрали какие дни выпали и в каком порядке. Так что правильная вероятность будет 4!*35/2401 = ~0.34.

Я, правда, так и не понял, как вы считаете вероятность через генерацию сочетания. Но возможно проблема в том, что вам важен еще и порядок элементов в сочетании. Ибо это разные события, когда первый эксперимент выпал на понедельник, а второй - на вторник и когда первый выпал на вторник, а первый - на понедельник. Поэтому после генерации сочетания вам надо полученные 4 элемента случайно перетасовать. Ну, или, действительно, вам лучше подойдет вариант через случайную перестановку массива: сгенерируйте массив от 1 до 7, перемешайте его и берите первые 4 элемента. Тут как раз будет 4! С(7,4) вариантов.

Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

floppa322, что за вероятность вы считаете? Она не та, что вы ожидаете? Этот код выдаст вам каждое из C(28, 4) сочетаний равновероятно.

Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

floppa322, можно и так. Мой метод тоже за O(n) работает, но не требует никакого массива на n элементов, так что он лучше по памяти.

Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

Akina,

Для чего собственно и нужен массив текущих местоположений гирь.

Что значит текущих положений гирь? Такое текущее положение может быть в переборе, где у вас одно состояние рассматривается в каждый момент времени и чуть чуть туда-сюда меняется. Если у вас ДП, то у вас куча состояний и для каждого из них есть "местоположение гирь".

Если стостояние {сколько гирек обработали, сколько весит первая кучка, сколько весит вторая кучка} (как у автора вопроса), то достаточно хранить одно только число - в какой кучке лежит последняя из обработанных гирек. Чтобы восстановить все гири, надо эту последнюю выкинуть из рассмотрения, вычев ее из нужной кучки и повторить операцию уже в новом состоянии. Именно это описанно у меня в ответе ниже.

Но там все-равно есть трехмерный массив для всех стостояний.

Или вы предлагаете сделать его четырехмерным и хранить еще для каждой гирьки, где она лежит - куб из "текущих местоположений гирек"?

Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

Akina, Это перебор и получается же. Хоть и не такой наивный. Вариантов набить первый рюкзак экспоненциально много. Вам надо для каждого попытаться потом набить второй рюкзак. В худшем случае - вы переберете их все, если решения для обоих рюкзаков нет.

Тут есть только одно быстрое решение - набивать оба рюкзака сразу, включив в стостояние ДП текущий вес в обоих рюкзаках.

Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

floppa322, Тогда вам нужно что-то вроде reservoir sampling. Гуглите. На каждом этапе вероятность взять текущий элемент зависит от того, сколько у вас элементов осталость и сколько еще надо взять.

int taken = 0;
for (int i = 0; i < n; ++i) {
  if (rand()*(n-i) < k-taken) {
    ++taken;
    // Взять элемент i.
  }
}

Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

Akina, Нет, без двумерного массива вы не восстановите ответ. (трюк с одномерной плоской индексацией и расправлением многомерного массива в одномерный не считается).

Всё равно ж надо начинать с подсчёта общего веса и проверки, что оно вообще возможно, а также расчёта веса каждой кучки. А потом, используя ДП, набиваем один рюкзак, а по завершении второй.

Целевой вес каждого рюкзака известен - общая сумма весов / 3.

Нельзя набивать рюкзаки по очереди. Вы можете найти решение для первого рюкзака такое, что никак не получится набить второй оставшимеся объектами. Например у вас веса {1, 3, 2, 2, 1, 3}. Если вы случайно в первый рюкзак возьмете {1,1,2}, то уже никак из оставшихся {2,3,3} вы второй рюкзак размера 4 не наберете.

Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

Akina, Нет, при таких маленьких весах и таком огромном количестве гирек - это задача на Динамическое Программирование. Ибо перебор тут будет из 3^60 вариантов - не дождетесь до смерти солнечной системы, а ДП тут 60*(1200)^2 = 60^5 = 86400000 операций - отработает за доли секунды. Даже если вы всякие хитрые отечения вроде ветвей и границ будете использовать - вы в ограничения по времени не уложитесь.

Ну и, там прямо на сайте наиписано

ДП: Условия задач

Когда передавать копию callable, а когда через rvalue reference?

Dyikot, а каких? Конкретнее пожалуйста.

Когда передавать копию callable, а когда через rvalue reference?

Пример бы кода, что у вас за библиотеки и как используются.

Вообше, callable может быть большим объектом из-за всяких связанных аргументов функции. Поэтому лучше его не копировать. Но, и перемещать его не всегда можно, ведь он может быть нужен потом опять.

В чем суть логической ошибки, продемонстрированной в старинном учебнике?

Rsa97,

Откуда вам известно, что существует прямоугольный треугольник со сторонами 3, 4 и 5?

По построению, например. Берем прямоугольный треугольник с двумя катетами 3 и 4. По теоремме пифагора получам гиппотенузу 5.