История изменений

Где я такое подаю? Но в практическом смысле таки победа - код получился намного прямее и читабельней сишной бажной лапши

Человек какие-то графы вычислял, и сначала реализовал на сишке. Всё по-красоте - списки на указателях и, вообще, оптимизировал как это полагается в сишке. Потом переписал на раст, и поначалу тоже закопался в RefCell-ах, не вывез, плюнул и переписал в лоб на хэшмапах вообще не задумываясь об оптимизации и … обошёл свою «оптимизированную» сишную версию процентов на 20-30 (точно не помню, но порядок такой).

Графы вычислял со списками на указателях — уже звучит странно. В «Алгоритмах» (3-е изд.) Кормена, Лейзерсона и Ко предлагают списки смежности для sparse графов и матрицы смежности для dense графов, проговаривая для первого случая, что нужен массив списков. При этом для любого графа известно, что для ориентированных графов сумма длин всех списков равна кол-ву вершин и в два раза больше для неориаентированного графа. Что также позволяет использовать один массив для представления «списков». На мой дилетантский взгляд, здесь не нужны ни списки (т.к. список смежности — это массив, два массива или массив массивов), ни указатели (т.к. для работы с массивами даже психически проще работать с индесками, а не с адресами и смещениями). При этом производить доп. аллокаций не нужно в обоих случаях, и даже у фанатов адресов+смещений указатели не «провиснут».

«Оптимизировал как это полагается в сишке» — я не очень понимаю, что это значит. В любом случае, похоже, что он оптимизировал очень неоптимальный выбор примитивов. Стоило ознакомиться со справочной литературой, ИМХО, прежде чем приступать к такому делу.

и переписал [списки] в лоб на хэшмапах вообще не задумываясь об оптимизации

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

Я, кстати, не оч понимаю зачем тут хешмап? Что там у него было ключом?

UPD: Полистал википедию, вижу такое: https://en.wikipedia.org/wiki/Sparse_matrix#Storage , где

• Coordinate list — это три массива

• CSR/CSC и Ко — это 3 массива

• DOK, где как раз нужна мапа, не приспособлен для вычислений

• LIL, где как раз «списки», тоже «another format good for incremental matrix construction», а не для проведения рассчетов.

Где я такое подаю? Но в практическом смысле таки победа - код получился намного прямее и читабельней сишной бажной лапши

Человек какие-то графы вычислял, и сначала реализовал на сишке. Всё по-красоте - списки на указателях и, вообще, оптимизировал как это полагается в сишке. Потом переписал на раст, и поначалу тоже закопался в RefCell-ах, не вывез, плюнул и переписал в лоб на хэшмапах вообще не задумываясь об оптимизации и … обошёл свою «оптимизированную» сишную версию процентов на 20-30 (точно не помню, но порядок такой).

Графы вычислял со списками на указателях — уже звучит странно. В «Алгоритмах» (3-е изд.) Кормена, Лейзерсона и Ко предлагают списки смежности для sparse графов и матрицы смежности для dense графов, проговаривая для первого случая, что нужен массив списков. При этом для любого графа известно, что для ориентированных графов сумма длин всех списков равна кол-ву вершин и в два раза больше для неориаентированного графа. Что также позволяет использовать один массив для представления «списков». На мой дилетантский взгляд, здесь не нужны ни списки (т.к. список смежности — это массив, два массива или массив массивов), ни указатели (т.к. для работы с массивами даже психически проще работать с индесками, а не с адресами и смещениями). При этом производить доп. аллокаций не нужно в обоих случаях, и даже у фанатов адресов+смещений указатели не «провиснут».

«Оптимизировал как это полагается в сишке» — я не очень понимаю, что это значит. В любом случае, похоже, что он оптимизировал очень неоптимальный выбор примитивов. Стоило ознакомиться со справочной литературой, ИМХО, прежде чем приступать к такому делу.

и переписал [списки] в лоб на хэшмапах вообще не задумываясь об оптимизации

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

Я, кстати, не оч понимаю зачем тут хешмап? Что там у него было ключом?