[naver boostcourse] Python data structure/ 데이터 스트럭쳐

Q. 특징이 있는 정보를 어떻게 저장하면 좋을까?

 

intro

데이터 구조 생각해보기

- 전화번호부 정보는 어떻게 저장하면 좋을까?

- 은행 번호표 정보는 어떻게 처리하면 좋을까?

- 창고에 쌓인 수화물의 위치를 역순으로 찾을 때?

효율적으로 데이터를 뽑고 처리할 필요

 

파이썬 기본 데이터 구조

- 스택과 큐(stack & queue with list)

- 튜플과 집합(tuple & set)

- 사전 (dictionary)

- collection 모듈

 

 

 

1. Stack

의미

- 나중에 넣은 데이터를 먼저 반환하도록 설계하는 메모리구조 (like 택배 화물차)

- Last In First Out > LIFO

- Data의 입력을 Push, 출력을 Pop이라고 함 

 

stack with list object

- 리스트를 사용해 스택 구조를 구현 가능

- push == append(), pop == pop()

- pop() : return O, 리스트에서 원소 삭제

- sort() : return X, 정렬만

- sorted() : return O, 정렬된 값을 return

 

 

입력된 글자를 역순으로 출력

word = input("input a word: ")
word_list = list(word)

for i in range(len(word_list)):
	print(word_list.pop())
    print(word_list)
-------------------------------------------------
>> input a word : naver
>> r
>> ['n', 'a', 'v', 'e']
>> e
>> ['n', 'a', 'v']
>> ...
>> ...
>> n
>> []

 

 

2. Queue

- 먼저 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조

- stack과 반대 개념

- First In First Out(FIFO)

a = [1, 4, 6, 13, 21, 26, 33]
first = a.pop(0)
a
>> [4, 6, 13, 21, 26, 33]

a,pop(0)     # 출력
>> 4

 

 

3. Tuple

- 값의 변경이 불가능한 리스트

    - 'tuple' object does not support item assignment

- []이 아닌 ()를 활용함

1 = (1, 2, 3)

print(t+t)
>> (1, 2, 3, 1, 2, 3)

print(t*2)
>> (1, 2, 3, 1, 2, 3)

t[1] = 5
type error : tuple object does not support item assignment

왜쓸까?

- 프로그램을 잘동하는 동안 변경되지 않은 데이터의 저장

- 학번, 이름, 우편번호 등

- 함수의 반환값 등 사용자의 실수에 의한 에러를 사전에 방지

 

 

 

 

4. Set

- 값의 순서는 없고, 중복 불허하는 자료형

- set 객체 선언을 이용해 객체 생성

# 1, 2, 3 이란 집합 객체 생성
s = set([1, 2, 3, 1, 2, 3])
s
>> {1, 2, 3}

a = {1,2,3,4,5}
type(a)
>> set

s = {2,3}
s.add(1)
s
>> {1, 2, 3}


s.remove(1)
s
>> {2,3}

s.update([1,4,5,6,7])                    # [1,4,5,6,7] 추가, 한번에 여러개
s
>> {1,2,3,4,5,6,7}

s.discard(3)
s
>>[1,2,4,5,6,7]

s.clear()                       # 모든 원소 삭제
s
>> set()

- 수학에서 활용하는 다양한 집합연산 가능

s1 = set([1,2,3,4,5])
s2 = set([3,4,5,6,7])
type(s1)m type(s2)
>> (set, set)


# 합집합
s1.union(s2)
>> {1,2,3,4,5,6,7}

s1 | s2
>> {1,2,3,4,5,6,7}


# 교집합
s1.intersection(s2)
>> {3,4,5}

s1 & s2
>> {3,4,5}


# 차집합
s1.difference(s2)
>> {1,2}

s1 - s2
>> {1,2}

 

 

5. Dictionary

- 데이터를 저장할 때, 구분지을 수 있는 값을 함께 저장

