[python] 파이썬 내장 자료구조 공부

www.inflearn.com 에서 무료로 강의를 제공해주었길래 몇가지 수강해서 듣고있습니다.

강의가 느린점이나 사전준비가 약간 부족해보이는 느낌도 있으나 전체적으로 몰랐던 자료형에 대해 배울 수 있던 좋은 기회였습니다.

진도율이 72%인데 오늘 내일내로 나머지 강의를 다 들을 것 같네요.

아래는 지금까지 정리한 내용입니다. 강의를 전부 다들으면 추가하겠습니다.

.

.

.

.

.

.

.

미리보기 오버헤드 방지

.

.

.

.

.

.

.

.

# -*- coding: utf-8 -*-


# namedtuple()에 대해.

import collections

listA = ("홍길동", 24, "남")

listB= ("광복녀", 21, "여")

print([listA, listB])
for n in [listA, listB]:
    print(n)
    #print("{0}은(는) {1}세의 {2}성 입니다.".format(n))
    print("%s은(는) %d세의 %s성 입니다." % n)


# 필드가 많을경우에 어떤 필드에 뭐가있는지 헷갈릴 수 있음
# 따라서 각 필드에 이름을 부여해주는것이 namedtuple.

#person = collections.namedtuple("man", "이름 나이 성")
# 필드명은 반드시 alaphanumeric이어야 한다.

person = collections.namedtuple("man", "name age gender")
# 타입객체명이 man임. (아래와 같이)

# man(name='\xed\x85\x8c\xec\x8a\xa4\xed\x8a\xb81', age=23, gender='\xeb\x82\xa8')
# man(name='\xed\x85\x8c\xec\x8a\xa4\xed\x8a\xb82', age=30, gender='\xec\x97\xac')

aa = person("테스트1", 23, "남") # 생략가능
bb = person(name="테스트2", age = 30, gender="여")
print(aa)
print(bb)



# --------------------------------------------------
# OrderedDict : 자료의 순서를 기억하는 사전형 클래스
# 일반적으로 Dict형은 key에 따라서 오름차순 정렬을하는데
# 리스트처럼 일반적으로 넣은 순서대로 정렬하기 위해
# OrderedDict를 사용한다.

non_ordDict = {}
non_ordDict.update({"2":"LG트윈스"})
non_ordDict.update({"3":"삼성 라이온즈"})
non_ordDict.update({"1":"KIA 타이거즈"})
print("non- orderedDict")
for i,j in non_ordDict.items():
    print(i + " " + j)

ordDict = collections.OrderedDict()
ordDict.update({"2":"LG트윈스"})
ordDict.update({"3":"삼성 라이온즈"})
ordDict.update({"1":"KIA 타이거즈"})
print("orderedDict")
for i,j in ordDict.items():
    print(i + " " + j)


# OrderedDict는 순서를 중요시하기 때문에
# 만약 순서가 다르고 내용은 같은 OrderedDict를 비교하면
# False가 return된다.

# -*- coding: utf-8 -*-

# pprint : pretty printer : 자료 구조를 사람이 보기 좋게 출력하는 모듈



data = [
        (1, {"a" : "가", "b" : "나", "c": "다", "d" : "라"}),
        (2, {"e": "마", "f": "바", "g": "사", "h": "아"})
        ]


print(data)
"""
[(1, {'a': '\xea\xb0\x80', 'c': '\xeb\x8b\xa4', 'b': '\xeb\x82\x98', 'd': '\xeb\x9d\xbc'}), (2, {'h': '\xec\x95\x84', 'e': '\xeb\xa7\x88', 'g': '\xec\x82\xac', 'f': '\xeb\xb0\x94'})]
"""


import pprint
# 혹은 pprint만 사용할 것이라면
# from pprint import pprint
pprint.pprint(data)


"""
[(1,
  {'a': '\xea\xb0\x80',
   'b': '\xeb\x82\x98',
   'c': '\xeb\x8b\xa4',
   'd': '\xeb\x9d\xbc'}),
 (2,
  {'e': '\xeb\xa7\x88',
   'f': '\xeb\xb0\x94',
   'g': '\xec\x82\xac',
   'h': '\xec\x95\x84'})]
"""




# array : 시퀀스 자료구조를 정의하는데, list와의 차이점은
# 모든 자료형이 같아야 한다. (numpy array생각하면됨)

import array

# array1 = array.array() # array(타입명, data)
"""
c : char
b : signed char
...

>> print(array.typecodes)

"""
array1 = array.array("i", range(5))

print(array1)


array1.extend(range(5)) # 추가하는 것.
print(array1)

