Какой самый эффективный способ создать дерево в Java?

Question

Я создаю дерево в Java для моделирования экстенсивной формы игры для ИИ. Дерево будет представлять собой 25-арное дерево (дерево, в котором каждая ветвь имеет максимум 25 дочерних веток), потому что на каждом ходу игры есть 25 различных ходов. Поскольку число новых ветвей, которые должны быть созданы в каждом новом слое дерева, равно 25 ^ n, я очень заинтересован в том, чтобы сделать это эффективным. (Я намерен безжалостно срезать ветки, чтобы они не росли, чтобы не увязнуть). Как лучше всего моделировать такое дерево, когда эффективность вызывает такое беспокойство? Мое первое впечатление - иметь объект узла, где у каждого узла есть родительский узел и массив дочерних узлов, но это означает создание большого количества объектов. В конечном итоге это мои вопросы:

Это самый быстрый способ создания и управления моим деревом?

Какой хороший способ выяснить, сколько времени займет тот или иной алгоритм или процесс в программе? (пока я думал только о том, чтобы создать дату до процесса, а затем после и сравнить число прошедших миллисекунд)

Любые другие мысли также приветствуются. Мой вопрос подразумевает и связан с большим количеством других вопросов, я бы ожидал. Если я был неоднозначен или неясен, пожалуйста, прокомментируйте, чтобы сообщить мне, вместо того, чтобы понижать голосование и штурмовать, поскольку это не продуктивно

Answer 1

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

Снова и снова люди задают вопросы о том, как сделать что-то «эффективно».Лучший ответ почти всегда, "даже не пытайтесь".Если ваше улучшение не является алгоритмическим, оно вряд ли что-то изменит в любом случае, и особенно в таком случае, дополнительные усилия и сложность не стоят того минимального выигрыша, которого вы могли бы достичь.

по-другому, и заимствовать цитату (хотя я не могу вспомнить автора), первое правило оптимизации: не.

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

Answer 2

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

С другой стороны, я осознаю несколько важных вещей:

1. Коэффициент ветвления 25: Несмотря на то, что он невероятно велик, он все же велик по сравнению с другими проблемами. Для дерева вам обязательно нужно будет иметь список для каждого узла, чтобы указать список подузлов. Вы можете сделать это либо создав класс Node, в котором есть набор узлов, либо создать внешнюю карту, которая отображает данный узел в список дочерних узлов.

2. Будет выполнено удаление и добавление элементов. Это позволяет реализовать реализацию сохраненных дочерних элементов LinkedList, поскольку вы не хотите выполнять дорогостоящие операции удаления и добавления. HashSet может также работать, но проблема в том, что вам может потребоваться больше памяти.

3. Итерация элементов может выполняться или не выполняться: если вы хотите выполнять итерацию по всему списку на каждом шаге, LinkedLists подойдут. Если вы хотите расставить приоритеты для узлов, вы можете экономить память, используя структуру данных очереди с приоритетами. Очереди с приоритетами особенно полезны, если вы собираетесь реализовать эвристическую функцию и определить, к какому дочернему элементу перейти в любом данном узле.

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