1

さまざまな長さの文字列の並べ替えとカスタムハッシュ関数のパフォーマンスを比較していますが、結果は少し驚くべきものです。次のコードの関数prime_hash（特にprime_hash2）は、sort_hashよりもパフォーマンスが優れていると期待していましたが、その逆が当てはまります。誰かがパフォーマンスの違いを説明できますか？誰かが代替ハッシュを提供できますか？[関数は、文字の同じ分布を含む文字列に対して同じ値を生成し、他のすべての文字列に対して異なる値を生成する必要があります]。

これが私が得ている結果です：

For strings of max length: 10
sort_hash: Time in seconds: 3.62555098534
prime_hash: Time in seconds: 5.5846118927
prime_hash2: Time in seconds: 4.14513611794
For strings of max length: 20
sort_hash: Time in seconds: 4.51260590553
prime_hash: Time in seconds: 8.87842392921
prime_hash2: Time in seconds: 5.74179887772
For strings of max length: 30
sort_hash: Time in seconds: 5.41446709633
prime_hash: Time in seconds: 11.4799649715
prime_hash2: Time in seconds: 7.58586287498
For strings of max length: 40
sort_hash: Time in seconds: 6.42467713356
prime_hash: Time in seconds: 14.397785902
prime_hash2: Time in seconds: 9.58741497993
For strings of max length: 50
sort_hash: Time in seconds: 7.25647807121
prime_hash: Time in seconds: 17.0482890606
prime_hash2: Time in seconds: 11.3653149605

そしてここにコードがあります：

#!/usr/bin/env python

from time import time
import random
import string
from itertools import groupby

def prime(i, primes):
   for prime in primes:
      if not (i == prime or i % prime):
         return False
   primes.add(i)
   return i

def historic(n):
   primes = set([2])
   i, p = 2, 0
   while True:
      if prime(i, primes):
         p += 1
         if p == n:
            return primes
      i += 1

primes = list(historic(26))

def generate_strings(num, max_len):
   gen_string = lambda i: ''.join(random.choice(string.lowercase) for x in xrange(i))
   return [gen_string(random.randrange(3, max_len)) for i in xrange(num)]

def sort_hash(s):
   return ''.join(sorted(s))

def prime_hash(s):
   return reduce(lambda x, y: x * y, [primes[ord(c) - ord('a')] for c in s])

def prime_hash2(s):
   res = 1
   for c in s:
      res = res * primes[ord(c) - ord('a')]
   return res

def dotime(func, inputs):
   start = time()
   groupby(sorted([func(s) for s in inputs]))
   print '%s: Time in seconds: %s' % (func.__name__, str(time() - start))

def dotimes(inputs):
   print 'For strings of max length: %s' % max([len(s) for s in inputs])
   dotime(sort_hash, inputs)
   dotime(prime_hash, inputs)
   dotime(prime_hash2, inputs)

if __name__ == '__main__':
   dotimes(generate_strings(1000000, 11))
   dotimes(generate_strings(1000000, 21))
   dotimes(generate_strings(1000000, 31))
   dotimes(generate_strings(1000000, 41))
   dotimes(generate_strings(1000000, 51))
4

2 に答える 2

2

sort_hash（O（n * log n））がO（n）である他の関数よりも速い理由を質問していると思います。

その理由は、あなたnが小さすぎlog(n)て重要ではないからです。

Pythonsort()はCでコーディングされています。算術関数をCでコーディングした場合n*log(n)、n

余談ですが、繰り返しアイテムがたくさんある場合は、ティムソートの方が優れていn*log(n)ます。256文字しかないため、文字列が算術バージョンの利点を得るのに十分な長さになるずっと前に、ティムソートがO（n）に近づくことに気付くでしょう。

于 2012-11-23T02:08:12.737 に答える
0

BoppreHからの入力に基づいて、Cで実装された「ソート済み」ベースのバージョンよりも優れたバージョンの算術ベースのハッシュを取得することができました。

primes = list(historic(26))
primes = {c : primes[ord(c) - ord('a')] for c in string.lowercase}

def prime_hash2(s):
   res = 1
   for c in s:
      res = res * primes[c]
   return res
于 2012-11-28T09:03:24.377 に答える