print(list(enumerate(array1))) # 총 10개에 대한 요소에대해
# 각각 인덱스와 값을 출력해줌 (index, value)

# -*- coding: utf-8 -*-


# 힙 정렬 알고리즘
# 힙은 이진트리에 기반하여 구성하는 자료구조랍니다.
# 9, 2, 4, 8, 6, 7, 1, 3, 8


"""
Heap이란, 자식노드가 부모노드와 정렬관계를 가지는 트리구조

이진 Heap의 경우 array나 list를 사용해서 표현할 수 있다. (인덱스를 이용해서 표시할 수 있다.)
이때 n(인덱스)을 부모로하는 자식 노드의 위치는 각각 2n+1, 2n+2

Heap은 최대힙(max-heap: 부모가 자식보다 크거나 같다), 최소 힙(min-heap : 부모가 자식보다 작거나 같다)이 있다.

python의 heapq모듈은 최소힙(min-heap)으로 구현된 모듈이다.
"""


import heapq

# 힙생성 방법
# heappush()
# heapify()

import math

from io import StringIO, BytesIO

def show_tree(tree, total_width=36, fill= ' '):
    """     Pretty-print a tree     """
    #output = StringIO()
    output = BytesIO()
    last_row = -1
    for i, n in enumerate(tree):
        if i:
            row = int(math.floor(math.log(i+1, 2)))  # 지수, 밑
            # i =0부터 시작돼서 i+1, 이진트리기떄문에 밑은 2
        else:
            row =0
        if row!= last_row:
            output.write('\n')
        columns = 2**row
        col_width = int(math.floor((total_width * 1.0) / columns ))
        output.write(str(n).center(col_width, fill))
        last_row = row
    print(output.getvalue())
    print('-'*total_width)
    #print(n)
    return

data = [10, 8, 5, 1,4, 6,3, 9,2]

#인덱스 순서대로 채워진다.
#    1
#  2   3
# 4 5 6 7


# ===============================================

import heapq
heap = []


# heappush를 이용한 heapq 생성
# 외부에 있는 데이터를 가져와서 삽입할 때.
# 요소를 하나씩 삽입해야함
"""

for i in data:
    print("%3d"%i)
    heapq.heappush(heap,i)

    show_tree(heap)

"""


# heapify를 이용한 heapq 생성
# 데이터가 메모리에 있다면 한번에 heap정렬을 할수 있다.
# 훨씬 간단하다.
heapq.heapify(data)
#print(type(data))
print(data)
show_tree(data)



# ----------------------------------------------

print("==========================================")

import heapq


data = [10, 8, 5, 1,4, 6,3, 9,2]

heapq.heapify(data)
print(data)
show_tree(data)

heapq.heappop(data) # heappop을 할때마다 트리가 재구성됨.
print(data)
# binary트리에서 높이가 안맞는걸 맞추기위해
# AVL트리처럼 LR회전을함. (RR(child)->LL(parent))
show_tree(data)

heapq.heappop(data)
print(data)
show_tree(data)


# ------------------------------------------------
# heapreplace: 힙에서 요소를 교체하는 함수
print("==========================================")
print("==========================================")
min = heapq.heapreplace(data, 100)
# 제일 작은 3(사실상 힙에서 맨앞쪽 인덱스)이빠지고
# 100이 삽입됨과 동시에 정렬이된다.

print(min)

show_tree(data)


# ------------------------------------------------
# nlargest(), nsmallest()
# 힙의 최대/최소 값 구하기

print(heapq.nlargest(2,data), heapq.nsmallest(3,data))

# heapq.nlargest(2,data) : data중에서 가장 큰 것2개
# heapq.nsmallest(3,data) : data중에서 가장 작은 것 3개

# -*- coding: utf-8 -*-


# bisect 모듈
# 리스트의 길이가 길때 정렬된 상태로 데이터를 추가할 수 있음
# heap정렬은 트리를 재구성하므로 매우큰 오버헤드
# heap에 비해 시간과 메모리 사용을 줄일 수 있다.


import random
import bisect

random.seed()
# seed 설정.
# 값을 지정해주면 의사난수가 발생됨.
# 랜덤은 랜덤이나 실행마다 같은 시드의 랜덤함이 나옴.


for i in xrange(5):
    print(round( random.random(), 4 ))

print("val index list")
print("=== ===== =======")

