Shulou(Shulou.com)06/03 Report--

This article mainly shows you the "sample analysis of data structures and algorithms in Python", which is easy to understand and well-organized. I hope it can help you solve your doubts. Let me lead you to study and learn "sample analysis of data structures and algorithms in Python".

Data structure and algorithm

Algorithm: methods and steps to solve the problem

Evaluate the quality of the algorithm: asymptotic time complexity and asymptotic space complexity.

Large O mark of asymptotic time complexity:

-constant time complexity-Bloom filter / hash storage

-logarithmic time complexity-half search (binary search)

-Linear time complexity-Sequential search / bucket sort

-logarithmic linear time complexity-advanced sorting algorithm (merge sort, quick sort)

-Square time complexity-simple sorting algorithm (select sort, insert sort, bubble sort)

-cubic time complexity-Floyd algorithm / matrix multiplication

-geometric series time complexity-Hanoi tower

-factorial time complexity-Travel Dealer problem-NP

Sorting algorithm (selection, bubbling and merging) and search algorithm (order and halving)

Def select_sort (origin_items, comp=lambda x, y: X

< y): """简单选择排序""" items = origin_items[:] for i in range(len(items) - 1): min_index = i for j in range(i + 1, len(items)): if comp(items[j], items[min_index]): min_index = j items[i], items[min_index] = items[min_index], items[i] return itemsdef bubble_sort(origin_items, comp=lambda x, y: x >

Y): "High quality bubbling sort (stirring sort)"items = origin_items [:] for i in range (len (items)-1): swapped = False for j in range (I, len (items)-1-I): if comp (items [j], items [j + 1]): items [j], items [j + 1] = items [j + 1] Items [j] swapped = True if swapped: swapped = False for j in range (len (items)-2-I, I,-1): if comp (items [j-1], items [j]): items [j], items [j-1] = items [j-1], items [j] swapped = True if not swapped: break return itemsdef merge_sort (items, comp=lambda x, y: X 100} print (prices2)

Description: generative (deductive) can be used to generate lists, collections, and dictionaries.

Nested list

