Park Wooseong

Just Learn it

경로 찾기같은 문제에서 격자형 공간이 주어질 때가 있다.

그럴 경우 입력형태는 보통 두 가지 형태가 있다.

1
2
3
4
5
6

7 8 5 5 2 7
7 1 9 6 2 3
4 4 8 7 3 4
7 8 1 4 9 6
4 6 6 5 6 2
9 0 4 9 6 7

1
2
3
4
5
6

785527
719623
448734
781496
466562
904967

첫 번째 같이 공백으로 값이 구분된 경우 split을 하면 되지만 두번째 같은 경우는 리스트를 List[List[Any]] 식으로 저장할지 List[str]와 같이 저장할지 고민이 될 때가 있다. (int로 변환하지 않는다고 하자)

그리하여 str을 직접 참조하는 것과, 리스트로 바꾼 후에 참조하는 것 중 무엇이 더 빠른지 비교하는 코드를 작성하였다.

독립변수(변화시키는 것)는 다음과 같다.

  1. 배열의 크기
  2. 배열의 차원(1차원, 2차원)
  3. 참조 횟수
  4. 리스트 참조, 문자열 참조

실험 방식은 다음과 같다.

  1. 배열(문자열)을 선언한다.
  2. 리스트로 참조할 경우 해당 배열을 리스트로 감싸서 리스트 객체로 만든다.
  3. 인덱스를 이용하여 객체를 참조하고 언더바 변수(무의미) _에 저장한다.
  4. 3번을 지정된 횟수만큼 반복한다.

먼저 1차원을 살펴보자

Base 10 Symbol (name)
$10^{−3}$ m (milli)
$10^{−6}$ µ (micro)
$10^{−9}$ n (nano) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# --------------------
L = 100

array = "1"*L

# --------------------
for i in range(L):
    _ = array[i]
# --------------------
>>> 5.61 µs ± 486 ns per loop
# --------------------
t_list = list(array)

for i in range(L):
    _ = t_list[i]
# --------------------
>>> 6.17 µs ± 2.11 µs per loop
# --------------------
for a in range(100):
    for i in range(L):
        _ = array[i]
# --------------------
>>> 623 µs ± 110 µs per loop
# --------------------
t_list = list(array)

for a in range(100):
    for i in range(L):
        _ = t_list[i]
# --------------------
>>> 389 µs ± 6 µs per loop
# --------------------

실험 결과는 다음과 같다.

  1. 요소를 한 번씩만 참조할 경우 리스트로 변환하지 않고 직접 문자열을 참조하는 것이 더 빠르다.
  2. 참조 횟수가 많을 경우 리스트로 변환하는 것이 리스트로 변환하는 시간을 상쇄할 정도로 빠르다.

배열의 크기를 늘려도 이 추세가 유지되는지 확인해보자.

각 셀별로 %%timeit을 활용해서 시간을 측정하였다. 셀은 주석창으로 구분되며 각 셀의 %%timeit은 가독성을 위해 지웠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# --------------------
L = 10000

array = "1"*L
# --------------------
for i in range(L):
    _ = array[i]
# --------------------
>>> 835 µs ± 290 µs per loop
# --------------------
t_list = list(array)

for i in range(L):
    _ = t_list[i]
# --------------------
>>> 560 µs ± 9.67 µs per loop
# --------------------
for a in range(100):
    for i in range(L):
        _ = array[i]
# --------------------
>>> 83.9 ms ± 27.2 ms per loop
# --------------------
t_list = list(array)

for a in range(100):
    for i in range(L):
        _ = t_list[i]
# --------------------
>>> 48.3 ms ± 720 µs per loop
# --------------------

앞선 실험보다 다른 결과가 있는데 한 번만 참조할 때도 리스트가 더 빨랐다는 것이다. 이로써 다음 결과를 도출하였다.

  1. 문자열을 리스트로 바꾸는 것은 문자열을 하나씩 인덱싱하는 것에 비해 시간 복잡도가 훨씬 낮다.

2차원에서도 이 결과가 유지되는지 확인해보자

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# --------------------
L = 10

array = ["1"*L for _ in range(L)]
# --------------------
for r in range(L):
    for c in range(L):
        _ = array[r][c]
# --------------------
>>> 10.8 µs ± 3.27 µs per loop
# --------------------
t_list = [list(array[i]) for i in range(L)]

for r in range(L):
    for c in range(L):
        _ = t_list[r][c]
# --------------------
>>> 10.2 µs ± 94.1 ns per loop
# --------------------
for i in range(100):
    for r in range(L):
        for c in range(L):
            _ = array[r][c]
# --------------------
>>> 1.06 ms ± 344 µs per loop
# --------------------
t_list = [list(array[i]) for i in range(L)]

for i in range(100):
    for r in range(L):
        for c in range(L):
            _ = t_list[r][c]
# --------------------
>>> 906 µs ± 272 µs per loop
# --------------------

이전 실험에서의 가설과 실험결과가 일치한다. 배열의 크기를 늘려보자

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# --------------------
L = 100

array = ["1"*L for _ in range(L)]
# --------------------
for r in range(L):
    for c in range(L):
        _ = array[r][c]
# --------------------
>>> 683 µs ± 13.9 µs per loop
# --------------------
t_list = [list(array[i]) for i in range(L)]

for r in range(L):
    for c in range(L):
        _ = t_list[r][c]
# --------------------
>>> 753 µs ± 225 µs per loop
# --------------------
for i in range(10):
    for r in range(L):
        for c in range(L):
            _ = array[r][c]
# --------------------
>>> 6.96 ms ± 116 µs per loop
# --------------------
t_list = [list(array[i]) for i in range(L)]

for i in range(10):
    for r in range(L):
        for c in range(L):
            _ = t_list[r][c]
# --------------------
>>> 5.61 ms ± 127 µs per loop
# --------------------

2차원의 경우 2차원 리스트를 구성하는 데 좀 더 많은 시간이 걸린 것을 확인할 수 있다.

이로써 다음과 같은 결과를 도출하였다.

  1. List[str] -> List[List[str]] 변환시 속도는 ‘열’의 개수보다 ‘행’의 개수에 좌우된다.
  2. 참조 횟수가 적을 경우 리스트와 문자열의 참조 속도를 비교하기 힘들다 왜냐하면 리스트의 경우 문자열을 리스트로 바꾸는 과정이 존재하기 때문이다.
  3. 참조 횟수가 많을 경우 무조건 리스트로 바꾸는 것이 유리하다.

참고