Python中高效检查字符串是否只包含一个字符

84

在Python中,如何高效地检查字符串s是否只包含一个字符,比如说'A'?类似于all_equal(s, 'A')这样的函数,其功能应该满足以下要求:

all_equal("AAAAA", "A") = True

all_equal("AAAAAAAAAAA", "A") = True

all_equal("AAAAAfAAAAA", "A") = False

有两种看起来不太高效的方法:第一种是将字符串转换为列表并检查每个元素,第二种是使用正则表达式。在Python中是否有更有效的方法,或者这些是最好的方法?谢谢。


6
有点惊讶还没有人问过以下问题:您输入的“不均匀”字符串的结构是什么?如果有一个结构(即它们不完全随机),您可以利用此知识来优化算法。 - mikołak
这个真的很重要吗?我想知道什么样的应用程序会在瓶颈代码中进行这种检查。 - Barmar
4
在我看来,这的效率很少是重要的,虽然谁知道呢?无论如何,这个任务很不错,了解代码内部发生的事情以及为什么有些解决方案很慢,有些解决方案很快,对于Python开发者来说是一个有用的训练。 - Ellioh
8个回答

143

这是目前最快的算法,速度比count()函数快几倍,您可以使用这个优秀的mgilson的计时套件来测试时间:

s == len(s) * s[0]

在Python C代码中,所有检查都在内部完成,它只执行以下操作:

  • 分配长度为len(s)的字符;
  • 用第一个字符填充空间;
  • 比较两个字符串。

字符串越长,时间奖励就越大。然而,正如mgilson所写,它会创建字符串的副本,因此如果你的字符串长度为数百万个符号,可能会成为问题。

从计时结果可以看出,通常解决任务最快的方法是不为每个符号执行任何Python代码。但是,set()解决方案也在Python库的C代码中完成了所有工作,但仍然很慢,可能是由于通过Python对象接口处理字符串。

UPD: 关于空字符串的情况。对它进行的操作取决于任务的要求。如果任务是“检查字符串中的所有符号是否相同”,那么 s == len(s) * s[0] 是一个有效的答案(没有符号意味着错误,异常也可以),如果任务是“检查是否只有一个唯一的符号”,空字符串应该为False,答案是 s and s == len(s) * s[0],或者如果您更喜欢接收布尔值,则可以使用 bool(s) and s == len(s) * s[0]。最后,如果我们将任务理解为“检查是否没有不同的符号”,那么空字符串的结果为True,答案是 not s or s == len(s) * s[0]


2
如果s是空字符串呢? - Hammerite
1
lol strmul和count在字符串规模上表现良好。以下是我在源字符串长度为1024个字符时得到的时间:[('test_strmul', 0.9134591826614835), ('test_set', 45.61518321462644), ('test_count', 2.706394388113573)]。 - sea-rob
@Hammerite -- 空字符串需要检查,这里我们只是在测试想法。此外,我不知道如何处理空字符串,True或False(问题是“检查字符串是否包含仅一个唯一字符”,还是“检查是否没有超过一个唯一字符”)。根据这个问题,完整的答案要么是“not s or s[0] * len(s) == s”,要么是“s and s[0] * len(s) == s”。 - Ellioh
2
作为一名数学家,我的直觉是如果s为空字符串,则该函数应返回True。但是OP真的应该指明。 - Hammerite
你说:“如果任务是'检查字符串中的所有符号是否相同',那么抛出异常就可以了”。我不同意。空字符串中的所有符号都是相同的,因为你无法向我展示在空字符串中存在两个不同的符号。 - Hammerite
显示剩余10条评论

49
>>> s = 'AAAAAAAAAAAAAAAAAAA'
>>> s.count(s[0]) == len(s)
True

这不会进行短路运算。进行短路运算的版本如下:

>>> all(x == s[0] for x in s)
True

然而,由于C语言实现的优化,我有一种感觉,非短路版本在某些字符串上(取决于大小等因素)可能会表现得更好。


这里有一个简单的timeit脚本,用于测试其他发布的选项:

import timeit
import re

def test_regex(s,regex=re.compile(r'^(.)\1*$')):
    return bool(regex.match(s))

def test_all(s):
    return all(x == s[0] for x in s)

def test_count(s):
    return s.count(s[0]) == len(s)

def test_set(s):
    return len(set(s)) == 1

def test_replace(s):
    return not s.replace(s[0],'')

def test_translate(s):
    return not s.translate(None,s[0])

def test_strmul(s):
    return s == s[0]*len(s)

tests = ('test_all','test_count','test_set','test_replace','test_translate','test_strmul','test_regex')

print "WITH ALL EQUAL"
for test in tests:
    print test, timeit.timeit('%s(s)'%test,'from __main__ import %s; s="AAAAAAAAAAAAAAAAA"'%test)
    if globals()[test]("AAAAAAAAAAAAAAAAA") != True:
        print globals()[test]("AAAAAAAAAAAAAAAAA")
        raise AssertionError