biList = []
if __name__ == '__main__':
    for i in xrange(15):
        num = random.randint(1,100)
        pos = bisect.bisect(biList, num) # 리스트에 값을 추가하는 것.
        # pos에는 아이템이 추가될 index를 반환함.
        # 즉 삽입 후 정렬했을 때 pos위치에 들어가야한다  를 반환
        # 꼭 해야하는 구문은 아니지만 어떤 index인지 확인할때만 사용하면됨.

        bisect.insort(biList, num)

        #print(pos)
        print('%3d %3d  '%(num, pos), biList)

    #print(biList)


# insort의 기본값은 append right임
# 중복되는 값이 들어갈때 (ex 100(1), 100(2))
# [ 100(1), 100(2) ]  순으로 삽입 됨.
# 근데 append_left()를 이용하면
# [ 100(1) ] ,  [ 100(2), 100(1) ] 이 됨.

# -*- coding: utf-8 -*-

# queue는 기본적으로 FIFO임.
# LIFO queue 는 stack과 비슷한 형태

from __future__ import print_function

import Queue

# 일반 큐 생성
q = Queue.Queue()

for i in xrange(5):
    q.put(i) # queue에 데이터 삽입

while (not q.empty()):
    print(q.get(), end=", ")
# 0, 1, 2, 3, 4,

print("\n\n")


# LIFO 큐 생성
lifoQueue = Queue.LifoQueue()
for i in xrange(5):
    lifoQueue.put(i)

while (not lifoQueue.empty()):
    print(lifoQueue.get(), end=", ")
# 4, 3, 2, 1, 0,
print("\n\n")

# priorityQueue
# 우선 순위에 따라서 아이템을 정렬,
# get()시 가장 우선순위가 높은 아이템부터 출력
priorityQueue = Queue.PriorityQueue()


# 우선순위 큐 구현하기
# >> heapq 모듈을 응용해서 우선순위 큐를 구현한다.

# -*- coding: utf-8 -*-

# 우선순위 큐 구현하기
# >> heapq 모듈을 응용해서 우선순위 큐를 구현한다.

# ---------------------------------------------

# aa = (1, 'aa')
# bb = (1,'bb')
# aa > bb
# False
# aa < bb
# True

# aa와 bb를 비교하는것은
# 각 요소에 대해 먼저 비교를한다.
# 1과 1이 같으므로 다음요소를 비교하면 'aa'는 'bb'보다 작으므로
# aa < bb가 True가 된다. ( ascii 테이블에 의거)

import heapq

class PriorityQueue:
    def __init__(self):
        self.index = 0
        self.__list__ = []

    def put(self, item, priority):
        heapq.heappush(self.__list__, (priority, self.index, item))
        self.index += 1
        # python의 heap은 min-heap을 베이스로 하기때문에
        # priority를 그대로 넣으면 값이 낮아 가장 높은 우선순위가 된다.

    def pop(self):
        # pop은 루트노드와 가장 마지막노드를 교환하고
        # 새로바뀐 마지막노드(기존 루트)를 출력,
        # 새로바뀐 루트노드(기존 마지막)의 위치를 다시 찾아가도록한다.

        return heapq.heappop(self.__list__)

    def print_(self):
        print(self.__list__)

    def isEmpty(self):
        return len(self.__list__) ==0


class Item:
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        # 객체를 문자열로
        return "Item({!r})".format(self.name)
        # !r은 repr를 호출하는 것과 같다.
        # !s는 str()호출하는 것과 같다
        # !a는 ascii로 변환



pQ = PriorityQueue()

print(Item("test"))
# __repr__() 함수를 설정해 주었기 때문에 Item('test') 가 리턴된다.


pQ.put(Item("test4"),4)
pQ.put(Item("test2"),2)
pQ.put(Item("test6"),6)
pQ.put(Item("test7"),7)
pQ.put(Item("test1"),1)
pQ.put(Item("test8"),8)
pQ.put(Item("test9"),9)
pQ.put(Item("test5"),5)
pQ.put(Item("test3"),3)

pQ.print_()
# priority, index, item

while (not pQ.isEmpty()):
    print(pQ.pop())


"""
인덱스가 아닌 우선순위에 따라 정렬되어 pop된 모습.
(1, 4, Item('test1'))
(2, 1, Item('test2'))
(3, 8, Item('test3'))
(4, 0, Item('test4'))
(5, 7, Item('test5'))
(6, 2, Item('test6'))
(7, 3, Item('test7'))
(8, 5, Item('test8'))
(9, 6, Item('test9'))
"""

tempList = []

heapq.heappush(tempList, Item("test4"))
heapq.heappush(tempList, Item("test2"))
heapq.heappush(tempList, Item("test6"))
heapq.heappush(tempList, Item("test7"))
heapq.heappush(tempList, Item("test1"))
heapq.heappush(tempList, Item("test8"))
heapq.heappush(tempList, Item("test9"))
heapq.heappush(tempList, Item("test5"))
heapq.heappush(tempList, Item("test3"))


