Советы по сортировке для специалистов по данным

оригинальное название | Surprising Sorting Tips for Data Scientists

автор | Jeff Hale

оригинальный | к data science.com/surprising-…

переводчик| kbsc13 (автор публичного аккаунта «The Growth of Algorithm Apes»)

утверждение| Перевод предназначен для общения и обучения, добро пожаловать на перепечатку, но, пожалуйста, сохраните эту статью для коммерческих или незаконных целей.

Управляемое чтение

В этом посте представлены методы сортировки для нескольких часто используемых библиотек в Python, в том числеРодной Python, Numpy, Pandas, PyTorch, TensorFlow и SQL.

предисловие

Сейчас на самом деле существует множество базовых алгоритмов сортировки, некоторые из них быстрые и требуют очень мало памяти, некоторые больше подходят для данных с большим объемом данных, а некоторые подходят для конкретных отсортированных данных, в следующей таблице приведены временная и пространственная сложность наиболее часто используемых алгоритмов сортировки:

Для большинства задач по науке о данных не обязательно хорошо разбираться в базовой реализации всех алгоритмов сортировки. На самом деле преждевременная оптимизация иногда считается корнем всех ошибок. Однако очень полезно знать, какую библиотеку и по каким параметрам нужно использовать для сортировки, вот шпаргалка, которую я сделал:

Далее мы представим методы сортировки вышеперечисленных библиотек, но в первую очередь представим версии этих библиотек, используемые в этой статье, потому что методы сортировки разных версий могут немного отличаться:

python 3.6.8
numpy 1.16.4
pandas 0.24.2
tensorflow==2.0.0-beta1  #tensorflow-gpu==2.0.0-beta1 slows sorting
pytorch 1.1

Python

Python включает два встроенных метода сортировки:

my_list.sort()изменит порядок сортировки самого списка, он должен вернуть значениеNone
sorted(my_list)Копирует список и сортирует его, не изменяет значение исходного списка и возвращает отсортированный список.

sortЭтот метод является более быстрым из двух, потому что это отношение изменяет сам список. Но такая операция очень опасна, потому что она изменит исходные данные.

Сортировка по умолчанию для обоих методов сортировки:по возрастанию--От мала до велика. Большинство методов сортировки могут принимать параметр для изменения сортировки в порядке убывания, но, к сожалению, имя этого параметра отличается для каждой библиотеки.

В python это имя параметраreverse, если установленоreverse=TrueУказывает, что используется метод сортировки по убыванию -- от наибольшего к наименьшему.

keyЭто также имя параметра, которое можно использовать для создания собственных критериев сортировки, таких какsort(key=len)Указывает на сортировку по длине элементов.

Единственный алгоритм сортировки в питонеTimsort.TimsortОн является производным от сортировки слиянием и сортировки вставками, которые выбирают метод сортировки в соответствии с характеристиками данных, которые необходимо отсортировать. Например, если вам нужно отсортировать краткий список, выберите метод сортировки вставками. точнееTimsortДля реализации см. статью Брэндона Скерритта:

Глубоко и день за днём.блог/Тим Сорт - Он и…

Timsortявляется стабильным алгоритмом сортировки, что означает, что для элементов с одинаковым значением исходный порядок будет сохраняться до и после сортировки.

заsort()иsorted()Память двух способов, тут маленькая хитрость, т.к.sorted()является более длинным словом, поэтому оно выполняется дольше, потому что необходимо выполнить операцию копирования.

Numpy

NumpyЭто базовая библиотека Python для научных вычислений, которая также имеет два метода сортировки: один для изменения самого массива, а другой для копирования:

my_array.sort()Измените сам массив, но верните отсортированный массив;
np.sort(my_array)Скопируйте массив и верните отсортированный массив без изменения исходного массива

Ниже приведены необязательные параметры для обоих методов:

axisЦелочисленный тип, указывающий, какое измерение выбрать для сортировки, значение по умолчанию равно -1, что указывает на то, что сортируется последнее измерение;
kindтип алгоритма сортировки, необязательный{quicksort’, ‘mergesort’, ‘heapsort’, ‘stable’}, алгоритм сортировки, по умолчанию используется быстрая сортировка --quicksort
orderКогда в массиве a определены поля, этот параметр может определять, с каким полем сравнивать.

