Как уменьшить время выполнения этого конкретного решения?

Я пытаюсь написать фрагмент кода, который будет генерировать перестановку, или некоторые серии символов, которые все разные рекурсивно.Как уменьшить время выполнения этого конкретного решения?

def getSteps(length, res=[]): 
    if length == 1: 
     if res == []: 
      res.append("l") 
      res.append("r") 
      return res 
     else: 
      for i in range(0,len(res)): 
       res.append(res[i] + "l") 
       res.append(res[i] + "r") 
      print(res) 
      return res 
    else: 
     if res == []: 
      res.append("l") 
      res.append("r") 
      return getSteps(length-1,res) 
     else: 
      for i in range(0,len(res)): 
       res.append(res[i] + "l") 
       res.append(res[i] + "r") 
      print(res) 
      return getSteps(length-1,res) 

def sanitize(length, res): 
    return [i for i in res if len(str(i)) == length] 

print(sanitize(2,getSteps(2)))

Так заносить бы

"LL", "LR", «RR, "RL" или некоторая перестановка ряда.

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

edit = Я хочу, чтобы иметь возможность переносить этот код на java или какой-либо другой язык, чтобы понять концепцию рекурсии, а не использовать внешние библиотеки и решить мою проблему, не понимая ее.

источник

2013-09-19 Swarage

ли стандартная библиотека предоставляет вам любые инструменты, которые вы могли бы полностью использовать или построить решение? http://docs.python.org/2/library/itertools.html – dm03514

Одной из вещей, которая могла бы улучшить производительность, было бы изменение «if res == []» на «if not res», поскольку пустые списки оцениваются в Ложно в Python. –

Благодарим вас за это, но я хочу, чтобы решение было рекурсивным, поскольку я пытаюсь создать своего рода «доказательство концепции» для рекурсии в этом фрагменте кода. Кроме того, я хочу, чтобы иметь возможность переносить это на java или C++, чтобы действительно понять концепцию больше, чем синтаксис. – Swarage

Есть ли способ объединить двоичный подход и рекурсивный подход?

Да и @gribbler пришли очень близко к тому, что в пост, к которому был прикреплен этот комментарий. Он просто складывал кусочки в «другом порядке».

Как вы можете построить все битстроны длины n в порядке возрастания (если рассматривать как двоичные целые числа)? Ну, если у вас уже есть все битстроны длины n-1, вы можете прикрепить их все 0, а затем префикс их снова 1. Это так просто.

def f(n): 
    if n == 0: 
     return [""] 
    return [a + b for a in "RL" for b in f(n-1)] 

print(f(3))

печатает

['RRR', 'RRL', 'RLR', 'RLL', 'LRR', 'LRL', 'LLR', 'LLL']

Заменить R с 0 и L с 1, и у вас есть 8 двоичных чисел от 0 до 7 в порядке возрастания.

источник

2013-09-19 02:26:08

Спасибо. Это было решение, которое я искал. Сначала я хотел сделать этот подход, который префикс результатов равен нулю, но мой метод был слишком избыточным Это быстро и эффективно выполняется. – Swarage

Вы должны изучить itertools. Существует функция, которая называется permutations, которая делает именно то, что вы хотите достичь здесь.

источник

2013-09-19 01:18:03

На самом деле «перестановки» - это не правильное слово. 'itertools.product' является правильным инструментом. 'map (''. join, product ('LR', repeat = n))' –

Ваш дизайн не работает. Если вы снова вызовете getSteps, res не будет пустым списком, у него останется мусор, оставшийся от последнего вызова в нем.

Я думаю, что вы хотите, чтобы генерировать перестановки рекурсивно, но я не понимаю, где вы собираетесь с getSteps функции

Вот простая рекурсивная функция

def fn(x): 
    if x==1: 
     return 'LR' 
    return [j+i for i in fn(x-1) for j in "LR"]

источник

2013-09-19 01:21:33

Я думаю, что это моя цель. Если я назову какую-нибудь функцию fn (x), то для некоторого числа выберем 3, fn (3) должен вернуть «LLL», «LLR», «LRL», «LRR», «RRR», «RRL», «RLR», «RLL» – Swarage

Если у вас есть только 2 значения, это намного проще. Представьте себе замену 'L = 0',' R = 1' теперь это просто выглядит как двоичные числа от 0-7 –

Это правда. Я понял, что вскоре после кодирования этого, но я не мог понять, как рекурсивно решить проблему. Есть ли способ объединить двоичный подход и рекурсивный подход? – Swarage

Как уменьшить время выполнения этого конкретного решения?

ответ

Смежные вопросы