print("\n==============================\n\n")

print(tempList)
for i in xrange(len(tempList)):
    print(heapq.heappop(tempList))

"""
??...
Item('test4')
Item('test1')
Item('test7')
Item('test6')
Item('test8')
Item('test2')
Item('test9')
Item('test5')
Item('test3')
"""

# -*- coding: utf-8 -*-

# Unpacking

pack = (1,2)

a, b  = pack

print(a)

print(b)



listData = ["홍길동", 23, "서울" , (1980, 11, 21)]

name , age, local, birthday = listData
print(name, age, local, birthday)

# name , age, local, (year, month)= listData
# 는 리스트 필드가 일치하지 않기때문에 에러
name , age, local, (year, month, day)= listData



# 특정 값을 무시하거나 *를 이용하여 여러개를 언패킹하기

name, _, local, _ = listData

# 사실상 안쓰는 변수를 이용하는거... del해주자
print(name)
print(local)
del(_)


print("==============================================")

person_info = ("장길산", "killmountain@naver.com", "010-kill-you", "010-you-killed")

# name, email, *hp = person_info   # python 3.x

name, email = person_info[:2]  # In python 2.x
hp = person_info[2:]

print(name)
print(email)
print(hp)

import random
randVal = [ random.randint(0,10) for i in xrange(5)]

a, b= randVal[:4], randVal[4]
print(a,b)
print(randVal)


# *을 활용한 unpacking은 args를 분리할 때 좋다.
str = "123/456/789/101112/131415"
# a, *b, c = str.split("/")
# 처럼 스트링을 델리미터로 분리해서도 활용 가능

# -*- coding: utf-8 -*-


# yield를 이용하여 generator를 만들기
# 추후 deque 생성할 때 활용


# =======================================================

# yield는 return값이 generator object.
# generator는 next()함수를 가지고 있다.

def generatorEx(n):
    for i in xrange(n):
        yield i ** 2

print(generatorEx(4))
# <generator object generatorEx at 0x026E7B20>

gen = generatorEx(4)
print(gen)
# <generator object generatorEx at 0x026E7B20>
# 둘의 주소가 같다. 같은 주소를 가르킴

print(next(gen))    # i는 0 / 0^2 = 0
print(gen.next())   # i는 1 / 1^2 = 1
print(next(gen))    # i는 2 / 2^2 = 4
print(gen.next())   # i는 3 / 3^2 = 9
# next함수를 이용해도 다음 값을 뽑아 먹을 수 있음.

gen = generatorEx(3)
print(gen)
# 얘는 다른주소


# generator object를 for문으로 돌리면
# hasNext() == False 가 될 때까지 요소들을 yield해준다.
for i in generatorEx(5):
    print(i)

# -*- coding: utf-8 -*-

# deque 자료구조 응용


# deque를 이용해서 고정크기의 큐를 생성하기 (max length = n)

from collections import deque

dQ = deque(maxlen=4)
# 최대 길이가 4인 deque생성

dQ.append("aa")
dQ.append("bb")
dQ.append("cc")
dQ.append("dd")

dQ.append("ee")
# 가장 처음에 들어갔던 aa가 빠지고 ee가 들어간다.

print(dQ)


def search_word(lines, find_word, history = 4):
    lineHistory = deque(maxlen=history)

    for line in lines:
        """
        >>> "aa" in "abcdaa"
        True
        >>> "aa" in "abcda"
        False
        """

        if find_word in line:
            yield line, lineHistory
        lineHistory.append(line)

testString = ["문장 부호는 글에서", "문장의 구조를 드러내거나", "글쓴이의 의도를 전달하기",
              "위하여 사용하는 부호이다.", "문장 부호의 이름과 사용법은"
             ,"다음과 같이 정한다."]
searched = search_word(testString, "문장")

for i in searched:
    print(i[0])

# -*- coding: utf-8 -*-

# defaultdict() 메서드는 컨테이너를 초기화 할 때 default값을 지정한다.

# defaultdict를 이용한 딕셔너리 키를 여러값으로 매핑하기


d = {}

d.setdefault('sel', []).append(02)
d.setdefault('sel', []).append('서울')
d.setdefault('sel', []).append(1)
d.setdefault('sel2', []).append('광주')

print(d)

from collections import defaultdict


d = {}
d['sel']= []
d.get('sel').append('test')
d.get('sel').append('test2')

