Покончить с Globals?
У меня есть набор древовидных объектов с глубиной где-то в 20-е годы. Каждому из узлов в этом дереве необходим доступ к корню своего дерева.
Пара решений:
- Каждый узел может хранить ссылку на корень напрямую (тратит память)
- Я могу вычислить корень во время выполнения, "поднявшись" (тратит циклы)
Я могу использовать статические поля (но это глобальные переменные)
Может ли кто-нибудь предоставить дизайн, который не использует глобальный (в любом варианте), но более эффективен, чем №1 или №2 как в памяти, так и в циклах соответственно?
Редактировать: Поскольку у меня есть набор деревьев, я не могу просто сохранить его в статике, так как было бы трудно различать деревья. (спасибо Maccullt)
Ответы 6
Передайте корень в качестве параметра тем функциям в узле, которым он нужен.
Обновлено: параметры действительно следующие:
- Сохраните корневую ссылку в узле
- Не храните корневую ссылку вообще
- Сохраните корневую ссылку в глобальном
- Сохраните корневую ссылку в стеке (мое предложение, либо шаблон посетителя, либо рекурсивный)
Думаю, это все возможности, варианта 5 нет.
Аля Visitor выкройка аккуратная. Я не думал об этом.
В find это может быть очень болезненным, когда что-то меняется, особенно когда стеки вызовов становятся глубже.
Я не интерпретировал это как рекурсивный. У меня мог бы быть фрагмент кода, который проходит по дереву и выполняется на каждом узле. В этом коде будет ссылка на корень.
Зачем вам нужно отказываться от глобальных переменных? Я понимаю, что глобальные переменные - это плохо и все такое, но иногда просто иметь глобальную структуру данных со всеми элементами - самое быстрое решение.
Вы идете на компромисс: ясность кода и меньше проблем с производительностью в будущем. Это означает, что «пока не оптимизируйте». Поскольку вы находитесь на этапе оптимизации, иногда необходимо отказаться от некоторых удобочитаемости и хороших методов программирования в пользу производительности. Я имею в виду, что побитовые хаки не читаются, но они быстрые.
Я не уверен, сколько у вас есть древовидных объектов, но лично я бы выбрал первый вариант. Если вы не имеете дело с тысячами + деревьев, указатели на самом деле не будут содержать намного больше, чем несколько строк. Если память действительно является очень важной проблемой, попробуйте оба метода (они кажутся довольно простыми в реализации) и запустите их через профилировщик. Или используйте отличный Обозреватель процессов.
Обновлено: одно из приложений, над которыми я работаю, имеет дерево узлов, содержащее около 55 тыс. Узлов. Мы строим древовидную структуру, но также поддерживаем массив для поиска O (1). Намного лучше, чем O (m * n), которое мы получали при использовании рекурсивного метода FindNodeByID.
80к ... ?? ты волнуешься меньше десятой доли мега ... ?? звучит так, будто вы переживаете из-за несуществующей проблемы
Не напрягая, просто любопытно. Я подумал, что это интересный вопрос.
80K - это тривиально, если до этого дойти. Когда я впервые увидел код, я был очень "бестолковым", пока не прогнал его через профилировщик и не понял, что наши выделения String были примерно в 400 раз больше.
Пункт №1 - преждевременная оптимизация памяти. №2 - преждевременная оптимизация производительности. Вы профилировали свое приложение, чтобы определить, не вызывают ли у вас проблемы из-за узких мест в памяти или ЦП? Если нет, зачем жертвовать более удобным дизайном ради «оптимизации», которая не помогает вашим пользователям?
Я настоятельно рекомендую вам выбрать №2. Всякий раз, когда вы сохраняете что-то, что могли бы вместо этого вычислить, вы делаете кеширование. В некоторых случаях кеширование - хорошая идея, но это еще и головная боль при обслуживании. (Например, что, если вы переместите узел из одного дерева в другое, изменив его родительский элемент, но забудете также обновить корневое поле?) Не кэшируйте, если вам это не нужно.
Вы можете унаследовать класс от TreeView, а затем добавить одноэлементное статическое свойство. Таким образом, вы эффективно добавляете глобальное поле, которое ссылается на единственный экземпляр класса, но имеет то преимущество, что пространство имен ограничено этим классом.
Игнорируя отвращение к внутренним классам, я мог бы определить класс Tree и определить узлы как внутренние классы. Каждый из узлов будет иметь доступ к состоянию своего дерева, включая его корень.
Это может оказаться таким же, как №1, в зависимости от того, как Java связывает узлы с их родителями. (Я не уверен, и мне придется это профилировать)
Я почти уверен, что это будет то же самое, что и №1, на самом деле нет другого способа реализовать это.
Как правило, лучше всего передавать корень в качестве параметра. Если вы используете какой-то итератор для навигации по дереву, альтернативой является сохранение в нем ссылки на root.
Неясно, есть ли у вас лес деревьев, и в этом случае вам нужно несколько корней или у вас один корень. В случае с лесом я не понимаю, как статика решит вашу проблему, разве вам не нужен один корень для каждого дерева, и каждое дерево будет ссылаться на свой корень (решение 1).