Разделение по значению столбца в 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) с использованием хешей. На практике мне понадобятся встроенные полярные операции, чтобы это было быстрее, чем обычная сортировка.

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