16

在使用循环时,我经常会两次编写一些代码。例如,在学习 Udacity 计算机科学课程时,我编写了代码(用于查找顺序重复次数最多的元素的函数):

def longest_repetition(l):
    if not l:
        return None
    most_reps = count = 0 
    longest = prv = None
    for i in l:
        if i == prv:
            count += 1
        else:
            if count > most_reps:
                longest = prv
                most_reps = count
            count = 1
        prv = i
    if count > most_reps:
        longest = prv
    return longest

在这种情况下,如果计数大于先前最重复的元素,我将检查两次。当当前元素与最后一个元素不同时以及当我到达列表的末尾时,都会发生这种情况。

在逐个字符解析字符串时,我也遇到过几次。也有几次它已经达到大约 5 行代码。这是常见的,还是我思考/编码方式的结果。我应该怎么办?

编辑:同样,在一个人为的字符串拆分示例中:

def split_by(string, delimeter):
    rtn = []
    tmp = ''
    for i in string:
        if i == delimeter:
            if tmp != '':
                rtn.append(tmp)
                tmp = ''
        else:
            tmp += i
    if tmp != '':
        rtn.append(tmp)
    return rtn

编辑:这个考试是为那些预计不会有任何 Python 外部知识的课程的学生编写的;只有在前面的单元中教过的东西。尽管我之前确实有 Python 方面的经验,但我正在努力遵守这些限制以充分利用这门课程。诸如 str.split、列表和 Python 的许多基础知识之类的东西都被教授了,但还没有关于导入的东西——尤其是诸如 groupby 之类的东西。话虽如此,如果没有任何可能不会在编程介绍课程中教授的语言特性,它应该如何编写。

4

6 回答 6

6

既然你标记language-agnostic了 ,我发现你不会对你可以用来使你的代码高效、紧凑和可读的特定于 python 的东西感兴趣。出于同样的原因,我不打算展示用 python 编写的代码有多漂亮。

在某些情况下,if根据您的算法可以避免最后的额外费用,但大多数情况下就像“如果它存在,它应该是重要的和/或有效的”。我不知道 python 解释器是如何工作的,但在 C/C++/等编译语言中。编译器执行各种循环优化,包括在执行相同操作时将 if 块移出循环。

我运行并比较了各种片段的运行时间:

  • @JFSebastian - 8.9939801693
  • @srgerg - 3.13302302361
  • 你的 - 2.8182990551。

if尾随为您提供最佳时间并不是一概而论。我的观点是:只需遵循您的算法,并尝试对其进行优化。结尾的 a 没有任何问题if。可能替代解决方案很昂贵。

关于您输入的第二个示例:tmp == ''完成检查以确保仅返回非空字符串。这实际上是您的拆分算法的一种附加条件。在任何情况下,您都需要在循环之后添加一个额外的内容rtn.append,因为在最后一个分隔符之外还有一些内容。你总是可以在循环中推送一个 if 条件,就像if curCharIndex == lastIndex: push items to list在每次迭代中执行的那样,它的情况又是相同的。

简而言之,我的回答:

  • 您的代码与您想到的算法一样有效。
  • 最后的ifs 在许多情况下都会遇到 - 无需担心它们,它们可能使代码比没有这种 if 的替代方法更有效(示例就在这里)。
  • 此外,编译器还可以发现和修改/移动代码周围的块。
  • 如果有一种语言特性/库可以使您的代码快速并同时具有可读性,请使用它。(这里的其他答案指出了 python 提供的内容:))
于 2012-06-22T05:04:45.177 回答
5

看看itertools.groupby哪个实现几乎完全符合您的要求。http://docs.python.org/library/itertools.html#itertools.groupby

这是使用所述代码的算法:

from itertools import groupby

string = "AAABBCCDDDD"

maximum = 0
max_char = ""

for i in groupby(string):
    x, xs = i
    n = len(list(xs))
    if n > maximum:
        max_char = x
        maximum = n

print max_char

我对考虑将来编写这样的算法的建议是尽量不要在一个函数中完成所有事情。考虑解决您要解决的问题的较小功能,例如“将序列中相等项目的每个序列分组为更小的序列”。

当然,它不一定是上述算法中的字符——它可以是任何可分组的东西。

编辑:为了响应 OP 的编辑,我认为您不会被允许在类设置中使用/了解诸如 itertools 之类的库,但我并不是建议您应该依赖外部库,而是您应该考虑的更多通过将问题拆分为更小的子问题来解决问题。因此,在这种情况下,您将实现自己的groupby并使用它。

于 2012-06-22T04:29:17.233 回答
5

避免在循环后重复条件的与语言无关的技术是将标记值附加到输入数据,例如,如果delimiter附加到末尾,string则条件在split_by(). 典型示例:在线性搜索算法中,可以将针附加到大海捞针以避免序列检查结束。

另一种选择是将一些工作委托给一个单独的函数,例如,一个函数计算重复次数,另一个找到最大值,如下所示longest_repetition()

from itertools import groupby

def longest_repetition(iterable):
    return max(groupby(iterable), key=lambda x: sum(1 for _ in x[1]))[0]

如果重复的代码是微不足道的;这可能不值得付出努力。

