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

旁白：当你有很多重复的项目时， timsort 会比n*log(n). 由于只有 256 个字符，您可能会发现 timsort 在字符串长到足以看到算术版本获得优势之前很久就接近 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 回答