Кустарное, домашнее тестирование скорости поиска по словарю в Петоне

Захотел тут узнать, как на самом деле выглядит скорость поиску по словарю. Одни люди говорят, что она О(1),

другие - что не так всё просто, что на самом деле О(log(x))
http://orleanz.livejournal.com/1788009.html?thread=7256937#t7256937

Чтобы пощупать реальные цифры, написал малэнки скрипт на Петоне, который сначала создает случайный массив размера N и словарь (ассоциативный массив, хэш), содержащий его элементы как ключи, а потом, по секундомеру, делаются лукапы всех значений массива в этом словаре, и берется среднее время лукапа.

Постепенно повышаем N и смотрим, шо будет со временем лукапа

import random
import datetime

def runTest(N):

	ar = []
	dict = {}

	for i in range(N):
		k = str(100*random.random()) + str(100*random.random())
		ar.append(k)
		dict[k] = 1

	start = datetime.datetime.now()
	for x in ar: result = dict[x]
	end = datetime.datetime.now()
	delta = end - start

	return delta.total_seconds()/N

million = 1*1000*1000

for x in range(million, 20*million, million):
	print("%d , %f" % (x, runTest(x)*million ))

Запустил его на 20 точек графика, с размера словаря в 1 миллион, до 20 миллионов, с шагом в 1 миллион

По вертикали - миллионные доли секунды (т.е. доля от миллионной доли)


Результаты такие - время лукапа ВСЕГДА МАЛЕНЬКОЕ. Пусть оно и растет, но оно все равно такое маленькое, что у вас гораздо быстрее кончится память на компе для словаря. А если словарь уменьшать, то там уже на изменение скорость лукапа будут влиять другие, левые факторы.

Иными словами, сама попытка взять ассимптотику скорость лукапа - неверна в корне. Не нужна вообще ассимптотика величины, которая или адски маленькая, или вы вообще не можете сделать бенчмарк.

Таким образом, парадоксально правы и те, кто говорит О(1), и кто О(лог(х)), но каждый по своему.