대수로 코드 최적화

Unsplash의 Roman Mager 사진

대학에서 한 학기 동안 "이산 수학"이라는 과목을 수강했습니다. 강사는 수업을 그룹으로 나누기로 결정했습니다. 각 그룹은 2~3명의 학생으로 구성되었습니다. 강사가 지정한 특정 주제에 대한 설명을 하기 위한 것이었습니다.

내가 속한 그룹(실제로 우리는 두 명뿐이었습니다)에서 우리는 순환 관계라는 주제를 할당받았습니다. According to Wikipedia , 이것은:

an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given: each further term of the sequence or array is defined as a function of the preceding terms.

즉, 재귀 함수;)

이 개념을 코드로 설명하기 딱 좋은 상황 :D

하노이 타워

이 장난감을 기억하시나요?



유명한 하노이 타워. 이 게임은 가능한 최소한의 단계로 모든 디스크를 첫 번째 극에서 마지막 극으로(왼쪽에서 오른쪽으로 또는 그 반대로) 이동하는 것으로 구성됩니다. 규칙은 더 큰 디스크가 더 작은 디스크 위에 있을 수 없으며 한 번에 하나의 디스크만 이동할 수 있다는 것입니다. 이 같은:



이 문제에는 이를 해결하는 알고리즘이 있으며 다음과 같습니다.


여기서 n은 문제의 디스크 수입니다.

그것을 코딩하자

Python을 사용하여 해당 알고리즘을 작성해 보겠습니다. 다음과 같습니다.

def hanoi(n):
    if n <= 1: return 1
    else: return 2 * hanoi(n-1) + 1

디스크가 4개라면...

>>> hanoi(4)
15

좋은. 효과가있다. 몇 번 시도해보자

>>> hanoi(5)
31
>>> hanoi(10)
1023
>>> hanoi(40)
1099511627775

꽤 좋아 보인다. 이제 40개의 디스크를 사용하는 경우 얼마나 많은 이동이 필요한지 알고 있습니다(btw, 이것은 10460년이 걸릴 것입니다. 집에서 시도하지 마십시오). 하지만 7000이 있다면 어떨까요?

>>> hanoi(7000)
Traceback (most recent call last):which
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in hanoi
  File "<stdin>", line 3, in hanoi
  File "<stdin>", line 3, in hanoi
  [Previous line repeated 994 more times]
  File "<stdin>", line 2, in hanoi
RecursionError: maximum recursion depth exceeded in comparison

아... 성능이 좀 부족한 것 같습니다. 물론 Python에서 최대 재귀 깊이를 늘리는 것만으로도 "해결"할 수 있지만(sys.setrecursionlimit(n) 포함) 이를 최적화하는 것이 훨씬 더 좋습니다.

최적화

반복 관계를 해결하는 방법에는 여러 가지가 있으며 그 중 하나가 반복입니다. 연산을 단계별로 풀고 그 과정에서 비재귀방정식을 빼는 것으로 구성된다. 먼저 주어진 값을 풀려고 합니다.



그런 다음 마지막 줄에서 동등한 방정식을 추론할 수 있습니다.



아시다시피 t(4) = 8 + 7 는 t(4) = 2^(4-1) + (2^(4-1) - 1) 와 동일합니다. 이것이 우리의 초기 진술인 이유입니다. 그러나 이제 우리는 반복 관계를 해결했습니다. 코드에서 사용하겠습니다.

def better_hanoi(n):
    return 2**n - 1

그리고...



이제 우리는 7000개의 디스크로 문제를 해결하는 데 몇 단계가 필요한지 알고 있습니다(아마도 우주의 수명, 여러 번).

결론

우리는 이산 수학의 개념으로 작은 알고리즘을 최적화했습니다. 이는 더 나은 프로그램을 구축하기 위해 이러한 간단한 개념의 이점을 얻을 수 있는 방법에 대한 약간의 통찰력을 제공하기 위한 것입니다.