2

〜300.000タプルを含むセットがあります

In [26]: sa = set(o.node for o in vrts_l2_5) 
In [27]: len(sa)
Out[27]: 289798
In [31]: random.sample(sa, 1)
Out[31]: [('835644', '4696507')]

ここで、最初の 4 つの「数字」など、共通の部分文字列に基づいて要素を検索したいと考えています (実際、要素は文字列です)。これが私のアプローチです：

def lookup_set(x_appr, y_appr):
    return [n for n in sa if n[0].startswith(x_appr) and n[1].startswith(y_appr)]

In [36]: lookup_set('6652','46529')
Out[36]: [('665274', '4652941'), ('665266', '4652956')]

より効率的な、つまりこれへのより速い方法はありますか?

4

7 に答える 7

2

タプルの2 つのソートされたコピーを保持する余裕があればO(log(n) + m)、時間内にそれを行うことができます。つまり、単純なアプローチよりも漸近的に遅くなりますが、特定の数のクエリを実行する必要がある場合（ほぼ確実に非常に小さい）、それは報われます。nmO(nlog(n))log(n)

二分法を使用して、正しい最初の値と正しい 2 番目の値を持ち、これらのセットと交差する候補を見つけることができるという考え方です。

ただし、奇妙な種類の比較が必要であることに注意してください。指定された引数で始まるすべての文字列を処理します。これは単純に、最も右側の出現箇所を検索するときに、キーに9s を入力する必要があることを意味します。

完全に機能する (あまりテストされていませんが) コード:

from random import randint
from operator import itemgetter

first = itemgetter(0)
second = itemgetter(1)

sa = [(str(randint(0, 1000000)), str(randint(0, 1000000))) for _ in range(300000)]
f_sorted = sorted(sa, key=first)
s_sorted = sa
s_sorted.sort(key=second)
max_length = max(len(s) for _,s in sa)

# See: bisect module from stdlib
def bisect_right(seq, element, key):
    lo = 0
    hi = len(seq)
    element = element.ljust(max_length, '9')
    while lo < hi:
        mid = (lo+hi)//2
        if element < key(seq[mid]):
            hi = mid
        else:
            lo = mid + 1
    return lo


def bisect_left(seq, element, key):
    lo = 0
    hi = len(seq)
    while lo < hi:
        mid = (lo+hi)//2
        if key(seq[mid]) < element:
            lo = mid + 1
        else:
            hi = mid
    return lo


def lookup_set(x_appr, y_appr):
    x_left = bisect_left(f_sorted, x_appr, key=first)
    x_right = bisect_right(f_sorted, x_appr, key=first)
    x_candidates = f_sorted[x_left:x_right + 1]
    y_left = bisect_left(s_sorted, y_appr, key=second)
    y_right = bisect_right(s_sorted, y_appr, key=second)
    y_candidates = s_sorted[y_left:y_right + 1]
    return set(x_candidates).intersection(y_candidates)

そして、最初のソリューションとの比較:

In [2]: def lookup_set2(x_appr, y_appr):
   ...:     return [n for n in sa if n[0].startswith(x_appr) and n[1].startswith(y_appr)]

In [3]: lookup_set('123', '124')
Out[3]: set([])

In [4]: lookup_set2('123', '124')
Out[4]: []

In [5]: lookup_set('123', '125')
Out[5]: set([])

In [6]: lookup_set2('123', '125')
Out[6]: []

In [7]: lookup_set('12', '125')
Out[7]: set([('12478', '125908'), ('124625', '125184'), ('125494', '125940')])

In [8]: lookup_set2('12', '125')
Out[8]: [('124625', '125184'), ('12478', '125908'), ('125494', '125940')]

In [9]: %timeit lookup_set('12', '125')
1000 loops, best of 3: 589 us per loop

In [10]: %timeit lookup_set2('12', '125')
10 loops, best of 3: 145 ms per loop

In [11]: %timeit lookup_set('123', '125')
10000 loops, best of 3: 102 us per loop

In [12]: %timeit lookup_set2('123', '125')
10 loops, best of 3: 144 ms per loop

ご覧のとおり、このソリューションは240-1400(これらの例では) 単純なアプローチよりも約 1 倍高速です。

マッチの数が多い場合:

In [19]: %timeit lookup_set('1', '2')
10 loops, best of 3: 27.1 ms per loop

In [20]: %timeit lookup_set2('1', '2')
10 loops, best of 3: 152 ms per loop

In [21]: len(lookup_set('1', '2'))
Out[21]: 3587
In [23]: %timeit lookup_set('', '2')
10 loops, best of 3: 182 ms per loop

In [24]: %timeit lookup_set2('', '2')
1 loops, best of 3: 212 ms per loop

In [25]: len(lookup_set2('', '2'))
Out[25]: 33053

ご覧のとおり、一致の数が合計サイズの約 10% であっても、このソリューションの方が高速です。ただし、すべてのデータを一致させようとすると、次のようになります。

In [26]: %timeit lookup_set('', '')
1 loops, best of 3: 360 ms per loop

In [27]: %timeit lookup_set2('', '')
1 loops, best of 3: 221 ms per loop

これは非常に特殊なケースですが、（それほどではありませんが）遅くなります。ほぼすべての要素に頻繁に一致するとは思えません。

データにかかる時間sortは非常に短いことに注意してください。

