Список рассылки python heapq не так ли?

Question

Я пытаюсь сортировать списки в один список, который содержит числа и названия разделов, подсекций и вспомогательных подразделов. Программа выглядит следующим образом:

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) 

Что я выберусь это:

['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'] 

Моего 12-й подраздел и субтропический подраздел находится в 8-м раздела, а не 12-го.

Почему это происходит? Исходные списки сортируются, и все идет хорошо, видимо, до номера 10.

Я не уверен, почему это происходит, и есть способ лучше сортировать это в «дерево» на основе чисел в списки? Я строй оглавления рода, и это будет возвращать (как только я отфильтровать список из)

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 

Обратите внимание на 12,1 Подраздел за 8,1 п и 12.1.1 подподраздела за 8.1.1 подподразделом.

Answer 1

Как объяснены в другом ответе, вы должны указать способ сортировки, в противном случае питон будет сортировать строки лексикографический. Если вы используете python 3.5+, вы можете использовать аргумент key в функции merge, в python 3.5 вы можете использовать itertools.chain и sorted, и в качестве общего подхода, можно использовать регулярное выражение для того, чтобы найти число и преобразовать их в целое:

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

Ваши списки могут быть сортированы, для человеческого глаза. Но для Python ваши входы не полностью отсортированы, потому что он сортирует строки лексикографически. Это означает, что '12' предшествует '8' в отсортированном порядке, поскольку сравниваются только первые символов.

Таким образом, слияние является полностью правильным; строка, начинающаяся '12.1', встречается после того, как была показана строка '8.1', но сортировка начинается с '8.1.1'.

Вы должны извлечь кортежей целых чисел из строки с ключом функции правильно сортировать:

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

Обратите внимание, что key аргумент доступен только в Python 3.5 и выше; в ранних версиях вам нужно будет выполнить ручной декорирование-слияние-undecorate.

Демонстрация (с использованием 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'] 

по ключу слияния легко портированном в Python 3.3 и 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__ 

украшение сортировки-undecorate слияния так же просто, как:

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))] 

Поскольку ваш вход уже отсортирован, использование сортировки слияния более эффективно. В крайнем случае, вы могли бы просто использовать sorted() однако:

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