MIT - Introduction to Algorithms - Lecture 2. Code 보기
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
코드는 공식 사이트인 첫 번째 링크에서 얻을 수 있었지만 데이터는 얻을 수 없었다. 그런데 찾다보니 두 번째 링크를 통해 추가 자료를 얻을 수 있다는 사실을 알게되었다. 참고
data는 9개의 데이터 중 t1.verne.txt와 t2.bobsey.txt를 사용했다.
우선 이 코드들은 총 8개의 구획으로 나뉘어 점차 속도가 빨리지는 것을 확인할 수 있도록 잘 만들어진 자료이다
여기 올린 코드는 python 2로 작성되었던 것을 python 3로 바꾸었기 때문에 크게 걱정하지 않고 봐도 된다.
공부하면서 진짜 공부한다는 느낌이 드는 코드들이므로 꼭 확인하길 바란다.
1. Init 시작 : 3.708s
파일 입출력이다.
import math
import sys
def read_file(filename):
try:
f = open(filename,'r',encoding='UTF8')
return f.readlines()
except IOError:
print("Error opening or reading input file", filename)
sys.exit()
f.readlines()으로 읽으면 list에 줄마다 append된 형태로 보인다.예)
["Project Gutenberg's In the Year 2889, by Jules Verne and Michel Verne\n", '\n', 'This eBook is for the use of anyone anywhere at no cost and with\n', 'almost no restrictions whatsoever. You may copy it, give it away or\n', 're-use it under the terms of the Project Gutenberg License included\n', 'with this eBook or online at www.gutenberg.org\n', '\n', '\n', 'Title: In the Year 2889\n', '\n'...]
이런 식으로 보인다. type은 당연히 list
파일에서 받은 list 각 줄을 단어별로 나누기 위해 넣은 함수이다.
def get_words_from_string(line):
word_list = []
character_list = []
for c in line:
if c.isalnum():
character_list.append(c)
elif len(character_list) > 0:
word = "".join(character_list)
word = word.lower()
word_list.append(word)
character_list = []
if len(character_list)>0:
word = "".join(character_list)
word = word.lower()
word_list.append(word)
return word_list
여기서 c.isalnum()에 대해 잘 모를 수 있다.사용법은 str.isalnum()이고 bool이다.
의미를 풀어 쓰면 str는 alpabet? or number? 이런 의미이다. 그러므로 처음 isalnum()으로 판단하면 al, num에 대해서만 True
이 이외의 구두문자, 띄어쓰기, 공백 등은 다 False로 판단한다
for a in str: 이런식이면 character 1글자씩 뽑는다
결과론적으로 1줄에 대한 get_word_from_string의 결과는 다음과 같이 나온다.
['project', 'gutenberg', 's', 'in', 'the', 'year', '2889', 'by', 'jules', 'verne', 'and', 'michel', 'verne']
get_word_from_string은 1줄에 대한 단어들의 모음이었다면 get_words_from_line_list는 입력받은 f 모든 줄에 대한 단어를 정리한다.
def get_words_from_line_list(L):
word_list = []
for line in L:
words_in_line = get_words_from_string(line)
word_list = word_list + words_in_line
return word_list
list + list는 두 리스트를 합쳐준다.
def count_frequency(word_list):
L = []
for new_word in word_list:
for entry in L:
if new_word == entry[0]:
entry[1] = entry[1] + 1
break
else:
L.append([new_word,1])
return L
단어들을 다 리스트에 저장했다면 이제 그것의 개수를 세는 함수이다. 다만 리스트 안에 리스트를 넣는 방식으로 아래와 같이 저장한다.[['project', 88], ['gutenberg', 93], ['s', 41], ['in', 159], ['the', 598], ['year', 14], ['2889', 11], ['by', 53], ['jules', 6], ['verne', 10]]
def insertion_sort(A):
for j in range(len(A)):
key = A[j]
i = j-1
while i>-1 and A[i]>key:
A[i+1] = A[i]
i = i-1
A[i+1] = key
return A
숫자, 알파벳 순서로 정렬하는 알고리즘이다.참고로 아래와 같은 결과에 대한 문자 비교는 다음과 같다.
print(['ddz'] > ['zzo']) #False print([8] > [5]) #True print(['8'] > ['5']) #True print(['ㄴ'] < ['ㅅ']) #True
def word_frequencies_for_file(filename):
line_list = read_file(filename)
word_list = get_words_from_line_list(line_list)
freq_mapping = count_frequency(word_list)
insertion_sort(freq_mapping)
print ("File",filename)
print (len(line_list),"lines,")
print (len(word_list),"words,")
print (len(freq_mapping),"distinct words")
return freq_mapping
이제까지의 함수들을 모은 함수이다. def inner_product(L1,L2):
sum = 0.
for word1, count1 in L1:
for word2, count2 in L2:
if word1 == word2:
sum += count1 * count2
return sum
def vector_angle(L1,L2):
numerator = inner_product(L1,L2) #numerator 분자
denominator = math.sqrt(inner_product(L1,L1) * inner_product(L2,L2)) #denominator 분모
return math.acos(numerator/denominator)
수업에서 배웠듯 우리는 단어간의 관계를 알기위해 각도 $\theta$를 구하는 것이 목적이다. 이를 위해서 내적을 해야하고 그 다음 $arccos(cos\theta)$ 형태로 만드는 과정을 할 것이다. 이를 위한 함수인데 딱봐도 $O(n^2)$의 내적을 구하고 있고 비효율적으로 보인다. def show():
import time
start = time.time()
sorted_word_list_1 = word_frequencies_for_file('t1.verne.txt')
sorted_word_list_2 = word_frequencies_for_file('t2.bobsey.txt')
distance = vector_angle(sorted_word_list_1,sorted_word_list_2)
print ("The distance between the documents is: %0.6f (radians)"%distance)
end = time.time()
print(end-start,'s')
이 함수는 내가 따로 만들었는데 시간을 재기 위한 방식이고 이를 통해 속도를 측정할 수 있다. 우리는 앞으로 나머지 7개의 값들을 보면서 시간을 비교할 것이다. Init으로 구한 이 함수들의 결과는 3.708s 각각의 시간복잡도는 제시해준 자료에서 rec02.pdf 파일로 확인할 수 있으며 그 내용은 다음과 같다. | Method | Time |
|---|---|
| get words from line list count frequency word frequencies for file | $O(W^2/k ) = O(W^2)$ $O(WL)$ $O(W^2)$ |
| inner product vector angle | $O(L_1L_2)$ $O(L_1L_2 + L_1^2+ L_2^2)$ $= O(L_1^2+ L_2^2)$ |
| main | $O(W_1^2 +W_2^2 )$ |
W : the number of words in a document
L : the number of unique words in a document
W>L
2. list1.extend(list2) : 3.027s
docdist2 - changed concatenate to extend in get_words_from_line_list
def get_words_from_line_list(L):
word_list = []
for line in L:
words_in_line = get_words_from_string(line)
# Using "extend" is much more efficient than concatenation here:
# docdist1.py에서는 word_list = word_list + words_in_line
word_list.extend(words_in_line)
return word_list
앞에서 list + list를 사용해서 list를 합쳤는데 여기서는 list.extend(list)형식을 사용한다.이 방식은 list1[len(list1):] = list2 와도 같은 방식이다.
시간은 3.026658773422241s
1번 : 3.708s
2번 : 3.027s
0.7s나 줄었다.
| Method | Time |
|---|---|
| get words from line list count frequency word frequencies for file | $O(W)$ $O(WL)$ $O(WL)$ |
| inner product vector angle | $O(L_1L_2)$ $= O(L_1^2+ L_2^2)$ |
| main | $O(W_1L_1 +W_2L_2 )$ |
W : the number of words in a document
L : the number of unique words in a document
3. for문 2개보다 whlie문 1개 - 1.842s
docdist3.py - improved dot product to exploit sorted order and achieve linear instead of quadratic time
def inner_product(L1,L2):
"""
Inner product between two vectors, where vectors
are represented as alphabetically sorted (word,freq) pairs.
Example: inner_product([["and",3],["of",2],["the",5]],
[["and",4],["in",1],["of",1],["this",2]]) = 14.0
"""
sum = 0.0
i = 0
j = 0
while i < len(L1) and j < len(L2):
# L1[i:] and L2[j:] yet to be processed
if L1[i][0] == L2[j][0]:
# both vectors have this word
sum += L1[i][1] * L2[j][1]
i += 1
j += 1
elif L1[i][0] < L2[j][0]:
# word L1[i][0] is in L1 but not L2
i += 1
else:
# word L2[j][0] is in L2 but not L1
j += 1
return sum
기존의 inner_product는 for문을 2번 돌며 비효율적인 모습을 보였지만 이 방식은 sorting을 했기 대문에 str간의 크기 비교를 통해 내적값을 구할 수 있다.시간은 1.8424656391143799 s
1번 : 3.708s
2번 : 3.027s
3번 : 1.842s
1.2초나 줄였다
| Method | Time |
|---|---|
| get words from line list count frequency insertion_sort word frequencies for file | $O(W)$ $O(WL)$ $O(L^2)$ $O(WL+L^2) = O(WL)$ |
| inner product vector angle | $O(L_1+L_2)$ $= O(L_1+ L_2)$ |
| main | $O(W_1L_1 +W_2L_2 )$ |
W : the number of words in a document
L : the number of unique words in a document
4.list를 이용한 list 단어 개수 세기보다 dict의 사용 - 0.799s
docdist4.py - changed count_frequency to use dictionaries instead of lists
def count_frequency(word_list):
"""
Return a list giving pairs of form: (word,frequency)
"""
D = {}
for new_word in word_list:
if new_word in D:
D[new_word] = D[new_word]+1
else:
D[new_word] = 1
return list(D.items())
list안에 list를 넣음으로써 단어와 count 개수를 넣었다. 그러나 여기서는 dict를 사용해 표현하도록 한다.그랬을 때의 시간은 0.799s
1번 : 3.708s
2번 : 3.027s
3번 : 1.842s
4번 : 0.799s
5. str.maketrans(A,B) - 0.747s
docdist5.py - change get_words_from_string to use string translate and split
def get_words_from_string(line):
"""
Return a list of the words in the given input string,
converting each word to lower-case.
Input: line (a string)
Output: a list of strings
(each string is a sequence of alphanumeric characters)
"""
translation_table = line.maketrans(string.punctuation+string.ascii_uppercase," "*len(string.punctuation)+string.ascii_lowercase)
line = line.translate(translation_table)
word_list = line.split()
return word_list
line을 받아 한 글자마다 뽑고 넣고를 반복하기보다. str.maketrans 방식으로 좀 더 수월하게 변형이 가능하다.참고로 이 방식은 python 2와 다르다
python 2는 import string 이후에 string.maketrans(A,B)이런 식으로 table을 구성했지만 python 3는 바로 사용이 가능한대신 string 말고 진짜 변형하고자하는 string값을 넣는다.
그렇게 한다면 A대신 B로 바꿔주세요 라는 식으로 전개가 가능하다.
dict 형태로 바꾸기 때문에 한 글자만 써도 바꿀 수 있다.
예를 보자
word = 'ababcdcd'
table = word.maketrans('ab','cd')
#table = word.maketrans('abab','cdcd') 위 식과 마찬가지 의미이다.
print(word.translate(table)) #cdcdcdcd
string.punctuation #'!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~'
string.ascii_uppercase #'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
string.ascii_lowercase #'abcdefghijklmnopqrstuvwxyz'
string.ascii_letters #'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
line.maketrans(string.punctuation+string.ascii_uppercase," "*len(string.punctuation)+string.ascii_lowercase)
그럼 바꾼 부분을 해석하면 구두문자를 공백문자*구두문자의 개수로 바꿔주시고 대문자를 소문자로 바꿔주세요라는 의미이다.
그러면 dict에 각 단어가 대응되어 짝지어지고 translate를 사용하면 dict에서 바꿔 저장해준다.
우리는 공백문자를 자르는 단위로 사용해서 split으로 단어를 구성할 수 있다.
시간은 0.747s
1번 : 3.708s
2번 : 3.027s
3번 : 1.842s
4번 : 0.799s
5번 : 0.747s
6. Merge Sort로 바꾼다. - 0.076s
docdist6.py - changed sorting from insertion sort to merge sort
def merge_sort(A):
"""
Sort list A into order, and return result.
"""
n = len(A)
if n==1:
return A
mid = n//2 # floor division
L = merge_sort(A[:mid])
R = merge_sort(A[mid:])
return merge(L,R)
def merge(L,R):
"""
Given two sorted sequences L and R, return their merge.
"""
i = 0
j = 0
answer = []
while i < len(L) and j < len(R):
if L[i] < R[j]:
answer.append(L[i])
i += 1
else:
answer.append(R[j])
j += 1
if i < len(L):
answer.extend(L[i:])
if j < len(R):
answer.extend(R[j:])
return answer
def word_frequencies_for_file(filename):
"""
Return alphabetically sorted list of (word,frequency) pairs
for the given file.
"""
line_list = read_file(filename)
word_list = get_words_from_line_list(line_list)
freq_mapping = count_frequency(word_list)
freq_mapping = merge_sort(freq_mapping)
return freq_mapping
유명한 Merge Sort로 바꾸는 것은 속도를 극감시켜준다.시간은 0.07679486274719238s
1번 : 3.708s
2번 : 3.027s
3번 : 1.842s
4번 : 0.799s
5번 : 0.747s
6번 : 0.076s
7. sorting 삭제 - 0.051s
docdist7.py - remove sorting altogether via more hashing
def inner_product(D1,D2):
"""
Inner product between two vectors, where vectors
are represented as dictionaries of (word,freq) pairs.
Example: inner_product({"and":3,"of":2,"the":5},
{"and":4,"in":1,"of":1,"this":2}) = 14.0
"""
D1=dict(D1)
D2=dict(D2)
sum = 0.0
for key in D1:
if key in D2:
sum += D1[key] * D2[key]
return sum
sorting을 지우고 dict의 능력을 발휘하겠다라는 의미로 해석이 가능합니다.실제로 sorting 자체가 불필요하고 그것으로 시간을 소모하는 것을 줄일 수 있습니다.
시간은 0.05085945129394531 s
1번 : 3.708s
2번 : 3.027s
3번 : 1.842s
4번 : 0.799s
5번 : 0.747s
6번 : 0.076s
7번 : 0.051s
8. 파일 입출력을 string으로 받는 f.read() - 0.018s
docdist8.py - treat whole file as a single "line"
def read_file(filename):
"""
Read the text file with the given filename;
return a list of the lines of text in the file.
"""
try:
f = open(filename, 'r', encoding='UTF8')
return f.read()
except IOError:
print ("Error opening or reading input file: ",filename)
sys.exit()
def get_words_from_text(text):
"""
Parse the given text into words.
Return list of all words found.
"""
translation_table = text.maketrans(string.punctuation+string.ascii_uppercase," "*len(string.punctuation)+string.ascii_lowercase)
text = text.translate(translation_table)
word_list = text.split()
return word_list
def word_frequencies_for_file(filename):
"""
Return dictionary of (word,frequency) pairs for the given file.
"""
text = read_file(filename)
word_list = get_words_from_text(text)
freq_mapping = count_frequency(word_list)
return freq_mapping
입력을 우리는 이제까지 list형태로 한 줄씩 받았다. 그러나 지금 이 과정을 통해 우리는 하나의 string으로 입력받았고 이를 기반으로 get_word_from_text 함수를 생성 table로 실행한다.0.01795172691345215 s
1번 : 3.708s
2번 : 3.027s
3번 : 1.842s
4번 : 0.799s
5번 : 0.747s
6번 : 0.076s
7번 : 0.051s
8번 : 0.018s
