В одном блоге нашёл описание небольшой задачи про винты и гнёзда.
Имеется n винтов и n гнезд, расположенных в произвольном порядке. Каждому винту соответствует по диаметру только одно гнездо. Все винты имеют разные диаметры.
Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. В результате такой операции можно выяснить:
- Винт тоньще гнезда - не подходит.
- Винт толще гнезда - не подходит.
- Или винт точно входит в гнездо - подходит.
Сравнивать винты или гнезда между собой нельзя.
Ну и чем-то она меня зацепила. В целом, на интуитивном уровне было понятно, что кроме полного перебора с O(n 2) можно добиться более быстрого решения (в идеальном случае O(log 2 n)) при помощи бинарного дерева. Однако ж во всех этих зависимостях O от n меня интересует не только вид зависимости, но и и константа, про которую часто забывают. Константа зависит от стоимости операций, выполняемых в том или ином алгоритме. Поэтому мне захотелось пощупать и цифры.
Для начала я сделал следующие допущения к описанию задачи:
- Гнёзда после нахождения нужного винта из множества поиска не исключаются.
- Количества гнёзд и винтов равны (чтобы не возиться с проверками).
- Каждому гнезду по размеру соответствует один и только один винт.
Ну а потом я начал писать код. Чтобы проверить соответствие результатов поиска, функции возвращают данные в виде ассоциативного массива, где каждому ключу соответствует кортеж. Ключ - это размер отверстия и винта, в кортеже содержатся индекс отверстия и индекс винта.
Код юнит-тестов я приводить не буду, потому что они не добавляют полезной информации о скорости работы.
Первым сделал простой поиск соответствий полным перебором fullsearch.py:
# -*- coding: utf-8 -*- def search(holes, screws): '''Ищет соответствия между значениями винтов и отверстий. Возвращает словарь, сотоящий из кортежей {размер:( индекс_отверстия, индекс_винта)} ''' matches = {} for s in screws: for h in holes: if s == h: matches[h] = (holes.index(h), screws.index(s)) break return matches
Потом взялся за написание скрипта, который делает поиск с помощью бинарного дерева. Тут нужно пояснить, что после того, как сформировано дерево, мне нужно сконвертировать его в словарь, содержащий соответствия индексов винтов и гнёзд. Конвертацию я делал не рекурсией, а в цикле, потому что если у нас отсортированный список шурупов, то рекурсия достигнет предельной глубины очень быстро (где-то на 1000 вызовов):
# -*- coding: utf-8 -*- class Node(object): def __init__(self, holeIdx, screwIdx, val, left, right): self.holeIdx = holeIdx self.screwIdx = screwIdx self.val = val self.left = {'node': None, 'list': left} self.right = {'node': None, 'list': right} def search(holes, screws): root = None holes = [(holes.index(h), h) for h in holes] for screw in screws: if root: node = root while True: nodedata = None if screw > node.val: # to right if node.right['node']: node = node.right['node'] else: nodedata = node.right else: # to left if node.left['node']: node = node.left['node'] else: nodedata = node.left if nodedata: left = [h for h in nodedata['list'] if h[1] < screw] right = [h for h in nodedata['list'] if h[1] > screw] holeIdx = [h[0] for h in nodedata['list'] if h[1] == screw][0] screwIdx = screws.index(screw) nodedata['node'] = Node(holeIdx, screwIdx, screw, left, right) nodedata['list'] = None # нужно очистить память, а то кончится break else: left = [h for h in holes if h[1] < screw] right = [h for h in holes if h[1] > screw] holeIdx = [h[0] for h in holes if h[1] == screw][0] screwIdx = screws.index(screw) root = Node(holeIdx, screwIdx, screw, left, right) # конвертирую дерево в словарь matches = {} nodelist = [root] while False: for node in nodelist: matches[node.val] = (node.holeIdx, node.screwIdx) nodelist = [node.left['node'] for node in nodelist if node.left['node']] +\ [node.right['node'] for node in nodelist if node.right['node']] return matches
Ну а после мне понадобился скрипт, который меряет время работы (скрипт, который сравнивает результаты работы двух методов приводить тоже не буду, но он мне всё же понадобился, чтобы убедиться, что оба скрипта выдают одинаковые словари на выходе).
# -*- coding: utf-8 -*- import btreesearch import fullsearch import random import timeit from datetime import datetime widths = (10, 20, 20, 20, 20, 20) df = '|%' + str(widths[0]) + 'd|' +\ '|'.join(['%' + str(w) + 'f' for w in widths[1:-1]]) +\ '|%' + str(widths[-1]) + 'd|' separator = '+%s+%s+%s+%s+%s+%s+' % tuple(['-' * w for w in widths]) thead = ('+%s|%s|%s|%s|%s|%s+' % tuple(['%' + str(w) + 's' for w in widths])) %\ ('count', 'fullsearch (sort)', 'btreesearch (sort)', 'fullsearch (rand)', 'btreesearch (rand)', 'first rand screw') print 'begin' , ':'.join(map(str, datetime.now().timetuple()[3:6])), '\n' print separator print thead setup = 'from __main__ import holes, screws, fullsearch, btreesearch' lengths = [10, 100, 500, 1000, 5000, 10000, 20000, 30000] for l in lengths: holes = range(l) screws = range(l) fTimeOrder = timeit.Timer('fullsearch.search(holes, screws)', setup).timeit(1) bTimeOrder = timeit.Timer('btreesearch.search(holes, screws)', setup).timeit(1) random.shuffle(holes) random.shuffle(screws) fTimeRand = timeit.Timer('fullsearch.search(holes, screws)', setup).timeit(1) bTimeRand = timeit.Timer('btreesearch.search(holes, screws)', setup).timeit(1) print separator print df % (l, fTimeOrder, bTimeOrder, fTimeRand, bTimeRand, screws[0]) print separator print '\nend' , ':'.join(map(str, datetime.now().timetuple()[3:6]))
Результат работы скрипта:
| count | fullsearch (sort) | btreesearch (sort) | fullsearch (rand) | btreesearch (rand) | first rand screw |
|---|---|---|---|---|---|
| 10 | 0.000030 | 0.000136 | 0.000027 | 0.000103 | 4 |
| 100 | 0.001225 | 0.007208 | 0.001242 | 0.002093 | 96 |
| 500 | 0.029338 | 0.171127 | 0.025904 | 0.022690 | 346 |
| 1000 | 0.098980 | 0.712090 | 0.105065 | 0.075805 | 723 |
| 5000 | 2.446349 | 17.888047 | 2.570363 | 1.523652 | 2123 |
| 10000 | 9.946249 | 77.531122 | 10.421238 | 5.964480 | 9905 |
| 20000 | 43.110249 | 323.101860 | 41.776272 | 23.398654 | 2207 |
| 30000 | 90.674444 | 770.846494 | 96.210516 | 53.148294 | 2292 |
По данным в таблице: первый столбец - это количество элеметов (пресловутое n), второй столбец - время работы полного перебора на отсортированном множестве, третий - поиск по дереву при отсортированном входном множестве, четвёртый - полный поиск при неупорядоченном множестве на входе, пятый - поиск по дереву при неупорядоченном множестве, и шестой - номер (размер) шурупа, с которого начинался поиск по дереву при неупорядоченном множестве на входе.
Тут, в общем-то, очевидно, что поиск по дереву очень сильно уступает в скорости, если
входное множество упорядоченно, и очень выигрывает, если входное множество перемешано.
Чтобы поиск по дереву был всегда эффективен, то нужно просто перемешивать (random.shuffle)
входное множество в функции btreesearch.search перед началом работы.
Причём, нужно именно перемешать, а не поменять местами первый элемент и тот, который
посредине (screws[0], screws[n/2] = screws[n/2], screws[0],
хоть мы не можем сравнивать значения, но можем сравнивать индексы), как мне предлагал
один камрад, потому что тогда поиск будет работать только в два раза быстрее, чем при упорядоченном множестве.