Группировки последовательных чисел в диапазоны в Python 3.2


Ниже приводится функция, которую я написал для отображения номеров страниц, как они появляются в книгах.

Если вы входите в список [1,2,3,6,7,10], например, она вернется:

1-3,6-7,10

Это казалось хорошим примером того, как тип данных словарь можно использовать в Python.

Есть еще код-эффективный способ сделать это?

def formatpagelist (numberlist):
    tempdic={}
    returnstring=''

    for number in numberlist:
        if number-1 in tempdic.keys():
            tempdic[number-1]=number
        elif number-1 in tempdic.values():
            for key in tempdic.keys():
                if number-1==tempdic[key]: foundkey=key
            tempdic[foundkey]=number
        else:
            tempdic[number]=0

    keylist=list(tempdic.keys())
    keylist.sort()

    for key in keylist:
        if tempdic[key]>0:
            returnstring+=(str(key)+'-'+str(tempdic[key])+',')
        else: returnstring+=str(key)+','

    return returnstring


13154
8
задан 5 октября 2011 в 04:10 Источник Поделиться
Комментарии
4 ответа

Вы можете использовать эту команду, чтобы генерировать групп подряд идущих чисел в списке:

from itertools import groupby, count

groupby(numberlist, lambda n, c=count(): n-next(c))

Затем, чтобы прикончить его, сгенерировать строку из группы.

def as_range(iterable): # not sure how to do this part elegantly
l = list(iterable)
if len(l) > 1:
return '{0}-{1}'.format(l[0], l[-1])
else:
return '{0}'.format(l[0])

','.join(as_range(g) for _, g in groupby(numberlist, key=lambda n, c=count(): n-next(c)))
# '1-3,6-7,10'

Это предполагает, что они находятся в отсортированном порядке и нет никаких дубликатов. Если не отсортирован, добавить отсортированный() позвонить на numberlist заранее. Если есть дубликаты, делают ее установить заранее.

12
ответ дан 5 октября 2011 в 07:10 Источник Поделиться

Немного короче версии, не используя словарь:

def formatpagelist(numberlist):
prev_number = min(numberlist) if numberlist else None
pagelist = list()

for number in sorted(numberlist):
if number != prev_number+1:
pagelist.append([number])
elif len(pagelist[-1]) > 1:
pagelist[-1][-1] = number
else:
pagelist[-1].append(number)
prev_number = number

return ','.join(['-'.join(map(str,page)) for page in pagelist])

3
ответ дан 5 октября 2011 в 05:10 Источник Поделиться

def formatpagelist (numberlist):

Руководство по стилю Python рекомендует words_with_underscores для имен функций.

    tempdic={}

Это действительно плохое имя переменной. Он говорит мне ничего о том, что переменная используется для. Он говорит мне, что переменная является временное (как и все переменные), и что его дикт, который очевиден, учитывая {}

    returnstring=''

Это не обнаруживается, только позже... Зачем это здесь?

    for number in numberlist:
if number-1 in tempdic.keys():

Это так же, как номер 1 в tempdic:

            tempdic[number-1]=number
elif number-1 in tempdic.values():
for key in tempdic.keys():
if number-1==tempdic[key]: foundkey=key

Если у вас есть сканирование по ключам словаря, что является признаком того, что вы, вероятно, не должны использовать словарь.

            tempdic[foundkey]=number
else:
tempdic[number]=0

keylist=list(tempdic.keys())
keylist.sort()

Это то же самое, что keylist = отсортированный(tempdic)

    for key in keylist:
if tempdic[key]>0:
returnstring+=(str(key)+'-'+str(tempdic[key])+',')
else: returnstring+=str(key)+','

Я думаю, что ставить на одну линию делает его труднее читать. Вы обычно лучше строить список, а затем войти в список.

    return returnstring

Здесь другой подход: я украл запчасти от @Джефф, но я хотел попробовать другой подход.

import collections

