Как максимизировать сумму элементов выбираемых из списка?

Роман Румянцев, спасибо за реализацию - познакомился с лямбдами (пришлось звать дочь для объяснения).
Кстати как минимум в пайтоновской реализации есть проблемка, из-за которого в результат могут попадать элемент за пределами списка. Вместо if next < 0 нужно использовать if next < 0 or next > len(data):

Но увы - программа теперь не проходит по скорости - сыплетася на больших k - всё из-за max() для скользящего отрезка. Попробую избавится от этого недостастака

Как максимизировать сумму элементов выбираемых из списка?

Роман Румянцев, нашёл как минимум одну ошибку в коде который описал выше - проблема была тут:

тут может быть выход за границы массива, это надо учесть

Я это сделал оригинальным образом - нарастил массив maxDef содержащий максимумы в окнах последним элементом, что конечно не правильно - правильным было нарастить исходный массив k-1 нулем, чтобы создать последнее псевдоокно, состоящее из 1 последнего элемента и нолей свисающих за край массива.

Внес изменения: https://pastebin.com/kq6kV4hZ

Но всё равно ошибка где-то в реализации последнего блока. На таком наборе выдает очевидно невернный результат:

8 3
1 2 3 4 1 6 7 8 1 1 9 11 7 14
minA: [1, 2, 1, 1, 1, 6, 1, 1, 1, 1, 7, 7]
defA: [6, 18, 8, 11, 14, 126, 16, 10, 11, 21, 189, 224, 0, 0]
defA: [6, 18, 8, 11, 14, 126, 16, 10, 11, 21, 189, 224, 0, 0]
maxDef: [1, 1, 4, 5, 5, 5, 6, 9, 10, 11, 11, 11]
best next: [5, 5, 5, 6, 9, 10, 11, 11, 11]
summ: [356, 368, 358, 251, 238, 350, 240, 234, 235, 224, 224, 224]
start chain: 1

Вместно 224 в конечном блоке максимум == 189

Завтра буду продолжать. Но ваша идея работает, я полагаю. Проблема в реализации.

Как максимизировать сумму элементов выбираемых из списка?