Names = ['Guan Yu', 'Zhang Fei', 'Zhao Yun','Ma Chao', 'Huang Zhong'] courses = [Chinese', 'Mathematics' 'English'] # enter five students' scores in three courses # error-refer to http://pythontutor.com/visualize.html#mode=edit# scores = [[None] * len (courses)] * len (names) scores = [[None] * len (courses) for _ in range (len (names))] for row, name in enumerate (names): for col Course in enumerate (courses): scores [row] [col] = float (input (please enter {course} score of {name}:') print (scores))

Python Tutor-VISUALIZE CODE AND GET LIVE HELP

The usage of heapq, itertools, etc.

"" import heapqlist1 = [34, 25, 12, 99, 87, 63, 58, 78, 88, 92] list2 = [{'name':' IBM', 'shares': 100,' price': 91.1}, {'name':' AAPL', 'shares': 50,' price': 543.22}, {'name':' FB'] 'shares': 200,' price': 21.09}, {'name':' HPQ', 'shares': 35,' price': 31.75}, {'name':' YHOO', 'shares': 45,' price': 16.35}, {'name':' ACME', 'shares': 75,' price': 115.65}] print (heapq.nlargest (3, list1) print (heapq.nsmallest (3, list1)) print (heapq.nlargest (2) List2, key=lambda x: X ['price']) print (heapq.nlargest (2, list2, key=lambda x: X [' shares']) "" iterative tools-permutation / combination / Cartesian product "import itertoolsitertools.permutations ('ABCD') itertools.combinations (' ABCDE', 3) itertools.product ('ABCD',' 123')

Tool classes under the collections module

"" from collections import Counterwords = ['look',' into', 'my',' eyes', 'look',' into', 'my',' eyes', 'the',' the', 'eyes',' the', 'eyes',' not', 'around',' the', 'eyes', "don't",' look' 'around',' the', 'eyes',' look', 'into',' my', 'eyes', "you're",' under'] counter = Counter (words) print (counter.most_common (3))

Common algorithms:

Exhaustion, also known as brute force cracking, validates all possibilities until the correct answer is found.

Greedy method-when solving a problem, always make the best choice at present, do not pursue the optimal solution, and quickly find a satisfactory solution.

Divide and conquer method-divide a complex problem into two or more identical or similar sub-problems, then divide the sub-problems into smaller sub-problems until they can be solved directly, and finally combine the solutions of the sub-problems to get the solution of the original problem.

The backtracking method, also known as the heuristic method, searches forward according to the selection conditions, and when it comes to a certain step and finds that the original choice is not excellent or can not achieve the goal, it will take a step back and re-select.

Dynamic programming-the basic idea is to decompose the problem to be solved into several sub-problems, and first solve and save the solutions of these sub-problems to avoid a large number of repeated operations.

Examples of exhaustive method: a hundred dollars, a hundred chickens and a fish for five people.

# Rooster 5 yuan per hen 3 yuan a chicken 1 yuan 3 # buy 100 yuan to ask the number of for x in range (20): for y in range (33): Z = 100x-y if 5 * x + 3 * y + z / / 3 = = 100 and z% 3 = 0: print (x, y) Z) # A, B, C, D, E went fishing together one night and finally went to sleep. # the next day A first woke up, he divided the fish into five parts, threw away the extra one, took his own # B the second woke up and divided the fish into five, threw away the extra one, took his own # and then C, D, E woke up in turn and divided the fish in the same way and asked them how many fish they had caught at least fish = 1while True: total = fish enough = True for _ in range (5): if (total-1)% 5 = = 0: total = (total-1) / / 5 * 4 else: enough = False break if enough: print (fish) break fish + = 1

Example of greed: suppose the thief has a backpack that can hold up to 20 kilograms of stolen goods. He breaks into a house and finds the items shown in the table below. Obviously, he can't put everything in his backpack, so he has to determine which items to take and which ones to leave.

Name Price (US dollars) weight (kg) computer radio 204clocks 17510 vases 17510 books 101Oil painting 909 "greedy method: when solving a problem, always make the best choice in the current view, do not pursue the optimal solution, and quickly find a satisfactory solution. Input: 20 6 computer 200 20 radio 20 4 clock 175 10 vase 50 2 books 10 1 oil painting 90 9 "class Thing (object):" item "" def _ init__ (self, name, price, weight): self.name = name self.price = price self.weight = weight @ property def value (self): "" Price / weight ratio "" return self.price / self.weightdef input_thing (): "" enter item information "name_str" Price_str, weight_str = input (). Split () return name_str, int (price_str), int (weight_str) def main (): "" main function "max_weight, num_of_things = map (int, input (). Split ()) all_things = [] for _ in range (num_of_things): all_things.append (Thing (* input_thing ()) all_things.sort (key=lambda x: x.value) Reverse=True) total_weight = 0 total_price = 0 for thing in all_things: if total_weight + thing.weight = 0 and col

< SIZE and \ board[row][col] == 0: board[row][col] = step if step == SIZE * SIZE: global total total += 1 print(f'第{total}种走法: ') print_board(board) patrol(board, row - 2, col - 1, step + 1) patrol(board, row - 1, col - 2, step + 1) patrol(board, row + 1, col - 2, step + 1) patrol(board, row + 2, col - 1, step + 1) patrol(board, row + 2, col + 1, step + 1) patrol(board, row + 1, col + 2, step + 1) patrol(board, row - 1, col + 2, step + 1) patrol(board, row - 2, col + 1, step + 1) board[row][col] = 0def main(): board = [[0] * SIZE for _ in range(SIZE)] patrol(board, SIZE - 1, SIZE - 1)if __name__ == '__main__': main() 动态规划例子1：斐波拉切数列。（不使用动态规划将会是几何级数复杂度） """动态规划 - 适用于有重叠子问题和最优子结构性质的问题使用动态规划方法所耗时间往往远少于朴素解法(用空间换取时间)"""def fib(num, temp={}): """用递归计算Fibonacci数""" if num in (1, 2): return 1 try: return temp[num] except KeyError: temp[num] = fib(num - 1) + fib(num - 2) return temp[num] 动态规划例子2：子列表元素之和的最大值。（使用动态规划可以避免二重循环） 说明：子列表指的是列表中索引（下标）连续的元素构成的列表；列表中的元素是int类型，可能包含正整数、0、负整数；程序输入列表中的元素，输出子列表元素求和的最大值，例如： 输入：1 -2 3 5 -3 2 输出：8 输入：0 -2 3 5 -1 2 输出：9 输入：-9 -2 -3 -5 -3 输出：-2 def main(): items = list(map(int, input().split())) size = len(items) overall, partial = {}, {} overall[size - 1] = partial[size - 1] = items[size - 1] for i in range(size - 2, -1, -1): partial[i] = max(items[i], partial[i + 1] + items[i]) overall[i] = max(partial[i], overall[i + 1]) print(overall[0])if __name__ == '__main__': main() 函数的使用方式 将函数视为"一等公民" 函数可以赋值给变量 函数可以作为函数的参数 函数可以作为函数的返回值 高阶函数的用法（filter、map以及它们的替代品） items1 = list(map(lambda x: x ** 2, filter(lambda x: x % 2, range(1, 10))))items2 = [x ** 2 for x in range(1, 10) if x % 2] 位置参数、可变参数、关键字参数、命名关键字参数 参数的元信息（代码可读性问题） 匿名函数和内联函数的用法（lambda函数） 闭包和作用域问题 Python搜索变量的LEGB顺序（Local -->

Embedded-- > Global-- > Built-in)

The role of global and nonlocal keywords

Global: declare or define global variables (either directly use variables with existing global scope, or define a variable to be placed in global scope).

Nonlocal: declare a variable that uses a nested scope (the variable must exist in the nested scope, otherwise an error is reported).

Decorator function (using decorator and undecorator)

Example: a decorator that outputs the execution time of a function.

Def record_time (func): "@ wraps (func) def wrapper (* args, * * kwargs): start = time () result = func (* args, * * kwargs) print (f'{func.__name__}: {time ()-start} seconds') return result return wrapper

If the decorator does not want to be coupled to the print function, you can write a decorator with parameters.

From functools import wrapsfrom time import timedef record (output): "" Custom decorator with parameters "" def decorate (func): @ wraps (func) def wrapper (* args, * * kwargs): start = time () result = func (* args) * * kwargs) output (func.__name__, time ()-start) return result return wrapper return decoratefrom functools import wrapsfrom time import timeclass Record (): "Custom decorator class (using the _ _ call__ magic method so that objects can be called as functions)" def _ _ init__ (self) Output): self.output = output def _ call__ (self, func): @ wraps (func) def wrapper (* args, * * kwargs): start = time () result = func (* args, * * kwargs) self.output (func.__name__, time ()-start) return result return wrapper

