WARNING: This article may be obsoleteThis post was published in 2021-10-15. Obviously, expired content is less useful to users if it has already pasted its expiration date.
This article is categorized as "Garbage" . It should NEVER be appeared in your search engine's results.Table of Contents
博客VPS操作系统变更实验
有关我部署本博客的VPS：
3天前由于一时手贱，我不慎删掉了centos系统里的 site-packages 文件夹，后来干脆决定重装系统，试试其他的发行版。我决定使用 debian 11 作为新的OS，但却遇到了最为麻烦的事情：明明我的软件版本、各项设置都和之前的centos一致，但我的 平均页面生成时间 莫名其妙变高了：之前好不容易降到 0.21~0.22(s) ，现在却变成了 0.25~0.28(s) ，多次重装系统、重新编译都没有改善。最终我换回了centos，（尽管还是用相同的配置文件）指标又重新回到了之前的 0.21~0.22(s) 水平。
原因还没有搞明白，但不想再搞多次试验了（重装系统+重新编译等步骤通常要好几个小时），先这样吧==
有关Disk I/O, Disk read/write
有关Disk I/O, Disk read/write：
长期以来我一直都潜意识里把disk I/O和read/write的对应关系搞反了（知道最近安装netdata以后才意识到这个问题）。
python初始化数组的方法比较
python 初始化数组
❗ 一定要注意不要用错了，见：🔗 [Python initializing a list of lists – Stack Overflow] https://stackoverflow.com/questions/12791501/python-initializing-a-list-of-lists
A = [0] * 100A = [0 for i in range(0, 100)]A = [i*2 for i in range(0, 10)]python版的计数排序/counting sort
Python: counting sort/计数排序
计数排序对输入的数据是有限制的：【计数排序假设n个输入元素中的每一个都是介于0到k的整数（k为整数）】.
详情见中文算法导论p98
时间复杂度：[mathjax]O(N+K)[/mathjax]，其中K=max(intput)-min(input).
❌ version 1：
A = [5, 4, 2, 3, 7, 13, 6, 8, 0, 1]
C = [0] * (int(max(A)) + 1)
O = []
for item in A:
C[item] += 1
for i in range(0, len(C)):
if C[i] != 0:
for j in range(0, C[i]):
O.append(i)
print(O)
version 2 (尽量接近算法导论的解法步骤)：
def counting_sort(A, B, k):
C = [0] * (k + 1)
for j in range(0, len(A)):
C[A[j]] += 1
for i in range(1, k + 1):
C[i] = C[i] + C[i - 1]
for j in range(len(A) - 1, -1, -1):
B[C[A[j]] - 1] = A[j]
C[A[j]] -= 1
return B
if __name__ == '__main__':
A = [2, 5, 3, 0, 2, 3, 0, 3]
B = [0] * len(A)
k = max(A)
print(counting_sort(A, B, k))
python版的插入排序/insertion sort
Python: insertion sort/插入排序
A = [2, 5, 4, 6, 3, 1, 10, 2, 6, 4]
for i in range(1, len(A)):
key = A[i]
j = i - 1
while (j >= 0 and A[j] > key):
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
print(A)python版的桶排序/bucket sort
python bucket sort/桶排序
见中文算法导论p102，桶排序对输入的数据也有一定要求：假设输入（的数据）由一个随机过程产生，该过程将元素均匀地分布在区间[mathjax][0, 1)[/mathjax]上.
其他延伸用法讨论：🔗 [Microsoft PowerPoint - sort2] https://courses.cs.washington.edu/courses/cse373/03au/lectures/sort2.pdf
容易出错的地方：🔗 [Python initializing a list of lists - Stack Overflow] https://stackoverflow.com/questions/12791501/python-initializing-a-list-of-lists
（默认搭配insertion sort）
def insertion_sort(A):
for i in range(1, len(A)):
key = A[i]
j = i - 1
while (j >= 0 and A[j] > key):
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
return A
if __name__ == '__main__':
A = [0.2, 0.5, 0.4, 0.15, 0.78, 0.1, 0.03, 0.9]
B = []
for i in range(len(A)):
B.append([])
C = []
for i in range(0, len(A)):
B[int(A[i] * len(A))].append(A[i])
for i in range(0, len(B)):
B[i] = insertion_sort(B[i])
for j in B[i]:
C.append(j)
print(C)
python版的堆排序/heap sort（代码不是最优）
python heap sort/堆排序
❗注意！这段代码没有做到就地排序，使用了额外空间，这是对max heap性质不熟练导致的。更新代码和分析见：🔗 [2021-10-18 - Truxton's blog] https://truxton2blog.com/2021-10-18/
import random
def max_heapify(arr, i):
left = 2 * i + 1
right = 2 * i + 2
if left < len(arr) and arr[left] > arr[i]:
largest = left
else:
largest = i
if right < len(arr) and arr[right] > arr[largest]:
largest = right
if largest != i:
temp = arr[largest]
arr[largest] = arr[i]
arr[i] = temp
max_heapify(arr, largest)
else:
return arr
def build_max_heap(arr):
for i in range(len(arr) // 2 - 1, -1, -1):
max_heapify(arr, i)
return arr
def heap_sort(arr):
arr = build_max_heap(arr)
sorted = []
for i in range(len(arr) - 1, -1, -1):
temp = arr[i]
arr[i] = arr[0]
arr[0] = temp
sorted = [arr.pop()] + sorted
max_heapify(arr, 0)
return sorted
if __name__ == '__main__':
A = []
for i in range(0, 15):
A.append(random.randint(0, 50))
print(A)
C = heap_sort(A)
print(C)
