Я пытался отсортировать список с помощью последовательной битонной сортировки и хотел сделать это быстрее, отсортировав массив numpy вместо списка, но он стал только медленнее. Что я сделал не так?
Вот алгоритм сортировки:
from datetime import datetime
import numpy as np
def compAndSwap(a, i, j, dire):
if (dire == 1 and a[i] > a[j]) or (dire == 0 and a[i] < a[j]):
a[i], a[j] = a[j], a[i]
def bitonicMerge(a, low, cnt, dire):
if cnt > 1:
k = cnt // 2
for i in range(low, low + k):
compAndSwap(a, i, i + k, dire)
bitonicMerge(a, low, k, dire)
bitonicMerge(a, low + k, k, dire)
def bitonicSort(a, low, cnt, dire):
if cnt > 1:
k = cnt // 2
bitonicSort(a, low, k, 1)
bitonicSort(a, low + k, k, 0)
bitonicMerge(a, low, cnt, dire)
def sort_(a, N, up):
bitonicSort(a, 0, N, up)
И вот часть при запуске этого алгоритма для списка:
with open('data.txt') as f:
line = f.readline()
a = line[1:-2].split(', ')
a = list(map(int, a))
n = len(a)
up = 1
time1 = datetime.now()
sort_(a, n, up)
time2 = datetime.now()
print("\nCurrent Time = ", time2-time1)
А вот для массива numpy:
with open('data.txt') as f:
line = f.readline()
a = np.array(line[1:-2].split(', ')).astype('int32')
n = a.size
up = 1
time1 = datetime.now()
sort_(a, n, up)
time2 = datetime.now()
print("\nCurrent Time = ", time2-time1)
Что я пропустил?
Я читал, что np.array работает быстрее, чем списки
ваш алгоритм не использует никаких функций numpy, поэтому он обрабатывает любой массив numpy как список. Разница во времени между двумя прогонами должна быть небольшой.
Нет, это как в два раза меньше, чем со списком
Вы ошиблись. На самом деле Numpy — это пакет научных вычислений, который лучше всего подходит для выполнения векторных операций, таких как умножение массивов. Он не оптимизирован для доступа к отдельным элементам массива по одному.
Если вы попробуете этот простой тест:
data = np.random.randint(0, 10000, 1000000)
a = data.tolist()
затем измерьте время выполнения простого цикла без каких-либо дополнительных операций:
%timeit for i in range(data.shape[0]): _ = data[i] # 145 ms ± 50.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Сделайте то же самое для списка:
%timeit for i in range(len(a)): _ = a[i] # 85.1 ms ± 28.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Вы заметили, что доступ к элементу в массиве numpy занимает больше времени.
Однако использование предварительно оптимизированных функций из библиотеки numpy может привести к значительной разнице в производительности.
%timeit np.sort(data, kind='mergesort') # 100 ms ± 11.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
а если вы использовали sorted
в списке
%timeit sorted(a) # 449 ms ± 69.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Это сравнение не будет точным, поскольку sorted
использует timsort, модифицированную версию сортировки слиянием. Тем не менее, разница в производительности все равно будет существенной.
Почему вы ожидали, что он станет быстрее?