3

私はいくつかのハッカソンに参加しています。コードを書くだけでは十分ではないことを理解し始めています。コードを最適化する必要があります。それが私の質問につながります。ここに私が直面した2つの質問があります。

def pairsum(numbers, k)
    """Write a function that returns two values in numbers whose sum is K"""
    for i, j in numbers:
        if i != j:
            if i+j == k
                return i, j

この関数を書きました。そして、私は最適化に行き詰まっていました。

次の問題。

string = "ksjdkajsdkajksjdalsdjaksda"

def dedup(string):
    """ write a function to remove duplicates in the variable string"""
    output = []
    for i in string:
        if i not in output:
            output.append(i)

これらは、私が作成した 2 つの非常に単純なプログラムです。しかし、私はこの後最適化に行き詰まっています。さらに、コードを最適化すると、複雑さがどのように軽減されるのでしょうか? 任意のポインターが役立ちます。前もって感謝します。

4

5 に答える 5

4

最も効率的な Python のイディオムを知っていることと、反復を減らして早期に解決できるコードを設計することは、最適化の主要な部分です。以下にいくつかの例を示します。

通常、リスト リスト内包表記とジェネレーターは最速です。

for簡単なネストされたアプローチでは、ジェネレーターはループよりも高速です。

def pairsum(numbers, k):
    """Returns two unique values in numbers whose sum is k"""
    return next((i, j) for i in numbers for j in numbers if i+j == k and i != j)

in numbersこれは、最大で 1 回の反復しか実行されず、可能性のある結果が次の場合を除き、チェックされないため、おそらく平均して高速ですk-i != i。

def pairsum(numbers, k):
    """Returns two unique values in numbers whose sum is k"""
    return next((k-i, i) for i in numbers if k-i != i and k-i in numbers)

出力:

>>> pairsum([1,2,3,4,5,6], 8)
(6, 2)

注: ドキュメント文字列にはタプルについて言及されていないため、数値はフラット リストであると想定しました。これは、コンペで予想される問題をより困難にします。

2番目の問題については、単に使用するのではなく、独自の関数を作成する場合は、次のようになりました''.join(set(s))。

def dedup(s):
    """Returns a string with duplicate characters removed from string s"""
    output = ''
    for c in s:
        if c not in output:
            output += c
    return output

stringヒント:名前として使用しないでください

次のこともできます。

def dedup(s):
    for c in s:
        s = c + s.replace(c, '')
    return s

またははるかに高速な再帰バージョン:

def dedup(s, out=''):
    s0, s = s[0], s.replace(s[0], '')
    return dedup(s, n + s0) if s else out + s0

setただし、多くの重複がない文字列ほど高速ではありません。

def dedup(s):
    return ''.join(set(s))

注:set()は残りの文字の順序を保持しませんが、他のアプローチは最初の出現に基づいて順序を保持します。

于 2013-06-29T00:35:01.760 に答える
1

最初のプログラムは少しあいまいです。タプルnumbersのリストか何かだと思いますか？のように[(1,2), (3,4), (5,6)]？もしそうなら、あなたのプログラムは複雑さの観点からはかなり良いです - それは O(n) です。おそらく、もう少しPythonicなソリューションが必要ですか? これをクリーンアップする最も適切な方法は、条件に参加することです。

if i != j and i + j == k:

しかし、これは読みやすさを向上させるだけです。ブール演算も追加される可能性があると思うので、最適化ではないかもしれません。

あなたのプログラムが、合計が k になる最初の数のペアを返すことを意図しているかどうかはわかりませんが、この要件を満たすすべてのペアが必要な場合は、内包表記を記述できます。

def pairsum(numbers, k):
    return list(((i, j) for i, j in numbers if i != j and i + j == k))

その例では、リスト内包表記の代わりにジェネレーター内包表記を使用して、リソースを節約しました。ジェネレーターはイテレーターのように機能する関数です。つまり、必要なときにのみデータを提供することでメモリを節約できます。これは遅延反復と呼ばれます。

述語が を返すセットから要素のみを返す関数であるフィルターを使用することもできますTrue。（つまり、ある条件を満たす要素です。）

import itertools
def pairsum(numbers, k):
    return list(itertools.ifilter(lambda t: t[0] != t[1] and t[0] + t[1] == k, ((i, j) for i, j in numbers)))

しかし、これは私の意見では読みにくいです。

2 番目のプログラムは、setを使用して最適化できます。小学校や大学で学んだ離散数学を思い出すと、集合は一意の要素の集まりです。つまり、集合には重複する要素はありません。

def dedup(mystring):
    return set(mystring)

コレクションの一意の要素を見つけるアルゴリズムは、一般に、空間で O(1) の場合、O(n^2) になります。より多くのメモリを割り当てることができる場合は、二分探索ツリーを使用して時間の複雑さを O(n log n) に減らします。これは、おそらく Python セットの実装方法です。

入力がすでに一意の要素のみを持つ文字列である場合、同じ量のスペースを占める可能性のある新しいリストを作成したため、ソリューションには O(n^2) 時間だけでなく O(n) スペースもかかりました。文字列内のすべての文字、出力を反復処理しました。それは本質的に O(n^2) です (ただし、実際には O(n*m) だと思いますが、何でも)。その理由がわかると思います。Binary Search Tree の記事を読んで、コードがどのように改善されるかを確認してください。二度と再実装したくありません... 1年生はとても大変でした!