Роман Румянцев, спасибо, но я уже сам размотал вашу идею. Это похоже на решение, и на тестовых данных у меня работает. Но не проходит онлайн проверку, не понятно на каком наборе данных :(

https://pastebin.com/UNK772g0 - вот реализация всей задачи. Конкретно вынесенное в вопрос сюда это блок начиная с
# =========================================================================================

Вот запуск на тестовых данных и промежуточные результаты:

def: [6, 18, 8, 11, 14, 126]
maxDef: [1, 1, 4, 5, 5, 5, 5]
best next: [5, 5, 5]
summ: [132, 144, 134, 126, 126, 126]

Здесь:
def - просматриваемый массив
maxDef - индекс максимум в скользящем окне 3, для окна начинающегося в i

best next и summ - то что вы называете кэшем:
Первый содержит индекс наиболее подходящего элемента для элемента i
второй собственно суммы.

Если интересно вся задача здесь: https://informatics.mccme.ru/moodle/mod/statements...
Правда решаем на Python и дочка только учит, а для меня язык не родной, поэтому наверно что-то в реализации может быть коряво написано - прошу простить за такое.

Сейчас пробую составить свои наборы данных и потестить ещё

Как максимизировать сумму элементов выбираемых из списка?

Похоже ваш код работает, но я по правде говоря не могу въехать в реализацию.

Последние k элементов заносятся в кэш как есть, от них никуда не деться.

В какой кэш? Что он нам даёт? Как мы его используем и почему последние k элементов должны попасть туда в начале?

Далее для каждого элемента с номером i нужно просмотреть, как он сочетается с элементами i + k .. i + 2k

Вы имеете ввиду найти в диапазоне от i+k до i+2k наилучшую для него пару? И что? Записать для этого элемента индекс наилучшей пары? Предположим.

И так идём до первого элемента. Потом выбираем лучший из элементов с номерами 1 .. k

А почему я тогда не могу начать с начала и выбрав максимум на отрезке 1..k подбирать наилучшую пару для него? На отрезке k..2k?
В смысле чем такой подход отличается от вашего предложения не могу уловить...

Но реализовывать пошёл - попробую.

Как максимизировать сумму элементов выбираемых из списка?

uvelichitel,

в один проход?

Не факт, что в один. Там у меня до этого еще несколько вычислений, которые уже делают 3 прохода, но там всегда три прохода (можно свести к двум, но сейчас не это важно) и от n не зависит.

храня промежуточные результаты в матрице и оптимизируя очередью или стеком.

Возможно деком - уже дек активно юзаю чтобы свести задачу к этой.

Как максимизировать сумму элементов выбираемых из списка?

dmshar,

Я имел ввиду, на ограничения количества элементов, из которых составляется сумма. Если нет - то все очень не радужно. Метод "ветвей и границ" точного решения не гарантирует.

Нет - ограничения нет. Количество элементов может быть любым.

Надеюсь, про O(n) это вы пошутили.

Я серьёзен как никогда - с этой задачей пришла дочь, а я не могу справится. Задача из раздела который называется "Линейные алгоритмы", что как бы намекает.
На самом деле задачка там сильно посложнее, но в итоге легко за линейное время сводится вот этой и дальше понять не могу чего делать.

Как максимизировать сумму элементов выбираемых из списка?

А есть-ли ограничения на количество элементов в списке?

Есть но их там десятки тысяч.
И есть основание полагать, что имеет решение со сложностью O(n)

Сайт аквариума? Что за технологии используются?

Ни разу не понял про волка, единорога

Мне кажется что это животные невиданной красы.

Bitrix как вывести $APPLICATION->GetProperty?

Прикинь тебе предлагают подработать и добавить какой нибудь компонент в битрикс,ты заходишь и глаза на лоб выскакивют от того что там вместо битрикса ты Zend увидел. При том ты в глаза не разу его не видел раньше,не то что не работал на нем.

Прикинь, со мной именно это и случилось лет 5 назад. Ничо - разобрался. Брат жив.

Bitrix как вывести $APPLICATION->GetProperty?

Контроллеры для компонентов есть,но не для страниц статичных.

ArrayPop, а что мешает тебе создать контроллеры для статичных страниц в виде тех же компонентов?

По идее заголовки страницы должны создаваться в контроллере и потом выводится шапка,шаблон,подвал.

На самом деле так тоже можно сделать и никто тебя не осудит. Другое дело что в CMS Bitrix УС используется несколько иной подход, но опять же - никто не заставляет тебя делать именно так.

Ты говоришь - вот в других фреймворках я так не делаю, а здесь так сделали. Так не пользуйся тем что сделали - сделай так как делают в других фреймворках, свободная же страна у нас.
Есть ещё варик прикрутить какой-нибудь фреймворк к Битрикс и делать на нём.
Неоднократно видел истории успеха на Zend + bitrix

Bitrix как вывести $APPLICATION->GetProperty?

ArrayPop, прикинь - здесь такая же фигня - данные подготавливаются в контроллере (комопненте заранее), а потом выводятся в шаблоне, который модифициуется уже после отработки контроллеров. Именно для такой модификации предусмотрены функции вроде $APPLICATION->ShowProperty
Видишь - дело только в трактовке.
Я согласен что есть некоторая костыльность, в том что нарушается обычное процедурное течение, но посмотри на это с другой стороны - у тебя могут быть на странице несколько независимых контроллеров, которым необязательно взаимосдействовать между собой и с родителем, а порядок выполнения больше не важен.

Bitrix как вывести $APPLICATION->GetProperty?

Каков битрикс? Как ты иначе это реализуешь?

Bitrix как вывести $APPLICATION->GetProperty?

ArrayPop, да уж расскажи. А теперь еще и заодно при чем тут вообще MVC если мы сейчас говорим о потоке обратки?

Bitrix как вывести $APPLICATION->GetProperty?

ArrayPop, что если тебе надо вывести данные ДО шаблона? Например что делать если у тебя компонент должен изменить тэг title в секции head?
Предложи свое решение - все будут только благодарны.

Почему атрибут «rel» тега «link» в разных ситуация имеет разные значения (stylesheet или preload)?

Андрей Белый, это совсем грустно бы было.
Для поиска ядерных методов отлично подходит bxapi.ru
https://bxapi.ru/src/?module_id=main&name=CMain%3A...

Почему атрибут «rel» тега «link» в разных ситуация имеет разные значения (stylesheet или preload)?

Андрей Белый, попробуй поискать по файлам в локал, подписку на событие завершение страницы, вроде:
OnEpilog
OnAfterEpilog
OnEndBufferContent

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

Почему атрибут «rel» тега «link» в разных ситуация имеет разные значения (stylesheet или preload)?

Андрей Белый, и в какой оптимизации кроме не очень-то нужной склейки, он участвует?

Как работает Битрикс с memcached?

Вы говорите о "дисковом буфере в оперативной памяти", я смею предположить, что вы говорите о DRAM. Так вот он есть не у всех SSD накопителей и его размер много меньше оперативной памяти и он не хранит в себе контент файлов.

Нет - я говорю о дисковом буфере в оперативной памяти: который занимает там столько места сколько надо.

К тому же вы приводите синтетический тест, так как он полностью игнорирует вытеснение информации (у вас же в реальном проекте читается не только этот файл, но и. сотня файлов битрикса + upload).

С одной стороны - да. С другой стороны, если вы забьете память Redis'ом, то он точно так же вытеснит из буферов файлы битрикса и upload и какая вам выгода в том, что у вас быстро считывается кэш, если этот кэ вытеснил другие файлы?

У вас либо хватает оперативки чтобы всё это там держать и тогда почти всё равно Redis у вас или просто файлы, либо не хватает и тогда тоже всё равно. В конце-концов если редиска в память не влезит она так же вытеснится на диск, не важно каким именно образом - в swap ли, просто вытеснится или будет перемещена в zswap/zram.

В целом хранение в Redis и в файлах во многих случаях может быть сопостовимо.

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

В реальной ситуации я бы предпочел тестирование на конкретном сервере с конкретной посещаемостью и определенным объемом оперативки, а не просто "включим редис - он быстрее".

А вообще можно же элементарно попробовать ;)

Как работает Битрикс с memcached?

Александр Маджугин, почему вы так считаете? Если сравнить файловый кеш на SSD диске и существующий ключ в оперативной памяти redis, то из redis данные прочитаются значительно быстрее.

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

Как работает Битрикс с memcached?

Все правильно, но маленькое уточнение:

Все относительно. Кеш memcached/redis работает однозначно быстрее чем файловый кеш.

Совсем не однозначно.