- 주민등록번호, 제품모델번호

- 구분을 위한 데이터 고유값을 identifier 혹은 key라고 함

- key값을 활용하여 데이터값(value)를 관리함

# dict 데이터 출력
dict1.items()
>> dict_items(['America',1}, {'Korea', 82} ... }])

# reading만 가능함!!?
for dict_items in dict1.items():
	print(type(dict_items))
>> <class 'tuple'>
	<class 'tuple'>
    <class 'tuple'>
    
# 그래서 unpacking이 일어나게됨
for k, v in dict1.itmes()
	print('key:", k)
    print('value:', v)
    


# only key
dict1.keys()
>> dict_keys(['America', 'Korea', ...])

'Korea' in dict1.keys()
>> True

# only value
dict1.values()
>> dict_values([1, 82, 86, 81, 55]) 


# add
dict1['newKeyName'] = 'new key value'
dict1
>> {'America':1, 'Korea':82, .., 'newKeyName':'new key value'}

 

 

Lab - dict

6. command

- 사용자의 서버가 입력한 명령어, 이 아이디가 입력함

- url > download

- cmd  > wget url? > 파일명 이상함, env ~~ 로 바꿔줘라

 

7. Collections

- list, tuple, dict에 대한 python built-in 확장 자료 구조(모듈)

- 편의성, 실행 효율 등을 사용자에게 제공함 (효율 == 메모리사용량을 줄이거나 혹은 빠르게)

 

7-1. deque

- stack & queue를 지원하는 모듈

- list에 비해 효율적인 = 빠른 자료 저장방식을 가짐

from collections import deque

deque_list = deque()
for i in range(5):
	deque_list.append(i)     # append 지원됨
print(deque_list)
>> deque([0, 1, 2, 3, 4])

- rotate, reverse 등 linked list의 특성을 지원함

- 기존 list 형태의 함수를 모두 지원함

- .append()

deque_list.append(100)
print(deque_list)
>> deque([0, 1, 2, 3, 4, 100])


# appendleft(i) == insert(0, i)
deque_list.appendleft(10)
print(deque_list)
>> deque([10, 0, 1, 2, 3, 4, 100])

-  .rotate(i) : i 만큼 건너가며 순환함

# rotate
deque_list.rotate(1)
deque_list
>> deque([3,4,10,0,1,2, 100])

- extend()

# extend
deque_list.extend([5,6,7])
deque_list
>> deque([3, 4, 10, 0, 1, 2, 100, 5, 6, 7])

deque_list.extendleft([5,6,7])
>> deque([5, 6, 7, 3, 4, 10, 0, 1, 2, 100, 5, 6, 7])

- deque는 기존 list보다 효율적인 자료구조를 제공

- 효율적인 메모리 구조로 처리속도 향상

    - time의 clock이란 모듈, 시간이 얼마나 소요되는지

    - jupyter notebook, %timeit function() : 시간을 재는 모듈(명령어), 평균시간에 대한 오차까지 정보제공됨

#deque
from collections improt deque
import time

start_time = time.clock()
deque_list = deque()

# stack
for i in range(10000):
	for i in range(10000):
    	deque_list.append(i)   # 넣고
        deque_list.pop()       # 출력하고 빼고
print(time.clock() - start_time, "seconds")

# list
import time

start_time = time.clock()
just_list = []
for i in range(10000):
	for i in range(10000):
    	just_list.append(i)
        just_list.pop()
print(time.clock() - start_time, "seconds")

 

 

7-2. OrderedDict

- dict와 달리, 데이터를 입력한 순서대로 dict를 반환함

- dict도 python 3.6부터 입력한 순서를 보장하여 출력함

- 현재, 보장 O

from collections import OrderedDict

d = {}
d['x'] = 100
d['y'] = 320
d['z'] = 80

for k, v in d.items():
	print(k, v)

def get_key(x):
	return [0]
    
sorted(d.itmes(), key=lambda t:t[0])
>> [('l', 500), ('x',100), ('y',200), ('z',300)]

- 과거, 보장 X -> OrderedDIct를 써야했다

for k, v in OrderedDict(sorted(d.items(), key=lambda t:t[0])).items()):
	print(k, v)
