TL & DR: перейдите ко второй части для реальной вещи
Часть I
@ Нина Шольц ответ на эту фундаментальную проблему просто показывает нампрекрасное проявление алгоритма.Честно говоря, это сильно смутило меня по двум причинам:
- Когда я пытаюсь
[14,6,10,7,3] с целью 500, он совершает 36 783 575 вызовов функции iter без потери стека вызовов.Тем не менее, память не показывает значительного использования вообще. - Мое решение для динамического программирования работает немного быстрее (или может быть нет), но нет никакого способа, как это было бы вышеописанным, без увеличения памяти на 16 ГБ.
Итак, я отложил свое решение и вместо этого начал исследовать ее код немного дальше на инструментах разработчика и обнаружил, как это красиво, так и немного его недостатков.
Сначала я верю этому алгоритмическому подходу, который включает в себяочень умное использование рекурсии, возможно, заслуживает собственного имени.Это очень эффективно использует память и использует только память для созданного набора результатов.Стек динамически растет и непрерывно сжимается до уровня, близкого к своему пределу.
Проблема в том, что, будучи очень эффективной, она по-прежнему выполняет огромное количество избыточных вызовов.Таким образом, с небольшой модификацией 36 783 575 вызовов на iter могут быть сокращены до 20 254 744 ... примерно до 45%, что дает гораздо более быстрый код.Дело в том, что входной массив должен быть отсортирован по возрастанию.
Итак, вот и модифицированная версия алгоритма Нины.(Наберитесь терпения ... это займет около 25 секунд, чтобы завершить)
function getSum(array, sum) {
function iter(index, temp) {cnt++ // counting iter calls -- remove in production code
var s = temp.reduce((a, b) => a + b, 0);
sum - s >= array[index] && iter(index, temp.concat(array[index]));
sum - s >= array[index+1] && iter(index + 1, temp);
s === sum && result.push(temp);
return;
}
var result = [];
array.sort((x,y) => x-y); // this is a very cheap operation considering the size of the inpout array should be small for reasonable output.
iter(0, []);
return result;
}
var cnt = 0,
arr = [14,6,10,7,3],
tgt = 500,
res;
console.time("combos");
res = getSum(arr,tgt);
console.timeEnd("combos");
console.log(`source numbers are ${arr}
found ${res.length} unique ways to sum up to ${tgt}
iter function has been called ${cnt} times`);
Часть II
Несмотря на то, что я был впечатлен производительностью, мне не понравилось вышеуказанное решение без веской причины, по которойя могу назвать.То, как это работает с побочными эффектами и очень трудно понять двойную рекурсию, и это беспокоило меня.
Итак, вот мой подход к этому вопросу.Это во много раз эффективнее по сравнению с принятым решением, хотя я работаю в JS.У нас все еще есть место, чтобы сделать это немного быстрее с безобразными императивными способами.
Разница:
Заданные числа: [14,6,10,7,3] Целевая сумма: 500
Принятый ответ:
- Количество возможных ansers: 172686
- Разрешается в: 26357ms
- Количество рекурсивных вызовов: 36783575
Ответ ниже
- Количество возможных ответов: 172686
- Разрешение в: 1000 мс
- Количество рекурсивных вызовов: 542657
function items2T([n,...ns],t){cnt++ //remove cnt in production code
var c = ~~(t/n);
return ns.length ? Array(c+1).fill()
.reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
: t % n ? []
: [Array(c).fill(n)];
};
var cnt = 0, result;
console.time("combos");
result = items2T([14, 6, 10, 7, 3], 500)
console.timeEnd("combos");
console.log(`${result.length} many unique ways to sum up to 500
and ${cnt} recursive calls are performed`);
Другим важным моментом является то, что если данный массив сортируется по убыванию, то количество рекурсивных итераций будет уменьшено (иногда значительно), что позволит нам выжать больше сока изэтот лимон.Сравните выше с приведенным ниже, когда входной массив отсортирован по убыванию.
function items2T([n,...ns],t){cnt++ //remove cnt in production code
var c = ~~(t/n);
return ns.length ? Array(c+1).fill()
.reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
: t % n ? []
: [Array(c).fill(n)];
};
var cnt = 0, result;
console.time("combos");
result = items2T([14, 10, 7, 6, 3], 500)
console.timeEnd("combos");
console.log(`${result.length} many unique ways to sum up to 500
and ${cnt} recursive calls are performed`);