python - Python 中字符串排序与自定义哈希函数的性能比较

Question

我正在比较不同长度字符串的排序与自定义哈希函数的性能，结果有点令人惊讶。我预计以下代码中的函数 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))

Answer 1

我认为您在问为什么 sort_hash (O(n*log n) )比其他 O(n) 函数更快。

原因是您的 n 太小，log(n) 不显着。

Python 的 sort() 是用 C 编写的。如果您用 C 编写算术函数，您会发现 n*log(n) 的损失要小得多n的值

旁白:当您有大量重复项时，timsort 会比 n*log(n) 更好。由于只有 256 个字符，您可能会发现在字符串足够长以看到算术版本获得优势之前，timsort 就已经接近 O(n) 了