print
print "WITH FIRST NON-EQUAL"
for test in tests:
    print test, timeit.timeit('%s(s)'%test,'from __main__ import %s; s="FAAAAAAAAAAAAAAAA"'%test)
    if globals()[test]("FAAAAAAAAAAAAAAAA") != False:
        print globals()[test]("FAAAAAAAAAAAAAAAA")
        raise AssertionError

在我的电脑上(OS-X 10.5.8,core2duo,python2.7.3)使用这些人工制造的(短)字符串,str.countsetall更快,并且比str.replace稍微快一点,但被str.translatestrmul超过了,在这两者中,strmul目前领先优势明显:

WITH ALL EQUAL
test_all 5.83863711357
test_count 0.947771072388
test_set 2.01028490067
test_replace 1.24682998657
test_translate 0.941282987595
test_strmul 0.629556179047
test_regex 2.52913498878

WITH FIRST NON-EQUAL
test_all 2.41147494316
test_count 0.942595005035
test_set 2.00480484962
test_replace 0.960338115692
test_translate 0.924381017685
test_strmul 0.622269153595
test_regex 1.36632800102

不同系统和不同字符串之间的时间可能会略有不同(甚至相差很大),因此值得使用实际要传递的字符串进行测试。

最终,如果在足够多的情况下达到了all的最佳情况,并且你的字符串足够长,则可以考虑使用该算法。它是一种更好的算法...不过我会避免使用set的解决方案,因为我没有看到任何它能够胜过count解决方案的情况。

如果内存可能成为问题,那么就需要避免使用str.translatestr.replacestrmul,因为这些会创建第二个字符串。但这通常不是一个问题。


哇!看起来我找到了一个更快的版本:s == len(s) * s[0] - Ellioh
1
@oefe -- 直到你实际测量,你才真正了解任何事情 :) - mgilson
正则表达式 ^(.)\1*$ 有什么比较? - Barmar
@Barmar -- 我不知道?抱歉,我不是正则表达式大师,所以你可能需要详细说明一下,这样我才能将其添加到测试套件中。 - mgilson
@Barmar -- 你的正则表达式解决方案还算不错,中规中矩。 - mgilson
显示剩余2条评论

17
你可以将其转换为集合并检查是否只有一个成员:
len(set("AAAAAAAA"))

13
尝试使用内置函数all
all(c == 'A' for c in s)

@InbarRose -- 这些时间差大约在1%的数量级上 -- 在我看来,这并不值得担忧。特别是考虑到is依赖于Cpython的实现细节。 - mgilson
@mgilson 我不记得确切地在哪里读到过,但我记得在处理字符比较时最好使用 is - Inbar Rose
@InbarRose -- 我怀疑。据我所知,没有保证字符是单例的(虽然我可能对此有所错误)。 - mgilson
11
我认为 is 不一定能够奏效。它依赖于解释器的实现细节,即字符串的内部化(interning),但根据我记得的 Python 规范,这不是被保证的。是的,至少对于短字符串来说,它在任何地方都可能会奏效,但是“可能”并不是最可靠的依赖。 - Silas Ray

6
如果您需要检查字符串中的所有字符是否相同且等于给定字符,则需要删除所有重复项并检查最终结果是否等于单个字符。
>>> set("AAAAA") == set("A")
True

如果您想查找是否存在任何重复项,请检查长度。

>>> len(set("AAAAA")) == 1
True

6
在解决这个问题时,可以添加另一个解决方案。
>>> not "AAAAAA".translate(None,"A")
True

令人惊讶的是,在我的计时中,“translate”正在获胜...(但并不多)(+1)。 - mgilson
而且显然已经输了很久。你被s == s[0]*len(s)打败了 :) - mgilson

3

迄今为止,回答都很有趣。下面是另一个:

flag = True
for c in 'AAAAAAAfAAAA':
    if not c == 'A': 
        flag = False
        break

我能想到的唯一优点是,如果发现一个不一致的字符,它不需要遍历整个字符串就可以完成操作。

3
all函数也是这样做的。一旦它找到一个值为假,它就停止了。 - Inbar Rose
有趣。很有道理。不过,相比set方法,可能更有效率,对吧? - Master_Yoda
你可以使用timeit来检查代码的运行时间。 - Inbar Rose

2
not len("AAAAAAAAA".replace('A', ''))

0的意思是真,所以需要用not运算符。这段代码的含义是:统计“AAAAAAAAA”中去掉所有'A'后剩余字符的数量。 - Ellioh
我对你的计时套件进行了添加。如果字符串由“A”组成,我的版本仍然比count()差得多,但是当第一个字符为“f”时略微更好。 - Ellioh

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接