Python heapq Sortierliste falsch?

Question

Ich versuche, Listen in eine Liste zu sortieren, die Nummern und Namen von Abschnitten, Unterabschnitten und Unterunterabschnitten enthält. Das Programm sieht wie folgt aus:

import heapq 

sections = ['1. Section', '2. Section', '3. Section', '4. Section', '5. Section', '6. Section', '7. Section', '8. Section', '9. Section', '10. Section', '11. Section', '12. Section'] 
subsections = ['1.1 Subsection', '1.2 Subsection', '1.3 Subsection', '1.4 Subsection', '2.1 Subsection', '4.1 My subsection', '7.1 Subsection', '8.1 Subsection', '12.1 Subsection'] 
subsubsections = ['1.2.1 Subsubsection', '1.2.2 Subsubsection', '1.4.1 Subsubsection', '2.1.1 Subsubsection', '7.1.1 Subsubsection', '8.1.1 Subsubsection', '12.1.1 Subsubsection'] 

sorted_list = list(heapq.merge(sections, subsections, subsubsections)) 

print(sorted_list) 

Was ich aus, ist dies:

['1. Section', '1.1 Subsection', '1.2 Subsection', '1.2.1 Subsubsection', '1.2.2 Subsubsection', '1.3 Subsection', '1.4 Subsection', '1.4.1 Subsubsection', '2. Section', '2.1 Subsection', '2.1.1 Subsubsection', '3. Section', '4. Section', '4.1 My subsection', '5. Section', '6. Section', '7. Section', '7.1 Subsection', '7.1.1 Subsubsection', '8. Section', '8.1 Subsection', '12.1 Subsection', '8.1.1 Subsubsection', '12.1.1 Subsubsection', '9. Section', '10. Section', '11. Section', '12. Section'] 

Mein 12. Unterabschnitt und Unterteilabschnitt innerhalb der 8. Abschnitt befindet, nicht 12..

Warum passiert das? Die ursprünglichen Listen sind sortiert, und alles geht gut, anscheinend bis zur Nummer 10.

Ich bin mir nicht sicher, warum das passiert und gibt es eine Möglichkeit, diese besser in einen "Baum" basierend auf den Zahlen in zu sortieren die Listen? Ich baue ein Inhaltsverzeichnis der Art, und dies wird zurückkehren (sobald ich die Liste herauszufiltern)

1. Section 
    1.1 Subsection 
    1.2 Subsection 
     1.2.1 Subsubsection 
     1.2.2 Subsubsection 
    1.3 Subsection 
    1.4 Subsection 
     1.4.1 Subsubsection 
2. Section 
    2.1 Subsection 
     2.1.1 Subsubsection 
3. Section 
4. Section 
    4.1 My subsection 
5. Section 
6. Section 
7. Section 
    7.1 Subsection 
     7.1.1 Subsubsection 
8. Section 
    8.1 Subsection 
    12.1 Subsection 
     8.1.1 Subsubsection 
     12.1.1 Subsubsection 
9. Section 
10. Section 
11. Section 
12. Section 

Beachten Sie die 12.1 Abs hinter 8.1 Unterabschnitt und 12.1.1 Subsubsection hinter 8.1.1 Subsubsection.

Answer 1

Wie in anderer Antwort müssen Sie eine Sortiermethode angeben, sonst wird Python die Saiten lexikographisch sortieren. Wenn Sie Python 3.5+ verwenden, können Sie key Argument in merge Funktion verwenden, in Python 3.5- Sie itertools.chain und sorted, und als allgemeiner Ansatz verwenden Sie Regex, um die Zahlen zu finden und wandeln sie in int verwenden können:

In [18]: from itertools import chain 
In [19]: import re 
In [23]: sorted(chain.from_iterable((sections, subsections, subsubsections)), 
       key = lambda x: [int(i) for i in re.findall(r'\d+', x)]) 
Out[23]: 
['1. Section', 
'1.1 Subsection', 
'1.2 Subsection', 
'1.2.1 Subsubsection', 
'1.2.2 Subsubsection', 
'1.3 Subsection', 
'1.4 Subsection', 
'1.4.1 Subsubsection', 
'2. Section', 
'2.1 Subsection', 
'2.1.1 Subsubsection', 
'3. Section', 
'4. Section', 
'4.1 My subsection', 
'5. Section', 
'6. Section', 
'7. Section', 
'7.1 Subsection', 
'7.1.1 Subsubsection', 
'8. Section', 
'8.1 Subsection', 
'8.1.1 Subsubsection', 
'9. Section', 
'10. Section', 
'11. Section', 
'12. Section', 
'12.1 Subsection', 
'12.1.1 Subsubsection'] 

Answer 2