Однако следует отметить, что использование этого алгоритма сортировки и ожидание этих имен параметров будут разными, например, передачаkind=quicksortФактически,introsortАлгоритм, вот объяснение документации numpy:

Когда прогресса недостаточно, он обращается к алгоритму сортировки кучей, который может сделать временную сложность быстрой сортировки в худшем случае O (n * log (n))

stableНаилучший устойчивый алгоритм сортировки выбирается автоматически в зависимости от типа сортируемых данных. И если вы выберетеmergesortпараметр, он будет использоваться в соответствии с типом данныхtimsortилиradix sort. Потому что соответствие API ограничивает выбор метода реализации, а также фиксирует метод упорядочения для разных типов данных.

Timsortиспользуется для отсортированных или почти отсортированных данных, а для случайно расположенных данных его эффект почти такой же, какmergesortТакой же. В настоящее время он используется как алгоритм сортировки, и если он не установленkindпараметр, выбор по умолчанию или быстрая сортировкаquicksort, в то время как для целочисленных типов данных «сортировка слиянием» и «стабильный» сопоставляются сradix sortметод

Приведенное выше объяснение из документации numpy с некоторыми изменениями от автора:

GitHub.com/num-py/num-py…

Среди описанных выше библиотек только numpy не имеет параметров, которые могут управлять методом сортировки, но умеет быстро реверсировать массив путем нарезки --my_arr[::-1].

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

Pandas

Pandasсредняя параDataFrameМетод сортировкиdf.sort_values(by=my_column), параметры:

by:strилиlist of str, необходимо указать. Сортировка по столбцу или столбцам. если параметрaxisравно 0 илиindex, то включается уровень индекса или метка столбца. еслиaxisравно 1 илиcolumns, то включается уровень столбца или метка индекса.
axis:{0 or index, 1 or columns}, по умолчанию0. отсортированная ось
ascending: boolилиlist of bool. По умолчаниюTrue. Метод сортировки, по возрастанию или по убыванию, можно указать несколько значений, но число должно совпадатьbyколичество параметров.
inplace:bool, по умолчаниюFalse. Если оно верно, то оно изменяет собственное значение, в противном случае — копирует;
kind:{quicksort, mergesort, heapsort, stable}, по умолчаниюquicksort. Выбор алгоритма сортировки. Подробности можно увидетьnumpyизndarray.np.sort. существуетpandasЭтот параметр будет использоваться только для одного ярлыка или столбца.
na_position:{'first', 'last'}. По умолчанию'last'. это указаноNaNместо на место,firstпоставить его в начале,lastПросто поставь в конце.

заSeriesПодобный же метод сортировки. ноSeriesне нужно указыватьbyпараметр, так как не будет нескольких столбцов.

Поскольку базовая реализация используетnumpy, так что вы также можете получить хорошие оптимизированные параметры сортировки, ноpandasЭто занимает немного дополнительного времени из-за его удобства.

Алгоритм сортировки по умолчанию для одного столбца — Numpy.quicksort, конечно, фактически вызываемый алгоритм сортировкиintrosort, потому что сортировка кучи будет медленнее. Для алгоритмов сортировки с несколькими столбцами Pandas гарантирует, что используется Numpy.mergesort, но на самом деле будет использоватьTimsortилиRadix sortалгоритм. Оба они являются стабильными алгоритмами сортировки, и стабильный алгоритм сортировки должен использоваться при сортировке нескольких столбцов.

Для Pandas необходимо помнить, что эти ключевые моменты:

Сортировка имен аспектов:sort_values()
Необходимо указать параметрыby=column_nameили список имен столбцов
Ключевые параметры в обратном порядке:ascending
стабильная сортировкаmergesortзначение параметра

При исследовании и анализе данных обычноDataFrameМетоды используются при суммировании и сортировке значенийSeries.value_counts(). Вот фрагмент кода для суммирования и сортировки наиболее часто встречающихся значений в каждом столбце:

for c in df.columns:
  print(f"---- {c} ----")
  print(df[c].value_counts().head())

