Делая с глобалами?

Question

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

Пара решений:

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

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

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

Answer 1

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

Edit: Варианты на самом деле следующее:

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

Я думаю, что это все возможностей нет, нет варианта 5.

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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