Подскажите, такой алгоритм можно только с unsafe написать? я хочу дерево

с обходом Breadth-First, при этом максимально выжать все что можно по производительности, так как планирую запускать метод visit очень много раз, на большие деревья каждую ms.

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

тут как видно rust не может передать владение child, так как он перезатирается в конце каждой итерации for цикла.

Пока никаких идей кроме unsafe в голову не приходит, мб есть ещё способы это реализовать без копирования?

а тут точно должно быть не for child in &cur.child?

о, помогло. А как это работает, мы сохраняет ссылку на ссылку в итоге в queue?

а зачем упарываться по производительности, когда надо закешировать все что можно и получать данные за хотя бы O(log) вместо O(n)?

нет, ссылку на вершину дерева, которое уже живет в self то есть &self - это ссылка на дерево, которое как-то лежит уже в памяти и на них сохраняем ссылки

unsafe здесь точно не поможет

затем что иногда нужно иметь дерево, а раз дерево то и ходить по нему нужно

вот иногда и ходите по дереву если надо иногда, а если надо очень часто и на больших деревьях то надо менять подход

возьмем тот же SQL, любой поиск оп индексу это ходим по дереву и что-то смотрим. Какой подход тут менять?

у вас линейный поиск, возьмите красное черное дерево и ищите за логарифм

мне очень часто и всегда по всем элементам (причем мутабельно их менять при обходе). если кратко: делаю игру, там будет что-то вроде электро-сеть. В дереве каждая нода это здание или электро-столб. Между нодами нужно каждый кадр игры передавать что-то вроде электричества (у root ноды -= someFloat, у детей += someFloat) (от рута дальше вниз по дереву).

а вот мутабельность кстати будет непросто добавить, потому что придётся одновременно в очереди держать мутабельные ссылки на разные элементы, но компилятору-то не доказать, что они разные :) и потом в правильном порядке ещё нужно обходить (сначала менять детей, потом — родителей, потому что иначе изменение родителя может удалить детей, а если хранить на них указатели, то..), тут уж придётся либо ансейф, либо rwlock, либо mutex, либо арены, либо что-то ещё для динамического управления памятью

тут вроде не очень сложно: если дерево меняется только этой функцией, то просто заменить &self на &mut self, и for child in cur.child.iter_mut()

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

что если у вас каждая нода иммет список других нод подписчиков (и как только вы обновляете ноду, вы уведомляете всех кто с ней связан?) и тогда линейное время для проходу по всему граффу не придется тратить? В общем я пытаюсь сказать то, что вам нужно над дизайном подумать и структурами а не пытаться оптимизировать то что и так на 95% работает от максимальной скорости

попробуйте :)

Почему? pub fn visit(&self, f: &mut impl FnMut(&T)) { что тут доказывать

FnMut(&mut T)

А можете скинуть код на play.rust-lang.org? Интересно попробовать стало

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=c0c638fc3f3a53b7d73483e8ed7e2050

ну если смотреть с точки зрения того что я пытаюсь сделать, в игре есть источники энергии (типо электро-станция), который каждый кадр передают энергию дальше по дереву. В любой имлементации, хоть событиями, хоть деревом, хоть списком, всё равно нужно каждый кадр обновить все N элементов, тут всегда будет O(N) и никак это не захешировать, в этом суть логики игровой. но в рамках O(N) я пытаюсь сделать максимально быстрый проход по дереву с изменением value каждого из объектов (в моем случае value это какой-то float с хранением тек. кол-ва энергии у здания)