LINUX.ORG.RU

Структура данных с зачисткой ненужных элементов


0

2

Как бы вы реализовали следующую функциональность? Сразу скажу, что код ради интереса пишется в стиле Performance Special Olympics. Различные сканирования в цикле структур данных надо избегать.

Есть некий обьект, у которого есть методы isValid(), invalidate() с очевидным назначением. Ссылка на обьект хранится в куче структур данных. Идея в том, что как только где-то этот обьект сделали invalid, сразу он магическим способом выпилился из всех структур.

Как бы вы делали?

1. Паттерн observer. Минус - регать в самом элементе каждую коллекцию и потом все это дебажить. При удалении элемента в многих коллекциях будет достаточно много сканирования по всей коллекции. Очевидно нельзя удалить 100 таких элементов за один проход.

2. Переписать (наследовать) коллекции так, чтобы они скипали и удаляли инвалидные элементы когда на них наталкиваются. Минус - переписывать и дебажить коллекции. А потом появятся еще какие нибудь хитрые коллекции с неочевидной работой и от них тоже расширяться

3. Написать специальные алгоритмы поиска, итерации и т.д. Чуть лучше пункта 2, потому что используется оборачивание интерфейса, что обеспечивает покрытие большего количества коллекций и не надо имплементить все методы коллекции и следить за их согласованостью.

4. Забить нах, доставать элемент, проверять на валидность и выкашивать ручками от случая к случаю.

5. Ваши идеи

★★★★☆

А если объект сделавшись невалидным делает невалидной какую то структуру и ее тоже надо выпиливать, такое может может быть?;-)

AIv ★★★★★ ()
Ответ на: комментарий от AIv

Возможно. В приципе объект - соединение с пользователем и другая инфа. Если пользователь вышел, то сразу различные subscriptions и т.д. должны сняться. Но такого много.

vertexua ★★★★☆ ()
Ответ на: комментарий от vertexua

Ужас-ужас-ужас тогда... вар 1 (граф с двунаправленными связями) первое что в голову приходит, но я не знаю, кто нить вообще так делает? Потому что ИМНО избыточность же аццкая, и возни много.

А так, КО - это же сборка мусора, тема прожеванная вдоль и поперек;-)

AIv ★★★★★ ()
Ответ на: комментарий от vertexua

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

AIv ★★★★★ ()
Ответ на: комментарий от vertexua

Не совсем сборка мусора. Мусор надо принудительно собрать если его решили выпилить в одном месте

Разве? Уборка может быть и отложенной, это уж как сборщик работает. Вон в питоне вообще на подсчете ссылок построено... Я не спец, но там же куча алгоритмов, наверняка чтт то подойдет.

AIv ★★★★★ ()
Ответ на: комментарий от vertexua

Ну это пункт 3

Точно. Ну я бы наверное делал так и не парился;-) Хотя от задачи зависит, если на все это навернуть многопоточность... йе, в общем хорошо что я таким уже не занимаюсь;-)

AIv ★★★★★ ()
Ответ на: комментарий от AIv

Многопоточность тут особая. Вся работа с коллекциями в одном потоке. Флажок выпиливания могут выставить в другом

vertexua ★★★★☆ ()

Минус - переписывать и дебажить коллекции. А потом появятся еще какие нибудь хитрые коллекции с неочевидной работой и от них тоже расширяться

Манагер памяти сразу перепиши, че там. Интрузивные элементы запили, которые делают вдоль, как только понимают «Не нужен!» :)

slackwarrior ★★★★★ ()
Ответ на: комментарий от slackwarrior

Проблема не освободить память, а выпилить ссылки на элемент

vertexua ★★★★☆ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.