16

ループを使用するとき、私はしばしば少しのコードを2回書くことになります。たとえば、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

この場合、カウントが以前に最も繰り返された要素よりも大きいかどうかを2回チェックしています。これは、現在の要素が最後の要素と異なる場合と、リストの最後に到達した場合の両方で発生します。

文字列を文字ごとに解析するときにも、これに何度か遭遇しました。また、最大で約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 ++/etcなどのコンパイル言語ではわかりません。コンパイラーは、同じことを行う場合にifブロックをループから移動するなど、さまざまな種類のループ最適化を実行します。

さまざまなスニペットの実行時間を比較しました。

  • @JFSebastian-8.9939801693
  • @srgerg-3.13302302361
  • あなたのもの-2.8182990551。

トレーリングifがあなたに最高の時間を与えるというのは一般化ではありません。私のポイントは、アルゴリズムに従って、最適化してみることです。最後に何も問題はありませんif。おそらく代替ソリューションは高価です。

入力した2番目の例について: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

将来、このようなアルゴリズムを書くことを考えるための私の推奨事項は、1つの関数ですべてを実行しないようにすることです。「シーケンス内の等しいアイテムの各シーケンスを小さなシーケンスにグループ化する」など、解決しようとしている問題を解決する小さな関数について考えてみてください。

また、もちろん、上記のアルゴリズムの文字である必要はありません。グループ化可能なものであれば何でもかまいません。

編集:OPの編集に応じて、クラス設定でitertoolsのようなライブラリを使用/知ることは許可されないだろうと思いましたが、外部ライブラリに依存することを提案していませんでしたが、もっと考える必要があります問題をより小さなサブ問題に分割することによって問題について。したがって、この場合は、独自groupbyに実装して使用します。

于 2012-06-22T04:29:17.233 に答える
5

ループの後に条件が繰り返されないようにするための言語に依存しない手法は、入力データに番兵値を追加することです。たとえば、delimiter最後に追加された場合string、条件はで必要ありませんsplit_by()。標準的な例:線形探索アルゴリズムでは、シーケンスチェックの終了を回避するために、干し草の山に針を追加できます。

もう1つのオプションは、一部の作業を別の関数に委任することです。たとえば、1つの関数は繰り返し回数をカウントし、もう1つの関数は次のように最大値を検出し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

ループ内でもチェックされていたループの最後で条件を再チェックする必要があることは珍しくありません。効率を少し犠牲にする準備ができている場合、繰り返しチェックを回避する1つの方法は、ループ内でそれをオーバーチェックすることです。例えば:

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

ループの最後でコードを繰り返さないようにするのに役立つ3つの一般的なアプローチがあると思います。3つすべてについて、文字列内の単語を数える、自分の問題とは少し異なる問題の例を使用します。これが「デフォルト」バージョンで、コードと同様に、ループの最後でいくつかのロジックを繰り返します。

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

最初のアプローチは、すべての文字の後に「サブシーケンスの終了」処理(の一部)を実行することです。これにより、シーケンスがその文字の直後に終了した場合に簿記が正しくなります。あなたの例では、あなたの「else」条件を排除し、その中で毎回コードを実行することができます。(これは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

2番目のオプションは、シーケンスの最後に番兵の値を追加することです。これにより、目的の「サブシーケンスの終わり」の動作がトリガーされます。番兵がデータを汚染するのを避ける必要がある場合(特に数字など)、これは注意が必要な場合があります。最長連続部分列問題の場合、シーケンスの最後の項目と等しくない値を追加できます。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

3番目のアプローチは、コードの構造を変更して、予期せず終了する可能性のあるシーケンスの反復を回避することです。groupbyfromを使用する他の回答のように、ジェネレーターを使用してシーケンスを前処理することができますitertools。(もちろん、ジェネレーター関数を自分で作成する必要がある場合は、同様の問題が発生する可能性があります。)

re単語カウントの例では、モジュールの正規表現を使用して単語を見つけることができます。

from re import finditer

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

適切なPythonicテキストが与えられた場合の出力(countWordsの4つのバージョンすべてで同じです):

>>> 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 に答える