python - リストからの整数

Question

リストから正と負の同じ整数を取得する必要があります。たとえば、リストが [0,1,-1,3] で構成されている場合、1 -1 が返されます。これまでのところ私は持っています。

s = []
for i in a:
    if i in s
        s.append(i and -i)
print s

Answer 1

これを英語から Python に直接翻訳してみましょう。

最初に、英語の説明を正確に取得する必要があります: にあるすべての値が必要でa、その否定も にありaます。

Python では、次のようになります。

[value for value in a if -value in a]

---

ただし、100 万の値がある場合-value in a、各値に対して平均で 50 万の値を検索する必要があります。つまり、合計で 5 兆回の比較を行うことになります。あなたの仲間の学生の 1 人がそれを提出したようで、約 1 秒かかるはずのいくつかのサンプル データに 1 分以上かかったことで怒られました。

を使用して修正できますset。セット内の値を探すには、すべての値と比較するのではなく、1 回のハッシュ ルックアップと 1 回の比較が必要です。そう：

s = set(a)
[value for value in a if -value in s]

---

さらに最適化するには、さまざまな方法があります。最も明白なのは、重複を保持したり、値を順番に返す必要がない場合は、元のリストの代わりにセットを反復処理することです。しかし、他にも賢いアイデアがあります。いくつかの比較とともに、それらの多くをここで見ることができます。

Answer 2

正と負の両方のカウンター部分を持つ数値のペアのみを取得するには、次のようにリスト内包表記を使用できます。

>>> a = [0, 1, -1, 3]
>>> 
>>> [val for val in a if -val in a]
[0, 1, -1]

期待どおり、も取得されることに注意してください0。それが望ましくない場合は、明示的なチェックも追加してください。

Answer 3

ループ ソリューション:

s = []
for i in a:
    if -i in a:
        s.append(i)

print s

フィルター ソリューション:

s = filter(lambda x: -x in s, s)

リスト理解ソリューション:

[x for x in s if -x in s]

解決策を注意深く見てください。-i と i を同時に追加しようとすると、重複した値が追加されます。また、@kindall が述べたように、両方の for ループで list a を使用する必要があります。

これは、ソリューションのパフォーマンス ベンチマークです。

これは、ソリューションのパフォーマンス ベンチマークです。

for ループには驚かされたと言わざるを得ません...

PS: 答えは python 2.7 用です。Python 3 では、map、filter などはレイであり、それらを評価するには list(filter(lambda x: -x in s, s)) のようなものを使用する必要があります。

Answer 4

index がどのように実装されているかは見ていませんが、おそらくこれは O(n^2) ソリューションです。

#!/usr/bin/env python

l = [ 1, 2 , -1 , 3]

for i in l:
    try:
        k = l.index(-1 * i )
        print i
    except ValueError as e:
        pass

より良いアプローチは次のとおりです。

1. リストを並べ替える: nlogn
2. 次に、リスト内の各要素に対して、現在の要素の否定をバイナリ検索します。そのために for ループを実行できます。ヒットした場合は、要素を印刷します。これも nlogn になります。

したがって、nlogn 時間で必要なことを達成できます。