Покончить с глобалами?

Question

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

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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