Эффективная память Рекурсия

Question

Я написал приложение на C #, которое генерирует все слова, которые могут существовать в комбинации алфавитов, цифр и нескольких специальных символов.

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

Есть ли способ заставить его работать в среде с ограниченной памятью?

Umair

Answer 1

Преобразовать его в итерационную функцию .

Answer 2

Ну ... я не уверен, с кем я пойду среди вас, но у меня есть решение. Я использую более одного процесса, который взаимодействует с пользователем, а другой - для нахождения словосочетания. Другой процесс находит 5000 слов, сохраняет их и выходит. Связь достигается через WCF. Это выглядит довольно хорошо, как при выходе из процесса = освобождает память.

Answer 3

К сожалению, компилятор C # не выполняет оптимизацию хвостового вызова , что вам и нужно в этом случае.CLR поддерживает это, вроде , но вы не должны на это полагаться.

Возможно, слева от поля, но, возможно, вы можете написать рекурсивную часть вашей программы на F #?Таким образом, вы можете использовать гарантированную оптимизацию хвостового вызова и повторно использовать биты своего кода C #.В то время как крутая кривая обучения, F # является более подходящим языком для этих комбинаторных задач.

Answer 4

Еще одно соображение: когда вы объединяете или используете какой-то другой метод для генерации строки в C #, она занимает собственную память и может некоторое время задерживаться. Если вы генерируете миллионы строк, вы, вероятно, заметите некоторое снижение производительности.

Если вам не нужно хранить множество строк, я бы посмотрел, есть ли что-нибудь, чтобы избежать генерации строк. Например, возможно, у вас есть массив символов, который вы обновляете при перемещении по комбинациям символов, и если вы выводите их в файл, вы выводите их по одному символу за раз, поэтому вам не нужно создавать строка.

Answer 5

Ну, очевидно, вы не можете хранить промежуточные результаты в памяти (если у вас нет какого-то абсурдного компьютера в вашем распоряжении);вам нужно будет записать результаты на диск.

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

Например, моя установка python 2.6.2 имеет предел рекурсии по умолчанию, установленный на 1000. Аргументируемый, я должен быть в состоянии генерировать все возможные строки длиной 1-1000 с учетом набора символов в пределах этого ограничения (теперь, я думаю, что предел рекурсии применяется к общей глубине стека, поэтомупредел может быть меньше 1000).

Редактировать (добавлен пример Python): Следующий фрагмент кода Python произведет то, что вы запрашиваете (ограничивая себя заданными пределами стека времени выполнения):

from string import ascii_lowercase

def generate(base="", charset=ascii_lowercase):
    for c in charset:
        next = base + c
        yield next
        try:
            for s in generate(next, charset):
                yield s
        except:
            continue

for s in generate():
    print s

Можно получить практически то же самое в C #, попробовав / поймав исключение StackOverflowException.Когда я набираю это обновление, скрипт работает, жуя одно из моих ядер.Тем не менее, использование памяти является постоянным и составляет менее 7 МБ.Теперь я печатаю только на стандартный вывод, поскольку мне не интересно запечатлеть результат, но я думаю, что это доказывает вышеприведенную точку.;)

Добавление к примеру: Интересное примечание: Если присмотреться к запущенным процессам, Python фактически связан с вводом-выводом в приведенном выше примере.Он использует только 7% моего ЦП, в то время как остальная часть ядра привязана к выводу результатов в моем командном окне.Минимизация окна позволяет Python подняться до 40% от общего использования ЦП, это на 2-ядерном компьютере.