Ihre Listen können erscheinen sortiert, für ein menschliches Auge. Aber zu Python sind Ihre Eingaben nicht vollständig sortiert, da sie Zeichenfolgen lexikografisch sortiert. Das heißt, '12' kommt vor '8' in sortierter Reihenfolge, weil nur die ersten Zeichen verglichen werden.

Als solche ist die Zusammenführung vollständig korrekt; Die Zeichenkette, die '12.1' beginnt, wird gefunden, nachdem die '8.1' Zeichenkette gesehen wurde, aber die eine, die mit '8.1.1' beginnt, wird danach sortiert.

Sie werden Tupel von ganzen Zahlen von den Saiten mit einer Schlüsselfunktion extrahieren müssen korrekt sortieren:

section = lambda s: [int(d) for d in s.partition(' ')[0].split('.') if d] 
heapq.merge(sections, subsections, subsubsections, key=section)) 

Beachten Sie, dass das key Argument in Python nur 3,5 und bis; Sie müssten in früheren Versionen einen manuellen Dekorations-Merge-undecorate-Tanz machen.

Demo (Python 3.6):

>>> section = lambda s: [int(d) for d in s.partition(' ')[0].split('.') if d] 
>>> sorted_list = list(heapq.merge(sections, subsections, subsubsections, key=section)) 
>>> from pprint import pprint 
>>> pprint(sorted_list) 
['1. Section', 
'1.1 Subsection', 
'1.2 Subsection', 
'1.2.1 Subsubsection', 
'1.2.2 Subsubsection', 
'1.3 Subsection', 
'1.4 Subsection', 
'1.4.1 Subsubsection', 
'2. Section', 
'2.1 Subsection', 
'2.1.1 Subsubsection', 
'3. Section', 
'4. Section', 
'4.1 My subsection', 
'5. Section', 
'6. Section', 
'7. Section', 
'7.1 Subsection', 
'7.1.1 Subsubsection', 
'8. Section', 
'8.1 Subsection', 
'8.1.1 Subsubsection', 
'9. Section', 
'10. Section', 
'11. Section', 
'12. Section', 
'12.1 Subsection', 
'12.1.1 Subsubsection'] 

Die getasteten merge zu Python leicht zurück portiert wird, 3.3 und 3.4:

import heapq 

def _heappop_max(heap): 
    lastelt = heap.pop() 
    if heap: 
     returnitem = heap[0] 
     heap[0] = lastelt 
     heapq._siftup_max(heap, 0) 
     return returnitem 
    return lastelt 

def _heapreplace_max(heap, item): 
    returnitem = heap[0] 
    heap[0] = item 
    heapq._siftup_max(heap, 0) 
    return returnitem 

def merge(*iterables, key=None, reverse=False):  
    h = [] 
    h_append = h.append 

    if reverse: 
     _heapify = heapq._heapify_max 
     _heappop = _heappop_max 
     _heapreplace = _heapreplace_max 
     direction = -1 
    else: 
     _heapify = heapify 
     _heappop = heappop 
     _heapreplace = heapreplace 
     direction = 1 

    if key is None: 
     for order, it in enumerate(map(iter, iterables)): 
      try: 
       next = it.__next__ 
       h_append([next(), order * direction, next]) 
      except StopIteration: 
       pass 
     _heapify(h) 
     while len(h) > 1: 
      try: 
       while True: 
        value, order, next = s = h[0] 
        yield value 
        s[0] = next()   # raises StopIteration when exhausted 
        _heapreplace(h, s)  # restore heap condition 
      except StopIteration: 
       _heappop(h)     # remove empty iterator 
     if h: 
      # fast case when only a single iterator remains 
      value, order, next = h[0] 
      yield value 
      yield from next.__self__ 
     return 

    for order, it in enumerate(map(iter, iterables)): 
     try: 
      next = it.__next__ 
      value = next() 
      h_append([key(value), order * direction, value, next]) 
     except StopIteration: 
      pass 
    _heapify(h) 
    while len(h) > 1: 
     try: 
      while True: 
       key_value, order, value, next = s = h[0] 
       yield value 
       value = next() 
       s[0] = key(value) 
       s[2] = value 
       _heapreplace(h, s) 
     except StopIteration: 
      _heappop(h) 
    if h: 
     key_value, order, value, next = h[0] 
     yield value 
     yield from next.__self__ 

A Verzieren-sort-undecorate merge ist so einfach wie:

def decorate(iterable, key): 
    for elem in iterable: 
     yield key(elem), elem 

sorted = [v for k, v in heapq.merge(
    decorate(sections, section), decorate(subsections, section) 
    decorate(subsubsections, section))] 

Da Ihre Eingabe bereits sortiert ist, ist die Verwendung einer Zusammenführungssortierung effizienter. Als letztes Mittel könnte man nur sorted() jedoch verwenden:

from itertools import chain 
result = sorted(chain(sections, subsections, subsubsections), key=section)