# Python Algorithms – chapter2 基础知识

2018-02-12 10:46:24来源:http://www.cnblogs.com/huangqiancun/p/8442103.html作者:Python_博客园人点击

Ο、Ω、Θ，Ο记法表示渐进上界，Ω记法表示渐进下界，Θ记法同时提供了函数的上下界

Tip1：If possible, don’t worry about it.

Tip2：用timeit模块进行计时

import timeit
timeit.timeit("x = 2+2") #0.003288868749876883
timeit.timeit("x = sum(range(10))") #0.003288868749897271

Tip3:用profiler找出瓶颈

import cProfile
cProfile.run("helloworld()")

Tip4:绘制出结果

Tip5:在根据计时比对结果做出判断时要小心仔细

Tip6:通过相关实验对渐进时间做出判断时要小心仔细

1 图的实现

a, b, c, d, e, f, g, h = range(8)
N = [
{b, c, d, e, f},# a
{c, e}, # b
{d},# c
{e},# d
{f},# e
{c, g, h},# f
{f, h}, # g
{f, g}# h
]
b in N[a] # True
len(N[f]) # 3

a, b, c, d, e, f, g, h = range(8)
N = [
[b,c,d,e,f], #a
[c,e], #b
[d], #c
[e], #d
[f], #e
[c,g,h], #f
[f,h], #g
[f,g] #h
]

a, b, c, d, e, f, g, h = range(8)
N = [
{b:2, c:1, d:3, e:9, f:4},# a
{c:4, e:3}, # b
{d:8},# c
{e:7},# d
{f:5},# e
{c:2, g:2, h:2},# f
{f:1, h:6}, # g
{f:9, g:8}# h
]
b in N[a] #True
len(N[f]) #3
N[a][b] #2

N = {
'a': set('bcdef'),
'b': set('ce'),
'c': set('d'),
'd': set('e'),
'e': set('f'),
'f': set('cgh'),
'g': set('fh'),
'h': set('fg')
}

a, b, c, d, e, f, g, h = range(8)
N = [[0,1,1,1,1,1,0,0], # a
[0,0,1,0,1,0,0,0], # b
[0,0,0,1,0,0,0,0], # c
[0,0,0,0,1,0,0,0], # d
[0,0,0,0,0,1,0,0], # e
[0,0,1,0,0,0,1,1], # f
[0,0,0,0,0,1,0,1], # g
[0,0,0,0,0,1,1,0]] # h
N[a][b] # Neighborhood membership -> 1
sum(N[f]) # Degree -> 3

a, b, c, d, e, f, g, h = range(8)
_ = float('inf')
W = [[0,2,1,3,9,4,_,_], # a
[_,0,4,_,3,_,_,_], # b
[_,_,0,8,_,_,_,_], # c
[_,_,_,0,7,_,_,_], # d
[_,_,_,_,0,5,_,_], # e
[_,_,2,_,_,0,2,2], # f
[_,_,_,_,_,1,0,6], # g
[_,_,_,_,_,9,8,0]] # h
W[a][b] < inf # True
sum(1 for w in W[a] if w < inf) - 1# 5

Numpy库中的专用数组

N = [[0]*10 for i in range(10)]
import numpy as np
N = np.zeros([10,10])

2 树的实现

T = [["a", "b"], ["c"], ["d", ["e","f"]]]
T[0][1] # 'b'
T[2][1][0] # 'e'

class Tree:
def __init__(self, left, right):
self.left = left
self.right = right
t = Tree(Tree("a", "b"), Tree("c", "d"))
t.right.left# 'c'

class Tree:
def __init__(self, kids, next=None):
self.kids = self.val = kids
self.next = next
return Tree
t = Tree(Tree("a", Tree("b", Tree("c", Tree("d")))))
t.kids.next.next.val# 'c'
Bunch模式

bunch类

class Bunch(dict):
def __init__(self, *args, **kwds):
super(Bunch, self).__init__(*args, **kwds)
self.__dict__ = self
x = Bunch(name = "Jayne Cobb", position = "Public Relations")
x.name #'Jayne Cobb'
T = Bunch
t = T(left = T(left = "a",right = "b"), right = T(left = "c"))
t.left # {'right': 'b', 'left': 'a'}
t.left.right #' b'
"left" in t.right # True

1 隐性平方级操作

from random import randrange
L = [randrange(10000) for i in range(1000)]
42 in L # False
S = set(L)
42 in S #False

lists = [[1,2], [3,4,5], [6]]
sum(lists, []) #[1, 2, 3, 4, 5, 6]
res = []
for lst in lists:
res.extend(lst)
# [1, 2, 3, 4, 5, 6]

sum函数是平方级的运行时间，第二个为更好的选择，当list的长度很短时，他们之间没有太大差距，但一旦超出某个长度，sum版本就会彻底完败

2 浮点运算的麻烦

sum(0.1 for i in range(10)) == 1.0 #False
def almost_equal(x, y, places=7):
return round(abs(x-y), places) == 0
almost_equal(sum(0.1 for i in range(10)), 1.0) # True
from decimal import *
sum(Decimal("0.1") for i in range(10)) == Decimal("1.0") #True