Note: since @ wraps decorator is added to the function with decoration function, the function or class before decoration can be obtained through func.__wrapped__ to cancel the role of the decorator.

Example: implement the singleton pattern with a decorator.

From functools import wrapsdef singleton (cls): "" decorative decorator "" instances = {} @ wraps (cls) def wrapper (* args, * * kwargs): if cls not in instances: instances [cls] = cls (* args, * * kwargs) return instances [cls] return wrapper@singletonclass President (): "President (singleton class)"pass

Description: closure is used in the above code. I don't know if you are aware of it. There is no small problem, that is, the above code does not implement a thread-safe singleton, so what should I do if I want to implement a thread-safe singleton?

From functools import wrapsfrom threading import Lockdef singleton (cls): "" thread-safe singleton decorator "instances = {} locker = Lock () @ wraps (cls) def wrapper (* args, * * kwargs): if cls not in instances: with locker: if cls not in instances: instances [cls] = cls (* args, * * kwargs) return instances [cls] return wrapper

Object-oriented related knowledge

Three pillars: encapsulation, inheritance and polymorphism

Example: wage settlement system.

"" monthly salary settlement system-Department manager 15000 programmers per hour 1800 salespeople per month 1800 base salary plus 5% commission on sales "" from abc import ABCMeta, abstractmethodclass Employee (metaclass=ABCMeta): "" employee (abstract class) "" def _ _ init__ (self) " Name): self.name = name @ abstractmethod def get_salary (self): "settlement monthly salary (abstract method)"passclass Manager (Employee):"Department Manager"def get_salary (self): return 15000.0class Programmer (Employee):"programmer"def _ _ init__ (self, name)" Working_hour=0): self.working_hour = working_hour super (). _ init__ (name) def get_salary (self): return 200.0 * self.working_hourclass Salesman (Employee): "salesperson"def _ _ init__ (self, name)" Sales=0.0): self.sales = sales super (). _ init__ (name) def get_salary (self): return 1800.0 + self.sales * 0.05class EmployeeFactory (): "" create a factory for employees (factory mode-decoupling between object consumers and objects through the factory) "@ staticmethod def create (emp_type, * args) * * kwargs): "" create employees "emp_type = emp_type.upper () emp = None if emp_type = = 'kwargs: emp = Manager (* args, * * kwargs) elif emp_type = =' playing: emp = Programmer (* args, * * kwargs) elif emp_type = 'slots: emp = Salesman (* args, * * kwargs) return empdef main ():" main function "" emps = [EmployeeFactory.create (' M' ") Cao Cao, EmployeeFactory.create, EmployeeFactory.create, Guo Jia, 85, EmployeeFactory.create, Dian Wei, 123000), for emp in emps: print (% s:% .2f yuan'% (emp.name, emp.get_salary () if _ name__ = ='_ _ main__': main ()

The relationship between classes

Is-a relationships: inheritance

Has-a relationships: Association / aggregation / synthesis

Use-a relationships: dependencies

Example: poker game.

Experience: symbolic constants are always better than literal constants. Enumerated types are the best choice for defining symbolic constants. From enum import Enum, uniqueimport random@uniqueclass Suite (Enum): SPADE, HEART, CLUB, DIAMOND = range (4) def _ lt__ (self, other): return self.value

< other.valueclass Card(): """牌""" def __init__(self, suite, face): """初始化方法""" self.suite = suite self.face = face def show(self): """显示牌面""" suites = ['♠️', '♥️', '♣️', '♦️'] faces = ['', 'A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K'] return f'{suites[self.suite.value]} {faces[self.face]}' def __str__(self): return self.show() def __repr__(self): return self.show()class Poker(): """扑克""" def __init__(self): self.index = 0 self.cards = [Card(suite, face) for suite in Suite for face in range(1, 14)] def shuffle(self): """洗牌（随机乱序）""" random.shuffle(self.cards) self.index = 0 def deal(self): """发牌""" card = self.cards[self.index] self.index += 1 return card @property def has_more(self): return self.index < len(self.cards)class Player(): """玩家""" def __init__(self, name): self.name = name self.cards = [] def get_one(self, card): """摸一张牌""" self.cards.append(card) def sort(self, comp=lambda card: (card.suite, card.face)): """整理手上的牌""" self.cards.sort(key=comp)def main(): """主函数""" poker = Poker() poker.shuffle() players = [Player('东邪'), Player('西毒'), Player('南帝'), Player('北丐')] while poker.has_more: for player in players: player.get_one(poker.deal()) for player in players: player.sort() print(player.name, end=': ') print(player.cards)if __name__ == '__main__': main() 对象的复制（深复制/深拷贝/深度克隆和浅复制/浅拷贝/影子克隆） 垃圾回收、循环引用和弱引用 Python使用了自动化内存管理，这种管理机制以引用计数为基础，同时也引入了标记-清除和分代收集两种机制为辅的策略。 typedef struct_object { /* 引用计数 */ int ob_refcnt; /* 对象指针 */ struct_typeobject *ob_type;} PyObject;/* 增加引用计数的宏定义 */#define Py_INCREF(op) ((op)->

Ob_refcnt++) / * Macro definition to reduce the reference count * / # define Py_DECREF (op)\ / / reduce the count if (--(op)-> ob_refcnt! = 0)\;\ else\ _ Py_Dealloc ((PyObject *) (op)

Cases that result in a reference count of + 1:

Object is created, for example, a = 23

Object is referenced, for example, b = a

Object is passed as a parameter to a function, such as f (a)

Object is stored as an element in a container, such as list1 = [a, a]

Cases that result in a reference count of-1:

The alias of the object is explicitly destroyed, such as del a

The alias of the object is assigned to the new object, for example, a = 24

An object leaves its scope, for example, when the f function is finished, the local variable in the f function (the global variable will not)

The container in which the object is located is destroyed or the object is deleted from the container

Reference counting can cause circular reference problems, which can lead to memory leaks, as shown in the following code. To solve this problem, "Mark-clear" and "generational collection" are introduced into Python. When creating an object, the object is placed in the first generation, and if the object survives in the first generation of garbage checks, the object will be placed in the second generation, in the same way it will survive in the second generation of garbage checks. The object will be placed in the third generation.

# Circular references can lead to memory leaks-Python introduces tag cleanup and generational recycling in addition to reference technology # rewriting the _ _ del__ magic method before Python 3.6 will cause circular reference processing to fail # if you do not want to cause circular references, you can use weak references list1 = [] list2 = [] list1.append (list2) list2.append (list1)

The following conditions can lead to garbage collection:

Call gc.collect ()

The counter of the gc module reaches the threshold

Program exit

If both objects in the circular reference define the _ _ del__ method, the gc module does not destroy these unreachable objects because the gc module does not know which object's _ _ del__ method should be called first, and this problem is resolved in Python 3.6.

You can also solve the problem of circular references by constructing weak references in the weakref module.

Magic attributes and methods (please refer to the Python Magic method Guide)

There are a few small questions for you to think about:

Can custom objects be operated with operators?

Can custom objects be put into set? Can I get heavy?

Can custom objects be used as keys for dict?

Can custom objects use context syntax?

Blend in (Mixin)

Example: a custom dictionary limit allows you to set key-value pairs in the dictionary only if the specified key does not exist.

Class SetOnceMappingMixin (): "" Custom blending class "" _ _ slots__ = () def _ setitem__ (self, key, value): if key in self: raise KeyError (str (key) + 'already set') return super (). _ setitem__ (key, value) class SetOnceDict (SetOnceMappingMixin) Dict): "" Custom dictionary "" passmy_dict= SetOnceDict () try: my_dict ['username'] =' jackfrued' my_dict ['username'] =' hellokitty'except KeyError: passprint (my_dict) "

