我正在通过Coursera学习Algorithms, Part I,并希望测试Quick Find、Quick Union和Weighted Quick Union算法的运行时间。该课程使用Java语言,而我不熟悉Java,因此我已经尝试用我更熟悉的Python重新编写了这些算法。
现在,我计划测试每个函数以验证其运行时间/复杂度。我一直在考虑使用timeit库,但似乎会产生错误的结果,例如,Weighted Quick Union所需的时间比QuickUnion还长。
我该如何验证Weighted Quick Union确实是O(log n),并且比Quick Union更快呢?以下是我迄今为止创建和尝试过的内容:
O(N**2) - 慢
class QuickFind_Eager:
def __init__(self, nodes):
self.array = [num for num in range(nodes)]
# Joins two nodes into a component
def union(self, first_node, second_node):
for pos, val in enumerate(self.array):
if self.array[pos] == self.array[first_node]:
self.array[pos] = self.array[second_node]
# Checks if two nodes are in the same component
def connected(self, first_node, second_node):
return self.array[first_node] == self.array[second_node]
O(N) - 仍然太慢 - 避免使用
class QuickUnion_Lazy:
def __init__(self, nodes):
self.array = [num for num in range(nodes)]
# Follows parent pointers to actual root
def root(self, parent):
while parent != self.array[parent]:
parent = self.array[parent]
return parent
# Joins two nodes into a component
def union(self, first_node, second_node):
self.array[first_node] = self.array[second_node]
# Checks if two nodes are in the same component
def connected(self, first_node, second_node):
return self.root(first_node) == self.root(second_node)
O(log N) - 相当快
class WeightedQuickUnion:
def __init__(self, nodes):
self.array = [num for num in range(nodes)]
self.weight = [num for num in range(nodes)]
# Follows parent pointers to actual root
def root(self, parent):
while parent != self.array[parent]:
parent = self.array[parent]
return parent
# Joins two nodes into a component
def union(self, first_node, second_node):
if self.root(first_node) == self.root(second_node):
return
if (self.weight[first_node] < self.weight[second_node]):
self.array[first_node] = self.root(second_node)
self.weight[second_node] += self.weight[first_node]
else:
self.array[second_node] = self.root(first_node)
self.weight[first_node] += self.weight[second_node]
# Checks if two nodes are in the same component
def connected(self, first_node, second_node):
return self.root(first_node) == self.root(second_node)
O(N + M lg* N) - 非常快
class WeightedQuickUnion_PathCompression:
def __init__(self, nodes):
self.array = [num for num in range(nodes)]
self.weight = [num for num in range(nodes)]
# Follows parent pointers to actual root
def root(self, parent):
while parent != self.array[parent]:
self.array[parent] = self.array[self.array[parent]]
parent = self.array[parent]
return parent
# Joins two nodes into a component
def union(self, first_node, second_node):
if self.root(first_node) == self.root(second_node):
return
if self.weight[first_node] < self.weight[second_node]:
self.array[first_node] = self.root(second_node)
self.weight[second_node] += self.weight[first_node]
else:
self.array[second_node] = self.root(first_node)
self.weight[first_node] += self.weight[second_node]
# Checks if two nodes are in the same component
def connected(self, first_node, second_node):
return self.root(first_node) == self.root(second_node)
测试运行时间
def test_quickfind(quickfind):
t = quickfind(100)
t.union(1,2)
t.connected(1,2)
t.union(4,2)
t.union(3,4)
t.connected(0,2)
t.connected(1,4)
t.union(0,3)
t.connected(0,4)
import timeit
t = timeit.timeit(stmt="test_quickfind(QuickFind_Eager)", setup="from __main__ import QuickFind_Eager; from __main__ import test_quickfind", number=100000)
print(t)
# 11.4380569069981
t = timeit.timeit(stmt="test_quickfind(QuickUnion_Lazy)", setup="from __main__ import QuickUnion_Lazy; from __main__ import test_quickfind", number=100000)
print(t)
# 1.4744456350017572
t = timeit.timeit(stmt="test_quickfind(WeightedQuickUnion)", setup="from __main__ import WeightedQuickUnion; from __main__ import test_quickfind", number=100000)
print(t)
# 2.738758583996969
t = timeit.timeit(stmt="test_quickfind(WeightedQuickUnion_PathCompression)", setup="from __main__ import WeightedQuickUnion_PathCompression; from __main__ import test_quickfind", number=100000)
print(t)
# 3.0113827050008695
更新 添加了来自timeit的结果。
timeit
性能分析方法有什么问题? - Cory Kramer