排序算法可视化:如何从紧密循环中提取值以动画 canvas
Sort Algorithm Visualization: How to pull values to animate the canvas, from inside a tight loop
我正在使用 tkinter 使用不同条形的高度来可视化不同的排序算法。我已经能够洗牌,并在一些帮助后对它们进行排序。我现在遇到的问题是减慢条形的排序速度,以便可以看到每种算法的工作原理。
这是我目前所拥有的:
import tkinter as tk
import random
def swap_two_pos(pos_0, pos_1):
Bar1x1, _, Bar1x2, _ = canvas.coords(pos_0)
Bar2x1, _, Bar2x2, _ = canvas.coords(pos_1)
canvas.move(pos_0, Bar2x1-Bar1x1, 0)
canvas.move(pos_1, Bar1x2-Bar2x2, 0)
def insertion_sort():
global barList
global lengthList
for i in range(len(lengthList)):
cursor = lengthList[i]
cursorBar = barList[i]
pos = i
while pos > 0 and lengthList[pos - 1] > cursor:
lengthList[pos] = lengthList[pos - 1]
barList[pos], barList[pos - 1] = barList[pos - 1], barList[pos]
canvas.after(1000,swap_two_pos(barList[pos],barList[pos-1]))
pos -= 1
lengthList[pos] = cursor
barList[pos] = cursorBar
swap_two_pos(barList[pos],cursorBar)
def shuffle():
global barList
global lengthList
canvas.delete('all')
xstart = 5
xend = 15
barList = []
lengthList = []
for x in range(1,60):
randomY = random.randint(1,390)
x = canvas.create_rectangle(xstart,randomY,xend,395, fill='red')
barList.append(x)
xstart += 10
xend += 10
for bar in barList:
x = canvas.coords(bar)
length = x[3]-x[1]
lengthList.append(length)
for i in range(len(lengthList)-1):
if lengthList[i] == min(lengthList):
canvas.itemconfig(barList[i], fill='blue')
elif lengthList[i] == max(lengthList):
canvas.itemconfig(barList[i], fill='green')
window = tk.Tk()
window.title('Sorting')
window.geometry('600x435')
canvas = tk.Canvas(window, width='600', height='400')
canvas.grid(column=0,row=0, columnspan = 50)
insert = tk.Button(window, text='Insertion Sort', command=insertion_sort)
shuf = tk.Button(window, text='Shuffle', command=shuffle)
insert.grid(column=1,row=1)
shuf.grid(column=0, row=1)
shuffle()
window.mainloop()
如您所见,我尝试在插入排序函数中使用 after()
方法,但它所做的只是冻结 window 并使其不响应。没有那个方法,它工作得很好,只是没有按照可以看到的速度进行。
耗时的函数是 "swap_two_pos()" 这是灾难性的,你 运行 它每个循环,你应该做的是完成排序然后重新绘制条形图,
下面是您修改后的代码,在没有 GUI 冻结的情况下工作,添加了一个函数并删除了 "swap_two_pos()" func.
import tkinter as tk
import random
def insertion_sort():
global barList
global lengthList
for i in range(len(lengthList)):
cursor = lengthList[i]
cursorBar = barList[i]
pos = i
while pos > 0 and lengthList[pos - 1] > cursor:
lengthList[pos] = lengthList[pos - 1]
barList[pos], barList[pos - 1] = barList[pos - 1], barList[pos]
# canvas.after(1000,swap_two_pos(barList[pos],barList[pos-1]))
pos -= 1
lengthList[pos] = cursor
barList[pos] = cursorBar
refresh()
# swap_two_pos(barList[pos],cursorBar)
def refresh():
canvas.delete('all')
xstart = 5
xend = 15
for i, length in enumerate(lengthList): #range(1,60):
y = random.randint(1,390)
x = canvas.create_rectangle(xstart,length,xend,395, fill='red')
barList.append(x)
xstart += 10
xend += 10
def shuffle():
global barList
global lengthList
canvas.delete('all')
xstart = 5
xend = 15
barList = []
lengthList = []
for x in range(1,60):
randomY = random.randint(1,390)
x = canvas.create_rectangle(xstart,randomY,xend,395, fill='red')
barList.append(x)
xstart += 10
xend += 10
for bar in barList:
x = canvas.coords(bar)
length = x[3]-x[1]
lengthList.append(length)
for i in range(len(lengthList)-1):
if lengthList[i] == min(lengthList):
canvas.itemconfig(barList[i], fill='blue')
elif lengthList[i] == max(lengthList):
canvas.itemconfig(barList[i], fill='green')
window = tk.Tk()
window.title('Sorting')
window.geometry('600x435')
canvas = tk.Canvas(window, width='600', height='400')
canvas.grid(column=0,row=0, columnspan = 50)
insert = tk.Button(window, text='Insertion Sort', command=insertion_sort)
shuf = tk.Button(window, text='Shuffle', command=shuffle)
insert.grid(column=1,row=1)
shuf.grid(column=0, row=1)
shuffle()
window.mainloop()
利用生成器函数(关键字yield
),你可以在循环中暂停代码的执行以花时间显示已更改的canvas元素,更新计算,等,然后在生成器上重复调用 next
恢复执行,直到完成排序。
我在代码中添加了一些注释,但最好的方法可能是盯着它看,直到您确信它可以正常工作。这是您需要了解的模式,因为它对于构建您想要的那种动画非常有用
建造。
import tkinter as tk
import random
def swap_two_pos(pos_0, pos_1):
Bar1x1, _, Bar1x2, _ = canvas.coords(pos_0)
Bar2x1, _, Bar2x2, _ = canvas.coords(pos_1)
canvas.move(pos_0, Bar2x1-Bar1x1, 0)
canvas.move(pos_1, Bar1x2-Bar2x2, 0)
def _insertion_sort():
global barList
global lengthList
for i in range(len(lengthList)):
cursor = lengthList[i]
cursorBar = barList[i]
pos = i
while pos > 0 and lengthList[pos - 1] > cursor:
lengthList[pos] = lengthList[pos - 1]
barList[pos], barList[pos - 1] = barList[pos - 1], barList[pos]
swap_two_pos(barList[pos],barList[pos-1]) # <-- updates the display
yield # <-- suspends the execution
pos -= 1 # <-- execution resumes here when next is called
lengthList[pos] = cursor
barList[pos] = cursorBar
swap_two_pos(barList[pos],cursorBar)
worker = None # <-- Not a thread in spite of the name.
def insertion_sort(): # <-- commands the start of both the animation, and the sort
global worker
worker = _insertion_sort()
animate()
def animate(): # <-- commands resuming the sort once the display has been updated
# controls the pace of the animation
global worker
if worker is not None:
try:
next(worker)
window.after(10, animate) # <-- repeats until the sort is complete,
except StopIteration: # when the generator is exhausted
worker = None
finally:
window.after_cancel(animate) # <-- stop the callbacks
def shuffle():
global barList
global lengthList
canvas.delete('all')
xstart = 5
xend = 15
barList = []
lengthList = []
for x in range(1, 60):
randomY = random.randint(1, 390)
x = canvas.create_rectangle(xstart, randomY, xend, 395, fill='red')
barList.append(x)
xstart += 10
xend += 10
for bar in barList:
x = canvas.coords(bar)
length = x[3] - x[1]
lengthList.append(length)
for i in range(len(lengthList)-1):
if lengthList[i] == min(lengthList):
canvas.itemconfig(barList[i], fill='blue')
elif lengthList[i] == max(lengthList):
canvas.itemconfig(barList[i], fill='green')
window = tk.Tk()
window.title('Sorting')
window.geometry('600x435')
canvas = tk.Canvas(window, width='600', height='400')
canvas.grid(column=0,row=0, columnspan = 50)
insert = tk.Button(window, text='Insertion Sort', command=insertion_sort)
shuf = tk.Button(window, text='Shuffle', command=shuffle)
insert.grid(column=1,row=1)
shuf.grid(column=0, row=1)
shuffle()
window.mainloop()
我正在使用 tkinter 使用不同条形的高度来可视化不同的排序算法。我已经能够洗牌,并在一些帮助后对它们进行排序。我现在遇到的问题是减慢条形的排序速度,以便可以看到每种算法的工作原理。 这是我目前所拥有的:
import tkinter as tk
import random
def swap_two_pos(pos_0, pos_1):
Bar1x1, _, Bar1x2, _ = canvas.coords(pos_0)
Bar2x1, _, Bar2x2, _ = canvas.coords(pos_1)
canvas.move(pos_0, Bar2x1-Bar1x1, 0)
canvas.move(pos_1, Bar1x2-Bar2x2, 0)
def insertion_sort():
global barList
global lengthList
for i in range(len(lengthList)):
cursor = lengthList[i]
cursorBar = barList[i]
pos = i
while pos > 0 and lengthList[pos - 1] > cursor:
lengthList[pos] = lengthList[pos - 1]
barList[pos], barList[pos - 1] = barList[pos - 1], barList[pos]
canvas.after(1000,swap_two_pos(barList[pos],barList[pos-1]))
pos -= 1
lengthList[pos] = cursor
barList[pos] = cursorBar
swap_two_pos(barList[pos],cursorBar)
def shuffle():
global barList
global lengthList
canvas.delete('all')
xstart = 5
xend = 15
barList = []
lengthList = []
for x in range(1,60):
randomY = random.randint(1,390)
x = canvas.create_rectangle(xstart,randomY,xend,395, fill='red')
barList.append(x)
xstart += 10
xend += 10
for bar in barList:
x = canvas.coords(bar)
length = x[3]-x[1]
lengthList.append(length)
for i in range(len(lengthList)-1):
if lengthList[i] == min(lengthList):
canvas.itemconfig(barList[i], fill='blue')
elif lengthList[i] == max(lengthList):
canvas.itemconfig(barList[i], fill='green')
window = tk.Tk()
window.title('Sorting')
window.geometry('600x435')
canvas = tk.Canvas(window, width='600', height='400')
canvas.grid(column=0,row=0, columnspan = 50)
insert = tk.Button(window, text='Insertion Sort', command=insertion_sort)
shuf = tk.Button(window, text='Shuffle', command=shuffle)
insert.grid(column=1,row=1)
shuf.grid(column=0, row=1)
shuffle()
window.mainloop()
如您所见,我尝试在插入排序函数中使用 after()
方法,但它所做的只是冻结 window 并使其不响应。没有那个方法,它工作得很好,只是没有按照可以看到的速度进行。
耗时的函数是 "swap_two_pos()" 这是灾难性的,你 运行 它每个循环,你应该做的是完成排序然后重新绘制条形图, 下面是您修改后的代码,在没有 GUI 冻结的情况下工作,添加了一个函数并删除了 "swap_two_pos()" func.
import tkinter as tk
import random
def insertion_sort():
global barList
global lengthList
for i in range(len(lengthList)):
cursor = lengthList[i]
cursorBar = barList[i]
pos = i
while pos > 0 and lengthList[pos - 1] > cursor:
lengthList[pos] = lengthList[pos - 1]
barList[pos], barList[pos - 1] = barList[pos - 1], barList[pos]
# canvas.after(1000,swap_two_pos(barList[pos],barList[pos-1]))
pos -= 1
lengthList[pos] = cursor
barList[pos] = cursorBar
refresh()
# swap_two_pos(barList[pos],cursorBar)
def refresh():
canvas.delete('all')
xstart = 5
xend = 15
for i, length in enumerate(lengthList): #range(1,60):
y = random.randint(1,390)
x = canvas.create_rectangle(xstart,length,xend,395, fill='red')
barList.append(x)
xstart += 10
xend += 10
def shuffle():
global barList
global lengthList
canvas.delete('all')
xstart = 5
xend = 15
barList = []
lengthList = []
for x in range(1,60):
randomY = random.randint(1,390)
x = canvas.create_rectangle(xstart,randomY,xend,395, fill='red')
barList.append(x)
xstart += 10
xend += 10
for bar in barList:
x = canvas.coords(bar)
length = x[3]-x[1]
lengthList.append(length)
for i in range(len(lengthList)-1):
if lengthList[i] == min(lengthList):
canvas.itemconfig(barList[i], fill='blue')
elif lengthList[i] == max(lengthList):
canvas.itemconfig(barList[i], fill='green')
window = tk.Tk()
window.title('Sorting')
window.geometry('600x435')
canvas = tk.Canvas(window, width='600', height='400')
canvas.grid(column=0,row=0, columnspan = 50)
insert = tk.Button(window, text='Insertion Sort', command=insertion_sort)
shuf = tk.Button(window, text='Shuffle', command=shuffle)
insert.grid(column=1,row=1)
shuf.grid(column=0, row=1)
shuffle()
window.mainloop()
利用生成器函数(关键字yield
),你可以在循环中暂停代码的执行以花时间显示已更改的canvas元素,更新计算,等,然后在生成器上重复调用 next
恢复执行,直到完成排序。
我在代码中添加了一些注释,但最好的方法可能是盯着它看,直到您确信它可以正常工作。这是您需要了解的模式,因为它对于构建您想要的那种动画非常有用 建造。
import tkinter as tk
import random
def swap_two_pos(pos_0, pos_1):
Bar1x1, _, Bar1x2, _ = canvas.coords(pos_0)
Bar2x1, _, Bar2x2, _ = canvas.coords(pos_1)
canvas.move(pos_0, Bar2x1-Bar1x1, 0)
canvas.move(pos_1, Bar1x2-Bar2x2, 0)
def _insertion_sort():
global barList
global lengthList
for i in range(len(lengthList)):
cursor = lengthList[i]
cursorBar = barList[i]
pos = i
while pos > 0 and lengthList[pos - 1] > cursor:
lengthList[pos] = lengthList[pos - 1]
barList[pos], barList[pos - 1] = barList[pos - 1], barList[pos]
swap_two_pos(barList[pos],barList[pos-1]) # <-- updates the display
yield # <-- suspends the execution
pos -= 1 # <-- execution resumes here when next is called
lengthList[pos] = cursor
barList[pos] = cursorBar
swap_two_pos(barList[pos],cursorBar)
worker = None # <-- Not a thread in spite of the name.
def insertion_sort(): # <-- commands the start of both the animation, and the sort
global worker
worker = _insertion_sort()
animate()
def animate(): # <-- commands resuming the sort once the display has been updated
# controls the pace of the animation
global worker
if worker is not None:
try:
next(worker)
window.after(10, animate) # <-- repeats until the sort is complete,
except StopIteration: # when the generator is exhausted
worker = None
finally:
window.after_cancel(animate) # <-- stop the callbacks
def shuffle():
global barList
global lengthList
canvas.delete('all')
xstart = 5
xend = 15
barList = []
lengthList = []
for x in range(1, 60):
randomY = random.randint(1, 390)
x = canvas.create_rectangle(xstart, randomY, xend, 395, fill='red')
barList.append(x)
xstart += 10
xend += 10
for bar in barList:
x = canvas.coords(bar)
length = x[3] - x[1]
lengthList.append(length)
for i in range(len(lengthList)-1):
if lengthList[i] == min(lengthList):
canvas.itemconfig(barList[i], fill='blue')
elif lengthList[i] == max(lengthList):
canvas.itemconfig(barList[i], fill='green')
window = tk.Tk()
window.title('Sorting')
window.geometry('600x435')
canvas = tk.Canvas(window, width='600', height='400')
canvas.grid(column=0,row=0, columnspan = 50)
insert = tk.Button(window, text='Insertion Sort', command=insertion_sort)
shuf = tk.Button(window, text='Shuffle', command=shuffle)
insert.grid(column=1,row=1)
shuf.grid(column=0, row=1)
shuffle()
window.mainloop()