Metaprogramming and metaclass

Example: implementing singleton pattern with metaclass

Import threadingclass SingletonMeta (type): "Custom metaclass" def _ _ init__ (cls, * args, * * kwargs): cls.__instance = None cls.__lock = threading.Lock () super (). _ _ init__ (* args, * * kwargs) def _ _ call__ (cls, * args) * * kwargs): if cls.__instance is None: with cls.__lock: if cls.__instance is None: cls.__instance = super (). _ _ call__ (* args, * * kwargs) return cls.__instanceclass President (metaclass=SingletonMeta): "President (singleton)"pass"

Principles of object-oriented design

Single responsibility principle (SRP)-A class only does what needs to be done (classes are designed to be highly cohesive)

Open-close principle (OCP)-Software entities should be closed for extension development and modification

Dependency inversion principle (DIP)-oriented abstract programming (weakened in weakly typed languages)

Richter substitution principle (LSP)-you can replace a parent object with a subclass object at any time

Interface isolation principle (ISP)-interfaces should be small but not large and comprehensive (there is no concept of interfaces in Python)

Principle of synthetic aggregate reuse (CARP)-reuse code with strong associations over inheritance relationships

Principle of least knowledge (Dimitt's rule, LoD)-do not send messages to objects that are not necessarily connected

Description: the bold letters above are put together as object-oriented SOLID principles.

GoF design pattern

Creative model: singleton, factory, builder, prototype

Structural patterns: adapters, facades (appearance), agents

Behavioral patterns: iterators, observers, states, strategies

Example: pluggable hash algorithm.

Class StreamHasher (): "" Hash digest generator (policy mode) "" def _ init__ (self, alg='md5', size=4096): self.size = size alg= alg.lower () self.hasher = getattr (_ _ import__ ('hashlib'), alg.lower ()) () def _ call__ (self, stream): return self.to_digest (stream) def to_digest (self) Stream): "" generate a summary in hexadecimal form "for buf in iter (lambda: stream.read (self.size), baked'): self.hasher.update (buf) return self.hasher.hexdigest () def main ():" main function "hasher1 = StreamHasher () with open ('Python-3.7.1.tgz'" 'rb') as stream: print (hasher1.to_digest (stream)) hasher2 = StreamHasher (' sha1') with open ('Python-3.7.1.tgz',' rb') as stream: print (hasher2 (stream)) if _ _ name__ = ='_ main__': main ()

