[Python 7] excel, matplotlib, sorting, tree traversal, line / process

1.csv


2.excel

Read:


Print sheet (not Workbook) Name:

Get each row:

Write:

3.matplotlib

import numpy as np
from matplotlib import pyplot as plt
import pandas as pd
df =pd.read_excel("Documents/b.xlsx")
df
plt.figure(figsize=(6,4))
plt.title("Train History")
plt.xlabel("Epoch")
plt.ylabel("Number of loss")

plt.plot(df.c,df.d,"r",marker='*', mec='r', mfc='w')
plt.plot(df.a,df.b, marker='*', mec='b', mfc='w')
plt.plot(df.g,df.h,marker='*', mfc='w')
plt.plot(df.e,df.f,"g",marker='*', mec='g', mfc='w')
plt.xticks(range(0,21))

plt.legend(["y=CNN-AlexNet-loss","y=CNN-VGGNet-loss","y=CNN-ResNet-loss","y=Improved CNN-ResNet-loss"])
plt.show

plt.figure(figsize=(6,4))
plt.title("YOLOV4")
plt.xlabel("Batch")
plt.ylabel("acc")

plt.plot(df.a,df.b,"")
plt.plot(df.c,df.d,"")
plt.legend(["train","test"])
plt.show

plt.figure(figsize=(6,4))
plt.xlabel("Precision")
plt.ylabel("Recall")

plt.plot(df.a,df.b, marker='o', mec='b', mfc='w')
plt.plot(df.c,df.d,"r",marker='o', mec='r', mfc='w')
#plt.xticks(range(0,21))
plt.legend(["y=Ours","y=YoloV4"])
plt.show

4. Time complexity

# If a+b+c=1000 and a^2+b^2=c^2 (a, B and C are natural numbers), how to find all possible combinations of a, B and C?
import time
start_time = time.time()
for a in range(0,1001):
    for b in range(0,1001):
        for c in range(0,1001):
            if a+b+c==1000 and a**2+b**2==c**2:
                print('a,b,c:%d,%d,%d'%(a,b,c))
end_time = time.time()
print('time:%d'%(end_time-start_time))
print('finished')

Output:

a,b,c:0,500,500
a,b,c:200,375,425
a,b,c:375,200,425
a,b,c:500,0,500
time:203
finished



From small to large, use functions to add elements to the list. Because functions are the encapsulation of basic steps, they cannot be counted as one step

5. Sequence list / linked list

Program = data structure + algorithm: the following figure shows the storage of data: one int takes up 4 bytes (char or B)(1B=8bit), and the following 1 is placed in 4 bytes.

The following int types are stored in order, that is, the sequence table, which is convenient for searching

In the following figure, the left side is the basic form of sequence table, and the right side is the external form (storage address) of elements

The following is the sequence table structure


The sequence table requires that the storage space must be continuous. Once it is insufficient, the data area must be changed dynamically. The linear list is divided into sequential list and linked list. The following figure is a linked list. There is no need to change the original data structure, one more and one more.

6. Six sorts


Stability of sorting algorithm: sort according to the size of the first element in the tuple (maintain the previous order, that is, the first group is stable as follows)

6.1 selection

from time import time # Timing decorator 
def timer(func):     
    def inner(*args,**kwargs):
        start = time()
        result = func(*args,**kwargs)
        end = time()
        usedTime = 1000 * (end - start)
        
        print("%s function used %.2f ms" %(func.__name__,usedTime))
        return result
    return inner
@timer
def select_sort(alist):#Select (traverse) sorting, select the smallest from the right and put it on the left
    n = len(alist)
    for j in range(n-1):#j:0 to n-2
        min_index=j #False minimum subscript, traversing from the first
        for i in range(j+1,n):
            if alist[min_index]>alist[i]:
                min_index=i
            alist[j],alist[min_index]=alist[min_index],alist[j] 
        #Here min_index is the minimum subscript of true
if __name__ == "__main__":
    blist = list(range(1,3000 + 1))
    import random
    blist = random.sample(blist, k=len(blist))
    alist = blist[:1000]
    select_sort(alist)
    print(alist)

6.2 insertion