于 2012-06-22T04:46:19.323 回答
2

在循环结束时需要重新检查条件并不少见,该条件也在循环内进行检查。如果您准备牺牲一点效率,避免重复检查的一种方法是在循环内过度检查它。例如:

def my_longest_repetition(l):
    if not l:
        return None
    most_reps = count = 0
    longest = prv = None
    for i in l:
        count = (count + 1) if i == prv else 1
        if count > most_reps:
            longest = prv
            most_reps = count
        prv = i
    return longest

此代码检查的count > most_reps频率超出了它的需要,但避免了在循环后再次检查它的需要。

不幸的是,这种变化并不适用于所有情况。

于 2012-06-22T04:26:37.220 回答
2

我认为有三种通用方法可以帮助您避免在循环结束时重复代码。对于这三个问题,我将使用一个与您自己的问题略有不同的示例问题,计算字符串中的单词。这是一个“默认”版本,就像您的代码一样,在循环结束时重复一些逻辑:

from collections import Counter

def countWords0(text):
    counts = Counter()
    word = ""

    for c in text.lower():
        if c not in "abcdefghijklmnopqrstuvwxyz'-":
            if word:
                counts[word] += 1
            word = ""
        else:
            word += c

    if word:
        counts[word] += 1 # repeated code at end of loop

    return counts

第一种方法是在每个字符之后进行(一些)“子序列结束”处理,以便如果序列在该字符之后立即结束,则簿记是正确的。在您的示例中,您可以消除您的“其他”条件并每次运行其中的代码。(这是 sergerg 的回答。)

不过,这对于某些类型的检查可能并不容易。为了计算单词,您需要添加一些额外的逻辑,以避免从您处理的“部分”子序列中积累垃圾。这是执行此操作的代码:

def countWords1(text):
    counts = Counter()
    word = ""

    for c in text.lower():
        if c not in "abcdefghijklmnopqrstuvwxyz'-":
            word = ""
        else:
            if word:
                counts[word] -= 1 # new extra logic
            word += c
            counts[word] += 1 # this line was moved from above

    return counts + Counter() # more new stuff, to remove crufty zero-count items

第二种选择是将标记值附加到序列的末尾,这将触发所需的“子序列结束”行为。如果您需要避免哨兵污染您的数据(尤其是数字之类的东西),这可能会很棘手。对于最长连续子序列问题,您可以添加不等于序列中最后一项的任何值。None可能是一个不错的选择。对于我的计数单词示例,非单词字符(例如换行符)将执行以下操作:

def countWords2(text):
    counts = Counter()
    word = ""

    for c in text.lower() + "\n": # NOTE: added a sentinel to the string!
        if c not in "abcdefghijklmnopqrstuvwxyz'-":
            if word:
                counts[word] += 1
            word = ""
        else:
            word += c

    # no need to recheck at the end, since we know we ended with a space

    return counts

第三种方法是更改​​代码的结构以避免迭代可能意外结束的序列。您可以使用生成器来预处理序列,就像使用groupbyfrom的其他答案一样itertools。(当然,生成器函数,如果非要自己写,可能也有类似的问题。)

对于我的字数统计示例,我可以使用模块中的正则表达式re来查找单词:

from re import finditer

def countWords3(text):
    return Counter(match.group() for match in
                   finditer("[\w'-]+", text.lower()))

输出,当给出适当的 Pythonic 文本时(所有四个版本的 countWords 都相同):

>>> text = """Well, there's egg and bacon; egg sausage and bacon;
              egg and spam; egg bacon and spam; egg bacon sausage and spam;
              spam bacon sausage and spam; spam egg spam spam bacon and spam;
              spam sausage spam spam bacon spam tomato and spam;
              spam spam spam egg and spam; spam spam spam spam spam spam
              baked beans spam spam spam; or Lobster Thermidor a Crevette
              with a mornay sauce served in a Provencale manner with shallots
              and aubergines garnished with truffle pate, brandy and with a
              fried egg on top and spam."""

>>> countWords0(text)
Counter({'spam': 28, 'and': 12, 'egg': 8, 'bacon': 7, 'sausage': 4, 'a': 4,
         'with': 4, 'well': 1, 'lobster': 1, 'manner': 1, 'in': 1, 'top': 1,
         'thermidor': 1, "there's": 1, 'truffle': 1, 'provencale': 1,
         'sauce': 1, 'brandy': 1, 'pate': 1, 'shallots': 1, 'garnished': 1,
         'tomato': 1, 'on': 1, 'baked': 1, 'aubergines': 1, 'mornay': 1,
         'beans': 1, 'served': 1, 'fried': 1, 'crevette': 1, 'or': 1})
于 2012-06-22T06:23:52.430 回答
1

迭代器提供了一种打破循环的好方法:

def longest_repetition(l):
  i=iter(l)
  n=next(i,None)
  longest=None
  most_reps=0
  while n is not None:
    p=n
    count=0
    while p==n:
      n=next(i,None)
      count+=1
    if count>most_reps:
      most_reps=count
      longest=p
  return longest

许多语言都有类似的概念。

于 2012-06-22T07:20:47.450 回答