Прикреплённый файл «hashtest.py»
Загрузка 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)
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2011-09-26 11:35:21, 3.5 KB) [[attachment:hash744.py]]
- [получить | показать] (2011-09-26 11:35:21, 4.8 KB) [[attachment:hashtest.py]]
Вам нельзя прикреплять файлы к этой странице.