Iterators and generators

Magic methods associated with iterators (_ _ iter__ and _ _ next__)

Two ways to create a generator (generator expression and yield keyword)

Def fib (num): "generator"a, b = 0,1 for _ in range (num): a, b = b, a + b yield a class Fib (object):"iterator"def _ init__ (self, num): self.num = num self.a, self.b = 0,1 self.idx = 0 def _ iter__ (self): return self def _ next__ (self): if self.idx

< self.num: self.a, self.b = self.b, self.a + self.b self.idx += 1 return self.a raise StopIteration() 并发编程 Python中实现并发编程的三种方案：多线程、多进程和异步I/O。并发编程的好处在于可以提升程序的执行效率以及改善用户体验；坏处在于并发的程序不容易开发和调试，同时对其他程序来说它并不友好。 多线程：Python中提供了Thread类并辅以Lock、Condition、Event、Semaphore和Barrier。Python中有GIL来防止多个线程同时执行本地字节码，这个锁对于CPython是必须的，因为CPython的内存管理并不是线程安全的，因为GIL的存在多线程并不能发挥CPU的多核特性。 """面试题：进程和线程的区别和联系？进程 - 操作系统分配内存的基本单位 - 一个进程可以包含一个或多个线程线程 - 操作系统分配CPU的基本单位并发编程（concurrent programming）1. 提升执行性能 - 让程序中没有因果关系的部分可以并发的执行2. 改善用户体验 - 让耗时间的操作不会造成程序的假死"""import globimport osimport threadingfrom PIL import ImagePREFIX = 'thumbnails'def generate_thumbnail(infile, size, format='PNG'): """生成指定图片文件的缩略图""" file, ext = os.path.splitext(infile) file = file[file.rfind('/') + 1:] outfile = f'{PREFIX}/{file}_{size[0]}_{size[1]}.{ext}' img = Image.open(infile) img.thumbnail(size, Image.ANTIALIAS) img.save(outfile, format)def main(): """主函数""" if not os.path.exists(PREFIX): os.mkdir(PREFIX) for infile in glob.glob('images/*.png'): for size in (32, 64, 128): # 创建并启动线程 threading.Thread( target=generate_thumbnail, args=(infile, (size, size)) ).start() if __name__ == '__main__': main() 多个线程竞争资源的情况 """多线程程序如果没有竞争资源处理起来通常也比较简单当多个线程竞争临界资源的时候如果缺乏必要的保护措施就会导致数据错乱说明：临界资源就是被多个线程竞争的资源"""import timeimport threadingfrom concurrent.futures import ThreadPoolExecutorclass Account(object): """银行账户""" def __init__(self): self.balance = 0.0 self.lock = threading.Lock() def deposit(self, money): # 通过锁保护临界资源 with self.lock: new_balance = self.balance + money time.sleep(0.001) self.balance = new_balanceclass AddMoneyThread(threading.Thread): """自定义线程类""" def __init__(self, account, money): self.account = account self.money = money # 自定义线程的初始化方法中必须调用父类的初始化方法 super().__init__() def run(self): # 线程启动之后要执行的操作 self.account.deposit(self.money)def main(): """主函数""" account = Account() # 创建线程池 pool = ThreadPoolExecutor(max_workers=10) futures = [] for _ in range(100): # 创建线程的第1种方式 # threading.Thread( # target=account.deposit, args=(1, ) # ).start() # 创建线程的第2种方式 # AddMoneyThread(account, 1).start() # 创建线程的第3种方式 # 调用线程池中的线程来执行特定的任务 future = pool.submit(account.deposit, 1) futures.append(future) # 关闭线程池 pool.shutdown() for future in futures: future.result() print(account.balance)if __name__ == '__main__': main() 修改上面的程序，启动5个线程向账户中存钱，5个线程从账户中取钱，取钱时如果余额不足就暂停线程进行等待。为了达到上述目标，需要对存钱和取钱的线程进行调度，在余额不足时取钱的线程暂停并释放锁，而存钱的线程将钱存入后要通知取钱的线程，使其从暂停状态被唤醒。可以使用threading模块的Condition来实现线程调度，该对象也是基于锁来创建的，代码如下所示： """多个线程竞争一个资源 - 保护临界资源 - 锁（Lock/RLock）多个线程竞争多个资源（线程数>

