11

文字を2回含まないという基準で文字列をフィルタリングする必要があります。

  • 文字列は多数あります(たとえば、1.4 兆)。
  • 文字列は短い(約 8 文字)。
  • 文字列は一意です(キャッシュは機能しません)。
  • 文字列には大きな文字セットがあります (Unicode 文字など)。
  • 通常、文字列は基準を満たしています(たとえば、2/3 には繰り返し文字がありません)。

使用コードは次のようになります。

>>> candidate_strings = ["foobnehg", "barfnehg", "bazfnehg"]
>>> result_strings = [s if unique_chars(s) for s in candidate_strings]
>>> print(result_strings)
["barfnehg", "bazfnehg"]

文字列を単純に繰り返す単純なバージョンを実装しました。

def unique_chars_naive(string_given):
    """
    Checks if a given string contains only unique characters.
    This version iterates the given string, saving all occurred characters.
    """
    chars_seen = []
    for char in string_given:
        if char in chars_seen:
            return False
        chars_seen.append(char)
    return True

私の次善の策は を使用することだったsetので、それを実装しました：

def unique_chars_set(string_given):
    """
    Checks if a given string contains only unique characters.
    This version exploits that a set contains only unique entries.
    """
    return len(string_given) == len(set(string_given))

関数をファイルに保存しUniqueCharacters.py、時間を計った：

$ python3 -m timeit -n 100000 --setup='import UniqueCharacters; candidate_strings = ["foobnehg", "barfnehg", "bazfnehg"]' '[UniqueCharacters.unique_chars_naive(s) for s in candidate_strings]'
100000 loops, best of 3: 20.3 usec per loop

$ python3 -m timeit -n 100000 --setup='import UniqueCharacters; candidate_strings = ["foobnehg", "barfnehg", "bazfnehg"]' '[UniqueCharacters.unique_chars_set(s) for s in candidate_strings]'
100000 loops, best of 3: 17.7 usec per loop

これは、unique_chars_setこのデータセットの が約 15 % 高速であることを示しています。

これを行うより速い方法はありますか？多分正規表現で？これを行う標準ライブラリのメソッドはありますか?

4

5 に答える 5

14

必要のないときに最適化を行っているのではないかと思うことから始めましょう。Python は、高度な方法で計算について考えるのをサポートする高度な言語です。読みやすく、エレガントで、再利用可能なソリューションは、多くの場合、非常に高速ですが理解しにくいソリューションよりも優れています。

速度が問題であると判断した場合にのみ、最適化を進める必要があります。おそらく、計算量の多い部分の C 拡張機能を作成することさえできます。

そうは言っても、いくつかのテクニックの比較は次のとおりです。

def unique_chars_set(s):
    return len(s) == len(set(s))

def unique_chars_frozenset(s):
    return len(s) == len(frozenset(s))

def unique_chars_counter(s):
    return Counter(s).most_common(1)[0][1] > 1

def unique_chars_sort(s):
    ss = ''.join(sorted(s))
    prev = ''
    for c in ss:
        if c == prev:
            return False
        prev = c
    return True

def unique_chars_bucket(s):
    buckets = 255 * [False]
    for c in s:
        o = ord(c)
        if buckets[o]:
            return False
        buckets[o] = True
    return True

そして、これがパフォーマンスの比較です（IPythonで）：

In [0]: %timeit -r10 [unique_chars_set(s) for s in candidate_strings]
100000 loops, best of 10: 6.63 us per loop

In [1]: %timeit -r10 [unique_chars_frozenset(s) for s in candidate_strings]
100000 loops, best of 10: 6.81 us per loop

In [2]: %timeit -r10 [unique_chars_counter(s) for s in candidate_strings]
10000 loops, best of 10: 83.1 us per loop

In [3]: %timeit -r10 [unique_chars_sort(s) for s in candidate_strings]
100000 loops, best of 10: 13.1 us per loop

In [4]: %timeit -r10 [unique_chars_bucket(s) for s in candidate_strings]
100000 loops, best of 10: 15 us per loop

結論：set他の多くの明白な方法よりもエレガントで高速です。しかし、違いは非常に小さいので、とにかく問題ではありません。

その他のベンチマークについては、@FrancisAvilaの回答を参照してください。

于 2013-04-01T20:50:44.567 に答える
4

さまざまなアプローチを試すために、タイミングとテストのハーネスを含むファイルを作成しました。

len(set())私が見つけた最速のものは正規表現ベースですが、最速の -ベースのアプローチよりもほんの少しだけ高速です。以下のisunique_reg()機能です。

import re
import array
import collections
import bisect

re_dup_g = re.compile(r'(.).*\1', re.DOTALL)
re_dup_ng = re.compile(r'(.).*?\1', re.DOTALL)


def isunique_reg(s, search=re_dup_g.search):
    return search(s) is None

def isunique_reng(s, search=re_dup_ng.search):
    return search(s) is None

