Разделение по значению столбца в O (n) ⇐ Python

[Anonymous]

Можно ли с помощью поляров изменить порядок строк в кадре данных так, чтобы

• Строки с одинаковым значением в столбце 1 располагались рядом
• Это операция 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:



Метод
Время




СОРТИРОВКА
0,26 с (2)


РАЗВРЫВАТЬ
0,22 с (1)


РАЗДЕЛ
3,89 с (3)



где

• СОРТИРОВКА просто сортирует по (столбец 1, столбец 2).
• РАЗВЛЕЧЕНИЕ использует предложение по @ BallpointBen, df.group_by("col1").all().explode(pl.exclude("col1"))
• PARTITION использует предложение @Dogbert, pl .concat(df.partition_by("col1"))

Сроки решения, предложенные на данный момент для моего второго вопроса (строки разделов и порядок внутри разделения по второму столбцу), далеко на примере с M=1, N=2 и 1M строк и средним размером группы 10:



Метод
Предварительно отсортировано




СОРТИРОВКА
0,03 с (1)


PARTITION
5,05 с (3)


PARALLELPARTITION
1,49 с (2)



где

[*]СОРТИРОВКА просто сортирует по (столбец 1, столбец 2).
[*]PARTITION использует предложение по @ Догберт, pl.concat([x.sort('col2') for x in df.partition_by("col1")])
[*]PARALLELPARTITION использует предложение @DeanMcGregor , pl.concat([x.lazy().sort('col2') for x в df.partition_by("col1")]).collect()


Подробнее здесь: https://stackoverflow.com/questions/787 ... alue-in-on