Resources)-semaphore (Semaphore) scheduling of multiple threads-pause thread execution / wake up waiting threads-Condition "from concurrent.futures import ThreadPoolExecutorfrom random import randintfrom time import sleepimport threadingclass Account ():" Bank account "def _ _ init__ (self, balance=0): self.balance = balance lock = threading.Lock () self.condition = threading.Condition (lock) def withdraw (self) Money): "" withdraw money "" with self.condition: while money > self.balance: self.condition.wait () new_balance = self.balance-money sleep (0.001) self.balance = new_balance def deposit (self Money): "" savings "" with self.condition: new_balance = self.balance + money sleep (0.001) self.balance = new_balance self.condition.notify_all () def add_money (account): while True: money = randint (5,10) account.deposit (money) print (threading.current_thread (). Name,':', money,'= = >' Account.balance) sleep (0.5) def sub_money (account): while True: money = randint (10,30) account.withdraw (money) print (threading.current_thread () .name,':', money,'', I) primes.append (I) await asyncio.sleep (0.001) return tuple (primes) async def square_mapper (m, n): "Square Mapper"squares = [] for i in num_generator (m) N): print ('Square = >', I * I) squares.append (I * I) await asyncio.sleep (0.001) return squaresdef main (): "" main function "" loop = asyncio.get_event_loop () future = asyncio.gather (prime_filter (2,100), square_mapper (1) Future.add_done_callback (lambda x: print (x.result ()) loop.run_until_complete (future) loop.close () if _ _ name__ = ='_ _ main__': main ()

