Python-сообщество

artemu88 · Фев. 12, 2023 13:52:48

Добрый день!
Только начал изучать алгоритмы. Для закрепления решаю задачи на сайте.
Написал код для генерации перестановок по алгоритму Хипа.
Код ниже проходит все тесты без ошибок, но выдает превышение времени выполнения.
Прошу Вас подсказать, как можно ускорить этот код. Что можно почитать для самостоятельного изучения этой темы?

Всем Большое Спасибо!

 def permutations(string):
    a = list(string)
    lst = []
    return generate_arr(a, len(a), lst)
def generate_arr(lst, k, arr):
    if k == 1 and ''.join(lst[:]) not in arr:
        arr.append(''.join(lst[:]))
    else:
        for i in range(k):
            generate_arr(lst, k - 1, arr)
            if k % 2 == 0:
                lst[i], lst[k-1] = lst[k-1], lst[i]
            else:
                lst[0], lst[k-1] = lst[k-1], lst[0]
    return arr
string = 'baab'
print(permutations(string))

py.user.next · Фев. 12, 2023 15:22:49

artemu88
Прошу Вас подсказать, как можно ускорить этот код.

Тебе надо представить просто, как эти тесты проводятся. Вот он берёт и подаёт туда миллион элементов в списке. Ты этого не делал, а он взял и сделал. Соответственно, все твои копирования списков через срезы дадут большой прирост и по памяти, и по времени. То же самое относится к формированию строк внутри функции. Каждое формирование строки занимает много времени, потому что строки занимают больше места в памяти, чем числа.

  
>>> import sys
>>> 
>>> sys.getsizeof(1)
28
>>> sys.getsizeof('1')
50
>>> 
>>> sys.getsizeof(123)
28
>>> sys.getsizeof('123')
52
>>>
>>> sys.getsizeof(123) + sys.getsizeof(456)
56
>>> sys.getsizeof('123') + sys.getsizeof('456')
104
>>>

Да и вообще, я нашёл множество кодов этой генерации, где нет никаких списков, где их вообще не надо делать в функции.

Отредактировано py.user.next (Фев. 12, 2023 15:25:32)

artemu88 · Фев. 12, 2023 16:19:43

py.user.next
множество кодов этой генерации, где нет никаких списков, где их вообще не надо делать в функции.

Согласен, можно сделать и при помощи модуля itertools, но интересно самому реализовать алгоритм и понять его.

Спасибо за примеры и советы. Теперь понял куда копать.
Большое Вам спасибо!

py.user.next · Фев. 12, 2023 16:28:08

artemu88
можно сделать и при помощи модуля itertools

Без itertools там есть алгоритмы. Полинтернета этих алгоритмов есть, уже реализованных. Ты же не первый, кто этот алгоритм пытается написать. Там тысячи таких учеников, которые писали и написали.

artemu88 · Фев. 12, 2023 16:36:36

Спасибо! Пойду мучить Поиск

xam1816 · Фев. 12, 2023 18:34:45

py.user.next
Полинтернета этих алгоритмов есть, уже реализованных.

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

и этот же запрос в чате выдал результат

  
def heap_permutation(data, n):
    if n == 1:
        yield data
    else:
        for i in range(n - 1):
            yield from heap_permutation(data, n - 1)
            if n % 2 == 0:
                data[i], data[n - 1] = data[n - 1], data[i]
            else:
                data[0], data[n - 1] = data[n - 1], data[0]
        yield from heap_permutation(data, n - 1)
# пример использования
data = [1, 2, 3]
for permutation in heap_permutation(data, len(data)):
    print(permutation)

Отредактировано xam1816 (Фев. 12, 2023 18:36:59)

py.user.next · Фев. 12, 2023 23:31:12

xam1816
вот к примеру даже, набрал запрос в поисковике, там выдало сайты, в несколько заглянул мельком, там примеры с рекурсией

и этот же запрос в чате выдал результат

