검색과 정렬

리스트에서 일치하는 항목의 인덱스를 반환하는 함수

while 루프를 이용한 선형 검색

from typing import Any

def linear_search(lst: list, value: Any) -> int:
    '''lst에서 처음으로 나오는 인덱스를 반환하거나 lst에 value가 없는 경우 -1을 반환한다.'''

    #   0  1  2  3  4  5
    # [ 1, 2, 3, 4, 5, 6 ]
    # len => 6


    i = 0 # lst 내에서 검사할 다음 항목의 인덱스
    while i != len(lst) and lst[i] != value:
        i = i + 1
    
    if i == len(lst):
        return -1
    else:
        return i


lst = [ 2, -3, 5, 9, 8, -6, 4, -15 ]        
value = 5
index = linear_search(lst, value)
print(index)

for 루프를 이용한 선형 검색

from typing import Any

def linear_search_for(lst: list, value: Any) -> int:
    for i in range(len(lst)):
        if lst[i] == value:
            return i

    return -1

lst = [ 2, -3, 5, 9, 8, -6, 4, -15 ]        
value = 5
index = linear_search_for(lst, value)
print(index)

센티널 검색

while 루프를 이용하는 선형 검색에서 while 루프를 수행할 때 마다 i != len(lst) 행위를 반복

while i != len(lst) and lst[i] != value:

리스트 마지막에 검색할 값(센티널)을 추가 ⇒ 리스트의 끝을 신경쓰지 않고 루프를 수행할 수 있도록 하는 기법

from typing import Any

def linear_search_sentinel(lst: list, value: Any) -> int:
    # 센티널을 리스트 마지막에 추가
    lst.append(value)

    i = 0
    while lst[i] != value:
        i = i + 1

    # 센티널을 제거
    lst.pop()

    # 일치하는 값의 위치가 센티널과 동일한지를 확인
    if i == len(lst):
        return -1
    else:
        return i

lst = [ 2, -3, 5, 9, 8, -6, 4, -15 ]        
value = 5
index = linear_search_sentinel(lst, value)
print(index)

검색 시간 측정

import time
from typing import Callable, Any

def time_it(search: Callable[[list, Any], Any], L: list, v: Any) -> float:
    t1 = time.perf_counter()
    search(L, v)
    t2 = time.perf_counter()

    return (t2 - t1) * 1000.0


def print_times(v: Any, L: list) -> None:
    t1 = time.perf_counter()
    L.index(v)
    t2 = time.perf_counter()
    index_time = (t2 - t1) * 1000.0

    while_time = time_it(linear_search_while, L, v)
    for_time = time_it(linear_search_for, L, v)
    sentinel_time = time_it(linear_search_sentinel, L, v)

    print("{0}\t{1:.2f}\t{2:.2f}\t{3:.2f}\t{4:.2f}\t".format(
        v, while_time, for_time, sentinel_time, index_time))



L = list(range(10000001))    

print_times(10, L)
print_times(5000000, L)
print_times(10000000, L)

실행결과

10      0.00    0.00    23.24   0.00

5000000 351.70  139.61  186.01  46.00

10000000      700.43 279.76  374.81  94.05

이진검색

정렬된 데이터에 대해 일정한 검색 성능을 보장

검색이 진행될 때 마다 검색할 데이터양이 1/2로 줄어듬

from typing import Any

def binary_search(lst: list, value: Any) -> int:
    i = 0                   # 리스트의 시작 인덱스
    j = len(lst) - 1        # 리스트의 끝 인덱스

    while i != j + 1:
        m = (i + j) // 2    # m: i와 j의 중간
        if lst[m] < value:
            i = m + 1
        else:
            j = m - 1

    if 0 <= i < len(lst) and lst[i] == value:
        return i
    else:
        return -1



def print_times(v: Any, L: list) -> None:
    t1 = time.perf_counter()
    L.index(v)
    t2 = time.perf_counter()
    index_time = (t2 - t1) * 1000.0

    while_time = time_it(linear_search_while, L, v)
    for_time = time_it(linear_search_for, L, v)
    sentinel_time = time_it(linear_search_sentinel, L, v)
    binary_time = time_it(binary_search, L, v)

    print("{0}\t{1:.2f}\t{2:.2f}\t{3:.2f}\t{4:.2f}\t{5:.2f}\t".format(
        v, while_time, for_time, sentinel_time, binary_time, index_time))


