python: поиск пропущенной буквы в алфавите из списка - минимум строк кода

Question

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

Если список уже отсортирован (с помощью list.sort ()), какой код кода является самым быстрым или наименьшим, чтобы найти пропущенную букву.

Если я знаю, что пропущена только одна буква.

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

Answer 1

Некоторые вопросы:

• Все буквы прописные или строчные? (А / А)
• Это единственный алфавит, который вы хотите проверить?
• Почему ты так часто это делаешь?

Наименее строчки кода:

# do this once, outside the loop
alphabet=set(string.ascii_lowercase)
# inside the loop, just 1 line:
missingletter=(alphabet-set(yourlist)).pop()

Преимущество вышеизложенного состоит в том, что вы можете сделать это без предварительной сортировки списка. Однако, если список всегда отсортирован, вы можете использовать разделение пополам, чтобы добраться туда быстрее. На простом 26-буквенном алфавите, есть ли смысл?

Разделение пополам (сделано в ~ 4 поисках):

frompos, topos = 0, len(str)
for i in range(1,100):  #never say forever with bisection...
    trypos = (frompos+topos+1)/2
    print "try:",frompos,trypos,topos
    if alphabet[trypos] != str[trypos]:
        topos = trypos
    else:
        frompos = trypos
    if topos-frompos==1:
        if alphabet[topos] != str[topos]:
            print alphabet[frompos]
        else:
            print alphabet[topos]
        break

Этот код требует меньшего количества поисков, поэтому гораздо лучше масштабируемая версия O (log n), но все же может быть медленнее при выполнении через интерпретатор python, потому что он проходит через python if s вместо set написанных операций в с.

(Спасибо Дж. Ф. Себастьяну и Килотану за их комментарии)

Answer 2

Использование списка понимания:

>>> import string
>>> sourcelist = 'abcdefghijklmnopqrstuvwx'
>>> [letter for letter in string.ascii_lowercase if letter not in sourcelist]
['y', 'z']
>>>

Модуль string имеет несколько предопределенных полезных констант.

>>> string.ascii_lowercase
'abcdefghijklmnopqrstuvwxyz'

>>> string.letters
'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

>>> string.hexdigits
'0123456789abcdefABCDEF'

>>> string.octdigits
'01234567'

>>> string.digits
'0123456789'

>>> string.printable
'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r\x0b\x0c'
>>>

Answer 3

Слишком умный для своей собственной хорошей категории, и предполагается, что в строчном алфавите ровно одна пропущенная буква:

print chr(2847 - sum(map(ord, theString)))

[Изменить] Я проверил несколько вариантов различных решений, чтобы увидеть, какие из них быстрее. Моя практика оказалась довольно медленной (чуть быстрее, если я вместо этого использую itertools.imap).

Удивительно, но решение listcomp от monkut оказалось самым быстрым - я ожидал, что установленные решения будут работать лучше, так как каждый раз при поиске пропущенной буквы приходится сканировать список. Я попытался сначала преобразовать список тестов в набор перед проверкой членства, ожидая, что это ускорит его, но на самом деле это сделало его медленнее. Похоже, что постоянная задержка фактора при создании заданного карлика снижает стоимость использования алгоритма O (n ** 2) для такой короткой строки.

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

def missing_letter_basic(s):
    for letter in string.ascii_lowercase:
        if letter not in s: return letter
    raise Exception("No missing letter")

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

[Edit2]

На самом деле, немного обманывая, я могу стать еще лучше, злоупотребляя тем фактом, что нужно проверить только 26 строк, вот последний искатель пропущенных букв O (1)!

find_missing_letter = dict((string.ascii_lowercase[:i]+string.ascii_lowercase[i+1:],
                            string.ascii_lowercase[i]) for i in range(26)).get

>>> find_missing_letter('abcdefghijklmnoprstuvwxyz')
'q'

Вот мои тайминги (500000 прогонов, проверено на отсутствие букв в начале, середине и конце строки (b, m и y)

                         "b"    "m"     "y"
               bisect : 2.762   2.872   2.922  (Phil H)
             find_gap : 3.388   4.533   5.642  (unwind)
             listcomp : 2.832   2.858   2.822  (monkut)
         listcomp_set : 4.770   4.746   4.700  As above, with sourcelist=set(sourcelist) first
       set_difference : 2.924   2.945   2.880  (Phil H)
                  sum : 3.815   3.806   3.868
             sum_imap : 3.284   3.280   3.260
                basic : 0.544   1.379   2.359 
          dict_lookup : 0.135   0.133   0.134

Answer 4

class MissingFinder(object):
    "A simplified missing items locator"
    def __init__(self, alphabet):
        "Store a set from our alphabet"
        self.alphabet= set(alphabet)
    def missing(self, sequence):
        "Return set of missing letters; sequence not necessarily set"
        return self.alphabet.difference(sequence)

>>> import string
>>> finder= MissingFinder(string.ascii_lowercase)

>>> finder.missing(string.ascii_lowercase[:5] + string.ascii_lowercase[6:])
>>> set(['f'])
>>> # rinse, repeat calling finder.missing

Я уверен, что имена классов и экземпляров могут быть улучшены:)

Answer 5

если вы говорите об алфавите в виде букв:

letterSet = set()
for word in wordList:
  letterSet.update(set(word.lower()))

import string
alphabet = set(string.lowercase)
missingLetters = alphabet.difference(letterSet)

Answer 6

С отсортированными списками бинарный поиск обычно является самым быстрым алгоритмом. Не могли бы вы предоставить список примеров и пример "отсутствующего алфавита"?

Answer 7

Вот один из способов сделать это, предполагая, что ваши «алфавиты» являются целыми числами, и что список содержит как минимум два элемента:

for i in xrange(1, len(a)):
  if a[i] != a[i - 1] + 1:
    print a[i - 1] + 1, "is missing"