[Python] +, append(), extend() 사용법과 내부로직

combinations, permutations 문제를 풀다가 생긴 문제이다.

조합, 순열의 결과 값은 튜플형태로 나온다.

 

예를 들어,

from itertools import combinations, permutations
import sys

num = sys.stdin.readline().rstrip()
x = [num[i] for i in range(len(num))]

permus = [] 
for i in range(1, len(x)+1):
    permu = list(permutations(x,i))
    print(permu)

위코드는 "리스트에 해당하는 모든 순열"을 구하는 코드이다.

input	output
127	[('1',), ('2',), ('7',)] [('1', '2'), ('1', '7'), ('2', '1'), ('2', '7'), ('7', '1'), ('7', '2')] [('1', '2', '7'), ('1', '7', '2'), ('2', '1', '7'), ('2', '7', '1'), ('7', '1', '2'), ('7', '2', '1')]

라고 n개에 해당하는 모든 순열을 구한다 (예시는, 길이가 3이므로 1~3개 의 해당하는 순열을 구한다.)

 

이때 

permus = []라는 리스트에서 모든 원소를 일차원 리스트로 저장하고 싶은데, 어떻게 해야 할까?

만약. append() 함수를 이용해서 저장한다면 

output은 

output

[ [('1',), ('2',), ('7',)], [('1', '2'), ('1', '7'), ('2', '1'), ('2', '7'), ('7', '1'), ('7', '2')], [('1', '2', '7'), ('1', '7', '2'), ('2', '1', '7'), ('2', '7', '1'), ('7', '1', '2'), ('7', '2', '1')] ]

이렇게 저장되게 된다.

 

따라서 extend() 함수를 이용해야 한다.

 

# extend()

append()와 다르게 extend()는 삽입 대상의  "모든 iterable자료형"에 대해서 "각각의 엘리먼트"로 확장(Extend)해 삽입

*iterable: 반복가능한 

따라서 위에 식을 적용한다면 코드는 다음과 같다.

 

from itertools import combinations, permutations
import sys

num = sys.stdin.readline().rstrip()

x = [num[i] for i in range(len(num))]

permus = [] 
for i in range(1, len(x)+1):
    permu = list(permutations(x,i))
    permus.extend(permu)

print(permus)

예시를 대입해 보면 

input	output
127	[('2',), ('1',), ('7',),  ('2', '1'), ('2', '7'), ('1', '2'), ('1', '7'), ('7','2'), ('7', '1'),  ('2', '1', '7'), ('2', '7', '1'), ('1', '2', '7'), ('1', '7', '2'), ('7', '2', '1'), ('7', '1', '2')]

과 같은 코드로 바뀐다.

 

"iterable한 모든 자료형"의 대해 동작하므로 

list, tuple, 문자열, set, dictionary들이 들어갈 수 있다.

 

# extend 예제

1. 문자열

my_list = [1, 2, 3]
my_list.extend("hello")
print(my_list)  # 출력: [1, 2, 3, 'h', 'e', 'l', 'l', 'o']

 

2. set

my_list = [1, 2, 3]
my_set = {4, 5}
my_list.extend(my_set)
print(my_list)  # 출력: [1, 2, 3, 4, 5]

 

3. dictionary

my_list = [1, 2, 3]
my_dict = {'a': 6, 'b': 7}
my_list.extend(my_dict.keys())
print(my_list)  # 출력: [1, 2, 3, 'a', 'b']

처럼 사용이 가능합니다.

 

# append(), extend(), + 차이 

+알파로 둘의 (append(), +, extend())  차이가 존재한다.

a = [1, 2, 3]
a = a + [4,5]
print(a)
# [1, 2, 3, 4, 5]

a = [1, 2, 3]
a.extend([4,5])
print(a)
# [1, 2, 3, 4, 5]

를 보면 둘 다 같은 결괏값을 도출한다. 

내부로직에서는 어떻게 변화할까? - append()도 같이 분석해 보자.

+	append()	extend()
b = [1,2,3] print('original id:', id(b)) b = b + [[4,5]] print('+ id:', id(b))	b = [1,2,3] print('original id:', id(b)) b.append([4,5]) print('append id:', id(b))	b = [1,2,3] print('original id:', id(b)) b.extend([4,5]) print('extend id:', id(b))
original id: 2359106440768 + id:           2359106439872	original id: 2359106439872 append id: 2359106439872	original id: 2359106440768 extend id: 2359106440768
주소: 바뀜	주소: 같음	주소: 같음

테스트 시, 이런 결과가 나왔다.

 

하지만 "간과한 사실"이 있다.

append(), extend()는 동적배열에 형태로 추가된다.

이때, append()를 예로 들면,

 

만약에 연속된 메모리의 자리가 없을 경우 새로운 큰 공간을 만들어 모든 값들을 복사시켜야 하기에 

이 경우, 여기서 꽤나 큰 overhead가 발생한다. (속도저하)

=> 따라서 이럴 경우 새로운 메모리를 할당받기에 주소가 변화된다.

 

따라서 큰 space가 필요한 경우 (ex. dp, 2차원배열 등)

미리 N개의 공간을 만들어두고 값을 대입합니다.

 

# solution, 속도최적화

def makeListUsingBulkAlloc(N):
    result = [0]*N #한번에 N개의 공간을 0으로 채우는 방법입니다.
    for i in range(N):
        result[i] = i
    return result

이런 식으로 가능하다.

 

여기서 조금 더 최적화하고 싶으면 Built-in(내장된) 함수를 사용한다.

range() 함수는 Built-in함수로 C언어로 최적화되어 있다. (더 빠른 속도 자랑)

def makeListUsingBuiltin(N):
    return range(N)

 

# 결과 (+, append(), extend() )

1. +
   1. 리스트가 더해진 새로운 리스트반환 (속도 느림)
2. append()
   1. 메모리 가능할 시: "주소 그대로 유지"하여 값 추가하여 반환(속도 빠름)
      메모리 부족할 시:리스트가 더해진 "새로운 리스트"반환(매우 큰 overhead)
   2. "iterable 자료형"의 요소를 각각 추가하는 것이 불가능
3. extend()
   1. 메모리 가능할 시: "주소 그대로 유지"하여 추가하여 반환 (속도 빠름)
      메모리 부족할 시:리스트가 더해진 "새로운 리스트"반환(매우 큰 overhead)
   2. "iterable 자료형"의 요소를 각각 추가하는 것이 가능