Отказ от глобалов?

Question

У меня есть набор объектов-деревьев глубиной где-то 20 с.Каждому из узлов этого дерева необходим доступ к корню своего дерева.

Несколько решений:

1. Каждый узел может хранить ссылку на корень напрямую (тратит память).
   • Я могу вычислить корень во время выполнения, «поднявшись» (циклы отходов)
   • Я могу использовать статические поля (но это глобалы)

Может ли кто-нибудь предоставить дизайн, который не использует глобальные переменные (в любом варианте), но более эффективен, чем № 1 или № 2 как в памяти, так и в циклах соответственно?

Редактировать: Поскольку у меня есть набор деревьев, я не могу просто хранить его в статическом виде, поскольку было бы трудно различать деревья.(спасибо, Маккаллт)

Answer 1

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

Редактировать:Варианты действительно следующие:

1. Сохраните корневую ссылку в узле
2. Не храните корневую ссылку вообще
3. Сохраните корневую ссылку в глобальном
4. Сохраните корневую ссылку в стеке (мое предложение, либо шаблон посетителя, либо рекурсивный)

Думаю это все возможности, варианта 5 нет.

Answer 2

Зачем вам нужно покончить с глобальными переменными?Я понимаю, что глобальные переменные — это плохо и все такое, но иногда самое быстрое решение — просто иметь глобальную структуру данных со всеми элементами.

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

Я не уверен, сколько у вас древовидных объектов, но лично я бы выбрал первый вариант.Если вы не имеете дело с тысячами деревьев, указатели на самом деле не будут превышать нескольких строк.Если память действительно является очень важной проблемой, попробуйте оба метода (они кажутся довольно простыми в реализации) и запустите их через профилировщик.Или воспользуйтесь отличным Обозреватель процессов.

Редактировать:Одно из приложений, над которыми я работаю, имеет дерево узлов, содержащее около 55 тысяч узлов.Мы строим древовидную структуру, но также поддерживаем массив для поиска O (1).Гораздо лучше, чем O(m*n), которое мы получали при использовании рекурсивного метода FindNodeByID.

Answer 3

Обычно лучше всего передавать корень в качестве параметра.Если вы используете какой-то итератор для навигации по дереву, альтернативой является сохранение в нем ссылки на корень.

Answer 4

Пункт №1 — преждевременная оптимизация памяти.№2 — преждевременная оптимизация производительности.Профилировали ли вы свое приложение, чтобы определить, вызывают ли у вас проблемы узкие места памяти или процессора?Если нет, то зачем жертвовать более удобным в обслуживании дизайном ради «оптимизации», которая не поможет вашим пользователям?

Я настоятельно рекомендую вам выбрать №2.Всякий раз, когда вы сохраняете что-то, что вместо этого могли бы вычислить, вы кешируете.Бывают случаи, когда кэширование — хорошая идея, но это также головная боль при обслуживании.(Например, что если вы переместите узел из одного дерева в другое, изменив его родительский элемент, но забудете также обновить корневое поле?) Не кэшируйте, если в этом нет необходимости.

Answer 5

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

Answer 6

Не обращая внимания на отвращение к внутренним классам, я мог бы определить класс Tree и определить узлы как внутренние классы.Каждый из узлов будет иметь доступ к состоянию своего дерева, включая его корень.

Это может оказаться таким же, как № 1, в зависимости от того, как Java связывает узлы с их родительскими узлами.(Я не уверен, и мне придется это профилировать)