Разделение по значению столбца в O (n)
Используя поляры, могу ли я изменить порядок строк кадра данных так, чтобы
- Строки с одинаковым значением в
col1располагаются рядом. - Это операция O(n).
Альтернативный способ сформулировать это так: я хочу, чтобы выходные данные были отсортированы в каком-то произвольном порядке col1, но мне неважно, в каком порядке, что должно сократить время выполнения с O(nlogn) до O(n).
Используя эту немного неуклюжую перефразировку, я могу задать вопрос, который мне в конечном итоге нужен: могу ли я переупорядочить строки фрейма данных так, чтобы выходные данные сортировались лексикографически по (col1, ..., colN), с некоторым произвольным порядком (col1,..., colM) и каноническим порядком (colM+1, ..., colN), отличным от через сортировку (которая выберет канонический порядок (col1, ..., colM) и потребует ненужной работы)?
Простой пример: у меня есть строки (Date, String, Int), содержащие годовые данные о населении разных городов за последнее столетие. Я хочу, чтобы строки для каждого города располагались рядом друг с другом и сортировались по годам (скажем, потому что я использую внешний инструмент для постобработки, требующий непрерывности), но меня не волнует, идет ли Амстердам раньше Берлина.
Теоретически это тривиально достижимо за O(n) с использованием хешей. На практике мне понадобятся встроенные полярные операции, чтобы это было быстрее, чем обычная сортировка.
Обновлено: Сроки решения, предложенные на мой первый вопрос (строки разделов, не обязательно упорядочивать их), далеко на примере со строками M = 1, N = 2 и 10M и средним размером группы 10:
где
- СОРТИРОВКА просто сортирует по (столбец1, столбец2)
- В EXPLODE используется предложение @BallpointBen,
df.group_by("col1").all().explode(pl.exclude("col1")) - PARTITION использует предложение @Dogbert,
pl.concat(df.partition_by("col1"))
Время решения, предложенного на данный момент для моего второго вопроса (строки разделения и порядок внутри разделения по второму столбцу), на примере со строками M = 1, N = 2 и 1M и средним размером группы 10:
где
- СОРТИРОВКА просто сортирует по (столбец1, столбец2)
- PARTITION использует предложение @Dogbert,
pl.concat([x.sort('col2') for x in df.partition_by("col1")]) - PARALLELPARTITION использует предложение @DeanMcGregor,
pl.concat([x.lazy().sort('col2') for x in df.partition_by("col1")]).collect()
Вы также можете df.group_by(partition_cols).head(df.height) попробовать.
Ответы 2
Вы можете использовать DataFrame.partition_by, чтобы разделить фрейм данных на отдельный фрейм данных для каждого значения в произвольном порядке, а затем вызвать pl.concat в списке фреймов данных. Теоретически так и должно быть O(n).
В моих тестах для больших фреймов данных и столбца с низкой мощностью для разделения это происходит быстрее, чем сортировка.
Это пример, когда столбец раздела имеет 100 уникальных значений:
import timeit
import numpy as np
import polars as pl
for size in [100_000, 1_000_000, 10_000_000]:
df = pl.DataFrame(
{
"foo": np.random.randint(0, 100, size),
"bar": np.random.randint(0, 1_000_000, size),
}
)
print(size)
print(timeit.timeit(lambda: df.sort("foo"), number=10))
print(timeit.timeit(lambda: pl.concat(df.partition_by("foo")), number=10))
Выход:
100000
0.01896386011503637
0.012146126013249159
1000000
0.3261005349922925
0.08920360007323325
10000000
4.747504440136254
1.4530502599664032
Но если мощность столбца велика, например. если разделить на bar, который имеет до 1 миллиона разделов, это будет очень медленно.
Спасибо за хорошее предложение. К сожалению, в моем примере у меня есть столбец с высокой мощностью для разделения (именно здесь, я надеюсь, будет достигнута экономия: сортировка внутри каждого раздела в среднем составляет всего 8 строк, тогда как общий объем данных составляет миллионы строк).
попробуйте pl.concat([x.lazy().sort('bar') for x in df.partition_by("foo")]).collect(), так как все подсортировки будут выполняться параллельно. Я недостаточно разбираюсь в алгоритмах, чтобы понять, что такое обозначение BigO. Я полагаю, что привнесение в него параллелизма делает нотацию BigO не совсем правильной метрикой.
Спасибо, я попробую это и другие предложения и сообщу о сроках.
@deanmacgregor Lazy помогает, но не так быстро, как обычная сортировка
Хотел бы я принять оба ответа. В итоге принял другой ответ, потому что он остается чисто полярным.
Не уверен, что это наиболее эффективно, но df.group_by("col1", ..., "colM").all().explode(pl.exclude("col1", ..., "colM")) сгруппирует их в списки, а затем разложит их обратно в длинный df.
Чтобы также сортировать по другим столбцам в группах, вы можете сделать:
cols = ["col1", ..., "colM"]
(
df.group_by(cols)
.all()
.explode(pl.exclude(cols))
.with_columns(pl.exclude(cols).sort().over(cols))
.collect()
)
Есть ли способ сортировки по colM+1,...,colN с помощью этого? (Или даже всего на один столбец+1)
(Это намного быстрее для моих данных, чем решения part_by, для первого вопроса, который я задал, но я чувствую, что нет способа объединить его с сортировкой внутри группы)
@Bananach, посмотри мое редактирование
Удивительный. (Небольшая придирка: мне пришлось заменить сортировку на sort_by(["colM+1", ...., "colN"]), потому что в противном случае каждый столбец сортируется индивидуально, а строки искажаются, и это недовольство, с которым я всегда сталкиваюсь при использовании поляров)
К сожалению, даже при #rows -> infinity это решение все равно в 2 раза медленнее, чем глобальная сортировка в моей задаче. И все же отличный ответ!
Интересно, можно ли группировать данные по ключевому столбцу, объединять данные в списки, а затем разбирать их? Я с мобильного, поэтому проверить не могу. Это может быть быстрее, чем сортировка (хотя не уверен насчет производительности взрыва/взорвания)