@timer
def insert_sort(alist):
    n=len(alist)
    for j in range(1,n):#How many elements are taken from the unordered sequence on the right to perform such a process
        #j=[1,2,3,n-1]
        #i represents the starting value of inner loop
        i=j
        #Execute to extract the first element from the unordered sequence on the right, that is, the element at i position
        #Then insert it into the correct position on the front
        while i>0:
            if alist[i]<alist[i-1]:
                alist[i],alist[i-1]=alist[i-1],alist[i]
                i-=1
            else:
                break

if __name__ == "__main__":
    blist = list(range(1,3000 + 1))
    import random
    blist = random.sample(blist, k=len(blist))
    alist = blist[:1000]
    insert_sort(alist)
    print(alist)

6.3 Hill

Selective sorting is to select one from the following unordered sequence and put it in the last position in front.
Insert sort is to select one from the following unordered sequence and insert which one in the position of the previous ordered sequence (from right to left).
Hill sorting is an improvement of insertion sorting: 54, 77 and 20 are sorted by insertion, from small to large, and then 26 and 31 are sorted from small to large.

The second row in the figure below is the row with gap=4 in the first row

@timer
def shell_sort(alist):#Shell Sort 
    n=len(alist) #n=9
    gap=n//2 #gap=4
    while gap>0:#The number of times the insertion algorithm is executed before gap changes to 0
        #The gap step size is different from the ordinary insertion algorithm
        for j in range(gap,n):
            i=j #j=[gap,gap+1,gap+2,gap+3,..,n-1]
            while i>0:
                if alist[i]<alist[i-gap]:
                    alist[i],alist[i-gap]=alist[i-gap],alist[i]
                    i-=gap
                else:
                    break
        gap//=2
if __name__ == "__main__":
    blist = list(range(1,3000 + 1))
    import random
    blist = random.sample(blist, k=len(blist))
    alist = blist[:1000]
    shell_sort(alist)
    print(alist)

6.4 bubbling

@timer
def bubble_sort(alist): 
    n = len(alist)
    for j in range(n-1):
        for i in range(n-1-j):
            if alist[i]>alist[i+1]:
                alist[i],alist[i+1]=alist[i+1],alist[i]
if __name__ == "__main__":
    blist = list(range(1,3000 + 1))
    import random
    blist = random.sample(blist, k=len(blist))#Get k elements randomly from blist
    alist = blist[:1000]
    #print(alist)
    bubble_sort(alist)
    print(alist)

6.5 fast exhaust

The previous sorting methods are divided into left and right parts. In the fast row, if the low element is larger than 54 and the high element is smaller than 54, then the low and high elements exchange with each other and continue to go to the middle. When overlapping, the first element of low refers to 54. The position is fixed, and the left and right sides of 54 continue to operate low and high respectively.

def quick_sort(alist,first,last):
    if first>=last:
        return
    mid_value=alist[first]
    low=first  #low and high are cursors, first is the first element, and last is the last element
    high=last
    while low<high:#No meeting
        while low<high and alist[high]>=mid_value:
            high-=1 #high shift left
        alist[low]=alist[high]#Element exchange, cursor does not exchange
        
        while low<high and alist[low]<mid_value:
            low+=1
        alist[high]=alist[low]
        
    #When exiting from the loop, low==high
    alist[low]=mid_value
    
    #Perform a quick sort on the list to the left of low
    quick_sort(alist,first,low-1)
     
    #Perform a quick sort on the list to the right of low
    quick_sort(alist,low+1,last)

def main():
    blist = list(range(1,3000 + 1))
    import random
    blist = random.sample(blist, k=len(blist))
    alist = blist[:1000]
    quick_sort(alist,0,len(alist)-1)
    print(alist)
main()

6.6 consolidation

The following figure splits the two parts until there is only one element, and then compares them.

In the figure above, compare 26 to 17, take out 17, and move the right pointer back. 26 compared with 93, 26 took out 26 and ranked behind 17.

7. Tree traversal


Pre order (pre root): left and right root
Middle order: projection
Post order: left and right roots (from bottom to top)

8. Line / process

8.1 threads






The following 2 (7) means that 2 have been borrowed and 7 are still missing

8.2 process



8.3 process pool



Multi task folder copy:

8.4 coordination process

gevent picture download:

8.5 GIL



python3 main.py, so solve GIL: 1 Replace cpython interpreter (c is compiled and Python is interpreted) 2 Replace thread with another language


B station / know / WeChat official account: Code agriculture programming

Tags: Python data structure Algorithm linked list quick sort

Posted by Q695 on Mon, 18 Apr 2022 05:11:08 +0930