常见算法的python实现
def search(li, target):
def binary_search(li, target, left, right):
# li is a sorted array
# target is the searching target, which should be unique in the array
# left and right set the search boundary
if left <= right:
mid = (left + right) // 2
if li[mid] < target:
return binary_search(li, target, mid, right)
elif li[mid] > target:
return binary_search(li, target, left, mid)
else:
return mid
else:
return -1
print(binary_search(li, target, 0, len(li)))
search([i for i in range(100)], 6)
- x raised to the n-th power
def power(x, n):
if n == 0:
return 1
t = power(x, n//2)
if n % 2 == 1:
return t*t*x
return t*t
- matrix multiplication - the strassen algorithm
# an amazing method of reducing the number of mutiplication
# coding: utf-8 -*-
# copied from https://blog.csdn.net/shaungyezhai/article/details/52229500
def matrixproduct(a, b):
def matrixproductmask(mat_a, mat_b):
if mat_a.row == 1:
c11 = [[mat_a.mat_list[mat_a.row_list[0]][mat_a.col_list[0]] *
mat_b.mat_list[mat_b.row_list[0]][mat_b.col_list[0]]]]
return Martrix(c11)
else:
mat_a11 = mat_a.divide('11')
mat_a12 = mat_a.divide('12')
mat_a21 = mat_a.divide('21')
mat_a22 = mat_a.divide('22')
mat_b11 = mat_b.divide('11')
mat_b12 = mat_b.divide('12')
mat_b21 = mat_b.divide('21')
mat_b22 = mat_b.divide('22')
s1 = mat_b12 - mat_b22
s2 = mat_a11 + mat_a12
s3 = mat_a21 + mat_a22
s4 = mat_b21 - mat_b11
s5 = mat_a11 + mat_a22
s6 = mat_b11 + mat_b22
s7 = mat_a12 - mat_a22
s8 = mat_b21 + mat_b22
s9 = mat_a11 - mat_a21
s10 = mat_b11 + mat_b12
p1 = matrixproductmask(mat_a11, s1)
p2 = matrixproductmask(s2, mat_b22)
p3 = matrixproductmask(s3, mat_b11)
p4 = matrixproductmask(mat_a22, s4)
p5 = matrixproductmask(s5, s6)
p6 = matrixproductmask(s7, s8)
p7 = matrixproductmask(s9, s10)
c11 = (p5 + p4 - p2 + p6)
c12 = (p1 + p2)
c21 = (p3 + p4)
c22 = (p5 + p1 - p3 - p7)
return matrixmerge(c11, c12, c21, c22)
mat_a = Martrix(a)
mat_b = Martrix(b)
product = matrixproductmask(mat_a, mat_b)
return product.mat_list
def matrixmerge(c11, c12, c21, c22):
mat_list = []
for i in c11.row_list:
mat_list.append(c11.mat_list[i] + c12.mat_list[i])
for i in c21.row_list:
mat_list.append(c21.mat_list[i] + c22.mat_list[i])
return Martrix(mat_list)
class Martrix(object):
def __init__(self, *args):
if len(args) == 1 and isinstance(args[0], list):
self.mat_list = args[0]
self.row = len(args[0])
self.col = len(args[0][0])
self.row_list = range(self.row)
self.col_list = range(self.col)
def __add__(self, mat2):
mat_list = [
[self.mat_list[self.row_list[i]][self.col_list[j]] + mat2.mat_list[mat2.row_list[i]][mat2.col_list[j]]
for j in range(self.col)] for i in range(self.row)]
return Martrix(mat_list)
def __sub__(self, mat2):
mat_list = [
[self.mat_list[self.row_list[i]][self.col_list[j]] - mat2.mat_list[mat2.row_list[i]][mat2.col_list[j]]
for j in range(self.col)] for i in range(self.row)]
return Martrix(mat_list)
def divide(self, block):
result = Martrix()
result.mat_list = self.mat_list
result.row = self.row / 2
result.col = self.col / 2
dic = {'11': [self.row_list[:result.row], self.col_list[:result.col]],
'12': [self.row_list[:result.row], self.col_list[result.col:]],
'21': [self.row_list[result.row:], self.col_list[:result.col]],
'22': [self.row_list[result.row:], self.col_list[result.col:]]}
result.row_list = dic[block][0]
result.col_list = dic[block][1]
return result
a = [[1, 4, 8, 7], [5, 7, 9, 13], [3, 6, 8, 11], [-1, -3, 5, 3]]
b = [[4, 8, -12, 5], [2, 1, 9, 4], [12, 45, -21, 5], [5, -1, 4, 7]]
c = matrixproduct(a, b)
print(c)
# sort in place and storage efficient
# coding: utf-8
def partition(sort_list: list, left: int, right: int):
pivot = sort_list[right]
# choose the right number as the pivot
i = left
for j in range(left, right + 1):
if sort_list[j] <= pivot:
sort_list[i], sort_list[j] = sort_list[j], sort_list[i]
i += 1
return i - 1
# return the index of pivot
def quick_sort(sort_list: list, left: int = None, right: int = None) -> object:
left = 0 if isinstance(left, (int, float)) == 0 else left
right = len(sort_list) - 1 if isinstance(right, (int, float)) == 0 else right
# these if-else sentences simplify the input of function
if left < right: # important judgement
x = partition(sort_list, left, right)
quick_sort(sort_list, left, x - 1)
quick_sort(sort_list, x + 1, right)
return sort_list
s_list = [1, 2, 0, 10, 14, 12, 3, 5, 4, 9, 6, 8, 7, 11, 13]
sorted_list = quick_sort(s_list)
print(sorted_list)
网友评论