4

Python 2.6 で、それぞれ同じサイズの整数の 2 つのリストを比較しようとしています。必要な比較は、リスト 1 の最初の項目とリスト 2 の最初の項目、リスト 1 の 2 番目の項目とリスト 2 の 2 番目の項目などを比較し、すべてのリスト項目が続く場合に結果を返すことです。比較基準は同じ。次のように動作する必要があります。

list1 = [1,1,1,1]
list2 = [2,1,2,3]
compare(list1,list2) 
# returns a "list 1 is <= list 2" response.

list1 = [4,1,4,3]
list2 = [2,1,2,3]
compare(list1,list2) 
# returns a "list 1 is >= list 2" response.

list1 = [3,2,3,2]
list2 = [1,4,1,4]
compare(list1,list2) 
# returns None— some items in list1 > list2, and some items in list2 > list1.

次のブロックのようなコードを書くことができると考えましたが、それが最も効率的かどうかはわかりません。私のプログラムはこのメソッドをたくさん呼び出すので、できるだけ合理化したいと考えています。

def compare(list1,list2):
    gt_found = 0
    lt_found = 0
    for x in range(len(list1)):
        if list1[x] > list2[x]:
            gt_found += 1
        elif list1[x] < list2[x]:        
            lt_found += 1
        if gt_found > 0 and lt_found > 0:
            return None   #(some items >, some items <)
    if gt_found > 0:
        return 1          #(list1 >= list2)
    if lt_found > 0:
        return -1         #(list1 <= list2)
    return 0              #(list1 == list2)

それはすでに得られるのと同じくらい良いですか（nのbig-O）、またはそれを行うためのより高速な方法（または代わりにシステム関数を使用する方法）はありますか？

明確化: 「None」を返すケースが最も頻繁に発生すると予想されるため、これは重要です。

4

3 に答える 3

5

zip素晴らしい機能をご存知ですか？

import itertools

def compare(xs, ys):
  all_less = True
  all_greater = True

  for x, y in itertools.izip(xs, ys):
    if not all_less and not all_greater:
      return None
    if x > y:
      all_less = False
    elif x < y:
      all_greater = False

  if all_less:
    return "list 1 is <= list 2"
  elif all_greater:
    return "list 1 is >= list 2"
  return None  # all_greater might be set False on final iteration

Zip は 2 つのリストを取り (xsこのys場合は、任意の名前を付けます)、一連のタプルの反復子を作成します。

izip([1,2,3,4], [4,3,2,1]) == [(1,4), (2,3), (3,2), (4,1)]

このようにして、両方のリストを同時に反復処理し、各値をタンデムで比較できます。時間計算量は O(n) である必要があります。n はリストのサイズです。

>= または <= 条件が満たされない場合は、早期に返されます。

アップデート

James Mattaが指摘しているように、Python 2itertools.izipの標準よりも優れたパフォーマンスを発揮しますzip。これは Python 3 には当てはまりません。Python 3 では、標準が古いバージョンと同じzipように機能します。izip

于 2013-10-09T21:24:05.550 に答える
5

numpy ベースのベクトル化された比較を検討できます。

import numpy as np

a = [1,1,1,2]
b = [2,2,4,3]

all_larger = np.all(np.asarray(b) > np.asarray(a))  # true if b > a holds elementwise

print all_larger

        True

明らかに、あなたはあなたの答えを持つように物事を設計することができます.

all_larger = lambda b,a : np.all(np.asarray(b) > np.asarray(a))

if all_larger(b,a):
       print "b > a"
elif all_larger(a,b):
       print "a > b"

else
       print "nothing!"

など、あらゆるタイプの比較が<, >, <=, >=,可能です。

于 2013-10-09T21:41:19.293 に答える