pages = [1,2,5,6,7,9]
starts = collections.OrderedDict()
ends = collections.OrderedDict()
for idx, page in enumerate(pages):
section = page - idx
starts.setdefault(section, page)
ends[section] = page
page_parts = []
for section, start in starts.items():
end = ends[section]
if start == end:
page_parts.append("{0}".format(start))
else:
page_parts.append("{0}-{1}".format(start, end))
print(','.join(page_parts))

1
ответ дан 6 октября 2011 в 12:10 Источник Поделиться

Использование словаря, кажется, есть способ разрешить цифры, чтобы прибыть из-за того.
А не сортировать их, вам кажется, пытаются использовать словарь (и связанные хеширования), чтобы максимизировать эффективность.

Это не идеально, поскольку вы завершаете делать последовательный поиск заданного значения.

Хеширование низкий:высокий диапазон (ключ словаря:пара значений), чтобы избежать поиск не очень помогает. Только они ключ хэшируется. Это поможет в том случае, когда вы расширяете диапазон на нижнем конце. Но для расширения диапазона по верхней границе, то придется прибегнуть к поискам ценностей словарь.

Что вы действительно создаете коллекция "разделы". Каждый раздел ограничен нижним и верхним значениями. А не словарь, вы также можете использовать тривиальный набор (низкая, высокая). Чтобы быть наиболее подходящие для Python, пара (низкий,высокий) включает в себя низкий, но не высокий. Это "полуинтервала".

Вот версия с помощью простого набора кортежей, опираясь на хэши вместо бисекции.

Двоичный поиск (с использованием пополам модуля) может выполнять также. Было бы немного упростить смежных слияние диапазона, с двумя диапазонами будет рядом. Однако, это приводит к стоимости в реструктуризации последовательности.

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

Каждый следующий ряд можно привести к одному из трех вещей.


  1. Он расширяет существующий раздел на нижнем конце или высокого класса. Количество примыкает к одному кругу.

  2. Она создает новый раздел. Номер не рядом с любой серии.

  3. Его "мосты" два смежных разделов, объединив их в один. Число рядом с двумя диапазонами.

Это что-то вроде этого.

def make_ranges(numberlist):
ranges=set()
for number in numberlist:
print ranges, number
adjacent_to = set( r for r in ranges if r[0]-1 == number or r[1] == number )
if len(adjacent_to) == 0:
# Add a new partition.
r = (number,number+1)
assert r[0] <= number < r[1] # Trivial, right?
ranges.add( r )
elif len(adjacent_to) == 1:
# Extend this partition, build a new range.
ranges.difference_update( adjacent_to )
r= adjacent_to.pop()
if r[0]-1 == number: # Extend low end
r= (number,r[1])
else:
r= (r[0],number+1) # Extend high end
assert r[0] <= number < r[1]
ranges.add( r )
elif len(adjacent_to) == 2:
# Merge two adjacent partitions.
ranges.difference_update( adjacent_to )
r0= adjacent_to.pop()
r1= adjacent_to.pop()
r = ( min(r0[0],r1[0]), max(r0[1],r1[1]) )
assert r[0] <= number < r[1]
ranges.add( r )
return ranges

Это довольно радикальное переосмысление вашего алгоритма, так что это не правильный комментарий код.

Монтаж строку с разделителями проще в Python. На вашем примере ", "разделенных строками, всегда думаю, что делать это таким образом.

final = ",".join( details )

После этого, вы просто сделать последовательность деталей. В этом случае, каждая деталь является либо "X-Y" или "X" в качестве этих двух форм, что диапазон может взять.

Так что это должно быть что-то вроде

details = [ format_a_range(r) for r in ranges ]

В этом примере, я показал формате в строке физ. Это может быть сделано, как если-то выражения, а также.

Учитывая ваши диапазоны, в целом функция этого.

def formatpagelist (numberlist):
ranges= make_ranges( numberlist )
def format_a_range( low, high ):
if low == high-1: return "{0}".format( low )
return "{0}-{1}".format( low, high-1 )
strings = [ format_a_range(r) for r in sorted(ranges) ]
return ",".join( strings )

0
ответ дан 6 октября 2011 в 07:10 Источник Поделиться