Разработка на коленке

"тут должна быть красивая цитата о программировании"

Отверстия, винты и О от n

2011-07-11 15:13

В одном блоге нашёл описание небольшой задачи про винты и гнёзда.

Имеется n винтов и n гнезд, расположенных в произвольном порядке. Каждому винту соответствует по диаметру только одно гнездо. Все винты имеют разные диаметры.

Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. В результате такой операции можно выяснить:

  • Винт тоньще гнезда - не подходит.
  • Винт толще гнезда - не подходит.
  • Или винт точно входит в гнездо - подходит.

Сравнивать винты или гнезда между собой нельзя.

Ну и чем-то она меня зацепила. В целом, на интуитивном уровне было понятно, что кроме полного перебора с O(n 2) можно добиться более быстрого решения (в идеальном случае O(log 2 n)) при помощи бинарного дерева. Однако ж во всех этих зависимостях O от n меня интересует не только вид зависимости, но и и константа, про которую часто забывают. Константа зависит от стоимости операций, выполняемых в том или ином алгоритме. Поэтому мне захотелось пощупать и цифры.

Для начала я сделал следующие допущения к описанию задачи:

  1. Гнёзда после нахождения нужного винта из множества поиска не исключаются.
  2. Количества гнёзд и винтов равны (чтобы не возиться с проверками).
  3. Каждому гнезду по размеру соответствует один и только один винт.

Ну а потом я начал писать код. Чтобы проверить соответствие результатов поиска, функции возвращают данные в виде ассоциативного массива, где каждому ключу соответствует кортеж. Ключ - это размер отверстия и винта, в кортеже содержатся индекс отверстия и индекс винта.

Код юнит-тестов я приводить не буду, потому что они не добавляют полезной информации о скорости работы.

Первым сделал простой поиск соответствий полным перебором 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], хоть мы не можем сравнивать значения, но можем сравнивать индексы), как мне предлагал один камрад, потому что тогда поиск будет работать только в два раза быстрее, чем при упорядоченном множестве.

comments powered by Disqus