>> l 500
	x 100
    y 200
    z 300

 

 

 

7-3. defaultdict

- dict type의 값에 기본 값을 지정할 때, 신규값 생성시 따로 뭘 안넣어줘도 생성됨

- 초기값을 지정해주지 않아도 자동 지정

 

- key, value지정해줘야하는 dict

d = dict()
print(d['first'])

>> keyError

- key가 없는 경우, error가 아닌 특정 default 값을 줘라

from collections import defaultdict

d = defaultdict(object)       # default dictionary(객체)를 생성
d = defaultdict(lambda : 0)   # default값을 0으로 설정함, (람다함수로 넣어줌)
d
>> defaultdict(<function __main__.<lambda>()>, {})      # 빈 dict라고 나옴

print(d['first']     # 하지만 임의 key 넣으면 0 출력
>> 0

def default_value():
	return 10

d = defaultdict(default_value)
d['ss']
>> 10

 

 

- 하나의 지문에 각 단어들이 몇 개나 있는지 세고 싶은 경우

- test-mining 접근법 - Vector Space Model

from collections import OrderDict

d = defaultdict(lambda :0)

for word in text.split():
	d[word] += 1

sorted_dict = OrderedDict()
for i, v in sorted(d.items((, key=get_key, reverse=True):   # 정렬
	sorted_dict[i] = v
print(sorted_dict)
sorted_dict['to']

test = """  a press release is the quickest and easiest way to get free public ~
				~~ .""".lower().split()

print(text)

 

 

 

7-4. Counter

- syquence type의 data element들의 갯수를 dict 형태로 반환

from collections import counter

ball_or_strike_list = ['b' , 's', 's', 's', 's', 's', 'b', 'b']

c = Counter(ball_or_strike_list)     $ a new counter from an iterable
c
>> Counter({'b':3, 's':4})

- a new counter from a mapping

c = Counter ({'red':4, 'blue':2})
print(list(c.elemcnts()))
>> ['red', 'red', 'red', 'red', 'blue', 'blue']

- a new counter from keyword args

c = Counter(cats=4, dogs=8)
print(list(c.elements()))

 

- set의 견산들을 지원함 : +, &, |

- text

text = "sdlkfjlskdjf sdlkfjlsdkjf  ```"
sorted(Counter(text).items(), key=lambda t :t[1], reverse=True)
print(Counter(text)['a'])

 

 

7-5. namedtuple

- tuple 형태로 data 구조체를 저장하는 방법

- 저장되는 data의 variable을 사전에 지정해서 저장함

from collections import namedtuple

# Point 선언
Point = namedtuple('Point', ['x', 'y'])      # namedtuple(tuple_name, elemens(들어가는 값들
Point
>> __main__.Point

# 구조체 이름은 Point, x와 y의 값
p = Point(x = 11, y = 22)
print(p[0] + p[1])
>> 33


x, y = p
print(x, y)
>> 11, 22

print(p.x, p.y)    # 이런식으로 불러와 쓸 수 있음
>> 33

- 불러온 데이터에서 student라는 구조체 만들어보기

from collections import namedtuple
improt csv

f = open('students_info.csv', 'r')
next(f)
reader = csv.reader(f)

student_list = []
for row in reader:
	student_list.append(row)

print(student_list)
>> [['sdf', 'sdf', ~~~], [``], ``[[``]``` ]


student_namedtuple_list = []
for row in student_list:
	print(row)
    student = Student(*row)
    print(student)
#    student_namedtuple_list.append(student)

# print(student_namedtuple_list[0])
# print(student_namedtuple_list[0].full_name)