1

テーブルルックアップからの int の反復子があり、それらのマルチセットが特定の固定 "マルチセット" に含まれているかどうかを確認する必要がありますms。現在、ms最初に並べ替えてから、イテレータで int を並べ替え、次のように (並べ替えられたリストの) マルチセットの包含を確認します。

vals = sorted(my_vals)
for it in ... :
    test_vals = sorted( i for i in it )
    if is_sublist(test_vals,vals):
        # do stuff

どこ

def is_sublist(L1,L2):
    m = len(L1)
    n = len(L2)
    i = j = 0
    while j <= n:
        if i == m:
            return True
        elif j == n:
            return False
        a,b = L1[i], L2[j]
        if a == b:
            i += 1
            j+= 1
        elif a > b:
            j += 1
        else:
            return False
  • 通常、私のリストはかなり短い (1 ～ 20 要素)
  • を使ってみたCounterのですが、封じ込め試験の時間的アドバンテージよりも、初期化の時間的アドバンテージの方が悪いです。
  • 私はこれを ~10^6 回行うので、おそらく 1 回で行う必要がありますcython

どんなアイデアや指針もいいでしょう - ありがとう！(早々に投稿ボタン押しちゃってすみません…)

4

1 に答える 1

0 
# edit: second attempt in response to Bakuriu's comment
#
from collections import Counter
from itertools import groupby
multiset = Counter(sorted(vals)) # only create one Counter object
for it in ...:
    grouped = groupby(sorted(it))
    if all(len(list(g)) <= multiset[k] for k, g in grouped):
        # do stuff



from operator import eq
# if you are using Python 2
from itertools import izip as zip
from itertools import starmap

vals = sorted(my_vals)
for it in ...:
    test_vals = sorted(it)
    zipped = zip(test_vals, vals)
    # check if test_vals' multiset is contained 
    # in vals' multiset but bale out as soon as
    # non-matching values are found.
    if all(starmap(eq, zipped)):
        # do stuff
于 2014-07-14T12:26:02.623 に答える