In [13]: from random import randint
    ...: from operator import itemgetter
    ...: 
    ...: first = itemgetter(0)
    ...: second = itemgetter(1)
    ...: 
    ...: sa2 = [(str(randint(0, 1000000)), str(randint(0, 1000000))) for _ in range(300000)]

In [14]: %%timeit
    ...: f_sorted = sorted(sa2, key=first)
    ...: s_sorted = sorted(sa2, key=second)
    ...: max_length = max(len(s) for _,s in sa2)
    ...: 
1 loops, best of 3: 881 ms per loop

ご覧のとおり、2 つの並べ替えられたコピーを実行するのに 1 秒もかかりません。実際には、上記のコードは 2 番目のコピーを「その場で」ソートするため、わずかに高速になります (ただし、tim-sort にはまだO(n)メモリが必要な場合があります)。

これは、約 6 ～ 8 個を超えるクエリを実行する必要がある場合、このソリューションの方が高速であることを意味します。

注: python 化された標準ライブラリはbisectモジュールを提供します。ただし、パラメーターは許可されていませんkey(Guido がそれを望んでいたと読んだことは覚えていますが、将来追加される可能性があります)。したがって、直接使用したい場合は、「decorate-sort-undecorate」イディオムを使用する必要があります。

それ以外の：

f_sorted = sorted(sa, key=first)

やったほうがいい：

f_sorted = sorted((first, (first,second)) for first,second in sa)

つまり、キーをタプルの最初の要素として明示的に挿入します。その後、('123', '')as element を使用してbisect_*関数に渡すことができ、正しいインデックスが見つかるはずです。

私はこれを避けることにしました。モジュールのソースからコードをコピーして貼り付け、わずかに変更して、ユースケースによりシンプルなインターフェイスを提供します。

最後の注意: タプル要素を整数に変換できれば、比較はより高速になります。ただし、ほとんどの場合、セットの交差を実行するのにまだ時間がかかるため、パフォーマンスがどの程度向上するかは正確にはわかりません。

于 2013-10-03T12:28:08.747 に答える
1

整数操作は、文字列よりもはるかに高速です。（そしてメモリも小さい）

したがって、代わりに整数を比較できれば、はるかに高速になります。次のようなものがうまくいくと思います：

sa = set(int(o.node) for o in vrts_l2_5)

次に、これはあなたのために働くかもしれません：

def lookup_set(samples, x_appr, x_len, y_appr, y_len):
    """

    x_appr == SSS0000  where S is the digit to search for
    x_len == number of digits to S (if SSS0000 then x_len == 4)
    """
    return ((x, y) for x, y in samples if round(x, -x_len) ==  x_appr and round(y, -y_len) == y_approx)

また、ジェネレーターを返すため、すべての結果を一度にメモリにロードするわけではありません。

Bakuriu が言及した round メソッドを使用するように更新

于 2013-10-03T09:31:03.413 に答える
0

あるかもしれませんが、それほど多くはありません。str.startswithandandは両方ともショートカット演算子であり (失敗を見つけたら戻ることができます)、タプルのインデックス作成は高速な操作です。ここで費やされる時間のほとんどは、各文字列の startswith メソッドの検索など、オブジェクトの検索に費やされます。おそらく最も価値のあるオプションは、Pypy を介して実行することです。

于 2013-10-03T08:34:30.493 に答える
0

ここでは、「in」メソッドと「find」メソッドを比較しました。

CSV 入力ファイルには、URL のリストが含まれています

# -*- coding: utf-8 -*-

### test perfo str in set

import re
import sys
import time
import json
import csv
import timeit

cache = set()

#######################################################################

def checkinCache(c):
  global cache
  for s in cache:
    if c in s:
      return True
  return False

#######################################################################

def checkfindCache(c):
  global cache
  for s in cache:
    if s.find(c) != -1:
      return True
  return False

#######################################################################

print "1/3-loading pages..."
with open("liste_all_meta.csv.clean", "rb") as f:
    reader = csv.reader(f, delimiter=",")
    for i,line in enumerate(reader):
      cache.add(re.sub("'","",line[2].strip()))

print "  "+str(len(cache))+" PAGES IN CACHE"

print "2/3-test IN..."
tstart = timeit.default_timer()
for i in range(0, 1000):
  checkinCache("string to find"+str(i))
print timeit.default_timer()-tstart

print "3/3-test FIND..."
tstart = timeit.default_timer()
for i in range(0, 1000):
  checkfindCache("string to find"+str(i))
print timeit.default_timer()-tstart

print "\n\nBYE\n"

数秒で結果:

1/3-loading pages...
  482897 PAGES IN CACHE
2/3-test IN...
107.765980005
3/3-test FIND...
167.788629055


BYE

したがって、「in」メソッドは「find」メソッドよりも高速です:)

楽しむ

于 2018-08-18T17:30:54.437 に答える
0

より迅速な解決策は、ディクショナリ dict を作成し、最初の値をキーとして、2 番目の値を値として配置することです。

  1. 次に、dict の順序付きキー リストで x_appr に一致するキーを検索します (順序付きリストを使用すると、キー リストの検索を二分法などで最適化できます)。これにより、k_list などの名前のキー リストが提供されます。

  2. 次に、k_list にキーがあり、y_appr に一致する dict の値を検索します。

k_list に追加する前に、2 番目のステップ (y_appr に一致する値) を含めることもできます。そのため、k_list には dict の正しい要素のすべてのキーが含まれます。

于 2013-10-03T08:40:06.790 に答える