Код занимает слишком много времени

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

ex input 8
Ответ должен быть: (1, 2, 3, 4, 7, 6, 5, 8)
Код следующим образом ….

  • Python-get строка между символами
  • Печать списков в виде табличных данных
  • Получение хромовой производительности и отслеживание журналов
  • Правильная печать функций Выход и отсутствие
  • Фильтрация по имени ключа объекта в Google App Engine на Python
  • (Python) добавление списка в другой без скобок
  • import itertools x = raw_input("please enter a number") range_x = range(int(x)+1) del range_x[0] result = list(itertools.permutations(range_x)) def prime(x): for i in xrange(1,x,2): if i == 1: i = i+1 if x%i==0 and i < x : return False else: return True def is_prime(a): for i in xrange(len(a)): print a if i < len(a)-1: if prime(a[i]+a[i+1]): pass else: return False else: return True for i in xrange(len(result)): if i < len(result)-1: if is_prime(result[i]): print 'result is:' print result[i] break else: print 'result is' print result[i-1] 

  • Написание и чтение последних (по дате) строк из базы данных
  • python NameError: имя 'файл' не определен
  • Учитывая большой список URL-адресов, какой способ проверить, какие из них активны / неактивны?
  • Тестирование допустимого ввода Python
  • Можно ли вводить пользователя без ввода новой строки?
  • В чем разница между «свойством» и «атрибутом» Python?
  • 4 Solutions collect form web for “Код занимает слишком много времени”

    Динамическое программирование, на помощь:

     def is_prime(n): return all(n % i != 0 for i in range(2, n)) def order(numbers, current=[]): if not numbers: return current for i, n in enumerate(numbers): if current and not is_prime(n + current[-1]): continue result = order(numbers[:i] + numbers[i + 1:], current + [n]) if result: return result return False result = order(range(500)) for i in range(len(result) - 1): assert is_prime(result[i] + result[i + 1]) 

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

    Для потомков ;-), вот еще один, основанный на нахождении гамильтонова пути. Это код Python3. Как написано, он останавливается при поиске первого пути, но его легко изменить, чтобы генерировать все пути. На моем ящике он находит решение для всех n с 1 до 900 включительно всего за одну минуту. Для n несколько превышающего 900, он превышает максимальную глубину рекурсии.

    Основной генератор ( psieve() ) является огромным излишеством для этой конкретной проблемы, но мне было удобно и не хотелось писать другое 😉

    Поиск пути ( ham() ) является рекурсивным поиском обратного отслеживания, используя часто (но не всегда) очень эффективную эвристику эвристики: из всех вершин, примыкающих к последней вершине пути до сих пор, посмотрите сначала на тех, у кого меньше всего остальные выходы. Например, это «обычная» эвристика, применяемая для решения проблем Knights Tour. В этом контексте он часто находит тур без необходимости возврата. Ваша проблема выглядит немного сложнее.

     def psieve(): import itertools yield from (2, 3, 5, 7) D = {} ps = psieve() next(ps) p = next(ps) assert p == 3 psq = p*p for i in itertools.count(9, 2): if i in D: # composite step = D.pop(i) elif i < psq: # prime yield i continue else: # composite, = p*p assert i == psq step = 2*p p = next(ps) psq = p*p i += step while i in D: i += step D[i] = step def build_graph(n): primes = set() for p in psieve(): if p > 2*n: break else: primes.add(p) np1 = n+1 adj = [set() for i in range(np1)] for i in range(1, np1): for j in range(i+1, np1): if i+j in primes: adj[i].add(j) adj[j].add(i) return set(range(1, np1)), adj def ham(nodes, adj): class EarlyExit(Exception): pass def inner(index): if index == n: raise EarlyExit avail = adj[result[index-1]] if index else nodes for i in sorted(avail, key=lambda j: len(adj[j])): # Remove vertex i from the graph. If this isolates # more than 1 vertex, no path is possible. result[index] = i nodes.remove(i) nisolated = 0 for j in adj[i]: adj[j].remove(i) if not adj[j]: nisolated += 1 if nisolated > 1: break if nisolated < 2: inner(index + 1) nodes.add(i) for j in adj[i]: adj[j].add(i) n = len(nodes) result = [None] * n try: inner(0) except EarlyExit: return result def solve(n): nodes, adj = build_graph(n) return ham(nodes, adj) 

    Этот ответ основан на предложении @Tim Peters о гамильтоновых путях .

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

     import multiprocessing as mp import sys def main(): number = int(sys.argv[1]) # directed graph, vertices: 1..number (including ends) # there is an edge between i and j if (i+j) is prime vertices = range(1, number+1) G = {} # vertex -> adjacent vertices is_prime = sieve_of_eratosthenes(2*number+1) for i in vertices: G[i] = [] for j in vertices: if is_prime[i + j]: G[i].append(j) # there is an edge from i to j in the graph # utilize multiple cpus q = mp.Queue() for _ in range(mp.cpu_count()): p = mp.Process(target=hamiltonian_random, args=[G, q]) p.daemon = True # do not survive the main process p.start() print(q.get()) if __name__=="__main__": main() 

    где Сито Эратосфена :

     def sieve_of_eratosthenes(limit): is_prime = [True]*limit is_prime[0] = is_prime[1] = False # zero and one are not primes for n in range(int(limit**.5 + .5)): if is_prime[n]: for composite in range(n*n, limit, n): is_prime[composite] = False return is_prime 

    а также:

     import random def hamiltonian_random(graph, result_queue): """Build random paths until Hamiltonian path is found.""" vertices = list(graph.keys()) while True: # build random path path = [random.choice(vertices)] # start with a random vertice while True: # until path can be extended with a random adjacent vertex neighbours = graph[path[-1]] random.shuffle(neighbours) for adjacent_vertex in neighbours: if adjacent_vertex not in path: path.append(adjacent_vertex) break else: # can't extend path break # check whether it is hamiltonian if len(path) == len(vertices): assert set(path) == set(vertices) result_queue.put(path) # found hamiltonian path return 

    пример

     $ python order-adjacent-prime-sum.py 20 

    Вывод

     [19, 18, 13, 10, 1, 4, 9, 14, 5, 6, 17, 2, 15, 16, 7, 12, 11, 8, 3, 20] 

    Выход представляет собой случайную последовательность, которая удовлетворяет условиям:

    • это перестановка диапазона от 1 до 20 (включая)
    • сумма смежных чисел является простой

    Время исполнения

    Для получения результата для n = 900 и экстраполяции времени как экспоненциальной функции требуется около 20 секунд, для n = 1000 требуется около 20 секунд:

    (нет установленного решения)

    Изображение создается с помощью этого кода:

     import numpy as np figname = 'hamiltonian_random_noset-noseq-900-900' Ns, Ts = np.loadtxt(figname+'.xy', unpack=True) # use polyfit to fit the data # y = c*a**n # log y = log (c * a ** n) # log Ts = log c + Ns * log a coeffs = np.polyfit(Ns, np.log2(Ts), deg=1) poly = np.poly1d(coeffs, variable='Ns') # use curve_fit to fit the data from scipy.optimize import curve_fit def func(x, a, c): return c*a**x popt, pcov = curve_fit(func, Ns, Ts) aa, cc = popt a, c = 2**coeffs # plot it import matplotlib.pyplot as plt plt.figure() plt.plot(Ns, np.log2(Ts), 'ko', label='time measurements') plt.plot(Ns, np.polyval(poly, Ns), 'r-', label=r'$time = %.2g\times %.4g^N$' % (c, a)) plt.plot(Ns, np.log2(func(Ns, *popt)), 'b-', label=r'$time = %.2g\times %.4g^N$' % (cc, aa)) plt.xlabel('N') plt.ylabel('log2(time in seconds)') plt.legend(loc='upper left') plt.show() 

    Установленные значения:

     >>> c*a**np.array([900, 1000]) array([ 11.37200806, 21.56029156]) >>> func([900, 1000], *popt) array([ 14.1521409 , 22.62916398]) 

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

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

     m = 8 n = m + 1 # Just so I don't have to worry about zero indexes and random +/- 1's primelen = 2 * m prime = [True] * primelen prime[0] = prime[1] = False for i in range(4, primelen, 2): prime[i] = False for i in range(3, primelen, 2): if not prime[i]: continue for j in range(i * i, primelen, i): prime[j] = False 

    Хорошо, теперь мы можем проверить для primality с prime[i] . Теперь легко сделать края графа. Если у меня есть число i, то какие числа могут появиться дальше. Я также воспользуюсь тем, что i и j имеют противоположную четность.

     pairs = [set(j for j in range(i%2+1, n, 2) if prime[i+j]) for i in range(n)] 

    Итак, здесь pairs[i] – это заданный объект, элементы которого являются целыми числами j такими, что i+j является простым.

    Теперь нам нужно пройти график. Это действительно то место, где требуется время, и все дальнейшие оптимизации будут сделаны здесь.

     chains = [ ([], set(range(1, n)) ] 

    chains будут отслеживать действительные пути, когда мы их прогуливаем. Ваш первый результат в кортеже. Второй элемент – все неиспользуемые числа или невидимые узлы. Идея состоит в том, чтобы вывести одну цепочку из очереди, сделать шаг вниз по пути и вернуть ее обратно.

     while chains: chain, unused = chains.pop() if not chain: # we haven't even started, all unused are valid valid_next = unused else: # We need numbers that are both unused and paired with the last node # Using sets makes this easy valid_next = unused & pairs[chains[-1]] for num in valid_next: # Take a step to the new node and add the new path back to chains # Reminder, its important not to mutate anything here, always make new objs newchain = chain + [num] newunused = unused - set([num]) chains.append( (newchain, newunused) ) # are we done? if not newunused: print newchain chains = False 

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

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

    РЕДАКТИРОВАТЬ

    Вот пример того, как вы можете реализовать свой приоритет пути. Мы назначим каждому пути счет и сохраним список chains отсортированный по этому счету. Для простого примера я предполагаю, что пути, содержащие «более сложные в использовании» узлы, заслуживают большего. То есть для каждого шага по пути оценка будет увеличиваться на n - len(valid_next) . Измененный код будет выглядеть примерно так.

     import bisect chains = ... chains_score = [0] while chains: chain, unused = chains.pop() score = chains_score.pop() ... for num in valid_next: newchain = chain + [num] newunused = unused - set([num]) newscore = score + n - len(valid_next) index = bisect.bisect(chains_score, newscore) chains.insert(index, (newchain, newunused)) chains_score.insert(index, newscore) 

    Помните, что вставка – O(n) поэтому накладные расходы на добавление этого могут быть довольно большими. Стоит сделать анализ на ваш алгоритм оценки, чтобы сохранить длину очереди len(chains) управляемой.

    Python - лучший язык программирования в мире.