L = list(range(10000001))    

print_times(10, L)
print_times(5000000, L)
print_times(10000000, L)

정렬

선택정렬

# L[b:] 내에서 가장 작은 값의 인덱스를 반환
def find_min(L: list, b: int) -> int:

    smallest = b
    i = b + 1
    while i != len(L):
        if L[i] < L[smallest]:
            smallest = i
        i = i + 1

    return smallest

def selection_sort(L: list) -> None:
    i = 0
    while i != len(L):
        smallest = find_min(L, i)
        L[i], L[smallest] = L[smallest], L[i]
        i = i + 1

L = [ 3, 4, 6, -1, 2, 5]
print(L)
selection_sort(L)
print(L)

삽입 정렬

# 기 정렬된 영역에 L[:b+1] 내 올바른 위치에 L[b]를 삽입
def insert(L: list, b: int) -> None:
    i = b
    while i != 0 and L[i -1] >= L[b]:
        i = i - 1
    
    value = L[b]
    del L[b]
    L.insert(i, value)

def insertion_sort(L: list) -> None:
    i = 0

    while i != len(L):
        insert(L, i)
        i = i + 1

L = [ 3, 4, 6, -1, 2, 5]
print(L)
insertion_sort(L)
print(L)

정렬 알고리즘 성능 측정

import time, random

def built_in(L: list) -> None:
    L.sort()

def print_times(L: list) -> None:
    print(len(L), end='\t')
    for func in (selection_sort, insertion_sort, built_in):
        if func in (selection_sort, insertion_sort) and len(L) > 10000:
            continue

        L_copy = L[:]
        t1 = time.perf_counter()
        func(L_copy)
        t2 = time.perf_counter()
        print("{0:7.1f}".format((t2 - t1) * 1000.0), end="\t")

    print()

for list_size in [ 10, 1000, 2000, 3000, 4000, 5000, 10000 ]: 
    L = list(range(list_size))
    random.shuffle(L)
    print_times(L)

병합 정렬

# 2개의 리스트를 하나의 정렬된 리스트로 반환
def merge(L1: list, L2: list) -> list:

    newL = [] 
    i1 = 0
    i2 = 0

    # [ 1, 1, 2, 3, 4, 5, 6, 7  ]
    # [ 1, 3, 4, 6 ]   [ 1, 2, 5, 7 ]
    #              i1            
    #                             i2 
    while i1 != len(L1) and i2 != len(L2):
        if L1[i1] <= L2[i2]:
            newL.append(L1[i1])
            i1 += 1
        else:
            newL.append(L2[i2])
            i2 += 1

    newL.extend(L1[i1:])
    newL.extend(L2[i2:])

    return newL


def merge_sort(L: list) -> None:        # [ 1, 3, 4, 6, 1, 2, 5, 7 ]
    workspace = []
    for i in range(len(L)):             
        workspace.append([L[i]])        # [ [1], [3], [4], [6], [1], [2], [5], [7] ]

    i = 0
    while i < len(workspace) - 1:
        L1 = workspace[i]               # [ [1], [3], [4], [6], [1], [2], [5], [7], [1,3],[4,6],[1,2],[5,7], [1,3,4,6],[1,2,5,7],[1,1,2,3,4,5,6,7]  ]
        L2 = workspace[i + 1]
        newL = merge(L1, L2)               
        workspace.append(newL)
        i += 2

    if len(workspace) != 0:
        L[:] = workspace[-1][:]


import time, random

def built_in(L: list) -> None:
    L.sort()

def print_times(L: list) -> None:
    print(len(L), end='\t')
    for func in (selection_sort, insertion_sort, merge_sort, built_in):
        if func in (selection_sort, insertion_sort, merge_sort) and len(L) > 10000:
            continue

        L_copy = L[:]
        t1 = time.perf_counter()
        func(L_copy)
        t2 = time.perf_counter()
        print("{0:7.1f}".format((t2 - t1) * 1000.0), end="\t")

    print()

