Помогите выяснить почему программа бесконечно выполняется
У меня есть 2 файла. В одном ("sorts.py") содержатся методы сортировки списков:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
return arr
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
less = [i for i in arr if i < pivot]
equal = [i for i in arr if i == pivot]
greater = [i for i in arr if i > pivot]
return quicksort(less) + equal + quicksort(greater)
def check_sorted(arr):
for i in range(len(arr) - 1):
if arr[i] > arr[i+1]:
return False
return True
В другом ("main.py") подключается модуль sorts.py и сортируется 3 последовательности: отсортированная, случайно сгенерированная и отсортированная в обратном порядке, тремя методами, указанными выше, а после подсчитывается время сортировки. Данные выводятся в отдельный текстовый файл.
import random
import time
import sorts
def measure_time(func, arr):
start_time = time.perf_counter()
func(arr)
end_time = time.perf_counter()
return end_time - start_time
def generate_sequences(n):
sorted_seq = list(range(n))
reversed_seq = list(range(n - 1, -1, -1))
random_seq = random.sample(range(n), n)
return sorted_seq, reversed_seq, random_seq
def main():
ns = [10, 20, 50000, 100000]
results = []
headers = ["N", "Тип последовательности", "Метод сортировки", "Время выполнения (сек)"]
for n in ns:
sorted_seq, reversed_seq, random_seq = generate_sequences(n)
sequences = {"Отсортированная": sorted_seq, "Обратно отсортированная": reversed_seq, "Случайная": random_seq}
# Убираем встроенную сортировку
sort_methods = {
"Пузырьковая сортировка": sorts.bubble_sort,
"Сортировка Шелла": sorts.shell_sort,
"Быстрая сортировка": sorts.quicksort,
}
for seq_name, original_seq in sequences.items():
for method_name, method in sort_methods.items():
seq_copy = original_seq[:]
time_taken = measure_time(method, seq_copy)
results.append([n, seq_name, method_name, time_taken])
with open("output.txt", "w", encoding="utf-8") as f:
f.write("".join(header.ljust(25) for header in headers) + "\n")
for row in results:
f.write("".join(str(item).ljust(25) for item in row) + "\n")
print("Результаты сохранены в файл output.txt")
if __name__ == "__main__":
main()
Проблема в том, что при списках небольшой длины всё выполняется успешно, но когда длина списка, например, 50000 или 100000, то она начинает выполнятся бесконечно. Что можно с этим сделать?
Ответы (3 шт):
Дело в том, что пузырьковая сортировка (как и выбором, и вставками, и некоторые другие) имеет квадратичную сложность, т.е. её время выполнения зависит от количества элементов как O(n^2).
Так что для списка длиной 100000 будет выполнено порядка 10^10 операций, что на Python займёт часы или сутки. Практическое применение эти сортировки могут иметь только для малых наборов данных, и сравнение времен стоит проводить, скажем, только до нескольких тысяч элементов.
Другое дело - быстрая сортировка, со временем выполнения порядка O(n*logn), для ваших размеров она будет проходить за секунды (а на компилируемом языке - за миллисекунды)
Вы запускаете сложную программу и гадаете, она повисла из-за ошибки или просто работает долго? Ситуацию портит то, что надо дождаться всех результатов, чтобы разобраться. Упростим всё до предела: одна сортировка, один тест, возможность управлять программой извне.
import random
import time
def measure_time(func, arr):
start_time = time.perf_counter()
func(arr)
end_time = time.perf_counter()
return end_time - start_time
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
def main():
n = int(input())
seq = random.sample(range(n), n)
time_taken = measure_time(bubble_sort, seq)
print(n, time_taken)
main()
Запускаю программу с растущим размером входа:
$ echo 10 | python temp.py 10 2.6152003556489944e-05 $ echo 100 | python temp.py 100 0.0006155550945550203 $ echo 1000 | python temp.py 1000 0.07188936602324247 $ echo 10000 | python temp.py 10000 8.005143661051989
Последний запуск занял восемь секунд. Прогоняю программу на входах, которые отличаются в два раза и так чтобы время работы измерялось в единицах секунд:
$ echo 1000 | python temp.py 1000 0.0722273220308125 $ echo 2000 | python temp.py 2000 0.29628414497710764 $ echo 4000 | python temp.py 4000 1.197030601091683 $ echo 8000 | python temp.py 8000 4.899013999849558
Увеличение размера входа в два раза приводит к увеличению времени работы примерно в четыре раза (нужен навык устного счёта или калькулятор). Так ведут себя программы с квадратичной сложностью.
В предположении квадратичного поведения делаем экстраполяцию. Запускать программу не надо, это просто арифметика, времена вычисляются:
| n | t – время работы |
|---|---|
| 8000 | 5с |
| 16000 | ≈ 20с |
| 32000 | ≈ 80с |
| 64000 | ≈ 320с ≈ 5 минут |
| 128000 | ≈ 1280с ≈ 21 минута |
Всё очень грубо, но особая точность тут не нужна. Сто тысяч элементов будут сортироваться от пяти до двадцати минут. Теперь вы знаете сколько вам нужно ждать чтобы собрать статистику. И у вас есть инструмент чтобы понять какую статистику можно собрать в разумное время, скажем в течении одной минуты.
Похожие тесты имеет смысл повторить для других сортировок и других данных. Затем можно отрегулировать размеры массивов в вашей основной программе и собрать данные по времени работы.
Если переписать функцию пузырьковой сортировки на отдельные переменные, то можно сократить время работы примерно в 2 раза
def bubble_sort2(arr):
n = len(arr)
newarr = [0] * n
maxi = 0
idx = 0
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
maxi = arr[j]
idx = j
newarr[idx] = maxi
return newarr
Правда, учитывая ответы Stanislav Volodarskiy и MBo вам это врят ли поможет