Так, и что?

  
>>> def f(n):
...     if n > 0:
...         yield from f(n - 1)
...     yield n
... 
>>> list(f(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> 
>>> list(f(1000))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in f
  File "<stdin>", line 3, in f
  File "<stdin>", line 3, in f
  [Previous line repeated 993 more times]
  File "<stdin>", line 2, in f
RecursionError: maximum recursion depth exceeded in comparison
>>>

Ой, а там есть рекурсия, оказывается

  
>>> def heap_permutation(data, n):
...     if n == 1:
...         yield data
...     else:
...         for i in range(n - 1):
...             yield from heap_permutation(data, n - 1)
...             if n % 2 == 0:
...                 data[i], data[n - 1] = data[n - 1], data[i]
...             else:
...                 data[0], data[n - 1] = data[n - 1], data[0]
...         yield from heap_permutation(data, n - 1)
... 
>>> list(heap_permutation([1, 2, 3, 4, 5, 6, 7, 8, 9, 10] * 100, 1000))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 6, in heap_permutation
  File "<stdin>", line 6, in heap_permutation
  File "<stdin>", line 6, in heap_permutation
  [Previous line repeated 992 more times]
  File "<stdin>", line 5, in heap_permutation
RecursionError: maximum recursion depth exceeded in comparison
>>>

А она-то сказала, что там рекурсии нет! Вот она врунья-то! Соврала тебе, а ты поверил.

Это хорошо, что она операцию тебе не делала на брюшной полости. Кетчуп бы залила тебе внутрь и сказала бы, что это физраствор типа. Инфа - сотка.

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

Вспомнился случай в институте. Преподша по матану даёт задачу всем, ну пример, типа решите его. Ну, бабы начинают решать там, им нужны оценки, поэтому они самые первые бросаются на всё, чтобы их считали хорошими, умными и так далее. Короче, решают-решают, решают-решают, решить не могут, не получается. Потом по новой начинают решать. Короче, решали три раза с самого начала. И потом такие говорят “всё, сдаёмся, не можем решить, как же она решается всё-таки?” и преподша такая говорит “а она не решается, я вам специально такую задачу дала, чтобы вы посмотрели”. Понимаешь, это ключевой момент. В мире, в реале, в дикой природе, в диком мире программ в том числе или там задач есть задачи, которые не решаются, у которых нет решения. И об этом нужно помнить. Это вот то, чему нас хотела научить преподша эта по матану. А эти девчонки просто дуры. Они так и будут всю жизнь долбиться лбом в стену, которую невозможно пробить, считая себя при этом очень умными.

Отредактировано py.user.next (Фев. 13, 2023 22:06:14)

artemu88 · Фев. 15, 2023 08:00:31

Решил отсавить решение тут, вдруг кому пригодится:

 def swap(a, b, c):
    '''
    функция для обмена значениями двух элемонтов списка
    '''
    a[b], a[c] = a[c], a[b]
    return a
def permute(s, j, a):
    '''
    функция для генерации перестановок
    '''
    if j == len(s):
        a.append(''.join(s))
    else:
        for i in range(len(s[:j+1])):
            s = swap(s, j, i)
            permute(s, j + 1, a)
            s = swap(s, j, i)
    return a
def permutations(s):
    '''
    основна функция
    '''
    s = list(s)
    a = []
    return list(set(permute(s, 0, a)))

Помимо форума, очень ещё помогло это видео:
https://www.youtube.com/watch?v=GuTPwotSdYw

Всем ещё раз большое спасибо!

Отредактировано artemu88 (Фев. 15, 2023 08:01:16)

Python-сообщество

Уведомления

#1 Фев. 12, 2023 13:52:48

Алгоритм перестановки. Ускорить код.

#2 Фев. 12, 2023 15:22:49

Алгоритм перестановки. Ускорить код.

#3 Фев. 12, 2023 16:19:43

Алгоритм перестановки. Ускорить код.

#4 Фев. 12, 2023 16:28:08

Алгоритм перестановки. Ускорить код.

#5 Фев. 12, 2023 16:36:36

Алгоритм перестановки. Ускорить код.

#6 Фев. 12, 2023 18:34:45

Алгоритм перестановки. Ускорить код.

#7 Фев. 12, 2023 23:31:12

Алгоритм перестановки. Ускорить код.

#8 Фев. 15, 2023 08:00:31

Алгоритм перестановки. Ускорить код.

Board footer