for list_size in [ 10, 1000, 2000, 3000, 4000, 5000, 10000 ]: 
    L = list(range(list_size))
    random.shuffle(L)
    print_times(L)

[6, 5, 4, 3, 7, 1, 2]를

선택 정렬

[ 6, 5, 4, 3, 7, 1, 2 ]

[ 1, 5, 4, 3, 7, 6, 2 ]

[ 1, 2, 4, 3, 7, 6, 5 ]

[ 1, 2, 3, 4, 7, 6, 5 ]

[ 1, 2, 3, 4, 5, 6, 7 ]

[ 1, 2, 3, 4, 5, 6, 7 ]

삽입 정렬

메서드

init / str / eq

from typing import List, Any

class Book:
    '''제목, 저자 목록, 출판사, ISBN, 가격을 포함하는 책 정보'''

    def __init__(self, title: str, authors: List[str], publisher: str, isbn: str, price: float) -> None:
        print("init called")

        self.title = title
        self.authors = authors[:]
        self.publisher = publisher
        self.isbn = isbn
        self.price = price

    def __str__(self) -> str:

        return 'Title: {}\nAuthors: {}\nPublisher: {}\nisbn: {}\nPrice: {}\n'.format(
            self.title, self.authors, self.publisher, self.isbn, self.price)

    def __eq__(self, other: Any) -> bool:

        return isinstance(other, Book) and self.title == other.title


    def print_authors(self) -> None:
        '''저자 목록을 출력'''

        for author in self.authors:
            print(author)

    def num_authors(self) -> int:
        '''저자 수를 반환'''
        
        return len(self.authors)


authors = ['aaa', 'bbb', 'ccc']
my_book = Book('Book', authors, '한빛출판사', '123-456-789', '30000')
your_book = Book('New Book', authors, '한빛출판사', '123-456-789', '30000')

print(my_book == my_book)

print(my_book == your_book)

Web Development for Beginners - A Curriculum

https://github.com/microsoft/Web-Dev-For-Beginners

PDB 파일에서 읽은 정보로 아래 같은 원자를 생성하는Atom 클래스를 정의

nitrogen = Atom(1, 'N', 0.257, -0.363, 0.0)

c:\python\atom.py

class Atom:
    '''번호, 기호, 좌표(X, Y, Z)를 갖는 원자'''

    def __init__(self, num: int, sym: str, x: float, y: float, z: float) -> None:
        self.num = num
        self.sym = sym
        self.center = (x, y, z)

    def __str__(self) -> str:
        '''(SYMBOL, X, Y, Z) 형식의 문자열을 반환'''
        return '({}, {}, {}, {}'.format(self.sym, self.center[0], self.center[1], self.center[2])

    def translate(self, x: float, y: float, z: float) -> None:
        self.center = (self.center[0] + x, self.center[1] + y, self.center[2] + z)

c:\python\molecule.py

from atom import Atom

class Molecule:
    ''' 이름과 원자 리스트를 갖는 분자 '''

    def __init__(self, name: str) -> None:
        self.name = name
        self.atoms = []

    def add(self, a: Atom) -> None:
        self.atoms.append(a)

    def __str__(self) -> str:
        '''(NAME, (ATOM1, ATOM2, ...)) 형식의 문자열을 반환'''

        atom_list = ''
        for a in self.atoms:
            atom_list = atom_list + str(a) + ', '
        
        atom_list = atom_list[:-2]      # 마지막에 추가된 ', ' 문자를 제거

        return '({}, ({}))'.format(self.name, atom_list)

    def translate(self, x: float, y: float, z: float) -> None:
        for a in self.atoms:
            a.translate(x, y, z)


ammonia = Molecule("AMMONIA")
ammonia.add(Atom(1, "N", 0.257, -0.363, 0.0))
ammonia.add(Atom(2, "H", 0.257, 0.727, 0.0))
ammonia.add(Atom(3, "H", 0.771, -0.727, 0.890))
ammonia.add(Atom(4, "H", 0.771, -0.727, -0.890))
ammonia.translate(0, 0, 0.2)



#assert ammonia.atoms[0].center[0] == 0.257
#assert ammonia.atoms[0].center[1] == -0.363

assert ammonia.atoms[0].center[2] == 0.2

print(ammonia)