Dask, основанная на Pandas библиотека для обработки больших данных, не реализовывала параллельную сортировку до осени 2019 года, хотя обсуждения начались. Об этой библиотеке, ее адрес на github:

github.com/dask/dask

Если это небольшой набор данных, использование Pandas для сортировки является хорошим выбором, но когда объем данных велик, если вы хотите выполнять параллельный поиск на графическом процессоре, вам необходимо использовать TensorFlow или PyTorch.

TensorFlow

TensorFlowВ настоящее время это самая популярная среда глубокого обучения.Здесь вы можете прочитать эту статью, которую я написал, сравнивая популярность и использование различных сред глубокого обучения:

к data science.com/what-deep-…

Следующие введения представляют собой все версии TensorFlow 2.0 для графических процессоров.

В TensorFlow метод сортировкиtf.sort(my_tensor), который возвращает отсортированную копию тензора. Необязательные параметры:

axis:{int, optional}, выберите измерение, в котором выполняется операция сортировки. Значение по умолчанию равно -1, что означает последнее измерение.
direction:{ascending or discending}. Восходящий или нисходящий.
name:{str, optional}. Имя для этой операции.

tf.sortиспользуетсяtop_kметод, в то время какtop_kБиблиотека CUB используется для упрощения распараллеливания операций на графических процессорах CUDA. Как говорится в официальной документации:

CUB предоставляет лучшие многоразовые программные компоненты для каждого уровня модели программирования CUDA.

Алгоритм сортировки TensorFlow реализован на GPU через библиотеку CUB.radix sort, подробности можно посмотреть по адресу:

GitHub.com/tensorflow/…

Информацию о графическом процессоре TensorFlow можно просмотреть:

www.tensorflow.org/install/gpu

Если вам нужно сделать GPU совместимым с версией 2.0, вам нужно использовать следующие команды установки:

!pip3 install tensorflow-gpu==2.0.0-beta1

Следующий код может проверить, выполняется ли каждая строка кода на GPU или CPU:

tf.debugging.set_log_device_placement(True)

Если вам нужно указать GPU, код выглядит следующим образом:

with tf.device('/GPU:0'):
  %time tf.sort(my_tf_tensor)

Если вы хотите использовать ЦП, вам нужно только изменить первую строку приведенного выше кода на:with tf.device('/CPU:0'), то есть заменить GPU на CPU.

tf.sort()Это очень простой способ запомнить, а другой — запомнить, что вам нужно изменить порядок сортировки, то есть изменить параметры.direction.

PyTorch

Метод сортировки PyTorch:torch.sort(my_tensor), который возвращает отсортированныйtensorкопия, необязательные параметры:

dim:{dim, optional}. Размер, по которому сортировать.
descending:{bool, optional}. Управляет порядком сортировки (по возрастанию или по убыванию)
out:{tuple, optional}.Tensor, LongTensorВыходной кортеж, который можно использовать в качестве выходного кеша.

Используйте следующий код, чтобы указать использование графического процессора:

gpu_tensor=my_pytorch_tensor.cuda()
%time torch.sort(gpu_tensor)

Когда PyTorch сталкивается с набором данных с объемом данных более 1 миллиона строк на 100 000 столбцов, он используетThrustРеализует параллельную сортировку сплитов.

Но, к сожалению, я получаю сообщение об ошибке нехватки памяти при попытке создать случайный набор данных размером 1,1 М * 100 КБ с помощью Numpy в Google Cola, а затем пытаюсь использовать 416 МБ GCP и получаю ту же ошибку нехватки памяти.

Thrust— это библиотека параллельных алгоритмов, которая обеспечивает перенос производительности между графическими процессорами и многоядерными графическими процессорами. Он может автоматически выбирать наиболее эффективную реализацию алгоритма сортировки. И только что представленный TensorFlow используетCUBбиблиотека праваThrustупаковка. Таким образом, и PyTorch, и TensorFlow используют аналогичные реализации алгоритмов сортировки.

Как и TensorFlow, метод сортировки PyTorch очень прост и легко запоминается:torch.sort(). Небольшая разница между ними заключается в имени параметра порядка сортировки: TensorFlow — этоdirection, в то время как PyTorchdescending. Также не забудьте пройти.cuda()Метод определяет использование графических процессоров для ускорения вычислений на больших наборах данных.

