{ : 'awesome'} 구종만 jongman@gmail.com 1 / 73
자기소개 년차 개발자 파이썬은 대략 년 퀀트 개발자 풀타임 파이썬 알고리즘 문제 해결 전략 운영진 10 ( 6 ( ) ) ('11) algospot.com ('07~) 2 / 73
오늘의 주제 기초 사용 동작 원리 이디엄들과 응용 클래스들 1. dict 2. dict 3. 3 / 73
이 톡 왜 하나요? 이론적인 흥미 이런 유용한 자료 구조를 어떻게 만들었을까 dict를 사용하며 발생하는 문제들은 왜 생길까 실용적인 흥미 코드를 쉽게 만들어 줄 수 있는 이디엄과 응용 클래 스들?? 4 / 73
Part I dict 의기초사용 5 / 73
dict = 연관 매핑 >>>d={'jan':1,'f eb':2,'mar':3} >>>pr intd['jan'],d ['feb'],d['mar'] 123 사전 자료 구조 키 와값 사이의 관계를 저장한다 " " (key) (value) 6 / 73
만들기 #dict 리터럴 >>>{'jan':1,'feb':2,'mar':3,...} {'apr':4,'aug':8,'dec':12,'feb':2,..} #dict() 의키워드인자 >>>dict(jan=1,feb=2,mar=3,apr=4,..) {'apr':4,'aug':8,'dec':12,'feb':2,..} #(key,value) 쌍의목록으로만들기 >>>month_names=[('jan',1),('feb',2),('mar',3), >>>dict(month_names) ('apr',4),('may',5),('jun',6),..] {'apr':4,'aug':8,'dec':12,'feb':2,..} 7 / 73
Dictionary Comprehension # 키나값변경하기 >>>{name.title():numforname,numinmonth_names} {'Mar':3,'Feb':2,'Aug':8,'Sep':9,..} # 짝수달만고르기 >>>{name:numforname,numinmonth_namesifnum%2==0} {'feb':2,'aug':8,'apr':4,'jun':6,..} #dict 뒤집기 >>>months=dict(month_names) >>>{v:kfork,vinmonths.items()} {1:'jan',2:'feb',3:'mar',4:'apr',..} 8 / 73
탐색 >>>months={'jan':1,'feb':2,'mar':3,'apr':4,..} >>>months['jan'] 1 >>>months['jan'] KeyError:Jan >>>'Jan'inmonths False 9 / 73
get() / setdefault() >>>months.get('jan') None >>>months.get('jan',1) 1 >>>months['jan'] KeyError:Jan >>>months.setdefault('jan',1) 1 >>>months['jan'] 1 10 / 73
예제 길이 분포 구하기 : >>>wo rds=open('/us r/share/dict/words').read(). splitlines() >>>wo rds ['A','a','aa','aal ','aalii','aam','aani',' aardvark',..] 목표 단어 길이의 분포를 구해 보자 길이 인 단어 개 길이 인 단어 개 길이 인 단어 개 : 1 : 52 2 : 160 3 : 1420.. 11 / 73
예제 : 길이분포구하기 >>>length_count={} >>>forlinmap(len,words): iflinlength_count: length_count[l]+=1 else: length_count[l]=1 12 / 73
예제 : 길이분포구하기 >>>length_count={} >>>forlinmap(len,words): length_count[l]=length_count.get(l,0)+1 13 / 73
예제 길이별 목록 구하기 : 아예 목록을 구해 보자! >>>by _len={} >>>fo rwinwords: by_len.get(len( w),[]).append(w) >>>by _len {} 어 #...? 14 / 73
예제 : 길이별목록구하기 setdefault() 로해결! >>>by_len={} >>>forwinwords: by_len.setdefault(len(w),[]).append(w) >>>by_len {1:['A','a','B','b','C',...], 2:['aa','Ab','ad','ae','Ah',...], 3:['aal','aam','aba','abb','Abe',..],..} 15 / 73
삭제 >>>delmonths['mar'] >>>'mar'inmonths False 16 / 73
순회 >>>months.keys() ['mar','feb','aug','sep',..] >>>[monthformonthinmonths] ['mar','feb','aug','sep',..] >>>months.values() [3,2,8,9,..] >>>months.items() [('mar',3),('feb',2),('aug',8),('sep',9),..] 순서는엉망진창! iterkeys(), itervalues(), iteritems() 17 / 73
Part II dict 구현하기 18 / 73
요구 조건 추가 검색 삭제 순회 연산을 지원할 것 가능한한 빠른 속도 적은 메모리 사용량 / / / : 19 / 73
속도란 무엇일까? 를 구현한 개의 서로 다른 클래스가 있다고 하자 각 클래스 인스턴스를 생성한 뒤 까지의 키를 넣고 이 중 임의의 한 키를 찾는 연산을 만번 반복 각 클래스마다 평균 소요 시간을 반환한다 dict 4 0~19 10. 20 / 73
결과 dict D 평균시간 구현 A 2ns B 5ns C 3ns D 0.5ns 가 가장 좋은 구현처럼 보인다 그러나 진실은 저 멀리에!.. 21 / 73
방법론의 문제 엄청나게 여러 가지 문제가 있지만 ( ) 가장 큰 문제 의 크기에 따라 속도는 변화한다 : dict! 22 / 73
속도의 가지 그림자 2 의 크기가 작을 때 얼마나 빠르게 동작하는가 프로그램 최적화 중복 연산 제거 캐시 친화적 자료 구조 dict의 크기가 커질 때 속도가 어떻게 변화하는가 자료를 어떠한 형태로 저장하는가 오늘의 주제 dict?,,..?? 23 / 73
어떻게 자료를 저장하나? 인덱스 키 값 0 'jan' 1 1 'feb' 2 2 'mar' 3 3 'apr' 4 4 'may' 5 5 'jul' 6 6 'jun' 7 7 'aug' 8...... 24 / 73
어떻게 자료를 저장하나? 인덱스 키 값 0 'apr' 4 1 'aug' 8 2 'dec' 12 3 'feb' 2 4 'jan' 1 5 'jul' 6 6 'jun' 7 7 'mar' 3...... 25 / 73
어떻게자료를저장하나? 26 / 73
서로다른속도변화 27 / 73
파이썬의 선택 해시테이블 을 사용 의 크기와 상관없이 일정한 속도를 유지 흔한 사용처에 빠르게 동작하도록 수많은 최적화 소스코드 참조 (hash table) dict (CPython! ) 28 / 73
핵심 아이디어 : 29 / 73
진짜 핵심 아이디어 값의 저장 위치가 그 값에 의해 정의된다 : 30 / 73
해시 테이블 일부는 키가 들어 있고 일부는 비어 있는 배열, 인덱스 키 값 0 'jan' 1 1 2 3 'mar' 3 4 'feb' 2 5 6 7 31 / 73
해시 함수 키를 갈아 넣으면 숫자가 나와요 >>>ha sh('jan') -86814 19883224622032 >>>ha sh('feb') -41771 97833201190620 >>>ha sh(float) -92233 72036574961420 >>>ha sh( builtins ) -92233 72036574926416 32 / 73
해시값 테이블내의위치 >>>hash('jan')%8 0 >>>hash('feb')%8 4 >>>hash('mar')%8 3 33 / 73
탐색이 간단하다 해시값 계산 후 바로 찾음 해당 자리가 비어 있으면 해당 키가 없다 키 개수와 상관 없이 일정한 속도! 34 / 73
영향 순서가 엉망진창 : 순회는 키와 상관없이 배열의 부터 번까지 이 중 비어 있지 않은 곳을 반환 0 n 1! 35 / 73
모두 평화로운줄 알았으나 커다란 문제가 있었으니.. 36 / 73
충돌! 37 / 73
충돌 : 문제 >>>hash('jan')%8 0 >>>hash('apr')%8 0 'apr' 은어디에넣지? 38 / 73
충돌 해결 체이닝 : 테이블의 각 자리에 연결 리스트를 넣어둔다 인덱스 키값 (, ) 0 [('jan', 1), ('apr', 4)] 1 [] 2 [] 3 [('mar', 3)] 4 [('feb', 2)] 5 [] 6 [] 7 [] 39 / 73
충돌 해결 체이닝 : 테이블의 각 자리에 연결 리스트를 넣어둔다 인덱스 키값 (, ) [('jan', 1), ('apr', 4), 0 ('may', 5)] 1 [] 2 [('nov', 11)] 3 [('mar', 3), ('dec', 12)] 4 [('feb', 2), ('jun', 6)] 5 [('oct', 10)] 6 [('jul', 7), ('aug', 8)] 7 [('sep', 9)] 40 / 73
체이닝 장단점 : 장점 간단하다 단점 한 리스트가 커지면 느려진다 대부분 자리에 한두 개의 키만 포함되도록 조절 단점 느리다 연결 리스트를 유지해야 함 메모리 할당 비용 캐시 로컬리티 ( ) ( ) ( ) : 41 / 73
충돌 해결 개방 주소 : (CPython) 그 다음 자리에 넣는다 (*)! 인덱스 키 값 0 'jan' 1 1 'apr' 4 2 3 'mar' 3 4 'feb' 2 5 6 7 42 / 73
영향 탐색도 까다로워요 : 다른 키가 들어 있으면 그 다음 자리도 봐야 함 원하는 키를 찾거나 빈 자리가 있어야 결론 빈 자리가 적으면 한바퀴를 다 돌아서야 확인 가능 빈 자리의 비율 이 중요해진다, (load factor) 43 / 73
영향 삭제가 까다로워요 : del months['jan'] 인덱스 키 값 0 1 'apr' 4 2 3 'mar' 3 4 'feb' 2 5 6 7 44 / 73
영향 삭제가 까다로워요 : " 변수가 여기 있었다 " 인덱스 키 값 0 *dummy* *dummy* 1 'apr' 4 2 3 'mar' 3 4 'feb' 2 5 6 7 45 / 73
영향 순서가 달라요 : 같은 사전도 순서가 달라요! >>>a={'jan':1,'a pr':4} >>>b={'apr':4,'j an':1} >>>pr inta,b {'jan' :1,'apr':4}{'apr':4,'jan':1} >>>pr inta==b True >>>pr inta.items()= =b.items() False 46 / 73
충돌 줄이기 적절한 리사이즈 널뛰는 해시 함수 47 / 73
리사이즈 중요성 키가 많아질 수록 충돌이 잦아진다 배열이 꽉 차면 영원히 빙빙 돌 수도 있다 배열 크기의 보다 키가 많아지면 크기를 늘린다 기존 배열 크기의 배 혹은 배?! 2/3 2 4 48 / 73
영향 엄청 빠르다 : 배열의 이상은 항상 비어 있다 만약 우리가 원하는 키가 없다면 번 헛수고할 확률 번 헛수고할 확률 번 헛수고할 확률 1/3 : 0 : 1/3 = 33% 1 : 2/3 * 1/3 = 22% 2 : 2/3 * 2/3 * 1/3 = 14%.. 번 헛수고할 확률 10 : 0.5% 49 / 73
영향 순서가 바뀜 : a={8 :'hello',1:' world'} b={8 :'hello',1:' world'} 키 몇 개를 주르르 추가:리사이징이 일어난다! # foriinxrange(5):b [i+100]=1 지워도 이미 늘어난 배열은 아직 줄어들지 않았다 # foriinxrange(5):d elb[i+100] printa==b#true printa.items()==b. items()#false! 50 / 73
영향 순서가 바뀜 : A B 인덱스 키 값 인덱스 키 값 0 8 'hello' 0 1 1 'world' 1 1 'world' 2 2 3 3 4 4 5 5 6 6 7 7 8 8 'hello'...... 51 / 73
영향 순서가 바뀜 : 의 순서가 달라질 수 있는 이유 values()를 호출하면 새 리스트를 만든다 이때 호출이 되면 사전의 크기가 바뀔 수 있음 와 keys() values() GC! 52 / 73
영향 : 순회중업데이트 months={'jan':1,'feb':2,'mar':3,'apr':4,..} fork,vinmonths.iteritems(): ifv>=6: delmonths[k] printmonths RuntimeError:dictionarychangedsizeduringiteration 53 / 73
영향 : 순회중업데이트 months={'jan':1,'feb':2,'mar':3,'apr':4,..} fork,vinmonths.items(): ifv>=6: delmonths[k] printmonths {'mar':3,'may':5,'feb':2,'jan':1,'apr':4} 54 / 73
영향 사용자 클래스 : classuser(object): de f init (self,name,email): self.name=n ame self.email=email >>>jo ngman=user('j ongman','jongman@gmail.com' ) >>>ra ting={jongman :'good'} >>>pr intrating[jong man] good 오 잘 된다..! 55 / 73
영향 사용자 클래스 : 과연 그럴까? >>>jo ngman2=user(' jongman','jongman@gmail.com ') >>>pr intrating[jong man2] KeyErr or:< main.u serobjectat0x105e1c910> 기본적으로는 모든 인스턴스를 다른 키로 인식 해시에 사용할 수 있도록 추가 구현이 필요! 56 / 73
영향 사용자 클래스 : 두 가지 메소드 구현 : 해시값을 반환 eq (self, other)두 값이 같은지 반환 충 돌 해결에 사용 어떻게 멤버 변수들이 모두 같으면 같은 값 hash (self): : ( )? (*)! 57 / 73
영향 : 사용자클래스 classuser(object):.. defmembers(self): return(self.name,self.email) def eq (self,other): returnself.members()==other.members() def hash (self): returnhash(self.members()) 58 / 73
결론적으로 배열의 크기와 상관 없이 거의 상수 시간에 동작하는 자료 구조 ( )! 59 / 73
Part 3 응용클래스 60 / 73
dict 스러운클래스들 collections.ordereddict collections.defaultdict collections.counter shelve.shelf 61 / 73
OrderedDict 삽입한 순서대로 순회가 이루어진다! >>>fr omcollectionsimportordereddict >>>d=ordereddict() >>>d[ 'girls']=1 >>>d[ 'generation']=2 >>>d[ 'gggg']=3 >>>d[ 'babybaby']=4 >>>d. items() [('gir ls',1),('gene ration',2),('gggg',3),(' babybaby',4)] 62 / 73
OrderedDict 이렇게 하면 실패 이렇게 하면 한줄에 할 수 있겠지?히히 # >>>d=ordereddict(g irls=1,generation=2,gggg=3, 이런.. b abybaby=4) # >>>d. items() [('bab ybaby',4),('g ggg',3),('generation',2), ('gir ls',1)] 63 / 73
defaultdict >>>fr omcollectionsimportdefaultdict >>>by _len=defaultd ict(lambda:[]) >>>fo rwinwords: by_len[len(w)]. append(w) >>>by _len {1:[' A','a','B',' b','c',...], 2:[' aa','ab','ad','ae','ah',...],..} 하는 것과 같은 효과 기본값이 아니라 기본값을 반환하는 함수 setdefault! 64 / 73
defaultdict >>>fromcollectionsimportdefaultdict >>>by_len=defaultdict(list) >>>forwinwords: by_len[len(w)].append(w) >>>by_len {1:['A','a','B','b','C',...], 2:['aa','Ab','ad','ae','Ah',...],..} 대부분타입명도함수 (callable) 65 / 73
nested defaultdicts 각 길이마다 첫 글자별로 모아 보자! A[4]['h ']=['haab','haaf','habu','hack',..] A[5]['h ']=['habit','hache','hacky','haddo',..] A=de faultdict(lambd a:defaultdict(list)) forwinwords: A[ len(w)][w[0]].a ppend(w) 66 / 73
infinite defaultdicts >>>infinite_dict=lambda:defaultdict(infinite_dict) >>>inf=infinite_dict() >>>inf['users'][0]['username']='jongman' >>>inf['users'][0]['email']='jongman@gmail.com' >>>inf.items() [('Users', defaultdict(<function<lambda>at0x1025d0938>, {0:defaultdict(<function<lambda>at0x1025d093 {'username':'jongman', 'email':'jongman@gmail.com'})})) 67 / 73
Counter >>>fromcollectionsimportcounter >>>length_count=counter(map(len,words)) #dict 처럼원소에접근 >>>printlength_count[1],length_count[2],length_count[3] 521601420 # 없는키는 0 을반환 >>>printlength_count[1237812] 0 # 가장흔한길이 >>>printlength_count.most_common(3) [(9,32403),(10,30878),(8,29989)] 68 / 73
shelve.shelf fromshelveimportopen shelf=open('test')#test.db 에사전내용을기록 shelf['hello']=1 shelf['world']=2 shelf.close() shelf=open('test')# 이미있는 test.db 를읽어옴 printshelf.items() [('hello',1),('world',2)] 69 / 73
shelve.shelf: 주의 문자열 키만 가능 close()를 빼먹으면 저장이 안됨 context manager! froms helveimportop en fromc ontextlibimpor tclosing withc losing(open('a. shelf'))asshelf: sh elf['hello']=1 sh elf['world']=2 70 / 73
Resources PyCon 2013: Raymond Hettinger PyCon 2010: The Mighty Dictionary CPython 소스코드 : dictnotes.txt, dictobject.c Module of the Week: defaultdict, shelve, OrderedDict, Counter Beautiful Code, 18장 71 / 73
감사합니다 72 / 73
Q&A 73 / 73