Note: the above code uses the get_event_loop function to obtain the default event loop of the system, and a future object can be obtained through the gather function. The add_done_callback of the future object can add the callback function when the execution is completed, and the run_until_complete method of the loop object can wait for the cooperative program execution result to be obtained through the future object.

There is a three-party library in Python called aiohttp, which provides asynchronous HTTP clients and servers, which works with the asyncio module and provides support for Future objects. Async and await were introduced in Python 3.6to define functions to execute asynchronously and to create asynchronous contexts, which officially became keywords in Python 3.7s. The following code fetches the page asynchronously from five URL and extracts the site title through a named capture group of regular expressions.

Import asyncioimport reimport aiohttpPATTERN = re.compile (r'\ (? P.*)\') async def fetch_page (session, url): async with session.get (url, ssl=False) as resp: return await resp.text () async def show_title (url): async with aiohttp.ClientSession () as session: html = await fetch_page (session, url) print (PATTERN.search (html) .group ('title') def main (): urls = (' https://www.python.org/',) 'https://git-scm.com/',' https://www.jd.com/', 'https://www.taobao.com/',' https://www.douban.com/') loop = asyncio.get_event_loop () tasks = [show_title (url) for url in urls] loop.run_until_complete (asyncio.wait (tasks)) loop.close () if _ _ name__ = ='_ main__': main ()

Description: comparison of asynchronous Imax O and multi-processes.

Asyncio is a good choice when programs don't need real concurrency or parallelism, but rely more on asynchronous processing and callbacks. If there is a lot of waiting and sleeping in the program, you should also consider asyncio, which is very suitable for writing Web application servers without real-time data processing requirements.

Python also has many tripartite libraries for dealing with parallel tasks, such as joblib, PyMP, and so on. In actual development, there are usually two ways to improve the scalability and concurrency of the system: vertical expansion (increasing the processing capacity of a single node) and horizontal expansion (turning a single node into multiple nodes). Applications can be decoupled through message queues, which are equivalent to extended versions of multithreaded synchronous queues, applications on different machines are threads, and shared distributed message queues are Queue in the original program. The most popular and standardized implementation of message queuing (message-oriented middleware) is AMQP (Advanced message queuing Protocol). AMQP originates from the financial industry and provides queuing, routing, reliable transmission, security and other functions. The most famous implementations include: Apache ActiveMQ, RabbitMQ and so on.

To asynchronize tasks, you can use a three-party library called Celery. Celery is a distributed task queue written by Python, which works with distributed messages and can be used as a back-end message broker based on RabbitMQ or Redis.

The above is all the contents of the article "sample Analysis of data structures and algorithms in Python". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.