defaultDict = defaultdict(list)
defaultDict['sel'].append('test')
defaultDict['sel'].append('test2')

defaultDict2 = defaultdict(set)
defaultDict2['sel'].add('test')
defaultDict2['sel'].add('test2')

print(d)
# {'sel': ['test', 'test2']}

print(defaultDict)
# defaultdict(<type 'list'>, {'sel': ['test', 'test2']})

print(defaultDict2)
# defaultdict(<type 'set'>, {'sel': set(['test', 'test2'])})


# ==========================================
print("=================================\n")

color = [('파랑',3 ), ('노랑', 2), ('빨강',1), ('파랑', 4), ('노랑',5)]
# 파랑이 2개 중복돼있음. 노랑도 2개가 중복돼있음

d = defaultdict(list)
for key, val in color:
    d[key].append(val) # 훨씬 간단하다.

test = list(d.items())

print(test)
# [('\xed\x8c\x8c\xeb\x9e\x91', [3, 4]), ('\xeb\x85\xb8\xeb\x9e\x91', [2, 5]), ('\xeb\xb9\xa8\xea\xb0\x95', [1])]
# 이렇게 2개씩 있는 데이터는 자동으로 리스트안으로 처리됌


string = "hello hi goodmorning"

d = defaultdict(int) # string에 들어있는 문자들의 갯수를 파악하기 위함
for key in string:
    d[key] += 1 # key에 해당하는 문자의 카운트가 +1

print(d)

# -*- coding: utf-8 -*-




# a = {"0":"123","1":"456", "2":"789"}

# zip함수는 iterable 객체의 각 키를
# 순서대로 묶어서 리턴해준다.

# zip([1,3],[5,6])
# [(1, 5), (3, 6)]
# zip([1,3],[5,6], [7,8])
# [(1, 5, 7), (3, 6, 8)]


f = {"banana" : 500 , "strawberry" : 5000, "watermelon" : 20000, "grape" : 3000, "apple" : 1500, "lemon" : 900}

print(max(f))

# watermelon  << 왜냐하면 f의 key중에서 watermelon이 앞글자가 w로 ascii값이 제일높기때문..

print(max(f.values())) # 이렇게 찾으면 최대값은 찾으나 키값을 찾을 수 없음

fForFind = zip(f.values(), f.keys())
# zip으로 f의 keys와 values를 반대로 위치를 바꾼다.
# >> values iterator 객체에서 1개, keys iterator 객체에서 1개씩 뽑아서 튜플을만듬

print(fForFind)
# [(900, 'lemon'), (1500, 'apple'), (5000, 'strawberry'), (20000, 'watermelon'), (3000, 'grape'), (500, 'banana')]

print(max(fForFind)) # key가 밸류이기때문에 바로 max값을 찾을 수 있음.
# (20000, 'watermelon')


# zip함수를 사용하지 않고 키값을 찾아내는 방법
print(max(f, key = lambda n: f[n]))
# max의 오버라이딩된 다른 형태.
# 첫번째 param에는 데이터변수를주고, key에는 func를 준다.
# 데이터변수의 각요소가 iterable되면 function으로 다시 param이 전달되는데
# 여기서는 효율을 위해 람다함수를 사용했고
# "banana"가 이터레이팅돼서 lambda에 전달되면
# f["lambda"] 의 값인 500이 리턴된다.
# 이걸 계속 반복하여 비교하여 최대값을 찾는 방법임.

# -*- coding: utf-8 -*-


# 두 개의 딕셔너리에서 동일 값 찾기
# 시퀀스의 순서를 유지하면서 중복 없애기


x = {
    "a" : 100,
    "b" : 200,
    "c" : 300
}

y = {
    "c" : 150,
    "d" : 200,
    "a" : 120
}


# key의 교집합
#xy = x.keys() & y.keys()
#print(x.keys() - y.keys())
# python 2에서는 지원되지않음...


# ==========================================
# 시퀀스의 중복값 없애기

aa= [1,2,3,1,5,6,4,1,5,9]
bb = set(aa)
print(bb) # 집합이기때문에 중복원소는 카피과정에서 스킵됨

# 시퀀스의 순서를 유지하면서 중복 없애기
aa = [8,1,9,1,5,6,3,1,5,2]
bb = set(aa)
print(bb) # 순서가 오름차순으로 정렬되었다.

def removeDuplicate(items):
    a = set()
    for item in items:
        if item not in a:
            yield item
            a.add(item)

# generator iterator생성

print(list(removeDuplicate(aa)))
# generator iterator객체를 list로 형변환하면 데이터객체가 나온다.