Practical Programming
An Introduction to Computer Science
Using Python 3
(Pragmatic Programmers)
(Pragmatic Bookshelf)
Paul Gries (著) Jennifer Campbell (著)
Jason Montojo (著) Lynn Beighley (編集)
開発環境
- OS X Yosemite - Apple (OS)
- Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
- Python 3.4 (プログラミング言語)
Practical Programming: An Introduction to Computer Science Using Python 3 (Pragmatic Programmers) (Paul Gries (著)、Jennifer Campbell (著)、Jason Montojo (著)、Lynn Beighley (編集)、Pragmatic Bookshelf)のChapter 13(Searching and Sorting)、13.7(Exercises) 7.を解いてみる。
13.7(Exercises) 7.
コード(BBEdit)
sample7.py
#!/usr/bin/env python3 #-*- coding: utf-8 -*- import time import random def built_in(L): L.sort() def findMin(L, b): smallest = b i = b + 1 while i != len(L): if L[i] < L[smallest]: smallest = i i += 1 return smallest def selectionSort(L): i = 0 while i != len(L): smallest = findMin(L, i) L[i], L[smallest] = L[smallest], L[i] i += 1 def insert(L, b): i = b while i != 0 and L[i - 1] >= L[b]: i -= 1 value = L[b] del L[b] L.insert(i, value) def insertionSort(L): i = 0 while i != len(L): insert(L, i) i += 1 def bubbleSort(l): i = 0 m = len(l) - 1 while m > 0: while i < m: if l[i] > l[i + 1]: l[i + 1], l[i] = l[i], l[i + 1] i += 1 i = 0 m -= 1 def printTimes(L): print(len(L), end='\t') for func in (selectionSort, insertionSort, bubbleSort, built_in): if func in (selectionSort, insertionSort, built_in) 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), end='\t') print() if __name__ == '__main__': for list_size in [10, 1000, 2000, 3000, 4000, 5000, 10000]: L = list(range(list_size)) random.shuffle(L) printTimes(L)
入出力結果(Terminal, IPython)
$ ./sample7.py 10 0.1 0.1 0.1 0.0 1000 526.4 228.2 687.8 1.0 2000 2038.0 927.2 2807.4 2.2 3000 4627.1 2109.8 6325.3 3.4 4000 8229.8 3795.4 11312.3 4.7 5000 13103.3 5894.8 17911.9 6.0 10000 66105.8 27104.1 72529.2 13.2 $
0 コメント:
コメントを投稿