Сортировка по графическому процессору отлично подходит для больших наборов данных, но сортировка непосредственно на SQL также имеет смысл.

SQL

Сортировка в SQL обычно очень быстрая, особенно когда данные загружаются в память.

SQL является лишь спецификацией и не определяет конкретную реализацию алгоритма сортировки. НапримерPostgresВыбирайте в зависимости от окруженияdisk merge sort,илиquick sort. Если памяти достаточно, данные можно загрузить в память для повышения скорости сортировки. установивwork_memЧтобы увеличить доступную память, см.:

wiki.PostgreSQL.org/wiki/тюнинг…

Другие базы данных SQL используют другие алгоритмы сортировки, например, Google BigQuery реализует некоторые приемы в соответствии с ответом ниже.introsort.

стек overflow.com/ah/53026600/…

Сортировка в SQL выполняется командойORDER_BY, это использование все еще отличается от реализации Python. Но у него уникальное имя команды, поэтому его легко запомнить.

Если это нужно для достижения убывающего порядка, используйте ключевое словоDESC. Таким образом, оператор для запроса имени клиента и возврата его в обратном алфавитном порядке выглядит следующим образом:

SELECT Names FROM Customers
ORDER BY Names DESC;

сравнивать

Для методов, представленных выше, я провел анализ, используя тот же формат данных: 1 миллион данных, один столбец, массив или список. Используя ноутбук Google Colab Jupyter, аппаратная сторона — графический процессор K80, процессор Intel (R) Xeon (R) @ 2,30 ГГц.

Адрес источника:col AB.research.Google.com/drive/1NN AR…

Результаты сравнения следующие:

По приведенному выше рисунку видно, что:

Версия PyTorch для графического процессора является самой быстрой;
Для numpy и pandas используйтеinplaceбыстрее, чем копирование данных;
Панды по умолчаниюquicksortвысокоскоростной
Большинство реализаций одного и того же алгоритма сортировки в pandas работают медленнее, чем numpy.
TensorFlow работает быстро на ЦП, а версия TensorFlow-gpu медленнее на ЦП и медленнее на ГП, похоже, это может быть ошибка;
родной PythoninplaceСкорость сортировки очень низкая, почти в 100 раз медленнее, чем у самой быстрой версии PyTorch для графического процессора. Измерьте этот метод несколько раз, чтобы убедиться, что это не аномалия.

Кроме того, это небольшой тест и определенно не авторитетный результат.

Суммировать

Наконец, нам обычно не нужно реализовывать алгоритм сортировки самостоятельно, текущие методы, реализованные различными библиотеками, очень мощны. Они не только используют один алгоритм сортировки, они тестируют разные алгоритмы сортировки на разных типах данных, чтобы выбрать лучший алгоритм сортировки в разных ситуациях, и даже некоторые реализации улучшат сам алгоритм для повышения скорости сортировки.

В этой статье представлены методы сортировки в разных библиотеках Python и SQL, вообще говоря, вам нужно только помнить, какой параметр для какой операции реализовать, а затем вот некоторые из моих предложений:

Для небольших наборов данных используйте Pandas по умолчанию.sort_values()Проводить исследование и анализ данных;
Для больших наборов данных или там, где скорость является приоритетом, попробуйте numpyinplaceизmergesort, или PyTorch, параллельная реализация TensorFlow на GPU, или SQL.

Для практики сортировки на GPU вы можете проверить эту статью:

Обсуждение разработчиков.NVIDIA.com/default/top…

Ссылаться на

docs.Python.org/3/library/… — это…
docs.Python.org/3/library/…
Глубоко и день за днём.блог/Тим Сорт - Он и…
docs.last friend.org/doc/num py-1…
docs.last friend.org/doc/num py-1…
En. Wikipedia.org/wiki/intros…
GitHub.com/num-py/num-py…
github.com/dask/dask
woohoo.tensorflow.org/versions/день 2…
к data science.com/what-deep-…
nvlabs.github.io/cub/
GitHub.com/tensorflow/…
thrust.github.io/
equinetoxindamen.com/blog/all-yo…
wiki.PostgreSQL.org/wiki/тюнинг…
стек overflow.com/ah/53026600/…