python:从列表中找到字母表中缺少的字母 - 最少的代码行

Question

我试图用最少的代码行从列表中找到字母表中缺少的字母.

如果列表已经排序(使用list.sort()),找到丢失的字母的最快或最少的代码行是什么.

如果我知道只有一封丢失的信件.

(这不是任何类型的面试问题.我实际上需要在我的脚本中执行此操作,我希望在此过程中进行最少量的工作,因为它将在不确定的情况下反复重复)

Answer 1

一些问题:

• 所有字母都是大写还是小写？(A/A)
• 这是你唯一要检查的字母吗？
• 你为什么经常这样做？

最少的代码行:

# 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而不是set用C编写的操作.

(感谢JFSebastian和Kylotan的评论)

Answer 2

使用列表理解:

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

该字符串模块有一些预定义的常量是有用的.

>>> 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则稍微快一些).

令人惊讶的是,monkut 的listcomp解决方案最快 - 我希望设置的解决方案做得更好,因为每次必须扫描列表才能找到丢失的字母.我尝试首先将测试列表转换为成员检查之前的一组,期望这样可以加快速度,但事实上它使速度变慢了.看起来创建集合时的常数因子延迟使得对这样的短字符串使用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")

然而,当使用更大的字符串时,二分法可能是最好的.它只是在这里被listcomp淘汰,并且具有更好的渐近复杂度,因此对于大于字母表的字符串,它将明显获胜.

[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