Как сохранить список списков, отсортированных по мере их создания

Я читаю в файле и вытаскиваю данные, содержащие некоторые строки и некоторые числа, в Python. Я сохраняю эту информацию в виде списков списков, например:

Я хочу, чтобы dataList отсортировался по второму элементу подкаталога: dataList [] [1]

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

Любые мысли здесь? Я просто добавлял данные до конца, а затем делал линейную сортировку, чтобы найти вещи позже. Но, бросьте несколько десятков тысяч суб-списков здесь, а затем ищите 100 тыс. Элементов, и требуется некоторое время.

Ответы

Ответ 1

dataList.sort(key=lambda x: x[1])

Это сортирует список по месту, вторым элементом в каждом элементе.

Как уже отмечалось в комментариях, гораздо эффективнее сортировать только один раз (в конце). Встроенный метод сортировки Python был сильно оптимизирован для быстрой работы. После тестирования это похоже на то, что встроенная сортировка последовательно примерно в 3,7 раза быстрее, чем с помощью метода кучи, предложенного в другом ответе, в разных списках размеров (я тестировал размеры до 600000).

Ответ 2

Зависит от нескольких вещей, но первое, что приходит в голову, это использовать модуль heapq:

import heapq
heap = []
for row in rows:
    heapq.heappush(heap, (row[1], row))

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

Самый простой способ прочитать их из кучи - скопировать его, а затем поп-элементы:

new_heap = list(heap)
while new_heap:
    _, row = heapq.heappop(new_heap)
    print row

Время выполнения вставки каждого элемента в кучу O(lg N), поэтому для создания кучи потребуется время O(N lg N), а для всплывающих элементов из кучи также требуется время O(lg N), поэтому O(N lg N) потребуется время пересечь его.

Если эти компромиссы не идеальны, вы можете использовать двоичное дерево поиска (ни одна из них не существует в стандартной библиотеке, но их легко найти), или, как предложили другие комментаторы, отсортируйте строки после их чтения: rows.sort(key=lambda row: row[1]).

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

Наконец, bisect является плохой идеей, потому что для вставки в списки Python требуется время O(N), поэтому для вставки элементов с bisect потребуется время O(N lg N) для каждого элемента, поэтому общее время O((N lg N) * N) = O(N**2) времени.