прикреплённый файл:hashtest.py к странице LecturesVMSH/2011-05-04

   1 #!/usr/bin?python
   2 # coding: utf8
   3 '''
   4 Тестирование ассоциативных структур данных. Сгенерировать текстовый файл с таблицей вида [уникальное случайное число, случайная строка без пробелов] на N = 10**5 элементов. Использовать эти данные (как набор пар "ключ-значение") в качестве входных для программы, которая тестирует производительность следующих структур данных:
   5 
   6     линейный список
   7     хешированная таблица
   8     двоичное дерева (заполняемого с балансировкой и без балансировки)
   9     стандартный словарь (dict) 
  10 
  11 Тестирует она каждую из них следующим образом. Для каждого из указанных ниже шагов измеряется общее (на весь шаг) и среднее (на каждый элемент) время выполнения операции со структурой (например, с помощью функции times() из модуля os). Шаги тестирования:
  12 
  13     Загрузить все данные в изначально пустую структуру.
  14     Составить случайную выборку из M = 1000 значений ключей, которые заведомо встречаются в структуре (эту подоперацию можно не измерять). Сделать поиск этих элементов, проверив, что они действительно в ней встречаются.
  15 
  16     Составить случайную выборку из M значений ключей, которые заведомо не встречаются в структуре (эту подоперацию можно не измерять). Сделать поиск этих элементов, проверив, что они действительно в ней не встречаются. 
  17 
  18 Подобрать параметры M и N так, чтобы вся программа работала не быстро и не медленно (от 1 до 3 минут) и не вызывала подкачки памяти.
  19 '''
  20 import random, sys, os, pickle
  21 
  22 Mx=10**8
  23 N=10**5
  24 M=10**6
  25 Alp="".join([chr(c) for c in xrange(33,127)])
  26 FData=len(sys.argv) > 1 and sys.argv[1] or sys.argv[0].split(".")[0]+".data"
  27 Data,YData,NData=[],[],[]
  28 
  29 def debug(s,t=1):
  30     if t: print s
  31     else: print s,
  32     sys.stdout.flush()
  33 
  34 if os.path.isfile(FData):
  35     debug("Read")
  36     f=file(FData)
  37     Data,NData,YData=pickle.load(f)
  38     if (len(Data),len(NData),len(YData)) != (N,M,M):
  39         Data,NData,YData=[],[],[]
  40 if not Data:
  41     debug("Generate",0)
  42     Data=[(i,"".join(random.sample(Alp,16))) for i in random.sample(xrange(Mx),N)]
  43     debug(".",0)
  44     NData=[random.randrange(Mx,Mx+N) for i in xrange(M)]
  45     debug(".",0)
  46     YData=[random.choice(Data)[0] for i in xrange(M)]
  47     debug(".",0)
  48     f=file(FData,"w")
  49     pickle.dump((Data,NData,YData),f)
  50     debug(" done.")
  51 f.close()
  52 
  53 class List(list):
  54     def __init__(self, d):
  55         for c in d:
  56             self.append(d)
  57     def Search(self,i):
  58         for c in self:
  59             if c[0]==i: return c[1]
  60         else:
  61             return None
  62 
  63 class Hashtable(list):
  64     def __init__(self, d):
  65         self.len=N
  66         self.extend(([] for i in xrange(self.len)))
  67         for i,v in d:
  68             self[i%self.len].append((i,v))
  69     def Search(self,i):
  70         for c in self[i%self.len]:
  71             if c[0]==i: return c[1]
  72         else:
  73             return None
  74             
  75 class ATree():
  76     def __init__(self, d):
  77         self.tree=[None,[],[]]
  78         for i,v in d:
  79             t=self.tree
  80             while t[0]:
  81                 t=t[t[0][0]<i and 1 or 2]
  82             t.extend(((i,v),[],[]))
  83     def Search(self, i):
  84         t=self.tree
  85         while t[0]:
  86             if t[0][0]==i:
  87                 return t[0][1]
  88         else:
  89             return None
  90 
  91 class Dict(dict):
  92     def __init__(self,d):
  93         for i,v in d:
  94             self[i]=v
  95     def Search(self, i):
  96         if self.has_key(i): return self[i]
  97         else: return None
  98 
  99 def Test(obj):
 100     t=[]
 101     t.append(os.times())
 102     O=obj(Data)
 103     t.append(os.times())
 104     for i in YData:
 105         c=O.Search(i)
 106     t.append(os.times())
 107     for i in NData:
 108         c=O.Search(i)
 109     t.append(os.times())
 110     return [t[i+1][0]-t[i][0] for i in xrange(len(t)-1)]
 111 
 112 debug("{0} {1} {2} {3}".format(M,N,len(NData),len(YData)))
 113 #T1=Test(List)
 114 #debug(T1)
 115 T2=Test(Hashtable)
 116 debug(T2)
 117 T3=Test(ATree)
 118 debug(T3)
 119 T4=Test(Dict)
 120 debug(T4)