Почему мой алгоритм сортировки с массивом numpy работает медленнее, чем со списками?

Я пытался отсортировать список с помощью последовательной битонной сортировки и хотел сделать это быстрее, отсортировав массив 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)

Что я пропустил?

Почему вы ожидали, что он станет быстрее?

Kelly Bundy 17.04.2023 15:15

Я читал, что np.array работает быстрее, чем списки

Diana 17.04.2023 15:18

ваш алгоритм не использует никаких функций numpy, поэтому он обрабатывает любой массив numpy как список. Разница во времени между двумя прогонами должна быть небольшой.

Quang Hoang 17.04.2023 15:28

Нет, это как в два раза меньше, чем со списком

Diana 17.04.2023 15:30
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
2
4
64
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы ошиблись. На самом деле 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, модифицированную версию сортировки слиянием. Тем не менее, разница в производительности все равно будет существенной.

Другие вопросы по теме