Czytam w pliku i ciągniesz dane, które obejmują niektóre struny i niektóre liczby w Pythonie. Przechowuję te informacje jako listy list, takich jak to:

dataList = [

['blah', 2, 3, 4],

['blahs', 6, 7, 8],

['blaher', 10, 11, 12],

]

Chcę zachować datalist posortowany przez drugi element pod Sub: Datalist [] [1]

Myślałem, że mogę użyć insion lub bisect tuż, gdy chcę je dodać, ale nie mogę dowiedzieć się, jak spojrzeć na drugiego elementu listy podrzędnej.

Jakieś myśli tutaj? Byłem włączony do końca, a następnie wykonałem liniowy rodzaj, aby znaleźć rzeczy później. Ale wyrzuć kilka 10-tych tysięcy pod-listy tutaj, a następnie wyszukaj 100 tys. Przedmiotów i zajmuje trochę czasu.

13
ErikS 7 wrzesień 2012, 23:46

2 odpowiedzi

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

To sortuje listę na miejscu przez drugi element w każdym elemencie.

Jak wskazano w komentarzach, jest znacznie bardziej wydajny, aby sortować tylko raz (na końcu). Wbudowana metoda sortowania Pythona była zoptymalizowana, aby pracować szybko . Po testowaniu wygląda na to, że wbudowany rodzaj jest konsekwentnie około 3,7 razy szybszy niż przy użyciu Metoda sterty sugerowana w innej odpowiedzi , na różnych listach rozmiarach (przetestowałem rozmiary do 600000).

9
Community 23 maj 2017, 12:16

Zależy od kilku rzeczy, ale pierwszą rzeczą, która przychodzi na myśl, używa modułu sterowania:

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

Stworzyłoby to stertę pełną Ktorek, gdzie pierwszy element jest elementem, który chcesz sortować, a drugi element to wiersz.

Najprostszą metodą czytania ich z powrotem z sterty byłoby skopiowanie, a następnie elementy pop:

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

Czas wstawienia każdego elementu do sterty jest O(lg N), więc tworzenie sterty będzie wymagać czasu O(N lg N) i pojawienia się elementów z sterty wymaga również czasu O(lg N), więc O(N lg N) Czas będzie musiał go przemierzać.

Jeśli te kompromety nie są idealne, można użyć drzewa wyszukiwania binarnego (brakuje w standardowej bibliotece, ale Są łatwe do znalezienia) lub jako sugerowali inni komentatorzy, sortują wiersze po ich przeczytaniu: rows.sort(key=lambda row: row[1]).

Teraz, w praktyce, chyba że masz do czynienia z bardzo dużą liczbą wierszy, prawie na pewno będzie szybciej posortować listę w miejscu po załadowaniu (tj. Za pomocą metody {x0}}) ... więc spróbuj Kilka rzeczy i zobacz, co działa najlepiej.

Wreszcie, bisect jest złym pomysłem, ponieważ wkładanie do list Python wymaga czasu O(N), więc wkładanie elementów z bisect wymagałoby czasu O(N lg N) czas na element , więc Całkowity czas O((N lg N) * N) = O(N**2) czas.

7
David Wolever 7 wrzesień 2012, 19:58