Chapter 1 Data Structures and Algorithms
1.1 Decompose a sequence into separate variables
p = (4, 5)
x, y = p
print x
print y
data = [ 'ACME', 50, 91.1, (2012, 12, 21) ]
name, shares, price, date = data
print name
print shares
print price
print date
name, shares, price, (year, mon, day ) = data
print year
p = (4, 5)
#x, y, z = p 错误!!!
s = 'hello!'
a, b, c, d, e, f = s
print a
print f
data = [ 'ACME', 50, 91.1, (2012, 12, 21) ]
_, shares, price, _ = data
print shares
print price
#其他数据可以丢弃了
Copy after login
1.2 Decompose elements from an iterable of arbitrary length
from audioop import avg
def drop_first_last(grades):
first, *middle, last = grades
return avg(middle)
record = ('Dave', 'dave@example.com', '777-333-2323', '234-234-2345')
name, email, *phone_numbers = record
print name
print email
print phone_numbers
*trailing, current = [10, 8, 7, 2, 5]
print trailing #[10, 8, 7, 2, ]
print current #5
records = [
('foo', 1, 2),
('bar', 'hello'),
('foo', 5, 3)
]
def do_foo(x, y):
print ('foo', x, y)
def do_bar(s):
print ('bar', s)
for tag, *args in records:
if tag == 'foo':
do_foo(*args)
elif tag == 'bar':
do_bar(*args)
line = 'asdf:fedfr234://wef:678d:asdf'
uname, *fields, homedir, sh = line.split(':')
print uname
print homedir
record = ('ACME', 50, 123.45, (12, 18, 2012))
name, *_, (*_, year) = record
print name
print year
items = [1, 10, 7, 4, 5, 9]
head, *tail = items
print head #1
print tail #[10, 7, 4, 5, 9]
def sum(items):
head, *tail = items
return head + sum(tail) if tail else head
sum(items)Copy after login
1.3 Save the last N elements
from _collections import deque
def search(lines, pattern, history=5):
previous_lines = deque(maxlen = history)
for line in lines:
if pattern in line:
yield line, previous_lines
previous_lines.append(line)
# Example use on a file
if __name__ == '__main__':
with open('somefile.txt') as f:
for line, prevlines in search(f, 'python', 5):
for pline in prevlines:
print (pline) #print (pline, end='')
print (line) #print (pline, end='')
print ('-'*20)
q = deque(maxlen=3)
q.append(1)
q.append(2)
q.append(3)
print q
q.append(4)
print q
q = deque()
q.append(1)
q.append(2)
q.append(3)
print q
q.appendleft(4)
print q
q_pop = q.pop()
print q_pop
print q
q_popleft = q.popleft()
print q_popleft
print qCopy after login
1.4 Find the largest or Minimum N elements
import heapq
nums = [1,30,6,2,36,33,46,3,23,43]
print (heapq.nlargest(3, nums))
print (heapq.nsmallest(3, nums))
portfolio = [
{'name':'IBM', 'shares':100, 'price':2.4},
{'name':'A', 'shares':1040, 'price':12.4},
{'name':'S', 'shares':40, 'price':23.4},
{'name':'D', 'shares':1, 'price':2.49},
{'name':'F', 'shares':9, 'price':24}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
print cheap
print expensive
nums = [1,8,2,23,7,-4,18,23,42,37,2]
heap = list(nums)
print heap
heapq.heapify(heap)
print heap
print heapq.heappop(heap)
print heapq.heappop(heap)
print heapq.heappop(heap)Copy after login
1.5 Implement priority queue
import heapq
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
#Example
class Item:
def __init__(self, name):
self.name = name
def __repr__(self):
return 'Item({!r})'.format(self.name)
q = PriorityQueue()
q.push(Item('foo'), 1)
q.push(Item('spam'), 4)
q.push(Item('bar'), 5)
q.push(Item('grok'), 1)
print q.pop()
print q.pop()
print q.pop()
a = Item('foo')
b = Item('bar')
#a < b error
a = (1, Item('foo'))
b = (5, Item('bar'))
print a < b
c = (1, Item('grok'))
#a < c error
a = (1, 0, Item('foo'))
b = (5, 1, Item('bar'))
c = (1, 2, Item('grok'))
print a < b
print a < cCopy after login
1.6 Map objects to multiple values in the dictionary
d = {
'a' : [1, 2, 3],
'b' : [4, 5]
}
e = {
'a' : {1, 2, 3},
'b' : {4, 5}
}
from collections import defaultdict
d = defaultdict(list)
d['a'].append(1)
d['a'].append(2)
d['a'].append(3)
print d
d = defaultdict(set)
d['a'].add(1)
d['a'].add(2)
d['a'].add(3)
print d
d = {}
d.setdefault('a', []).append(1)
d.setdefault('a', []).append(2)
d.setdefault('b', []).append(3)
print d
d = {}
for key, value in d:#pairs:
if key not in d:
d[key] = []
d[key].append(value)
d = defaultdict(list)
for key, value in d:#pairs:
d[key].append(value)Copy after login
1.7 Keep the dictionary in order
from collections import OrderedDict
d = OrderedDict()
d['foo'] = 1
d['bar'] = 2
d['spam'] = 3
d['grol'] = 4
for key in d:
print (key, d[key])
import json
json.dumps(d)Copy after login
1.8 Computational issues related to dictionary
price = {
'ACME':23.45,
'IBM':25.45,
'FB':13.45,
'IO':4.45,
'JAVA':45.45,
'AV':38.38,
}
min_price = min( zip( price.values(), price.keys() ) )
print min_price
max_price = max( zip( price.values(), price.keys() ) )
print max_price
price_sorted = sorted( zip( price.values(), price.keys() ) )
print price_sorted
price_and_names = zip( price.values(), price.keys() )
print (min(price_and_names))
#print (max(price_and_names)) error zip()创建了迭代器，内容只能被消费一次
print min(price)
print max(price)
print min(price.values())
print max(price.values())
print min(price, key = lambda k : price[k])
print max(price, key = lambda k : price[k])
min_value = price[ min(price, key = lambda k : price[k]) ]
print min_value
price = {
'AAA': 23,
'ZZZ': 23,
}
print min( zip( price.values(), price.keys() ) )
print max( zip( price.values(), price.keys() ) )Copy after login
1.9 Find similarities in two dictionaries
a = {
'x':1,
'y':2,
'z':3
}
b = {
'x':11,
'y':2,
'w':10
}
print a.keys() & b.keys() #{'x','y'}
print a.keys() - b.keys() #{'z'}
print a.items() & b.items() #{('y', 2)}
c = {key: a[key] for key in a.keys() - {'z', 'w'} }
print c #{'x':1, 'y':2}Copy after login
1.10 Remove duplicates from the sequence and keep the order of elements unchanged
def dedupe(items):
seen = set()
for item in items:
if item not in seen:
yield item
seen.add(item)
#example
a = [1,5,2,1,9,1,5,10]
print list(dedupe(a))
def dedupe2(items, key = None):
seen = set()
for item in items:
val = item if key is None else key(item)
if val not in seen:
yield item
seen.add(val)
#example
a = [
{'x':1, 'y':2},
{'x':1, 'y':3},
{'x':1, 'y':2},
{'x':2, 'y':4},
]
print list( dedupe2(a, key=lambda d : (d['x'], d['y']) ) )
print list( dedupe2(a, key=lambda d : (d['x']) ) )
a = [1,5,2,1,9,1,5,10]
print set(a)Copy after login
1.11 Name the slices
items = [0,1,2,3,4,5,6]
a = slice(2,4)
print items[2:4]
print items[a]
items[a] = [10,11]
print items
print a.start
print a.stop
print a.step
Copy after login
1.12 Find the one that appears the most in the sequence Elements
words = [
'look', 'into', 'my', 'eyes', 'look', 'into', 'my', 'eyes',
'the', 'look'
]
from collections import Counter
word_counts = Counter(words)
top_three = word_counts.most_common(3)
print top_three
print word_counts['look']
print word_counts['the']
morewords = ['why', 'are', 'you', 'not', 'looking', 'in', 'my', 'eyes']
for word in morewords:
word_counts[word] += 1
print word_counts['eyes']
print word_counts['why']
word_counts.update(morewords)
print word_counts['eyes']
print word_counts['why']
a = Counter(words)
b = Counter(morewords)
print a
print b
c = a + b
print c
d = a - b
print bCopy after login
1.13 Sorting dictionary lists by common keys
rows = [
{'fname':'Brian', 'lname':'Jones', 'uid':1003},
{'fname':'David', 'lname':'Beazley', 'uid':1002},
{'fname':'John', 'lname':'Cleese', 'uid':1001},
{'fname':'Big', 'lname':'Jones', 'uid':1004}
]
from operator import itemgetter
rows_by_fname = sorted(rows, key=itemgetter('fname'))
rows_by_uid = sorted(rows, key=itemgetter('uid'))
print rows_by_fname
print rows_by_uid
rows_by_lfname = sorted(rows, key=itemgetter('lname', 'fname'))
print rows_by_lfname
rows_by_fname = sorted(rows, key=lambda r: r['fname'])
rows_by_lfname = sorted(rows, key=lambda r: (r['fname'], r['lname']))
print rows_by_fname
print rows_by_lfname
print min(rows, key=itemgetter('uid'))
print max(rows, key=itemgetter('uid'))Copy after login
1.14 Sorting objects that do not natively support comparison operations
class User:
def __init__(self, user_id):
self.user_id = user_id
def __repr__(self):
return 'User({})'.format(self.user_id)
users = [User(23), User(3), User(99)]
print users
print sorted(users, key = lambda u: u.user_id)
from operator import attrgetter
print sorted(users, key=attrgetter('user_id'))
print min(users, key=attrgetter('user_id'))
print max(users, key=attrgetter('user_id'))Copy after login
1.15 Grouping records based on fields
rows = [
{'address':'5412 N CLARK', 'data':'07/01/2012'},
{'address':'5232 N CLARK', 'data':'07/04/2012'},
{'address':'5542 E 58ARK', 'data':'07/02/2012'},
{'address':'5152 N CLARK', 'data':'07/03/2012'},
{'address':'7412 N CLARK', 'data':'07/02/2012'},
{'address':'6789 w CLARK', 'data':'07/03/2012'},
{'address':'9008 N CLARK', 'data':'07/01/2012'},
{'address':'2227 W CLARK', 'data':'07/04/2012'}
]
from operator import itemgetter
from itertools import groupby
rows.sort(key=itemgetter('data'))
for data, items in groupby(rows, key=itemgetter('data')):
print (data)
for i in items:
print (' ', i)
from collections import defaultdict
rows_by_date = defaultdict(list)
for row in rows:
rows_by_date[row['data']].append(row)
for r in rows_by_date['07/04/2012']:
print(r)Copy after login
1.16 Filtering elements in a sequence
mylist = [1,4,-5,10,-7,2,3,-1]
print [n for n in mylist if n > 0]#列表推导式
print [n for n in mylist if n < 0]
pos = (n for n in mylist if n > 0)#生成器表达式
print pos
for x in pos:
print(x)
values = ['1', '2', '-3', '-', '4', 'N/A', '5']
def is_int(val):
try:
x = int(val)
return True
except ValueError:
return False
ivals = list(filter(is_int, values))
print(ivals)
mylist = [1,4,-5,10,-7,2,3,-1]
import math
print [math.sqrt(n) for n in mylist if n > 0]
clip_neg = [n if n > 0 else 0 for n in mylist]
print clip_neg
clip_pos = [n if n < 0 else 0 for n in mylist]
print clip_pos
addresses = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
counts = [0, 3, 10, 4, 1, 7, 6, 1]
from itertools import compress
more5 = [n > 5 for n in counts]
print more5
print list(compress(addresses, more5))Copy after login
1. 17 from the dictionary Extract the subset
prices = {'ACNE':45.23, 'AAPL':612.78, 'IBM':205.55, 'HPQ':37.20, 'FB':10.75}
p1 = { key:value for key, value in prices.items() if value > 200 }
print p1
tech_names = {'AAPL', 'IBM', 'HPQ'}
p2 = { key:value for key, value in prices.items() if key in tech_names }
print p2
p3 = dict( (key, value) for key, value in prices.items() if value > 200 ) #慢
print p3
tech_names = {'AAPL', 'IBM', 'HPQ'}
p4 = { key:prices[key] for key in prices.keys() if key in tech_names } #慢
print p4Copy after login
1.18 Map the name to the elements of the sequence
from collections import namedtuple
Subscriber = namedtuple('Subscriber', ['addr', 'joined'])
sub = Subscriber('wang@qq.com', '2020-10-10')
print sub
print sub.joined
print sub.addr
print len(sub)
addr, joined = sub
print addr
print joined
def compute_cost(records):
total = 0.0
for rec in records:
total += rec[1]*rec[2]
return total
Stock = namedtuple('Stock', ['name', 'shares', 'price'])
def compute_cost2(records):
total = 0.0
for rec in records:
s = Stock(*rec)
total += s.shares * s.price
return total
s = Stock('ACME', 100, 123.45)
print s
#s.shares = 75 #error
s = s._replace(shares=75)
print s
Stock = namedtuple('Stock', ['name', 'shares', 'price', 'date', 'time'])
stock_prototype = Stock('',0, 0.0, None, None)
def dict_to_stock(s):
return stock_prototype._replace(**s)
a = {'name':'ACME', 'shares':100, 'price':123.45}
print dict_to_stock(a)
b = {'name':'ACME', 'shares':100, 'price':123.45, 'date':'12/12/2012'}
print dict_to_stock(b)Copy after login
1.19 Convert and convert the data at the same time
nums = [1, 2, 3, 4, 5]
s = sum( x*x for x in nums )
print s
import os
files = os.listdir('dirname')
if any(name.endswith('.py') for name in files):
print('There be Python!')
else:
print('sorry, no Python!')
s = ('ACME', 50, 123.45)
print(','.join(str(x) for x in s))
portfolio = [
{'name':'GOOG', 'shares':50},
{'name':'YHOO', 'shares':75},
{'name':'AOL', 'shares':20},
{'name':'SCOX', 'shares':65}
]
min_shares = min(s['shares'] for s in portfolio)
print min_shares
min_shares = min(portfolio, key=lambda s: s['shares'])
print min_shares
1.20 将多个映射合并为单个映射
Java代码
a = {'x':1, 'z':3}
b = {'y':2, 'z':4}
#from collections import ChainMap
from pip._vendor.distlib.compat import ChainMap
c = ChainMap(a, b)
print(c['x'])
print(c['y'])
print(c['z']) #from a 第一个映射中的值
print len(c)
print list(c.values())
c['z'] = 10
c['w'] = 40
del c['x']
print a
#del c['y'] #error 修改映射的操作总是会作用在列表的第一个映射结构上
values = ChainMap()
values['x'] = 1
values = values.new_child()#add a new map
values['x'] = 2
values = values.new_child()
values['x'] = 3
#print values
print values['x']
values = values.parents
print values['x']
values = values.parents
print values['x']
a = {'x':1, 'z':3}
b = {'y':2, 'z':4}
merged = dict(b)
merged.update(a)
print merged['x']
print merged['y']
print merged['z']
a['x'] = 13
print merged['x'] #不会反应到合并后的字典中
a = {'x':1, 'z':3}
b = {'y':2, 'z':4}
merged = ChainMap(a, b)
print merged['x']
a['x'] = 42
print merged['x'] #会反应到合并后的字典中Copy after login
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
