时间戳

首页 > 解决方案 > 关于 Python 中字符串切片的性能问题

python-3.x - 关于 Python 中字符串切片的性能问题

问题描述

我正在学习一些 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？

标签： python-3.xstringsetslice

解决方案

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

首先，我们可以用其复杂性标记每个单独的语句，其中n是 的长度是s1的m长度s2：

def scramble(s1,s2):
    result = True                  # O(1)
    for character in s2:           # loop runs O(m) times
        if character not in s1:        # O(n) to search characters in s1
            return False               # O(1)
        i = s1.index(character)        # O(n) to search characters in s1
        s1 = s1[0:i] + s1[i+1:]        # O(n) to build a new string
    return result                  # O(1)

那么总复杂度为 O(1 + m*(n + 1 + n + n) + 1) 或更简单的 O(m*n)。这对这个问题没有效率。

替代算法更快的关键在于set(s2)它只包含字符串中的不同字符s2。这很重要，因为构成这些字符串的字母表具有恒定的、有限的大小。小写字母大概是 26。鉴于此，替代算法的外循环实际上最多运行 26 次：

def scramble(s1,s2):
    for letter in set(s2):                      # O(m) to build a set 
                                                # loop runs O(1) times
        if s1.count(letter) < s2.count(letter):     # O(n) + O(m) to count
                                                    # chars from s1 and s2
            return False                            # O(1)
    return True                                 # O(1)

这意味着替代算法的复杂度为 O(m + 1*(n + m + 1) + 1) 或更简单的 O(m + n)，这意味着它比您的算法渐近更有效。

推荐阅读