def isunique_set(s, set=set, len=len):
    return len(s) == len(set(s))

def isunique_forset(s, set=set):
    seen = set()
    add = seen.add
    for c in s:
        if c in seen:
            return False
        add(c)
    return True

def isunique_array(s, array=array.array):
    seen = array('u')
    append = seen.append
    for c in s:
        if c in seen:
            return False
        append(c)
    return True

def isunique_deque(s, deque=collections.deque):
    seen = deque()
    append = seen.append
    for c in s:
        if c in seen:
            return False
        append(c)
    return True

def isunique_bisect(s, find=bisect.bisect_right, array=array.array):
    seen = array('u')
    insert = seen.insert
    for c in s:
        i = find(seen, c)
        if i and seen[i-1] == c:
            return False
        insert(i, c)
    return True

def isunique_bisectl(s, find=bisect.bisect_right):
    seen = []
    insert = seen.insert
    for c in s:
        i = find(seen, c)
        if i and seen[i-1] == c:
            return False
        insert(i, c)
    return True

def isunique_count(s, Counter=collections.Counter):
    return Counter(s).most_common(1)[0][1]==1

def isunique_list(s):
    seen = []
    append = seen.append
    for c in s:
        if c in seen:
            return False
        append(c)
    return True


def _test():
    funcs = [f for n,f in globals().items() if n.startswith('isunique_')]
    cases = [
        (u'string given', False),
        (u'string uoqzd', True),
    ]
    for func in funcs:
        for s,rv in cases:
            try:
                assert rv is func(s)
            except AssertionError, e:
                print "%s(%r) is not %r" % (func.__name__, s, rv)
                raise e

def _time():
    import timeit
    funcs = [f for n,f in globals().items() if n.startswith('isunique_')]
    funcs.sort(key=lambda f: f.__name__)
    cases = [
        ('!uniq', u'string given', False),
        ('uniq', u'string uoqzd', True),
    ]

    casenames = [name for name, _, _ in cases]
    fwidth = max(len(f.__name__) for f in funcs)
    timeitsetup = 's = {!r}; from __main__ import {} as u'

    print('{: <{fwidth}s}|{: >15s}|{: >15s}'.format('func', *casenames, fwidth=fwidth))
    print('-'*(fwidth+2+15+15))
    for f in funcs:
        times = [timeit.timeit('u(s)', setup=timeitsetup.format(input, f.__name__)) for _, input, _ in cases]
        print('{: <{fwidth}s}|{: >15.10f}|{: >15.10f}'.format(f.__name__, *times, fwidth=fwidth))

if __name__=='__main__':
    _test()
    _time()

CPython 2.7.1 では、次の結果が得られます (残念ながら、手元に CPython 3.x がありません)。

func            |          !uniq|           uniq
------------------------------------------------
isunique_array  |   6.0237820148|  11.0871050358
isunique_bisect |  10.8665719032|  18.4178640842
isunique_bisectl|   8.2648131847|  13.9763219357
isunique_count  |  23.1477651596|  23.5043439865
isunique_deque  |   4.0739829540|   7.3630020618
isunique_forset |   2.8148539066|   4.1761989594
isunique_list   |   3.6703650951|   6.9271368980
isunique_reg    |   1.7293550968|   2.8794138432
isunique_reng   |   1.9672849178|   3.3768401146
isunique_set    |   2.3157420158|   2.2436211109

文字列が一意でない場合、正規表現ベースのアプローチはセットベースのアプローチよりも高速ですが、正規表現ベースのアプローチの最悪のケースはセットよりも遅いことに気付くでしょう。

于 2013-04-01T20:51:17.027 に答える
0

文字列を並べ替えて繰り返し、同じ文字が連続していないかどうかを確認できますが、これは N*log(N) であるため、set ソリューションよりも高速になるかどうかはわかりません。

于 2013-04-01T20:17:17.590 に答える
0

バケットソートを参照してください。これはソリューションのベースとなるソートアルゴリズムですが、基本的に n 位置の配列を定義し、文字ごとに ASCII または UNICODE 値で指定された位置に配列に配置します (Unicode については以下を参照)。各反復で最大で O(n) 時間の複雑さがあります (配列内の位置が既に使用されている場合は中断できます) ... しかし、単純にできることを考えると、どちらの方法でも大きな違いは見つからないと思います最初にチェックするif(string.length < 255)か、文字列内の有効な値の数をチェックしてください。

このチェックにより、ループは最大でも 255 文字を超えないことが保証されます。これにより、ほとんどの場合、パフォーマンスが心配されるほど小さくなります。

（私はpythonを知りませんが、いくつかのstring.lengthプロパティまたは同等のものがあると確信しています）

@JOHNが述べたように、大きな文字列値またはすべての可能な文字列値をサポートする必要がある場合、これはスペースと時間の両方で問題を引き起こします

于 2013-04-01T20:22:38.383 に答える