Как Вы выполняете итерации по дереву?
Например, вы должны выполнить итерацию следующим образом:
#!/bin/bash
INPUT_FIELDS_LIST=( one two three four five)
REQ_FIELDS_LIST=( one six seven eight )
NON_INPUT_FIELDS_LIST=( two three seven eight nine )
for ifl in "${INPUT_FIELDS_LIST[@]}"
do
for rfl in "${REQ_FIELDS_LIST[@]}"
do
myvar=0
if [[ $ifl == "$rfl" ]]
then myvar=1; break
else continue
fi
done
for nifl in "${NON_INPUT_FIELDS_LIST[@]}"
do
myvar2=0
if [[ $ifl == "$nifl" ]]
then myvar2=1; break
else continue
fi
done
if [[ $myvar == 1 ]] || [[ $myvar2 == 1 ]]
then continue
else echo "$ifl"
fi
done
Выполнить итерацию по вторичным циклам вручную, а затем пометить их как недействительные.
Оператор if в конце проверяет, было ли сопоставлено какое-либо значение, если оно есть, оно переходит к следующей первичной итерации.
Выход:
four
five
8 ответов
Я не могу думать ни о каких больших алгоритмических улучшениях, но простая микрооптимизация, которую можно сделать, должна связать часто вызываемые методы (такие как stack.append / stack.pop) местным жителям (это сохраняет поиск по словарю),
def children(self):
stack = [self.entities]
push = stack.append
pop = stack.pop
while stack:
for e in pop():
yield e
if e.entities:
push(e.entities)
Это дает маленькое ускорение (на ~15%) моими тестами (использующий 100 обходов глубокого из 8 дерева с 4 детьми в каждом узле, дает мне ниже синхронизаций:)
children : 5.53942348004
children_bind: 4.77636131253
Не огромный, но стоящий выполнения, если скорость важна.
Если Ваше дерево не является действительно большим, или у Вас есть действительно высокие (реальные) требования для скорости, я выбрал бы рекурсивный метод. Легче читать, легче кодировать.
Вызовы рекурсивной функции весьма достоверно неэффективны, который является старым мифом о программировании. (Если они плохо реализованы, они могут подвергнуться большим издержкам, чем необходимый, но вызов их "невероятно неэффективный" прост неправильный.)
Помните: не оптимизируйте преждевременно и никогда не оптимизируйте, не сравнивая сначала.
Если у Вас есть много RAM, и дерево часто не изменяется, можно кэшировать результат вызова:
def children(self):
if self._children_cache is not None:
return self._children_cache
# Put your code into collectChildren()
self._children_cache = self.collectChildren()
return self._children_cache
Каждый раз, когда дерево изменяется, установите кэш ни на Один. В этом случае использование рекурсивных вызовов могло бы быть более эффективным, так как результаты накопятся быстрее.
Я не уверен, можно ли уменьшить издержки очень на полном, чтобы обход дерева при использовании рекурсии стек вызовов, вырастит некоторых, иначе необходимо вручную использовать стек для продвижения ссылок детей при посещении каждого узла. То, какой путь является самым быстрым и использует меньше памяти, зависит от дороговизны стека вызовов по сравнению с нормальным стеком. (Я предположил бы, что стек вызовов быстрее, так как он должен быть оптимизирован для его использования, и рекурсию намного легче реализовать),
Если Вы не заботитесь о порядке, Вы посещаете узлы, некоторые реализации деревьев на самом деле хранится в динамическом массиве или связанном списке или стеке, который можно пересечь линейно, если Вы не заботитесь о порядке, он пересечен.
Но почему важно иметь быстрый обход так или иначе? Деревья хороши для поиска, массивы/связанные списки хорошо для полного обхода. Если Вам часто нужно полный, чтобы обход, но немного поисков и вставок/удалений, заказанный связанный список мог бы быть лучшим, если поиск - то, что Вы делаете больше всего, Вы используете дерево. Если данные являются действительно крупными, так, чтобы память наверху могла представить невозможную рекурсию, необходимо использовать базу данных.
Я не знаю слишком много о внутренностях Python вызовов функции, но я действительно не могу предположить, что Ваш фрагмент кода быстрее, чем рекурсивное пересечение дерева.
Стек вызовов (используемый для вызовов функции, включая рекурсивные) обычно очень быстр. Движение к следующему объекту будет только стоить Вам единственного вызова функции. Но в Вашем отрывке - то, где Вы используете объект стека, идя в следующий объект, будет стоить Вам stack.append (возможно выделяющий память на "куче"), stack.push (возможно освобождающий память от "кучи"), и урожай.
Основная проблема с рекурсивными вызовами состоит в том, что Вы могли бы унести стек, если Ваше дерево становится слишком глубоким. Этого, вероятно, не произойдет.
Вот пара маленьких исправлений.
def children(self):
stack = [self.entities]
for e in stack:
yield e
if e.entities:
stack.extend(e.entities)
Я на самом деле думаю генератор, использование добавляет, не посещает все узлы. Я думаю, что Вы значите для extend стек со всеми объектами, нет append простой список объектов к стеку.
Кроме того, когда for цикл завершается, while цикл в Вашем исходном примере также завершится, потому что нет никакого изменения в пустом стеке после for цикл.
Я написал повторяющийся код обхода дерева в прошлом: это очень ужасно, и не быстро, если Вы не знаете точно, сколько детей не только каждое поддерево будет иметь, но и сколько уровней, там.