于 2013-06-29T00:26:14.007 に答える
0

最適化の鍵は、基本的に、実行する必要があるプリミティブ ステップの総数に関して、コードの作業を減らす方法を見つけることです。ネストされたループのような制御構造を使用するコードは、必要なプリミティブ ステップの数にすぐに貢献します。したがって、最適化とは、多くの場合、完全なリストを反復するループをより巧妙なものに置き換えることです。

最適化されていないpairum()メソッドを使用できるように少し変更する必要がありました。

def pairsum(numbers, k):
    """
    Write a function that returns two values in numbers whose sum is K
    """
    for i in numbers:
        for j in numbers:
           if i != j:
              if i+j == k:
                 return i,j

ここでは、2 つのループがあり、一方が他方の内側にネストされています。このようなメソッドの時間計算量を説明するとき、O(n²) であるとよく言います。渡された数値配列の長さが n に比例して増加するため、プリミティブ ステップの数は n² に比例して増加します。具体的には、i+j == k条件は正確にlen(number)**21 回評価されます。

ここでできる巧妙な方法は、O(n log(n)) のコストで配列を事前に並べ替えることです。これにより、並べ替えられた配列の各要素を最大 1 回評価することで、正しい答えに絞り込むことができます。

def fast_pairsum(numbers, k):
    sortedints = sorted(numbers)
    low = 0
    high = len(numbers) - 1
    i = sortedints[0]
    j = sortedints[-1]
    while low < high:
        diff = i + j - k
        if diff > 0:
            # Too high, let's lower
            high -= 1
            j = sortedints[high]
        elif diff < 0:
            # Too low, let's increase.
            low += 1
            i = sortedints[low]
        else:
            # Just right
            return i, j

    raise Exception('No solution')

この種の最適化は、問題のサイズが大きくなったときにのみ、実際に問題になり始めます。pairsum()私のマシンでは、との間の損益分岐点はfast_pairsum()、13 個の整数を含む数値配列です。配列が小さいほどpairsum()高速であり、配列が大きいほどfast_pairsum()高速です。サイズが大きくfast_pairsum()なるにつれて、最適化されていない よりも大幅に高速になりpairsum()ます。

賢明な方法はdedup()、出力リストを直線的にスキャンして、既に文字を見たかどうかを確認する必要がないようにすることです。これは、通常のリストの O(n) ルックアップ コストではなく、O(log(n)) ルックアップ コストを持つセットで見た文字に関する情報を保存することで実行できます。

外側のループでは、総コストは O(n²) ではなく O(n log(n)) になります。

def fast_dedup(string):
    # if we didn't care about the order of the characters in the
    # returned string we could simply do
    # return set(string)

    seen = set()
    output = [] 
    seen_add = seen.add  
    output_append = output.append
    for i in string:
        if i not in seen:
            seen_add(i)
            output_append(i)

    return output

dedup()私のマシンでは、との間の損益分岐点はfast_dedup()、長さ 30 の文字列です。

このfast_dedup()方法は、別の簡単な最適化のトリックも示しています。それは、できるだけ多くのコードをループ本体の外に移動することです。andオブジェクト内のadd()andappend()メンバーの検索には時間がかかるため、ループ本体の外で一度実行し、ループ本体内で繰り返し使用される変数にメンバーへの参照を格納する方が安価です。seenoutput

于 2013-06-29T01:02:09.307 に答える
0

Python を適切に最適化するには、問題に適したアルゴリズムと、そのアルゴリズムに近い Python イディオムを見つける必要があります。あなたのpairsum例は良い例です。まず、実装が間違っているように見えます —numbers数字のペアのシーケンスではなく、数字のシーケンスである可能性が最も高いです。したがって、素朴な実装は次のようになります。

def pairsum(numbers, k)
    """Write a function that returns two values in numbers whose sum is K"""
    for i in numbers:
        for j in numbers:
            if i != j and i + j != k:
                return i, j

これは、 の長さであるn^2反復を実行します。小さいs の場合、これは問題ではありませんが、数百になるとネストされたループが明らかに遅くなり、数千になると使用できなくなります。nnumbersnnn

最適化は、内側のループと外側のループの違いを認識することです。外側のループはnumbers1 回だけトラバースし、避けられません。ただし、内側のループは、他の数値 ( である必要があります) が実際に存在することを確認するためにのみ使用されます。k - iこれは単なるルックアップであり、辞書を使用するか、さらに良いことに、セットを使用して非常に高速にすることができます。

def pairsum(numbers, k)
    """Write a function that returns two values in numbers whose sum is K"""
    numset = set(numbers)
    for i in numbers:
        if k - i in numset:
            return i, k - i

これは、Python でコード化されたループの代わりに組み込み操作 (set lookup) を使用しているため、定数だけ高速であるだけではありません。setルックアップを行うよりスマートなアルゴリズムを備えているため、実際には作業が少なくなり、一定時間で実行されます。

同様の方法で最適化dedupすることは、読者の演習として残します。

于 2013-06-29T07:21:10.457 に答える