关于Python中字符串切片的性能问题

Question

我正在学习一些python，在此过程中，我正在从codewars中做一些简单的katas。我遇到https://www.codewars.com/kata/scramblies问题。

我的解决方案如下：

def scramble(s1,s2):
    result = True
    for character in s2:
        if character not in s1:
            return False
        i = s1.index(character)
        s1 = s1[0:i] + s1[i+1:]
    return result

虽然结果正确，但速度不够快。我的解决方案在12000毫秒后超时。我查看了其他人提出的解决方案，其中涉及一组解决方案。

  def scramble(s1,s2):
     for letter in set(s2):
        if s1.count(letter) < s2.count(letter):
          return False
     return True

为什么我的解决方案比另一个解决方案要慢得多？除非我误解了切片字符串的效率，否则它看起来应该不是。我解决此问题的方法是否有缺陷或不是pythonic？

Answer 1

首先，set快速且非常出色。对于in之类的东西，set比list快。

第二，您的解决方案比正确的解决方案要做的[[way更多的工作。请注意，第二个解决方案是如何从未修改过s1或s2的，而您的解决方案都采用了s1的two slices，然后重新分配了s1。这以及调用.index()。切片并不是最快的操作，主要是因为必须分配内存并且必须复制数据。 .remove()可能比.index()和您正在切片的组合要快。

这里的基本信息是，如果任务可以用更少的操作完成，那么显然可以更快地执行。切片也比大多数其他方法昂贵，因为

分配空间和复制内存

是比正确解决方案使用的诸如.count()之类的计算方法更昂贵的操作。

Answer 2

对于这种对程序运行时间有限制的在线编程挑战，测试输入将包含一些相当大的示例，并且通常设置时间限制，这样您就不必浪费最后一毫秒的时间了。代码，但您必须编写足够低的算法computational complexity。为了回答您的算法超时的原因，我们可以使用big O notation对其进行分析，以找到其计算复杂度。