Оптимально создать словарь с суммами по ключам на основе списка пар ключ:значение?

Смотря что тебе надо, феншуй он разный. Бывает что надо код красивый написать, а бывает что надо производительный. Тебе какой вариант нужен? А всё увидел. Уточнить надо затык в производительности или в потреблении памяти?

PS

У тебя 2 обращения же. Не 1. Ты должен взять значение что там было и прибавляя сохранить новое.

В производительности.

Через setdefault обращение одно, но тормозит прилично.

Ну у тебя не так много вариантов. dict сам по себе довольно быстрый. Если бы у тебя пары суммировать не надо было, то можно было бы проще сделать - собирая всё в строку, а потом её в словарь конвертнуть, ХЗ иногда это быстрее https://stackoverflow.com/questions/40694470/is-there-anything-faster-than-dict но особо вариантов не вижу если от самого dict-а к какой-то другой структуре данных не переходить.

https://stackoverflow.com/questions/4156392/fastest-way-to-update-a-dictionar...

Если через dict update действовать, то быстрее всего будет, но у тебя надо суммировать же, а не просто менять. А значит сверху оверхед будет, надо смотреть есть ли в этом толк.

ну это update, это другое…

Спасибо!

https://docs.python.org/3/library/collections.html#collections.defaultdict

А там нельзя ключи в растопыренном дереве хранить?

С т.з. производительности тут две работы:

1. добавить ключ

2. найти ключ

Оптимизация 1 и 2 делается по-разному, соотв. на основе предварительных знаний о характере данных можно пытаться оптимизировать что-то одно.

Что такое растопыренное дерево?:-)

В некоторых случаях набор ключей заранее известен, наверное можно взять named tuple. В других неизвестен.

Я для расширения кругозора решил спросить, а то сейчас уткнулись в производительность на ровном в общем то месте…

collections.Counter.update

splay tree, я почему-то его называю растопыренным. одна из структур для кеширования, можно в корень подтягивать как добавляющиеся данные, так и последние к которым было обращение.

https://en.wikipedia.org/wiki/Splay_tree

PS: с практической т.з. я бы для начала просто распараллелил, если нужна скорость, а потом слил результаты, если в серваке 100+ потоков, то ускорение будет хорошим.

Что значит оптимально? В бидоне?

В бидоне не бывает оптимального, интерпретатор бидона в любом случае будет тормозить и жрать память.

Если вдруг понадобилась скорость или что-то такое, то значит не надо было брать бидон.

С параллельностью там алгоритмическте сложности, кмк проще будет уже на плюсах переписать после отработки алгоритма.

Там довольно спецефический разбор входящего потока.

Глянул про это дерево - интересно, спасибо, не знал.

Но у меня в работе много маленьких деревьев, мне кажется надо брать какие то стандартные структуры данных.

Десять лет назад, когда я пытался сделать хороший курс по алгоритмам, я составил такой вот список, часть которого я знал, часть планировал освоить:

https://habr.com/ru/articles/340044/#comment_10472088

может что из раздела кеширования подойдет под задачу, или что-то другое какие-то мысли / ассоциации вызовет…

Часть этого курса мне даже удалось пару раз прочитать, но сравнительно небольшую, а потом там все окончательно развалилось…

ты упрлс?

Counter ибо реализовано https://github.com/python/cpython/blob/main/Lib/collections/__init__.py#L545

from collections import Counter

d=Counter(int)

#и суммируй:

d['a']+=3

Просто аналог Кнутовской библии можно написать:-)

Смотрел бегло - сходу не увидел задачи коммивояжера, машины изинга, SAT/maxSAT, Z-кривой Мортона.

Но вообще конечно в этом можно утонуть…

А по графам в той программе был отдельный жирный курс.

интерпретатор бидона в любом случае будет тормозить и жрать память

Поэтому есть PyPy и Nuitka.

D = defaultdict(int)
D[key] += value

Int по умолчанию ноль

Либо counter, та же фигня по сути

интерпретатор бидона в любом случае будет тормозить и жрать память

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

и FishHook, qulinxao3, peregrine - фигня эти ваши Counter/defaultdict(int)

Т.е. юзать удобно, но медленней процентов на 20 чем

D.setdefault(k, [0])[0] += v

вариант

D[k] = D.get(k, 0)+v

оказался почти таким же быстрым как и

D.setdefault(k, [0])[0] += v

Слушай, ну если надо вот прям чтоб совсем быстро и частью удобств можно пожертвовать - возьми сразу cython или вообще кресты с ctypes. Ну или builtins, но это по читабельности даже хуже крестов

На плюсы я перейти всегда успею:-)

Claude 3:

Для решения этой задачи оптимальным образом можно использовать словарь (dict) в Python. Вот как это можно реализовать:

def func(key, value):
    result = {}
    for k, v in ((key, value), ):
        result[k] = result.get(k, 0) + v
    return result

result = {}
for key, value in [('a', 1), ('b', 2), ('a', 5)]:
    result.update(func(key, value))

print(result)

Выход:

{'a': 6, 'b': 2}

Разберем код:

1. Функция func принимает ключ и значение. Внутри функции создается пустой словарь result.
2. Используется генератор ((key, value), ) для создания итерируемого объекта с одним кортежем (key, value).
3. В цикле for k, v in ((key, value), ): этот кортеж распаковывается в переменные k и v.
4. Для каждого ключа k мы получаем текущее значение из словаря result.get(k, 0) или 0, если ключа нет в словаре. Затем к нему прибавляется новое значение v.
5. Обновленное значение сохраняется в словаре result[k].
6. Функция func возвращает обновленный словарь result.
7. В основном коде создается пустой словарь result.
8. В цикле for key, value in [('a', 1), ('b', 2), ('a', 5)] мы проходим по списку пар ключ-значение.
9. Для каждой пары key, value вызывается функция func(key, value), которая возвращает промежуточный словарь.
10. Промежуточный словарь объединяется с основным словарем result с помощью метода result.update(func(key, value)).
11. После завершения цикла в result содержится итоговый словарь с суммами значений для каждого ключа.

Этот подход является оптимальным, потому что он использует словари, которые обеспечивают быстрый доступ к элементам по ключу (время доступа O(1) в среднем случае). Также, операция result.get(k, 0) избегает ненужных проверок на наличие ключа в словаре, что также оптимизирует производительность.

Вообще то про O(1) неправда - есть хэш-коллизии. И этот вариант в исходном посте есть:-)

Как это сделать оптимальным (с т.з. производительности) образом?

Зависит от двух факторов:

1. Реализация словаря.
2. Стоимость сравнения ключей.

За то, как реализованы словари в python не скажу, так как не знаю, но могу предположить, что реализован самый распространённый вариант: хеш таблица -> сбалансированное дерево -> список. Т.е. стоимость доступа в лучшем случае O(1) и O(n) - в случае полной коллизии хешей ключей. Если в реализацию встроен механизм кеширования пути к последнему запрошенному ключу, то стоимость повторного доступа к последнему ключу будет O(1) даже при полной коллизии хешей ключей.

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

Все так, но на это накладывается еще общая питонья тормознутость.

Это наркоманский бред от ChatGPT?

они не на 100% совместимы. можно сказать, что в большинстве случаев их и невозможно никуда прикрутить

Это Claude 3.