Python алгоритмы

Python Profiling

2015-04-26T13:35:00.001-07:00

Здесь рассматриваются методики профилировали в Питоне.

Это скорее памятка самому себе, но если кому-то пригодится, буду рад!)

Так же доступна интерактивная версия Ipython Notebook.

http://pynash.org/2013/03/06/timing-and-profiling.html - По теме
https://ru.wikipedia.org/wiki/Множество_Жюлиа - Рассматриваемый пример

In [2]:

#  Перед этим pip install line_profiler, memory_profiler
%load_ext line_profiler
%load_ext memory_profiler

In [6]:

from functools import wraps

def timefn(fn):
    @wraps(fn)
    def measure_time(*args, **kwargs):
        t1 = time.time()
        result = fn(*args, **kwargs)
        t2 = time.time()
        print ("@timefn:" + fn.func_name + " took " + str(t2 - t1) + " seconds")
        return result
    return measure_time

In [5]:

#@timefn
#@profile
def calculate_z_serial_purepython(maxiter, zs, cs): 
    """Calculate output list using Julia update rule"""
    
    output = [0] * len(zs)
    for i in xrange(len(zs)):
        n=0
        z = zs[i]
        c = cs[i]
        while abs(z) < 2 and n < maxiter:
            z=z*z+c
            n+=1
        output[i] = n

    return output

In [15]:

import time

x1, x2, y1, y2 = -1.8, 1.8, -1.8, 1.8
c_real, c_imag = -0.62772, -.42193

def calc_pure_python(desired_width, max_iterations): 
    """Create a list of complex coordinates (zs) and complex parameters (cs), build Julia set, and display"""
    
    x_step = (float(x2 - x1) / float(desired_width))
    y_step = (float(y1 - y2) / float(desired_width))
    x=[]
    y=[]
    ycoord = y2
    while ycoord > y1:
        y.append(ycoord)
        ycoord += y_step
    xcoord = x1
    while xcoord < x2:
        x.append(xcoord)
        xcoord += x_step
        
    ##################### SHOW PYTHON HEAP
    from guppy import hpy;
    hp = hpy()
    print "heapy after creating y and x lists of floats"
    h = hp.heap()
    print h
    ######################
    
        
    # Build a list of coordinates and the initial condition for each cell.
    # Note that our initial condition is a constant and could easily be removed; # we use it to simulate a real-world scenario with several inputs to
    # our function.
    zs=[]
    cs=[]
    
    for ycoord in y:
        for xcoord in x:
            zs.append(complex(xcoord, ycoord))
            cs.append(complex(c_real, c_imag))
            
    print "Length of x:", len(x)
    print "Total elements:", len(zs)
    start_time = time.time()
    output = calculate_z_serial_purepython(max_iterations, zs, cs)
    end_time = time.time()
    secs = end_time - start_time
    print calculate_z_serial_purepython.func_name + " took", secs, "seconds"
    # This sum is expected for a 1000^2 grid with 300 iterations. # It catches minor errors we might introduce when we're
    # working on a fixed set of inputs.
    #assert sum(output) == 33219980
    return output

In [6]:

"""
При построении с учетом отттенков серого, цвет меняющийся высоким контрастом дал бы нам представление о том, 
где стоимость функции медленно меняется, а где быстро. На данном рисунке, мы имеем линейный цветовую карту: 
черный дорого вычислять(>300), серый бесплатен (сразу 0) и белый дешевле максимума(0<x<300).
"""


from PIL import Image, ImageDraw

width = height = 1000

image = Image.new("RGBA", (width, height), (0,0,0,0))
pixels = image.load()

output = calc_pure_python(desired_width=height, max_iterations=300)
#print output

i = 0
x, y = 0, 0
for val in output:
    if i and i%height == 0:
        y += 1
        x = 0
        
    if val == 300:
        color = (0, 0, 0)
    elif val == 0:
        color = (125, 125, 125)
    else:
        color = (255, 255, 255)
        
    pixels[x, y] = color
    i += 1
    x += 1
    
image.show()

heapy after creating y and x lists of floats
Partition of a set of 2125520 objects. Total size = 96975808 bytes.
 Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
     0 2000001  94 64000032  66  64000032  66 complex
     1   1228   0 16507040  17  80507072  83 list
     2  56303   3  4946792   5  85453864  88 str
     3  28739   1  2462944   3  87916808  91 tuple
     4   1701   0  1640952   2  89557760  92 dict (no owner)
     5    420   0  1240416   1  90798176  94 dict of module
     6   7150   0   915200   1  91713376  95 types.CodeType
     7   7023   0   842760   1  92556136  95 function
     8    854   0   769040   1  93325176  96 type
     9    854   0   684560   1  94009736  97 dict of type
<540 more rows. Type e.g. '_.more' to view.>

Length of x: 1000
Total elements: 1000000
calculate_z_serial_purepython took 6.69428300858 seconds

Приступим к профайлингу

Производительность

In [7]:

output = calc_pure_python(desired_width=1000, max_iterations=300)

heapy after creating y and x lists of floats
Partition of a set of 2227318 objects. Total size = 107656256 bytes.
 Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
     0 2000001  90 64000032  59  64000032  59 complex
     1   1191   0 24628920  23  88628952  82 list
     2  57069   3  5003896   5  93632848  87 str
     3  29259   1  2510848   2  96143696  89 tuple
     4 103191   5  2476584   2  98620280  92 int
     5   1711   0  1656808   2 100277088  93 dict (no owner)
     6    427   0  1252360   1 101529448  94 dict of module
     7   7263   0   929664   1 102459112  95 types.CodeType
     8   7129   0   855480   1 103314592  96 function
     9    854   0   769040   1 104083632  97 type
<546 more rows. Type e.g. '_.more' to view.>

Length of x: 1000
Total elements: 1000000
calculate_z_serial_purepython took 6.71625804901 seconds

In [41]:

#  in IPython (probably because you’re using %run)
%timeit calc_pure_python(desired_width=1000, max_iterations=300)

Length of x: 1000
Total elements: 1000000
@timefn:calculate_z_serial_purepython took 6.66308379173 seconds
calculate_z_serial_purepython took 6.66349101067 seconds
Length of x: 1000
Total elements: 1000000
@timefn:calculate_z_serial_purepython took 6.68743419647 seconds
calculate_z_serial_purepython took 6.68781113625 seconds
Length of x: 1000
Total elements: 1000000
@timefn:calculate_z_serial_purepython took 6.79939007759 seconds
calculate_z_serial_purepython took 6.79975104332 seconds
Length of x: 1000
Total elements: 1000000
@timefn:calculate_z_serial_purepython took 6.83708381653 seconds
calculate_z_serial_purepython took 6.83745718002 seconds
1 loops, best of 3: 7.24 s per loop

In [43]:

#  cProfile
#  this time includes the overhead of using cProfile
%prun calc_pure_python(desired_width=1000, max_iterations=300)

Length of x: 1000
Total elements: 1000000
@timefn:calculate_z_serial_purepython took 9.6828110218 seconds
calculate_z_serial_purepython took 9.68326115608 seconds

In [21]:

#  line_profiler
%lprun -f calculate_z_serial_purepython calc_pure_python(desired_width=1000, max_iterations=300)

UsageError: option -l not recognized ( allowed: "rsf:m:D:T:" )

In [1]:

z = 0+0j
%timeit abs(z) < 2

n=1
maxiter = 300
%timeit n < maxiter

# Тут можно порассуждать, о правильности порядка abs(z) < 2 and n < maxiter или n < maxiter and abs(z) < 2
# мы знаем, что только 10% точек доходит до 300-го вычисления и при этом проверка n < maxiter в 2 раза дешевле

The slowest run took 66.17 times longer than the fastest. This could mean that an intermediate result is being cached 
10000000 loops, best of 3: 93.7 ns per loop
10000000 loops, best of 3: 44 ns per loop

Память

Основной закон этого мира - это "Закон сохранения энергии" Это он мешает создать нам вечный двигтаель и он же создает проблему перетягивания каната: память - скорость

Понимание использования памяти вашего кода позволяет вам задать себе два вопроса: • Можем ли мы использовать меньше памяти, переписав эту функцию, чтобы работать более эффективно? • Можем ли мы использовать больше оперативной памяти и сохранить ресурсы процессора за счет кэширования?

In [14]:

from calc_pure_python import calc_pure_python2
#  NOTE: %mprun can only be used on functions defined in physical files, and not in the IPython environment.
%mprun -f calc_pure_python calc_pure_python2(desired_width=10, max_iterations=300)

Length of x: 11
Total elements: 121
calculate_z_serial_purepython took 0.00995206832886 seconds
('',)

In [15]:

import os
os.path.dirname(os.getcwd())

Out[15]:

'/Users'

In [16]:

z = 0+0j
%memit abs(z) < 2

n=1
maxiter = 300
%memit n < maxiter

peak memory: 22.28 MiB, increment: 0.99 MiB
peak memory: 22.34 MiB, increment: 0.05 MiB

CherryPy server

In [8]:

def launch_memory_usage_server(port=8080): 
    import cherrypy
    import dowser
    cherrypy.tree.mount(dowser.Root())
    cherrypy.config.update({
        'environment': 'embedded',
        'server.socket_port': port
    })
    cherrypy.engine.start()

In [13]:

import time

x1, x2, y1, y2 = -1.8, 1.8, -1.8, 1.8
c_real, c_imag = -0.62772, -.42193

def calc_pure_python_cherry(desired_width, max_iterations): 
    """Create a list of complex coordinates (zs) and complex parameters (cs), build Julia set, and display"""
    
    x_step = (float(x2 - x1) / float(desired_width))
    y_step = (float(y1 - y2) / float(desired_width))
    x=[]
    y=[]
    
    ycoord = y2
    while ycoord > y1:
        y.append(ycoord)
        ycoord += y_step
    
    xcoord = x1
    while xcoord < x2:
        x.append(xcoord)
        xcoord += x_step

        
    # Build a list of coordinates and the initial condition for each cell.
    # Note that our initial condition is a constant and could easily be removed; # we use it to simulate a real-world scenario with several inputs to
    # our function.
    zs=[]
    cs=[]
    
    for ycoord in y:
        for xcoord in x:
            zs.append(complex(xcoord, ycoord))
            cs.append(complex(c_real, c_imag))

    #  тут стартуем сервер
    launch_memory_usage_server()
            
    start_time = time.time()
    output = calculate_z_serial_purepython(max_iterations, zs, cs)
    end_time = time.time()
    secs = end_time - start_time

    #  делаем так, чтобы сервер не потух
    print "now waiting..."
    while True:
        time.sleep(1)
    
    return output
calc_pure_python_cherry(desired_width=1000, max_iterations=300)

INFO:cherrypy.error:[26/Apr/2015:22:31:29] ENGINE Bus STARTING
INFO:cherrypy.error:[26/Apr/2015:22:31:29] ENGINE Monitor thread '_TimeoutMonitor' already started.
INFO:cherrypy.error:[26/Apr/2015:22:31:29] ENGINE Already serving on http://127.0.0.1:8080
INFO:cherrypy.error:[26/Apr/2015:22:31:29] ENGINE Bus STARTED

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-13-8b6b3a917280> in <module>()
     48 
     49     return output
---> 50 calc_pure_python_cherry(desired_width=1000, max_iterations=300)

<ipython-input-13-8b6b3a917280> in calc_pure_python_cherry(desired_width, max_iterations)
     38 
     39     start_time = time.time()
---> 40     output = calculate_z_serial_purepython(max_iterations, zs, cs)
     41     end_time = time.time()
     42     secs = end_time - start_time

<ipython-input-5-0ee9a7f0d062> in calculate_z_serial_purepython(maxiter, zs, cs)
     11         while abs(z) < 2 and n < maxiter:
     12             z=z*z+c
---> 13             n+=1
     14         output[i] = n
     15 

KeyboardInterrupt:

Byte Code

Первый столбец содержит номера строк исполнения.Вторая колонка содержит символы - >>; это направления для точек перехода, в других местах в коде.Третий столбец адрес операции вместе с именем операции.Четвертый столбец содержит параметры для работы.Пятая колонна содержит аннотации, чтобы помочь выстроить байт-код с оригинальными параметрами Python.

In [16]:

import dis
dis.dis(calc_pure_python)

  9           0 LOAD_GLOBAL              0 (float)
              3 LOAD_GLOBAL              1 (x2)
              6 LOAD_GLOBAL              2 (x1)
              9 BINARY_SUBTRACT     
             10 CALL_FUNCTION            1
             13 LOAD_GLOBAL              0 (float)
             16 LOAD_FAST                0 (desired_width)
             19 CALL_FUNCTION            1
             22 BINARY_DIVIDE       
             23 STORE_FAST               2 (x_step)

 10          26 LOAD_GLOBAL              0 (float)
             29 LOAD_GLOBAL              3 (y1)
             32 LOAD_GLOBAL              4 (y2)
             35 BINARY_SUBTRACT     
             36 CALL_FUNCTION            1
             39 LOAD_GLOBAL              0 (float)
             42 LOAD_FAST                0 (desired_width)
             45 CALL_FUNCTION            1
             48 BINARY_DIVIDE       
             49 STORE_FAST               3 (y_step)

 11          52 BUILD_LIST               0
             55 STORE_FAST               4 (x)

 12          58 BUILD_LIST               0
             61 STORE_FAST               5 (y)

 13          64 LOAD_GLOBAL              4 (y2)
             67 STORE_FAST               6 (ycoord)

 14          70 SETUP_LOOP              39 (to 112)
        >>   73 LOAD_FAST                6 (ycoord)
             76 LOAD_GLOBAL              3 (y1)
             79 COMPARE_OP               4 (>)
             82 POP_JUMP_IF_FALSE      111

 15          85 LOAD_FAST                5 (y)
             88 LOAD_ATTR                5 (append)
             91 LOAD_FAST                6 (ycoord)
             94 CALL_FUNCTION            1
             97 POP_TOP             

 16          98 LOAD_FAST                6 (ycoord)
            101 LOAD_FAST                3 (y_step)
            104 INPLACE_ADD         
            105 STORE_FAST               6 (ycoord)
            108 JUMP_ABSOLUTE           73
        >>  111 POP_BLOCK           

 17     >>  112 LOAD_GLOBAL              2 (x1)
            115 STORE_FAST               7 (xcoord)

 18         118 SETUP_LOOP              39 (to 160)
        >>  121 LOAD_FAST                7 (xcoord)
            124 LOAD_GLOBAL              1 (x2)
            127 COMPARE_OP               0 (<)
            130 POP_JUMP_IF_FALSE      159

 19         133 LOAD_FAST                4 (x)
            136 LOAD_ATTR                5 (append)
            139 LOAD_FAST                7 (xcoord)
            142 CALL_FUNCTION            1
            145 POP_TOP             

 20         146 LOAD_FAST                7 (xcoord)
            149 LOAD_FAST                2 (x_step)
            152 INPLACE_ADD         
            153 STORE_FAST               7 (xcoord)
            156 JUMP_ABSOLUTE          121
        >>  159 POP_BLOCK           

 23     >>  160 LOAD_CONST               1 (-1)
            163 LOAD_CONST               2 (('hpy',))
            166 IMPORT_NAME              6 (guppy)
            169 IMPORT_FROM              7 (hpy)
            172 STORE_FAST               8 (hpy)
            175 POP_TOP             

 24         176 LOAD_FAST                8 (hpy)
            179 CALL_FUNCTION            0
            182 STORE_FAST               9 (hp)

 25         185 LOAD_CONST               3 ('heapy after creating y and x lists of floats')
            188 PRINT_ITEM          
            189 PRINT_NEWLINE       

 26         190 LOAD_FAST                9 (hp)
            193 LOAD_ATTR                8 (heap)
            196 CALL_FUNCTION            0
            199 STORE_FAST              10 (h)

 27         202 LOAD_FAST               10 (h)
            205 PRINT_ITEM          
            206 PRINT_NEWLINE       

 34         207 BUILD_LIST               0
            210 STORE_FAST              11 (zs)

 35         213 BUILD_LIST               0
            216 STORE_FAST              12 (cs)

 37         219 SETUP_LOOP              75 (to 297)
            222 LOAD_FAST                5 (y)
            225 GET_ITER            
        >>  226 FOR_ITER                67 (to 296)
            229 STORE_FAST               6 (ycoord)

 38         232 SETUP_LOOP              58 (to 293)
            235 LOAD_FAST                4 (x)
            238 GET_ITER            
        >>  239 FOR_ITER                50 (to 292)
            242 STORE_FAST               7 (xcoord)

 39         245 LOAD_FAST               11 (zs)
            248 LOAD_ATTR                5 (append)
            251 LOAD_GLOBAL              9 (complex)
            254 LOAD_FAST                7 (xcoord)
            257 LOAD_FAST                6 (ycoord)
            260 CALL_FUNCTION            2
            263 CALL_FUNCTION            1
            266 POP_TOP             

 40         267 LOAD_FAST               12 (cs)
            270 LOAD_ATTR                5 (append)
            273 LOAD_GLOBAL              9 (complex)
            276 LOAD_GLOBAL             10 (c_real)
            279 LOAD_GLOBAL             11 (c_imag)
            282 CALL_FUNCTION            2
            285 CALL_FUNCTION            1
            288 POP_TOP             
            289 JUMP_ABSOLUTE          239
        >>  292 POP_BLOCK           
        >>  293 JUMP_ABSOLUTE          226
        >>  296 POP_BLOCK           

 42     >>  297 LOAD_CONST               4 ('Length of x:')
            300 PRINT_ITEM          
            301 LOAD_GLOBAL             12 (len)
            304 LOAD_FAST                4 (x)
            307 CALL_FUNCTION            1
            310 PRINT_ITEM          
            311 PRINT_NEWLINE       

 43         312 LOAD_CONST               5 ('Total elements:')
            315 PRINT_ITEM          
            316 LOAD_GLOBAL             12 (len)
            319 LOAD_FAST               11 (zs)
            322 CALL_FUNCTION            1
            325 PRINT_ITEM          
            326 PRINT_NEWLINE       

 44         327 LOAD_GLOBAL             13 (time)
            330 LOAD_ATTR               13 (time)
            333 CALL_FUNCTION            0
            336 STORE_FAST              13 (start_time)

 45         339 LOAD_GLOBAL             14 (calculate_z_serial_purepython)
            342 LOAD_FAST                1 (max_iterations)
            345 LOAD_FAST               11 (zs)
            348 LOAD_FAST               12 (cs)
            351 CALL_FUNCTION            3
            354 STORE_FAST              14 (output)

 46         357 LOAD_GLOBAL             13 (time)
            360 LOAD_ATTR               13 (time)
            363 CALL_FUNCTION            0
            366 STORE_FAST              15 (end_time)

 47         369 LOAD_FAST               15 (end_time)
            372 LOAD_FAST               13 (start_time)
            375 BINARY_SUBTRACT     
            376 STORE_FAST              16 (secs)

 48         379 LOAD_GLOBAL             14 (calculate_z_serial_purepython)
            382 LOAD_ATTR               15 (func_name)
            385 LOAD_CONST               6 (' took')
            388 BINARY_ADD          
            389 PRINT_ITEM          
            390 LOAD_FAST               16 (secs)
            393 PRINT_ITEM          
            394 LOAD_CONST               7 ('seconds')
            397 PRINT_ITEM          
            398 PRINT_NEWLINE       

 52         399 LOAD_FAST               14 (output)
            402 RETURN_VALUE

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

Оптимизация с учетом предпочтений

2014-10-21T17:19:00.003-07:00

В прошлый раз, мы рассмотрели пример одной задачи, которую можно решить методами оптимизации. Напомним, что для применения оптимизации должны выполняться два основных требования: наличие целевой функции и тот факт, что близкие параметры дают близкие решения. Не каждую задачу, удовлетворяющую этим требованиям, можно решить методами оптимизации, но есть неплохие шансы, что попытка применить эти методы даст интересные результаты, о которых вы даже не подозревали.

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

Оптимизация распределения студентов по комнатам

Сегодня мы решим задачу о распределении студентов по комнатам в общежитии с учетом их основного и альтернативного пожеланий. Хотя формулировка довольно специфична, ее можно легко обобщить на похожие задачи, – тот же самый код годится для распределения игроков по столам в онлайновой карточной игре, для распределения ошибок между разработчиками в большом программном проекте и даже для распределения работы по дому между прислугой. Как и раньше, наша цель – собрать информацию об отдельных людях и найти такое сочетание, которое приводит к оптимальному результату.

В нашем примере будет пять двухместных комнат и десять претендующих на них студентов. У каждого студента есть основное и альтернативное пожелание.

# Двухместные комнаты
dorms = ['Zeus','Athena','Hercules','Bacchus','Pluto']

# Люди и два пожелания у каждого (основное, второстепенное)
prefs = [('Toby', ('Bacchus', 'Hercules')),
       ('Steve', ('Zeus', 'Pluto')),
       ('Karen', ('Athena', 'Zeus')),
       ('Sarah', ('Zeus', 'Pluto')),
       ('Dave', ('Athena', 'Bacchus')), 
       ('Jeff', ('Hercules', 'Pluto')), 
       ('Fred', ('Pluto', 'Athena')), 
       ('Suzie', ('Bacchus', 'Hercules')), 
       ('Laura', ('Bacchus', 'Hercules')), 
       ('James', ('Hercules', 'Athena'))]

Сразу видно, что удовлетворить основное пожелание каждого человека не удастся, так как на два места в комнате Bacchus имеется три претендента. Поместить любого из этих трех в ту комнату, которую он указал в качестве альтернативы, тоже невозможно, так как в комнате Hercules всего два места.

В приведенном примере общее число вариантов порядка 100 000, то можно перебрать их все и найти оптимальный. Но если комнаты будут четырехместными, то количество вариантов будет исчислять триллионами.

Представление решения

В каждой комнате должно оказаться ровно два студента. Будем считать, что в каждой комнате есть два отсека, то есть всего их в нашем случае будет десять. Каждому студенту по очереди назначается один из незанятых отсеков; первого можно поместить в любой из десяти отсеков, второго – в любой из оставшихся девяти и т. д.

Область определения для поиска (смотри предыдущую статью):

# [9, 8, 7, 6,..., 1]
domain = [i for i in xrange(9, 0, -1)]

Целевая функция

Целевая функция работает следующим образом. Создается начальный список отсеков, и уже использованные отсеки из него удаляются. Стоимость вычисляется путем сравнения комнаты, в которую студент помещен, с двумя его пожеланиями. Стоимость не изменяется, если студенту досталась та комната, в которую он больше всего хотел поселиться; увеличивается на 1, если это второе из его пожеланий; и увеличивается на 3, если он вообще не хотел жить в этой комнате.

def dorm_cost(vec):
 cost=0

 # Создаем список отсеков, т.е. первые 2 места - 0 отсек и т.д.
 slots = [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]

 # Цикл по студентам, i - порядковый номер студента
 for i in xrange(len(vec)):
  x = int(vec[i])
  dorm = dorms[slots[x]]
  pref = prefs[i][1]
  print x, '->', slots[x],'->', prefs[i][0], pref, '->', dorm

  # Стоимость основного пожелания равна 0, альтернативного – 1
  # Если комната не входит в список пожеланий, стоимость увеличивается на 3
  if pref[0] == dorm: cost += 0
  elif pref[1] == dorm: cost += 1
  else: cost += 3

  # Удалить выбранный отсек
  # Это самое важное действие тут,
  # прошу особо обратить на него внимание и учесть, что элементы сдвигаются
  del slots[x]

 return cost

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

Оптимизация

Всем кто не изучил методы оптимизации в предыдущей статье, бегом изучать!) Хорошим мальчикам и может даже девочкам, импортировать любой из методов и запустить!) Я, для примера, попробую на генетическом алгоритме.

result, score = genetic_optimize(domain, dorm_cost)
print result, score

Например у меня, нашелся такой результат [7, 1, 2, 0, 0, 1, 2, 1, 0] 1, что соответствует следующему выводу:

7 -> 3 -> Toby ('Bacchus', 'Hercules') -> Bacchus
1 -> 0 -> Steve ('Zeus', 'Pluto') -> Zeus
2 -> 1 -> Karen ('Athena', 'Zeus') -> Athena
0 -> 0 -> Sarah ('Zeus', 'Pluto') -> Zeus
0 -> 1 -> Dave ('Athena', 'Bacchus') -> Athena
1 -> 2 -> Jeff ('Hercules', 'Pluto') -> Hercules
2 -> 4 -> Fred ('Pluto', 'Athena') -> Pluto
1 -> 3 -> Suzie ('Bacchus', 'Hercules') -> Bacchus
0 -> 2 -> Laura ('Bacchus', 'Hercules') -> Hercules

Т.е. не устроило только Lauru и то, учтен был ее 2й вариант)

Вместо вывода

Итак, надеюсь, я показал, что используя одни алгоритмы, но меняя область определения и принцип расчета целевой функции, мы можем решить абсолютно разные оптимизационные задачи!)

Задачи оптимизации

2014-10-21T15:18:00.002-07:00

Давайте разберемся, как решать задачи со множеством участников, применяя технику стохастической оптимизации. По существу, оптимизация сводится к поиску наилучшего решения задачи путем апробирования различных решений и сравнения их между собой для оценки качества. Обычно оптимизация применяется в тех случаях, когда число решений слишком велико и перебрать их все невозможно.

У методов оптимизации весьма широкая область применения: в физике они используются для изучения молекулярной динамики, в биологии – для прогнозирования белковых структур, а в информатике – для определения времени работы алгоритма в худшем случае. В НАСА методы оптимизации применяют даже для проектирования антенн с наилучшими эксплуатационными характеристиками. Выглядят они так, как ни один человек не мог бы вообразить.

Мы же, для примера, возьмем классическую задачу группового путешествия!)

Наш пример относится к планированию группового путешествия дружеской компании из разных частей света. Всякий, кто пытался планировать поездку группы людей или даже одного человека, понимает, что нужно учитывать множество исходных данных, например: каким рейсом должен лететь каждый человек, сколько нужно арендовать машин и от какого аэропорта удобнее всего добираться. Также следует принять во внимание ряд выходных переменных: полная стоимость, время ожидания в аэропортах и непроизводительно потраченное время.

Формат данных

Планирование путешествия группы людей (в данном примере семейства Сидоровых), которые, отправляясь из разных мест, должны прибыть в одно и то же место.

Члены семьи живут в разных концах страны и хотят встретиться в Урюпинске. Все они должны вылететь в один день и в один день улететь и при этом в целях экономии хотели бы уехать из аэропорта и приехать в него на одной арендованной машине. Ежедневно, в славный город Урюпинск, из мест проживания любого члена семьи отправляются десятки рейсов, все в разное время. Цена билета и время в пути для каждого рейса разные.

Начнем со списка самих Сидоровых:

peoples = [('Seymour','BOS'),
    ('Franny','DAL'),
    ('Zooey','CAK'),
    ('Walt','MIA'),
    ('Buddy','ORD'),
    ('Les','OMA')]

# место назначения
destination = 'LGA'

# словарь рейсов

flights = {('LGA', 'CAK'): [('6:58', '9:01', 238), ('8:19', '11:16', 122), ('9:58', '12:56', 249), ('10:32', '13:16', 139), ('12:01', '13:41', 267), ('13:37', '15:33', 142), ('15:50', '18:45', 243), ('16:33', '18:15', 253), ('18:17', '21:04', 259), ('19:46', '21:45', 214)], ('DAL', 'LGA'): [('6:12', '10:22', 230), ('7:53', '11:37', 433), ('9:08', '12:12', 364), ('10:30', '14:57', 290), ('12:19', '15:25', 342), ('13:54', '18:02', 294), ('15:44', '18:55', 382), ('16:52', '20:48', 448), ('18:26', '21:29', 464), ('20:07', '23:27', 473)], ('LGA', 'BOS'): [('6:39', '8:09', 86), ('8:23', '10:28', 149), ('9:58', '11:18', 130), ('10:33', '12:03', 74), ('12:08', '14:05', 142), ('13:39', '15:30', 74), ('15:25', '16:58', 62), ('17:03', '18:03', 103), ('18:24', '20:49', 124), ('19:58', '21:23', 142)], ('LGA', 'MIA'): [('6:33', '9:14', 172), ('8:23', '11:07', 143), ('9:25', '12:46', 295), ('11:08', '14:38', 262), ('12:37', '15:05', 170), ('14:08', '16:09', 232), ('15:23', '18:49', 150), ('16:50', '19:26', 304), ('18:07', '21:30', 355), ('20:27', '23:42', 169)], ('LGA', 'OMA'): [('6:19', '8:13', 239), ('8:04', '10:59', 136), ('9:31', '11:43', 210), ('11:07', '13:24', 171), ('12:31', '14:02', 234), ('14:05', '15:47', 226), ('15:07', '17:21', 129), ('16:35', '18:56', 144), ('18:25', '20:34', 205), ('20:05', '21:44', 172)], ('OMA', 'LGA'): [('6:11', '8:31', 249), ('7:39', '10:24', 219), ('9:15', '12:03', 99), ('11:08', '13:07', 175), ('12:18', '14:56', 172), ('13:37', '15:08', 250), ('15:03', '16:42', 135), ('16:51', '19:09', 147), ('18:12', '20:17', 242), ('20:05', '22:06', 261)], ('CAK', 'LGA'): [('6:08', '8:06', 224), ('8:27', '10:45', 139), ('9:15', '12:14', 247), ('10:53', '13:36', 189), ('12:08', '14:59', 149), ('13:40', '15:38', 137), ('15:23', '17:25', 232), ('17:08', '19:08', 262), ('18:35', '20:28', 204), ('20:30', '23:11', 114)], ('LGA', 'DAL'): [('6:09', '9:49', 414), ('7:57', '11:15', 347), ('9:49', '13:51', 229), ('10:51', '14:16', 256), ('12:20', '16:34', 500), ('14:20', '17:32', 332), ('15:49', '20:10', 497), ('17:14', '20:59', 277), ('18:44', '22:42', 351), ('19:57', '23:15', 512)], ('LGA', 'ORD'): [('6:03', '8:43', 219), ('7:50', '10:08', 164), ('9:11', '10:42', 172), ('10:33', '13:11', 132), ('12:08', '14:47', 231), ('14:19', '17:09', 190), ('15:04', '17:23', 189), ('17:06', '20:00', 95), ('18:33', '20:22', 143), ('19:32', '21:25', 160)], ('ORD', 'LGA'): [('6:05', '8:32', 174), ('8:25', '10:34', 157), ('9:42', '11:32', 169), ('11:01', '12:39', 260), ('12:44', '14:17', 134), ('14:22', '16:32', 126), ('15:58', '18:40', 173), ('16:43', '19:00', 246), ('18:48', '21:45', 246), ('19:50', '22:24', 269)], ('MIA', 'LGA'): [('6:25', '9:30', 335), ('7:34', '9:40', 324), ('9:15', '12:29', 225), ('11:28', '14:40', 248), ('12:05', '15:30', 330), ('14:01', '17:24', 338), ('15:34', '18:11', 326), ('17:07', '20:04', 291), ('18:23', '21:35', 134), ('19:53', '22:21', 173)], ('BOS', 'LGA'): [('6:17', '8:26', 89), ('8:04', '10:11', 95), ('9:45', '11:50', 172), ('11:16', '13:29', 83), ('12:34', '15:02', 109), ('13:40', '15:37', 138), ('15:27', '17:18', 151), ('17:11', '18:30', 108), ('18:34', '19:36', 136), ('20:17', '22:22', 102)]}

Словарь рейсов имеет следующий формат: {('LGA', 'CAK'): [('6:58', '9:01', 238), ('8:19', '11:16', 122),....], .....} - (аэропорт вылета, прилета), как ключ и (время вылета, время прилета, стоимость), как значение. Заполните его произвольным способом, можно поискать на сайтах авиа и заполнить реальной ситуацией))

Для подобных задач необходимо определиться со способом представления потенциальных решений. Функции оптимизации, с которыми вы вскоре ознакомитесь, достаточно общие и применимы к различным задачам, поэтому так важно выбрать простое представление, которое не было бы привязано к конкретной задаче о групповом путешествии. Очень часто для этой цели выбирают список чисел. Каждое число обозначает рейс, которым решил лететь участник группы.

Например, в решении, представленном списком [1,4,3,2,7,3,6,3,2,4,5,3]
Сеймур (Seymour) летит первым рейсом из Бостона в Нью-Йорк и четвертым рейсом из Нью-Йорка в Бостон, а Фрэнни (Franny) – третьим рейсом из Далласа в Нью-Йорк и вторым обратно.

Целевая функция

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

Рассмотрим несколько параметров, которые можно измерить в примере с групповым путешествием:

Цена

Полная стоимость всех билетов или, возможно, среднее значение, взвешенное с учетом финансовых возможностей.

Время в пути

Суммарное время, проведенное всеми членами семьи в полете.

Время ожидания

Время, проведенное в аэропорту в ожидании прибытия остальных членов группы.

Время вылета

Если самолет вылетает рано утром, это может увеличивать общую стоимость из-за того, что путешественники не выспятся.

Время аренды автомобилей

Если группа арендует машину, то вернуть ее следует до того часа, когда она была арендована, иначе придется платить за лишний день.

Определившись с тем, какие переменные влияют на стоимость, нужно решить, как из них составить одно число. В нашем случае можно, например, выразить в деньгах время в пути или время ожидания в аэропорту. Скажем, каждая минута в воздухе эквивалентна $1 (иначе гово- ря, можно потратить лишние $90 на прямой рейс, экономящий полтора часа), а каждая минута ожидания в аэропорту эквивалентна $0,50. Можно было бы также приплюсовать стоимость лишнего дня аренды машины, если для всех имеет смысл вернуться в аэропорт к более поз- днему часу.

Определенная ниже, целевая функция shedule_cost принимает во внимание полную стоимость поездки и общее время ожидания в аэропорту всеми членами семьи. Кроме того, она добавляет штраф $50, если машина возвращена в более поздний час, чем арендована.

# время в минутах
def get_minutes(t):
 x=time.strptime(t,'%H:%M')
 return x[3]*60+x[4]

def schedule_cost(sol):
 totalprice = 0
 latestarrival = 0
 earliestdep = 24*60

 for d in xrange(len(sol)/2):
  # Получить список прибывающих и убывающих реисов
  origin = peoples[d][1]
  outbound = flights[(origin, destination)][int(sol[d])]
  returnf = flights[(destination, origin)][int(sol[d+1])]

  # Полная цена равна сумме цен на билет туда и обратно
  totalprice += outbound[2]
  totalprice += returnf[2]

  # Находим самыи позднии прилет и самыи раннии вылет
  if latestarrival < get_minutes(outbound[1]): latestarrival = get_minutes(outbound[1])
  if earliestdep > get_minutes(returnf[0]): earliestdep = get_minutes(returnf[0])

 # Все должны ждать в аэропорту прибытия последнего участника группы.
 # Обратно все прибывают одновременно и должны ждать свои реисы.
 totalwait = 0  
 for d in xrange(len(sol)/2):
  origin = peoples[d][1]
  outbound = flights[(origin, destination)][int(sol[d])]
  returnf = flights[(destination, origin)][int(sol[d+1])]
  totalwait += latestarrival - get_minutes(outbound[1])
  totalwait += get_minutes(returnf[0]) - earliestdep  

 # Для этого решения требуется оплачивать дополнительныи день аренды?
 # Если да, это обоидется в лишние $50!
 if latestarrival > earliestdep: totalprice += 50

 return totalprice + totalwait

Логика этой функции очень проста, но суть вопроса она отражает. Улучшить ее можно несколькими способами. Так, в текущей версии предполагается, что все члены семьи уезжают из аэропорта вместе, когда прибывает самый последний, а возвращаются в аэропорт к моменту вылета самого раннего рейса. Можно поступить по-другому: если человеку приходится ждать два часа или дольше, то он арендует отдельную машину, а цены и время ожидания соответственно корректируются.

Случайный поиск

Случайный поиск – не самый лучший метод оптимизации, но он позволит нам ясно понять, чего пытаются достичь все алгоритмы, а также послужит эталоном, с которым можно будет сравнивать другие алгоритмы.

Соответствующая функция принимает два параметра. Domain – это список значений, определяющих количество вариантов рейсов каждого из участников путешествия. Важно что они отсортированы в том же порядке, что и сами участники, сначала идут в Урюпинск, потом оттуда. Длина решения совпадает с длиной этого списка.

Второй параметр, costf, – это целевая функция; в нашем примере в этом качестве используется schedule_cost. Она передается в виде параметра, чтобы алгоритм можно было использовать повторно и для других задач оптимизации. Алгоритм случайным образом генерирует 1000 гипотез и для каждой вызывает функцию costf. Возвращается наилучшая гипотеза (с минимальной стоимостью).

domain = []
for people in peoples:
 domain.append(len(flights[(people[1], destination)]) - 1)
 domain.append(len(flights[(destination, people[1])]) - 1)
print domain

def random_optimize(domain, costf):
 best=999999999
 bestr=None

 for i in xrange(0, 1000):
  # Выбрать случаиное решение
  r = [random.randint(0, domain[i]) for i in xrange(len(domain))]

  # Get the cost
  cost = costf(r)

  # Сравнить со стоимостью наилучшего наиденного к этому моменту решения
  if cost < best:
   best = cost
   bestr = r
 return r, best

result, score = random_optimize(domain, schedule_cost)
print result, score

Позапускав, я получил макс хороший вариант (из 10 запусков по 1000 вариантов) 3208$, будем с ним и сравнивать)

Алгоритм спуска с горы

Случайное апробирование решений очень неэффективно, потому что пренебрегает выгодами, которые можно получить от анализа уже найденных хороших решений. В нашем примере можно предположить, что расписание с низкой полной стоимостью похоже на другие расписания с низкой стоимостью.

Альтернативный метод случайного поиска называется алгоритмом спуска с горы (hill climbing). Он начинает со случайного решения и ищет лучшие решения (с меньшим значением целевой функции) по соседству. Можно провести аналогию со спуском с горы.

Представьте, что человечек на рисунке – это вы и оказались в этом месте по воле случая. Вы хотите добраться до самой низкой точки, чтобы найти воду. Для этого вы, наверное, осмотритесь и направитесь туда, где склон самый крутой. И будете двигаться в направлении наибольшей крутизны, пока не дойдете до точки, где местность становится ровной или начинается подъем.

Применим этот подход. Начнем со случайно выбранного расписания и просмотрим все расписания в его окрестности. В данном случае это означает просмотр таких расписаний, для которых один человек выбирает рейс, вылетающий чуть раньше или чуть позже. Для каждого из соседних расписаний вычисляется стоимость, и расписание с наименьшей стоимостью становится новым решением. Этот процесс повторяется и завершается, когда ни одно из соседних расписаний не дает улучшения стоимости.

def hill_climb(domain, costf):

 # Выбрать случаиное решение
 sol = [random.randint(0, domain[i]) for i in xrange(len(domain))]
 best = costf(sol)

 # Главныи цикл
 is_stop = False
 while not is_stop:
  # Создать список соседних решении
  neighbors = []
  for j in xrange(len(domain)):

   # Отходим на один шаг в каждом направлении
   if 0 < sol[j] < 9:
    neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])
    neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])

   if 0 == sol[j]:
    neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])

   if sol[j] == domain[j]:
    neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])

  # Ищем наилучшее из соседних решении

  is_stop = True
  for j in xrange(len(neighbors)):
   cost = costf(neighbors[j])
   if cost < best:
    is_stop = False
    best = cost
    sol = neighbors[j]

 return sol, best

result, score = hill_climb(domain, schedule_cost)
print result, score

Для выбора начального решения эта функция генерирует случайный список чисел из заданного диапазона. Соседи текущего решения ищутся путем посещения каждого элемента списка и создания двух новых списков, в одном из которых этот элемент увеличен на единицу, а в другом уменьшен на единицу. Лучшее из соседних решений становится новым решением.

На самом деле, в данном случае этот мест даст так себе результаты. Хотя, в большинстве случаев, лучше чем 1000 случайных вариантов. Однако у алгоритма спуска с горы, есть один существенный недостаток.

Из рисунка видно, что, спускаясь по склону, мы необязательно отыщем наилучшее возможное решение. Найденное решение будет локальным минимумом, то есть лучшим из всех в ближайшей окрестности, но это не означает, что оно вообще лучшее. Решение, лучшее среди всех возможных, называется глобальным минимумом, и именно его хотят найти все алгоритмы оптимизации. Один из возможных подходов к решению проблемы называется спуском с горы со случайным перезапуском. В этом случае алгоритм спуска выполняется несколько раз со случайными начальными точками в надежде, что какое-нибудь из найденных решений будет близко к глобальному минимуму. Так же, все усугубляется тем, что у такой ф-ии как наша, большая импульсивность (много локальных минимумов и максимумов), очень не линейная скорость роста в разных точках, в общем очень много факторов, с учетом того, что мы рассматриваем ф-ию в 12 мерном пространстве и в каждом из них она ведет себя по-разному...

Алгоритм имитации отжига

Алгоритм имитации отжига навеян физическими аналогиями. Отжигом называется процесс нагрева образца с последующим медленным охлаждением. Поскольку сначала атомы заставляют попрыгать, а затем постепенно «отпускают вожжи», то они переходят в новую низко-энергетичную конфигурацию.

Алгоритмическая версия отжига начинается с выбора случайного решения задачи. В ней используется переменная, интерпретируемая как температура, начальное значение которой очень велико, но постепенно уменьшается. На каждой итерации случайным образом выбирается один из параметров решения и изменяется в определенном направлении.

Тут есть важная деталь: если новая стоимость ниже, то новое решение становится текущим, как и в алгоритме спуска с горы. Но, даже если новая стоимость выше, новое решение все равно может стать текущим с некоторой вероятностью. Так мы пытаемся избежать ситуации скатывания в локальный минимум.

Иногда необходимо перейти к худшему решению, чтобы найти лучшее. Алгоритм имитации отжига работает, потому что всегда готов перейти к лучшему решению, но ближе к началу процесса соглашается принять и худшее. По мере того как процесс развивается, алгоритм соглашается на худшее решение все с меньшей охотой, а в конце работы принимает только лучшее. Вероятность того, что будет принято решение с более высокой стоимостью, рассчитывается по формуле:

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

def annealing_optimize(domain, costf, T=10000.0, cool=0.99, step=1):
 
 # Выбрать случаиное решение
 vec = [random.randint(0, domain[i]) for i in xrange(len(domain))]

 while T > 0.1:
  # Выбрать один из индексов
  i = random.randint(0, len(domain)-1)

  # Выбрать направление изменения
  dir = random.randint(-step, step)

  # Создать новыи список, в котором одно значение изменено
  vecb = vec[:]
  vecb[i] += dir
  if vecb[i] < 0: vecb[i] = 0
  elif vecb[i] > domain[i]: vecb[i] = domain[i]

  # Вычислить текущую и новую стоимость
  ea = costf(vec)
  eb = costf(vecb)
  p = pow(math.e, (-eb-ea)/T)

  # Новое решение лучше? Если нет, метнем кости
  if (eb < ea or random.random() < p):
   vec = vecb      

  # Уменьшить температуру
  T = T * cool
 return vec, eb

result, score = annealing_optimize(domain, schedule_cost)
print result, score

На каждой итерации в качестве i случайно выбирается одна из переменных решения, а dir случайно выбирается между –step и step. Вычисляется стоимость теку- щего решения и стоимость решения, получающегося изменением пе- ременной i на величину step.

В p, вычисляется вероятность, которая уменьшается с уменьшением T. Если величина, случайно выбранная между 0 и 1, оказывается меньше вычисленной вероятности или если новое решение лучше текущего, то новое решение становится текущим. Цикл продолжается, пока температура почти не достигнет нуля, причем каждый раз температура умножается на скорость охлаждения.

По-поводу лучше или нет результаты, сказать не могу, скорее всего, приблизительно одинаково(

Генетические алгоритмы

Отцом генетических алгоритмов принято считать ученого-тео- ретика Джона Холланда (John Holland), который в 1975 году написал книгу «Adaptation in Natural and Artificial Systems» (издательство Мичиганского университета). Но корни этих работ восходят к биологам 1950-х годов, которые пытались моделировать эволюцию на компьютерах. С тех пор генетические алгоритмы и другие методы оптимизации использовались для решения широчайшего круга задач, в том числе:

Нахождения формы концертного зала с оптимальными акустическими характеристиками.

Проектирования оптимальной формы крыла сверхзвукового самолета.

Составления оптимальной библиотеки химических веществ для синтеза потенциальных лекарств.

Автоматического проектирования микросхем для распознавания речи.

Решения этих задач можно представить в виде списков чисел. Это упрощает применение к ним генетических алгоритмов или метода имитации отжига.

Еще один класс методов оптимизации, также навеянный природой, называется генетическими алгоритмами. Принцип их работы состоит в том, чтобы создать набор случайных решений, который называется популяцией. На каждом шаге оптимизации целевая функция вычисляется для всей популяции, в результате чего получается ранжирован- ный список решений.

Ранжированный список решений иих стоимостей

Проранжировав решения, мы создаем новую популяцию, которая называется следующим поколением. Сначала в новую популяцию включаются самые лучшие решения из текущей. Этот процесс называется элитизмом. Кроме них, в следующую популяцию входят совершенно новые решения, получающиеся путем модификации наилучших.

Модифицировать решения можно двумя способами. Более простой называется мутацией; обычно это небольшое, простое, случайное изменение существующего решения. В нашем случае для мутации достаточно выбрать одну из переменных решения и уменьшить либо увели- чить ее.

Пример мутации

Другой способ называется скрещиванием (или кроссовером). Состоит он в том, что мы берем какие-нибудь два из лучших решений и как-то комбинируем их. В нашем примере достаточно взять случайное число элементов из одного решения, а остальные – из другого, как показано.

Пример скрещивания

Размер новой популяции обычно совпадает с размером предыдущей, а создается она путем случайных мутаций и скрещиваний лучших решений. Затем этот процесс повторяется – новая популяция ранжируется и создается очередное поколение. Так продолжается заданное число раз или до тех пор, пока на протяжении нескольких поколений не наблюдается никаких улучшений.

# pop_size - размер популяции
# mutprob - чем меньше, тем реже берем мутацию и чаще скрещивание
# elite - Доля особеq в популяции, считающихся хорошими решениями и переходящих в следующее поколение
# maxiter - Количество поколений

def genetic_optimize(domain, costf, pop_size=50, step=1, mutprob=0.2, elite=0.2, maxiter=100):
 
 # Мутация
 def mutate(vec):
  i = random.randint(0, len(domain)-1)
  if vec[i] < domain[i]:
   return vec[0:i]+[vec[i]+step]+vec[i+1:]
  else:
   return vec[0:i]+[vec[i]-step]+vec[i+1:]

 # Скрещивание
 def crossover(r1, r2):
  i = random.randint(1, len(domain)-2)
  return r1[0:i]+r2[i:]

 # Создаем первую популяцию
 pop = []
 for i in xrange(pop_size):
  vec = [random.randint(0, domain[i]) for i in xrange(len(domain))]
  pop.append(vec)

 # Сколько лучших оставляем из каждого поколения
 topelite = int(elite*pop_size)

 for i in xrange(maxiter):
  scores = [(costf(v), v) for v in pop]
  scores.sort()
  ranked = [v for (s,v) in scores]

  # Сначала включаем только победителеи
  pop = ranked[0:topelite]

  # Добавляем особей, полученных мутацией и скрещиванием победивших родителей
  while len(pop) < pop_size:

   if random.random() < mutprob:
    # Мутация
    c = random.randint(0, topelite)
    pop.append(mutate(ranked[c]))

   else:
    # Скрещивание
    c1 = random.randint(0, topelite)
    c2 = random.randint(0, topelite)
    pop.append(crossover(ranked[c1], ranked[c2]))

 return scores[0][1], scores[0][0]

Вместо вывода

Будет ли работать конкретный метод оптимизации, в значительной мере зависит от задачи. Метод имитации отжига, генетические алгоритмы и прочие методы оптимизации основаны на том факте, что в большинстве задач оптимальное решение близко к другим хорошим решениям. А на рисунке ниже представлен случай, когда оптимизация может и не сработать.

Оптимальная стоимость соответствует низшей точке очень крутого участка кривой в правой части рисунка. Любое достаточно близкое решение, скорее всего, будет отвергнуто из-за его высокой стоимости, поэтому мы никогда не сможем добраться до глобального минимума. Большинство алгоритмов остановятся в каком-то локальном минимуме в левой части рисунка.

Пример с составлением расписания полетов работает, потому что выбор второго рейса вместо третьего, скорее всего, изменит стоимость менее значительно, чем выбор восьмого рейса. Если бы рейсы были упорядочены случайным образом, то методы оптимизации работали бы не лучше случайного поиска; на самом деле не существует ни одного метода оптимизации, который в этом случае работал бы устойчиво лучше, чем случайный поиск.

Кластеризация данных

2014-10-12T16:37:00.001-07:00

Кластеризация данных – это метод обнаружения и визуализации групп связанных между собой предметов. Данный инструмент часто используется в приложениях, обрабатывающих большие объемы данных. Кластеризация – пример обучения без учителя. В отличие от нейронных сетей или деревьев решений, алгоритмам обучения без учителя не сообщаются правильные ответы. Их задача – обнаружить структуру в наборе данных, когда ни один элемент данных не является ответом.

Постановка задачи

Совсем недавно, компания Adobe, выпустила на iPhone програмку Adobe Color CC. До меня дошла эта новость и я понял, что пора объяснить, как же это делается!) Метод известный и описан во многих местах, но наше - всегда лучше))) Задача у нас простая, методом K-средних сделать K кластеров цветов картинки и выявив центры кластеров, посмотреть какому цвету он соответствует. Таким образом мы узнаем основные тона картинки ;) Но сначала, немножко теории.

Иерархическая кластеризация

Методоово кластеризации бывает несколько, в основном, мы будем рассматривать метод k-средних, но есть так же и метод иерархической кластеризации. Алгоритм иерархической кластеризации строит иерархию групп, объединяя на каждом шаге две самые похожие группы. В начале каждая группа состоит из одного элемента, в данном случае – одного блога. На каждой итерации вычисляются попарные расстояния между группами, и группы, оказавшиеся самыми близкими, объединяются в новую группу. Так повторяется до тех пор, пока не останется всего одна группа.

Иерархическая кластеризация в действии

Здесь схожесть элементов представлена их относительным расположением – чем элементы ближе друг к другу, тем более они схожи. В начале каждый элемент – это отдельная группа. На втором шаге два самых лизких элемента A и B объединены в новую группу, расположенную посередине между исходными. На третьем шаге эта новая группа объединяется с элементом C. Поскольку теперь два ближайших элемента – это D и E, то из них образуется новая группа. И на последнем шаге две оставшиеся группы объединяются в одну.

Результаты иерархической кластеризации обычно представляются в виде графа, который называется дендрограммой. На нем изображено, как из узлов формировалась иерархия.

Дендрограмма как способ визуализации иерархической кластеризации

На дендрограмме представлены не только ребра графа, показывающие, из каких элементов составлен каждый кластер, но и расстояния, говорящие о том, как далеко эти элементы отстояли друг от друга. Кластер AB гораздо ближе к составляющим его элементам A и B, чем кластер DE к элементам D и E. Изображение графа таким образом помогает понять, насколько схожи элементы, вошедшие в кластер. Эта характеристика называется теснотой (tightness) кластера.

Иерархическая кластеризация дает на выходе симпатичное дерево, но у этого метода есть два недостатка. Древовидное представление само по себе не разбивает данные на группы, для этого нужна дополнительная работа. Кроме того, алгоритм требует очень большого объема вычисле- ний. Поскольку необходимо вычислять попарные соотношения, а затем вычислять их заново после объединения элементов, то на больших наборах данных алгоритм работает медленно. И тут на помощь приходит другой метод!)

Кластеризация методом k-средних

Он в корне отличается от иерархической кластеризации, поскольку ему нужно заранее указать, сколько кластеров генерировать. Алгоритм определяет размеры кластеров исходя из структуры данных.
Кластеризация методом K-средних начинается с выбора k случайно расположенных центроидов (точек, представляющих центр кластера). Каждому элементу назначается ближайший центроид. После того как назначение выполнено, каждый центроид перемещается в точку, рассчитываемую как среднее по всем приписанным к нему элементам. Затем назначение выполняется снова. Эта процедура повторяется до тех пор, пока назначения не прекратят изменяться.

На первом шаге случайно размещены два центроида (изображены темными кружками). На втором шаге каждый элемент приписан к ближайшему центроиду. В данном случае A и B приписаны к верхнему центроиду, а C, D и E – к нижнему. На третьем шаге каждый центроид перемещен в точку, рассчитанную как среднее по всем приписанным к нему элементам. После пересчета назначений оказалось, что C теперь ближе к верхнему центроиду, а D и E – по-прежнему ближе к нижнему. Окончательный результат достигается, когда A, B и C помещены в один кластер, а D и E – в другой.

В данном методе, ОЧЕНЬ важен выбор центроидов, т.к. в конечном итоге все точки к ним стянутся, но если все 4 будут очень близкие цвета и из них будут состоять большие области, то в конечном итоге вы и получите приблизительно одинаковые центры. Таким образом центроиды должны быть максимально разнесены (желательно равномерно и равноудаленно).

Для большего понимания приведу пример. Давайте рассмотрим такую картинку.

Чтобы решить поставленную задачу в такой, монотонной четко разделенной картинке, достаточно написать небольшой код:

def k_cluster_by_area(points, k=4):

 clusters_by_area = {}

 for point in points:
  clusters_by_area[point] = clusters_by_area.setdefault(point, 0) + 1

 sorted_x = sorted(clusters_by_area.items(), key=operator.itemgetter(1))

 return sorted_x[-k:]

Тут мы просто посчитали, сколько раз, какой цвет встречается, отсортировали и вывели k результатов. Этот метод можно применить к любому изображению, работает достаточно быстро, но есть НО! А именно, мы не получим ТОНАЛЬНОСТЬ картинки! Однако, как я писал выше, в нашей задаче важны центры, вот эту задачу и решает этот код!) Мы берем самые популярные цвета, за изначальные центры кластеров, а потом они постепенно мутируют) На самом деле, желательно брать не просто первые k, а посчитать все комбанации расстояний и выбрать k по макс расстояниям, чтобы центры не оказались рядом (например 2 оттенка серого). Но мне влом и вы сделаете это сами)

Надеюсь, стало яснее. Таким образом, как найти изначальные центры кластеров нам известно, осталось только свести все пиксели в эти точки. А теперь сам код:

def k_cluster(img, distance=euclidean, k=4):
 
 points = get_points(img)
 clusters = {}

 # центры кластеры
 cluster_centers = k_cluster_by_area(points, k)
 for cluster_center in cluster_centers:
  # avg_sum_coords - список сумм r, g, b координат всех пикселей кластера
  # count_points - кол-во пикселей в кластере
  # какие конкретно пиксели в кластере не запоминаем в целях экономии памяти и времени
  clusters[cluster_center] = {'avg_sum_coords':list(cluster_center), 'count_points':1}

 while len(points):

  # находим ближайшие точки к центрам кластеров
  bestmatches = {}
  for point in points:

   # расстояние каждой точки до каждого центра кластера
   for cluster_center in clusters:
    d = distance(cluster_center, point)
    if not bestmatches:
     bestmatches = {'distance':d, 'point': point, 'cluster_center': cluster_center}

    if d < bestmatches['distance']:
     bestmatches = {'distance': d, 'point': point, 'cluster_center': cluster_center}

  # перекидываем ближайшие точки в соответствующий кластер
  bestmatch = bestmatches['point']
  cluster_center = bestmatches['cluster_center']
  points2 = []
  new_points = []

  for point in points:
   if point == bestmatch:
    new_points.append(point)
   else:
    points2.append(point)


  points = points2[:]

  # меняем центр кластера
  print clusters.keys(), len(points)

  r_avg, g_avg, b_avg = 0, 0, 0
  cluster_avg_coord = clusters[cluster_center]['avg_sum_coords']

  new_points_len = len(new_points)
  clusters[cluster_center]['count_points'] += new_points_len
  claster_count_points = clusters[cluster_center]['count_points']

  cluster_avg_coord[0] += bestmatch[0]*new_points_len
  cluster_avg_coord[1] += bestmatch[1]*new_points_len
  cluster_avg_coord[2] += bestmatch[2]*new_points_len


  new_center = cluster_avg_coord[0]/claster_count_points, cluster_avg_coord[1]/claster_count_points, cluster_avg_coord[2]/claster_count_points
  
  # если новый центр кластера отличается от предыдущего
  if not new_center in clusters:
   clusters[new_center] = clusters.pop(cluster_center)

 return clusters.keys()

Работает это дело не быстро ;(, поэтому я советую сжимать картинку, хотя бы до разрешения 100 на 100.
Понятно, что идея не нова и сравнить вы можете, например с данным сайтом http://design-seeds.com
Давайте разберем пример. С указанного выше сайта взяли картинку и их разбиение на цвета. Здесь можно заметить, что их задача - это выбрать основные центровые цвета, что немного отличается от нашей задачи, но все же.

Пример с сайта

Сначала посмотрим на наш метод выбора первоначальных центров, исходя из предположения простого количественного показателя использования цветов. Изначальные центры ниже подписано, сколько раз цвет встречался на картинке.

7 раз

4 раза

5 раз

6 раз

Ммммм, кто бы сказал по картинке, что это самые часто встречающиеся цвета? Понятно, что это вызвано так же и сжатием до 100 пикселей по меньшей из сторон, но все же. Сразу можно сказать, что притягивать к таким центрам остальные цвета сложно. В результате:

Все плохо, как и следовало ожидать. А что если попробовать представить спектр цветов в виде прямой от 0 до 255, равномерно разбить его на k отрезков и сделать центры точками с одинаковыми равномерными координатами? По понятным причинам они все будут оттенками серого. Пример для 6:

В результате:

Вот, уже лучше) Однако, чем плох этот метод? А тем, что этих цветов может и не быть на картинке (она может просто красная), получается, что изначально мы как бы сбиваем мишень(

Как вывод, могу сказать, что метод k-средних очень чувствителен к этим самы центроидам. И их поиск - это не менее важная задача, которую я Вам и предлагаю решить) Например, представьте что вы как бы объединяете точки, расширяя территории. Объединяя их в 3х мерном пространстве линейно увеличивая координаты. И без учета количественных показателей весов!)

Обучение нейронной сети

2014-10-08T15:09:00.001-07:00

Одно из основных достоинств онлайновых приложений состоит в том, что они все время получают обратную связь в виде поведения пользователей. В случае поисковой машины каждый пользователь тут же сообщает о том, насколько ему понравились результаты поиска, щелкая по одному результату и игнорируя остальные. Мы рассмотрим способ регистрации действий пользователя после получения результатов и то, как собранную таком образом информацию можно применить для более качественного ранжирования результатов.

Итак, для тех, кто справился с предыдущей статьей, создал и запустил своего поискового робота, сегодня мы построим и обучим искусственную нейронную сеть. Предлагая ей поисковой запрос, результаты обработки запроса и ту ссылку, по которой пользователь пе- решел, мы научим нейронную сеть, как использовать для упорядочения результатов поиска, реальный выбор пользователя.

Проектирование сети отслеживания переходов

Есть много разновидностей нейронных сетей, но все они состоят из множества узлов (нейронов) и связей между ними (синапсов). Мы собираемся построить MLP сеть (multilayer perceptron). Такая сеть состоит из нескольких уровней нейронов, первый из которых принимает входные данные – в данном случае поисковой запрос. Последний уровень возвращает результаты – список весов найденных URL.

Промежуточных уровней может быть много, но мы ограничимся только одним. Он называется скрытым уровнем, так как не взаимодействует напрямую с внешним миром, а реагирует на комбинации входных данных.

Общий принцип таков, значения входных узлов для указанных в запросе слов устанавливают равными 1. Включаются выходы этих узлов, и они пытаются активировать скрытый слой. В свою очередь, узлы скрытого слоя, получающие достаточно сильный входной сигнал, включают свои выходы и пытаются активировать узлы выходного уровня. Узлы выходного уровня оказываются активны в разной степени, и по уровню их активности можно судить, как сильно данный URL ассоциирован со словами исходного запроса. Разумеется, для этого необходимо, чтобы сила связей была установлена правильно. Это достигается обучением сети всякий раз, как кто-то выполняет поиск и выбирает один из результатов.

Уровни в БД: word_list word_hidden hidden_node hidden_urls url_list .

Как пример, в сети, изображенной на рисунке выше, сколько-то человек переходили на сайт Всемирного банка (World Bank) после запроса world bank, и это усилило ассоциацию между данными словами и URL. Сплошными линиями показаны сильные связи, а полужирный текст говорит о том, что узел стал очень активным.

Мы будем обучать сеть с помощью алгоритма обратного распространения backpropagation.

Прошу обратить внимание на подпись под картинкой. Каждый уровень (прямоугольничек или стрелочка) имеет свое отображение в БД. Я подписал названия таблиц им соответствующих, для большего понимания, что мы будем делать, но если сейчас Вам что-то не очень понятно, вернитесь к прочтению данного принципа, после описания механизма работы и все встанет на свои места!)

Подготовка базы данных

У тех, кто осилил прошлую статью, уже есть 2 таблицы - это word_list и url_list, где хранятся списки слов и урлов, соответственно. Теперь нужно еще 3: 1 - hidden_node (скрытый слой) и 2 таблицы связи с ним (одна hidden_word – для связей между слоем слов и скрытым слоем, другая hidden_url – для связей между скрытым и выходным слоем).

Нам потребуется два метода для доступа к базе данных. Первый, get_strength, определяет текущую силу связи. Поскольку новые связи создаются только по мере необходимости, этот метод должен возвращать некое специальное значение, если связей еще нет. Для связей между словами и скрытым слоем мы выберем в качестве такого значения –0,2, так что по умолчанию дополнительные слова будут несколько снижать уровень активации скрытого узла. Для связей между скрытым слоем и URL метод по умолчанию будет возвращать значение 0.

 def get_strength(self, from_id, to_id, layer):

  if layer == 0: 
   table = 'word_hidden'
  else: 
   table = 'hidden_url'

  self.cur.execute('select strength from %s where from_id = %d and to_id = %d' % (table, from_id, to_id))
                res = self.cur.fetchone()

  if res == None: 
   if layer == 0: 
    return -0.2

   if layer == 1: 
    return 0
    
  return res[0]

Еще необходим метод set_strength, который выясняет, существует ли уже связь, и создает либо обновляет связь, приписывая ей заданную силу. Он будет использоваться в коде для обучения сети:

 def set_strength(self, from_id, to_id, table, strength):

  self.cur.execute('select id from %s where from_id = %d and to_id = %d' % (table, from_id, to_id))
  res = self.cur.fetchone()

  if res == None: 
   self.cur.execute('insert into %s (from_id, to_id, strength) values (%d, %d, %f)' % (table, from_id, to_id, strength))
  else:
   row_id = res[0]
   self.cur.execute('update %s set strength = %f where id = %d' % (table, strength, row_id))

  self.db_commit()

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

Следующая функция создает новый скрытый узел всякий раз, как ей передается не встречавшаяся ранее комбинация слов. Затем она создает связи с весами по умолчанию (для url сила маленькая, т.к. сеть не обучена, пусть 0.1, а для слов в сумме = 1) между этими словами и скрытым узлом и между узлом запроса и URL, который этот запрос возвращает.

 def generate_hidden_node(self, word_ids, urls):

                # Для простоты ограничимся 2-х словными фразами
  if len(word_ids) > 3: 
   return None

  # Проверить, создавали ли мы уже узел для данного набора слов
  sorted_words = map(str, word_ids)
  sorted_words.sort()
  create_key = '_'.join(sorted_words)
  self.cur.execute("select count(id) from hidden_node where create_key = '%s'" % create_key)
  count_hidden_id = self.cur.fetchone()

  # Если нет, создадим сейчас
  if not count_hidden_id:
   self.cur.execute("insert into hidden_node (create_key) values ('%s')  returning hidden_node.id" % create_key)
   hidden_id = self.cur.fetchone()[0]

   # Задать веса по умолчанию
   for word_id in word_ids:
    self.set_strength(word_id, hidden_id, 'word_hidden', 1.0/len(word_ids))

   for url_id in urls:
    self.set_strength(hidden_id, url_id, 'hidden_url', 0.1)

   self.db_commit()

Прямой проход

Теперь все готово для написания функций, которые принимают на входе слова, активируют связи в сети и формируют выходные сигналы для URL.

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

Функция tanh

По оси X откладывается входной сигнал, подаваемый узлу. В окрестности 0 выходной сигнал быстро нарастает. Когда сила входного сигнала равна 2, выходной сигнал почти равен 1 и дальше уже почти не растет. Функции такого типа называются сигмоидными, они имеют форму буквы S. Для вычисления силы выходного сигнала нейронов в нейронных сетях почти всегда используются сигмоидные функции.

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

 def get_all_hidden_ids(self, word_ids, url_ids):

  l1 = {}
  for word_id in word_ids:

   self.cur.execute('select to_id from word_hidden where from_id = %d' % word_id)
   cur = self.cur.fetchall()

   for row in cur:
    l1[row[0]] = 1

  for url_id in url_ids:

   cur = self.cur.execute('select from_id from hidden_url where to_id = %d' % url_id)
   cur = self.cur.fetchall()
   
   for row in cur:

    l1[row[0]] = 1

  return l1.keys()

Нам также понадобится метод для конструирования релевантной сети с текущими весами из базы данных. Эта функция инициализирует различные переменные экземпляра класса: список слов, относящиеся к запросу узлы и URL, уровень выходного сигнала для каждого узла и веса всех связей между узлами. Веса считываются из базы данных с помощью ранее разработанных функций.

 def setup_network(self, word_ids, url_ids):

  # списки значений
  self.word_ids = word_ids
  self.hidden_ids = self.get_all_hidden_ids(word_ids, url_ids)
  self.url_ids = url_ids

  # выходные сигналы узлов
  self.hidden_word_output = [1.0]*len(self.word_ids)
  self.hidden_layer_output = [1.0]*len(self.hidden_ids)
  self.hidden_url_output = [1.0]*len(self.url_ids)

  # создаем матрицу весов
  self.word_layer_weights = [
     [self.get_strength(word_id, hidden_id, 0) for hidden_id in self.hidden_ids] for word_id in self.word_ids
       ]

  self.layer_url_weights = [
     [self.get_strength(hidden_id, url_id, 1) for url_id in self.url_ids] for hidden_id in self.hidden_ids
     ]

Вот теперь все готово для реализации алгоритма feedforward. Он принимает список входных сигналов, пропускает их через сеть и возвращает выходные сигналы от всех узлов на выходном уровне. Поскольку в данном случае мы сконструировали сеть только для слов, входящих в запрос, то выходной сигнал от всех входных узлов равен 1:

 def feed_forward(self):

  # единственные входные сигналы – слова из запроса
  for i in xrange(len(self.word_ids)):
   self.hidden_word_output[i] = 1.0

  # возбуждение скрытых узлов
  for j in xrange(len(self.hidden_ids)):
   sum = 0.0
   for i in xrange(len(self.word_ids)):
    sum = sum + self.hidden_word_output[i] * self.word_layer_weights[i][j]
   self.hidden_layer_output[j] = tanh(sum)

  # возбуждение выходных узлов
  for k in xrange(len(self.url_ids)):
   sum = 0.0
   for j in range(len(self.hidden_ids)):
    sum = sum + self.hidden_layer_output[j] * self.layer_url_weights[j][k]
   self.hidden_url_output[k] = tanh(sum)

  return self.hidden_url_output[:]

Алгоритм feedforward в цикле обходит все узлы скрытого слоя и для каждого из них вычисляет сумму величин выходных сигналов от узлов входного слоя, помноженных на вес соответствующей связи. Выходной сигнал каждого скрытого узла – это результат применения функции tanh к взвешенной сумме входных сигналов. Этот сигнал передается на выходной уровень. Выходной уровень делает то же самое – умножает полученные от предыдущего уровня сигналы на веса связей и применяет функцию tanh для получения окончательного результата. Сеть можно легко обобщить, введя дополнительные уровни, которые будут преобразовывать выходные сигналы от предыдущего уровня во входные сигналы следующему.

Теперь можно написать небольшую функцию, которая подготовит сеть и вызовет метод feedforward для получения реакции на заданный набор слов и URL:

 def get_result(self, word_ids, url_ids):

  self.setup_network(word_ids, url_ids)
  return self.feed_forward()

Числа в полученном списке обозначают релевантность поданных на вход URL. Не удивляйтесь, что для всех URL нейронная сеть выдает один и тот же ответ, ведь она еще не прошла обучения!)

Обучение с обратным распространением

А вот теперь начинаются самое интересное. Сеть принимает вход- ные сигналы и генерирует выходные, но, поскольку ее не научили, какой результат считать хорошим, выдаваемые ею ответы практически бесполезны. Сейчас мы это исправим!)

Чтобы это сделать, нам необходим алгоритм, который будет изменять веса связей между узлами, так чтобы сеть поняла, как выглядит пра- вильный ответ. Веса следует подстраивать постепенно, поскольку нельзя предполагать, что ответ, выбранный одним пользователем, устроит и всех остальных. Описанный ниже алгоритм называется обратным распространением, поскольку в процессе подстройки весов он продвигается по сети в обратном направлении.

Во время обучения сети вы в каждый момент знаете желаемый выходной сигнал. В данном случае необходимо получить 1, если пользователь перешел по ссылке, и 0 в противном случае. Изменить выходной сигнал узла можно только одним способом – изменить сигнал, поданный ему на вход.

Чтобы определить, насколько следует изменить суммарный входной сигнал, алгоритм обучения должен знать наклон функции tanh для текущего уровня выходного сигнала. В средней точке графика, когда выходной сигнал равен 0, функция изменяется очень круто, поэтому небольшое изменение входного сигнала приводит к большому изменению выходного. По мере того как уровень выходного сигнала приближается к –1 или к 1, изменение входного сигнала меньше сказывается на выходном. Наклон нашей функции для любого значения выходного сигнала вычисляется с помощью следующей функции:

def dtanh(y):
 return 1.0 - y*y

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

Для каждого узла из выходного слоя необходимо:

Вычислить разность между текущим и желательным уровнем выходного сигнала.
С помощью функции dtanh определить, насколько должен измениться суммарный входной сигнал для этого узла.
Изменить вес каждой входящей связи пропорционально ее текущему весу и скорости обучения.

Для каждого узла в скрытом слое необходимо:

Изменить выходной сигнал узла на сумму весов каждой выходной связи, умноженных на величину требуемого изменения выходного сигнала конечного узла этой связи.
С помощью функции dtanh вычислить, насколько должен измениться суммарный входной сигнал для этого узла.
Изменить вес каждой входящей связи пропорционально ее текущему весу и скорости обучения.

 def back_propagate(self, targets, N=0.5):

  # вычислить поправки для выходного слоя
  output_deltas = [0.0] * len(self.urlids)
  for k in xrange(len(self.urlids)):
   error = targets[k] - self.hidden_url_output[k]
   output_deltas[k] = dtanh(self.hidden_url_output[k]) * error

  # вычислить поправки для скрытого слоя
  hidden_deltas = [0.0] * len(self.hiddenids)
  for j in xrange(len(self.hiddenids)):
   error = 0.0
   for k in xrange(len(self.urlids)):
    error = error + output_deltas[k]*self.layer_url_weights[j][k]
   hidden_deltas[j] = dtanh(self.hidden_layer_output[j]) * error

  # обновить веса связеи между узлами скрытого и выходного слоя
  for j in xrange(len(self.hiddenids)):
   for k in xrange(len(self.urlids)):
    change = output_deltas[k]*self.hidden_layer_output[j]
    self.layer_url_weights[j][k] = self.layer_url_weights[j][k] + N*change

  # обновить веса связей между узлами входного и скрытого слоя
  for i in xrange(len(self.wordids)):
   for j in xrange(len(self.hiddenids)):
    change = hidden_deltas[j]*self.hidden_word_output[i]
    self.word_layer_weights[i][j] = self.word_layer_weights[i][j] + N*change

Осталось только написать простой метод, который подготовит сеть, вызовет алгоритм feed_forward и запустит обратное распространение. Этот метод принимает в качестве параметров списки word_ids, url_ids и выбранный URL:

 def train_query(self, word_ids, url_ids, selected_url_id): 

  # сгенерировать скрытыи узел, если необходимо
  self.generate_hidden_node(word_ids, url_ids)

  self.setup_network(word_ids, url_ids)      
  self.feed_forward()
  targets = [0.0]*len(urlids)
  targets[urlids.index(selected_url_id)] = 1.0
  error = self.back_propagate(targets)
  self.update_database()

Для сохранения результатов понадобится метод записи в базу данных новых весов, которые хранятся в переменных экземпляра word_layer_weights и layer_url_weights:

 def update_database(self):
  
  for i in xrange(len(self.word_ids)):
   for j in xrange(len(self.hidden_ids)):
    self.set_strength(self.word_ids[i], self. hidden_ids[j], 0, self.word_layer_weights[i][j])

  for j in xrange(len(self.hidden_ids)):
   for k in xrange(len(self.url_ids)):
    self.set_strength(self.hidden_ids[j], self.url_ids[k], 1, self.layer_url_weights[j][k])

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

Подключение к поисковой машине

Ну вот и все!) Нам осталось только подключить результаты работы сети к поисковой машине. Это для тех, кто читал прошлую статью). Соответствующая функция похожа на все остальные весовые функции.

def neiron_net_score(self, rows, word_ids):

  # Get unique URL IDs as an ordered list
  url_ids = [row[0] for row in rows]

  nn_res = self.neiron_net.get_result(word_ids, url_ids)
  scores = {url_ids[i]: nn_res[i] for i in xrange(len(url_ids))}
  return self.normalize_scores(scores)

Включите его в список weights и поэкспериментируйте с заданием разных весов. На практике следует повременить с привлечением этого метода к реальному ранжированию до тех пор, пока сеть не обучится на большом числе примеров.

Мы не уделяли внимание вопросам производительности, но безусловно - это очень острый вопрос в таких системах. Тут я полностью доверяю Вам!)

Поиск и ранжирование

2014-10-05T14:44:00.002-07:00

Сегодня мы рассмотрим систему полнотекстового поиска, она позволяют искать слова в большом наборе документов и сортируют результаты поиска по релевантности найденных документов запросу. Алгоритмы полнотекстового поиска относятся к числу важнейших среди алгоритмов коллективного разума. Новые идеи в этой области помогли сколотить целые состояния. Широко распространено мнение, что своей быстрой эволюцией от академического проекта к самой популярной поисковой машине в мире система Google обязана прежде всего алгоритму ранжирования страниц PageRank.

Что такое поисковая машина

Итак, давайте же создадим здоровую конкуренцию мировым поисковикам!) Статья так же будет полезна начинающим SEO специалистам, т.к. покажет некоторые величины, которые могут влиять на позиции вашего сайта в поиске.

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

Далее собранные документы необходимо проиндексировать. Обычно для этого строится большая таблица, содержащая список документов и вхождений различных слов. В зависимости от конкретного приложения сами документы могут и не храниться в базе данных; в индексе находится лишь ссылка (путь в файловой системе или URL) на их местонахождение

Ну и последний шаг – это, конечно, возврат ранжированного списка документов в ответ на запрос. Имея индекс, найти документы, содержащие заданные слова, сравнительно несложно; хитрость заключается в том, как отсортировать результаты. Можно придумать огромное количество метрик, и недостатков в них.

Итак, для данной задачи нам потребуется DB (PostgreSQL) и Python (библиотека Grab). А за источник индексирования, новостную ленту rambler'а.

Все функции, описаные ниже, у меня являются методами классов, с такой инициализацией:

class Indexer:

 def __init__(self):
   
  self.conn = psycopg2.connect("dbname='postgres' user='postgres' password='120789' host='localhost'")

  self.cur = self.conn.cursor()
  self.cur.execute("set search_path to 'rambler_search'")

  self.grab = Grab()

 def __del__(self):
  self.conn.close()

 def dbcommit(self):
  self.conn.commit()

Код паука

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

Эта функция в цикле обходит список страниц, вызывая для каждой функцию addtoindex. Далее она получает все ссылки на данной странице и добавляет их URL в список newpages. В конце цикла newpages присваивается pages, и процесс повторяется.

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

  
  # Начинаем со списка страниц для индексации
  # опускаемся в глубину на 2 уровня
 def crawl(self, pages, depth=2):

  rambler_news_href_pattern = re.compile(r'(^http:\/\/news\.rambler\.ru\/[\d]+)')

  for i in range(depth):
   newpages={}

   for page in pages:

    try:
      self.grab.go(page)

    except:
      print "Could not open %s" % page
      continue

    try:
      article_text = '' # текст статьи
      for paragraph in self.grab.tree.xpath("//p[contains(@class, 'b-article__paragraph')]"):
      article_text += paragraph.text_content()

      self.addtoindex(page, article_text) # записываем в базу текст статьи с индексацией

      links = self.grab.tree.xpath("//a")
      for link in links:

     if ('href' in link.attrib):
       url = urljoin(page, link.attrib['href']).split('#')[0]# делаем полную ссылку и удаляем часть за # если она есть

       match = rambler_news_href_pattern.findall(url)
       if match:
        url = match[0]

      if url[0:4] == 'http' and not self.isindexed(url):
       newpages[url] = 1

      linkText = link.text_content() # текст ссылки
      self.addlinkref(page, url, linkText) # записываем в базу текст ссылки с индексацией

      self.dbcommit()

    except Exception, e:
      print "Could not parse page %s" % page, e

   pages = newpages

Построение индекса

Наш следующий шаг – подготовка базы данных для хранения полнотекстового индекса. Я уже говорил, что такой индекс представляет собой список слов, с каждым из которых ассоциировано множество документов, где это слово встречается, и место вхождения слова в документ. В данном примере мы анализируем только текст на странице, игнорируя все нетекстовые элементы. Кроме того, индексируются только сами слова, а все знаки препинания удаляются. Такой метод выделения слов несовершенен, но для построения простой поисковой машины сойдет.

Создание схемы

Подождите запускать программу – нужно сначала подготовить базу данных. Схема простого индекса состоит из пяти таблиц. Первая (url_list) – это список проиндексированных URL. Вторая (word_list) – список слов, а третья (word_location) – список мест вхождения слов в документы. В оставшихся двух таблицах хранятся ссылки между документами. В таблице link хранятся идентификаторы двух URL, связанных ссылкой, а в таблице link_words есть два столбца – word_id и link_id – для хранения слов, составляющих ссылку. Вся схема изображена на рисунке ниже. Код запросов приводить не буду, должны ведь и вы поработать)))

Выделение слов на странице

Для решения данной задачи, воспользуемся простейшей функцией. Мы не будем вводить стоп слова, которые не нужно индексировать, а просто введем ограничение на длину слова в 3 символа, тем самым убрав предлоги и другой мусор (хоть и пострадают всякие мелкие слова, типа "мир", "тир", "пир").

def getwords(html):
    words = []
    for split_str in html.split():
        t = re.split("[\s;:\-_*\".,?!()'&#«»]", split_str)
        words += [a.lower() for a in t if a != '' and len(a) > 3]
    return words

Добавление в индекс

Теперь мы готовы написать код метода addtoindex. Он вызывает две функции, написанные в предыдущем разделе, чтобы получить список слов на странице. Затем эта страница и все найденные на ней слова добавляются в индекс и создаются ссылки между словами и их вхождениями в документ. В нашем примере адресом вхождения будет считаться номер слова в списке слов.

  
        def addtoindex(self, url, text):

  if self.isindexed(url): return # если уже индексирована - пропускаем
  print 'Indexing %s' % url

  # Получаем слова из текста
  words = getwords(text)

  # Получаем id url'а
  url_id = self.getentryid('url_list', 'url', url)

  # Связываем слова с этим урлом
  for i, word in enumerate(words): # пронумеруем слова
    word_id = self.getentryid('word_list', 'word', word)
    self.cur.execute("insert into word_location(url_id, word_id, location) values (%d, %d, %d)" % (url_id, word_id, i))
    self.dbcommit()

Хорошо, теперь нужно описать функцию getentryid - возвращающую id записи из бд и isindexed - проверяющую, не индексировали ли мы эту страницу раньше.

  
        # Узнаем id записи в БД, если нет
        # иначе записываем и возвращаем новый
 def getentryid(self, table, field, value, createnew=True):

  self.cur.execute("select id from %s where %s = '%s'" % (table, field, value))
  cur = self.cur.fetchone()

  if not cur:
   # print (table, field, value)
   self.cur.execute("insert into %s (%s) values ('%s') returning %s.id" % (table, field, value, table))
   cur = self.cur.fetchone()
   self.dbcommit()

   return cur[0]

  else:
    return cur[0]

       # Возвращаем True, если посещали страницу
 def isindexed(self, url):
  self.cur.execute("select id from url_list where url = '%s'" % url)
  u = self.cur.fetchone()

  if u:
   # Проверяем, что паук посещал страницу
   self.cur.execute("select count(1) from word_location where url_id = %d" % u[0])
   v = self.cur.fetchone()

   if v[0]:
    return True

  return False

Последняя функция, необходимая нам для начала индексирования - это addlinkref. Как следует из ее названия, она заносит ссылки и слова из которых они состоят к нам в БД.

 def addlinkref(self, urlFrom, urlTo, linkText):

  words = getwords(linkText)
  from_id = self.getentryid('url_list', 'url', urlFrom)
  to_id = self.getentryid('url_list', 'url', urlTo)

  if from_id == to_id: return

  self.cur.execute("insert into link(from_id, to_id) values (%d, %d) returning link.id" % (from_id, to_id))
  link_id = self.cur.fetchone()[0]

  for word in words:

    word_id = self.getentryid('word_list', 'word', word)
    self.cur.execute("insert into link_words(link_id, word_id) values (%d, %d)" % (link_id, word_id))

Ну что же, на этом этапе мы можем запустить паука и создать базу данных)

Запросы

Теперь, когда у нас есть материал, с которым можно работать, необходимо написать сам поисковик. Начнем мы с малого, грубого поиска, по абсолютному вхождению фразы в новость.

Таблица word_location обеспечивает простой способ связать слова с документами, так что мы можем легко найти, какие страницы содержат данное слово. Однако поисковая машина была бы довольно слабой, если бы не позволяла задавать запросы с несколькими словами. Чтобы исправить это упущение, нам понадобится функция, которая принимает строку запроса, разбивает ее на слова и строит SQL-запрос для поиска URL тех документов, в которые входят все указанные слова.

 def get_match_rows(self, query):

  select_query_add = []
  join_query_add = []
  where_query_add = []

  main_search_query = """ 
     SELECT wl0.url_id, %s
     FROM word_location wl0
     %s 
     WHERE %s
    """

  query_words = getwords(query)

  query_word_ids = []
  for query_word in query_words:

   self.cur.execute("select id from word_list where word = '%s'" % query_word)
   query_word_id = self.cur.fetchone()

   if query_word_id:
    query_word_ids.append(query_word_id[0])

  if query_word_ids:
   for position, query_word_id in enumerate(query_word_ids):

    if position:
     join_query_add.append('JOIN word_location wl%d ON wl%d.url_id = wl%d.url_id' % (position, position-1, position))

    select_query_add.append('wl%d.location' % position)
    where_query_add.append('wl%d.word_id = %d' % (position, query_word_id))

   main_search_query = main_search_query % (', '.join(select_query_add), ' '.join(join_query_add), ' and '.join(where_query_add))

   self.cur.execute(main_search_query)
   search_results = self.cur.fetchall()
   
   return search_results, query_word_ids

Данная функция всего лишь создает строгий JOIN, типа такого:

 
 SELECT wl0.url_id, wl0.location, wl1.location
 FROM word_location wl0
 JOIN word_location wl1 ON wl0.url_id = wl1.url_id 
 WHERE wl0.word_id = 2734 and wl1.word_id = 2698

В результате, получаем список кортежей и список с id слов. Каждый кортеж - это сто список вида (id новости, позиция 1го слова, позиция 2го слова...)

Ранжирование по содержимому

Итак, худо-бедно, но мы научились искать по индексу. Однако возвращаем мы их в том порядке, в котором они посещались пауком. Чтобы решить эту проблему, необходимо как-то присвоить страницам ранг относительно данного запроса и уметь возвращать их в порядке убывания рангов.

В этом разделе мы рассмотрим несколько способов вычисления ранга
на основе самого запроса и содержимого страницы, а именно:

Частота слов

Количество вхождений в документ слова, указанного в запросе, помогает определить степень релевантности документа.

Расположение в документе

Основная тема документа, скорее всего, раскрывается ближе к его началу.

Расстояние между словами

Если в запросе несколько слов, то они должны встречаться в документе рядом.

Самые первые поисковые машины (кстати rambler.ru) часто работали только с подобными метриками и тем не менее давали пристойные результаты. Давайте добавим следующие методы:

 # Функция, которая взвешивает результаты
 def get_scored_list(self, rows, word_ids):

  total_scores = {row[0]: 0 for row in rows}

  if rows:
   # Список весовых функций
   weight_functions = [
      ]

   for (weight, scores) in weight_functions:
     for url in total_scores:
    total_scores[url] += weight * scores[url]

  return total_scores

 # Возвращает полный урл по id
 def get_url_name(self, url_id):

  self.cur.execute("select url from url_list where id = %d" % url_id)

  return self.cur.fetchone()[0]

 # Основная функция поиска
 def search(self, search_sentence):

  search_results, word_ids = self.get_match_rows(search_sentence)
  scores = self.get_scored_list(search_results, word_ids)

  ranked_scores = [(score, url) for (url, score) in scores.items()]
  ranked_scores.sort()
  ranked_scores.reverse()

  for (score, url_id) in ranked_scores[0:10]:
    print '%f\t%s' % (score, self.get_url_name(url_id))

  return word_ids, [r[1] for r in ranked_scores[0:10]]

Наиболее важна здесь функция get_scored_list, код которой мы будем постепенно уточнять. По мере добавления функций ранжирования мы будем вводить их в список weight_functions и начнем взвешивать полученные результаты.

Функция нормализации

Все рассматриваемые ниже функции ранжирования возвращают словарь, в котором ключом является идентификатор URL, а значением – числовой ранг. Иногда лучшим считается больший ранг, иногда – меньший. Чтобы сравнивать результаты, получаемые разными методами, необходимо как-то нормализовать их, то есть привести к одному и тому же диапазону и направлению.
Функция нормализации принимает на входе словарь идентификаторов и рангов и возвращает новый словарь, в котором идентификаторы те же самые, а ранг находится в диапазоне от 0 до 1. Ранги масштабируются по близости к наилучшему результату, которому всегда припи- сывается ранг 1. От вас требуется лишь передать функции список рангов и указать, какой ранг лучше – меньший или больший:

 def normalize_scores(self, scores, smallIsBetter=0):

  vsmall = 0.00001 # Avoid division by zero errors

  if smallIsBetter:
   minscore = min(scores.values())
   return {u: float(minscore)/max(vsmall, l) for (u,l) in scores.items()}

  else:
   maxscore = max(scores.values())
   if maxscore == 0: maxscore = vsmall
   return {u: float(c)/maxscore for (u,c) in scores.items()}

  return scores

Отлично! Пора заняться весовыми функциями, для которых мы и придумали эту нормализацию.

Весовые функции

Частота слов

Метрика, основанная на частоте слов, ранжирует страницу исходя из того, сколько раз в ней встречаются слова, упомянутые в запросе. Если я выполняю поиск по слову python, то в начале списка скорее получу страницу, где это слово встречается много раз, а не страницу о музыканте, который где-то в конце упомянул, что у него дома живет питон.

def frequency_score(self, rows):

  counts = {row[0]:0 for row in rows}
  for row in rows: 
   counts[row[0]] += 1

  return self.normalize_scores(counts)

Чтобы активировать ранжирование документов по частоте слов, измените строку функции get_scored_list, где определяется список weight_functions, следующим образом:

weight_functions = [(1.0,self.frequency_score(rows))]

Запустите поиск снова и радуйтесь!)

Расположение в документе

Еще одна простая метрика для определения релевантности страницы запросу – расположение поисковых слов на странице. Обычно, если страница релевантна поисковому слову, то это слово расположено близко к началу страницы, быть может, даже находится в заголовке.

def location_score(self, rows):

  locations = {}
  for row in rows:
   loc = sum(row[1:])
   if locations.has_key(row[0]):
    if loc < locations[row[0]]:
     locations[row[0]] = loc
   else:
    locations[row[0]] = loc

  return self.normalizescores(locations, smallIsBetter=1)

Расстояние между словами

Если запрос содержит несколько слов, то часто бывает полезно ранжировать результаты в зависимости от того, насколько близко друг к другу встречаются поисковые слова. Как правило, вводя запрос из нескольких слов, человек хочет найти документы, в которых эти слова концептуально связаны. Рассматриваемая метрика допускает изменение порядка и наличие дополнительных слов между поисковыми.

 def distance_score(self, rows):

  mindistance = {}

  # Если только 1 слово, любой документ выигрывает
  if len(rows[0]) <= 2:
   return {row[0]: 1.0 for row in rows}

  mindistance = {}

  for row in rows:
   dist = sum([abs(row[i]-row[i-1]) for i in xrange(2, len(row))])

   if mindistance.has_key(row[0]):
    if dist < mindistance[row[0]]:
     mindistance[row[0]] = dist
   else:
    mindistance[row[0]] = dist

  return self.normalize_scores(mindistance, smallIsBetter=1)

Использование внешних ссылок на сайт

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

Простой подсчет ссылок

Простейший способ работы с внешними ссылками заключается в том, чтобы подсчитать, сколько их ведет на каждую страницу, и использовать результат в качестве метрики. Так обычно оцениваются научные работы; считается, что их значимость тем выше, чем чаще их цитируют.

def inbound_link_score(self, rows):

  unique_urls = {row[0]: 1 for row in rows}
  inbound_count = {}
  
  for url_id in unique_urls:
   self.cur.execute('select count(*) from link where to_id = %d' % url_id)
   inbound_count[url_id] = self.cur.fetchone()[0]

  return self.normalize_scores(inbound_count)

Описанный алгоритм трактует все внешние ссылки одинаково, но такой уравнительный подход открывает возможность для манипулирования, поскольку кто угодно может создать несколько сайтов, указывающих на страницу, ранг которой он хочет поднять. Также возможно, что людям более интересны страницы, которые привлекли внимание каких-то популярных сайтов. Далее мы увидим, как придать ссылкам с популярных сайтов больший вес при вычислении ранга страницы.

Алгоритм PageRank

Алгоритм PageRank был придуман основателями компании Google, и вариации этой идеи теперь применяются во всех крупных поисковых машинах. Этот алгоритм приписывает каждой странице ранг, оценивающий ее значимость. Значимость страницы вычисляется исходя из значимостей ссылающихся на нее страниц и общего количества ссылок, имеющихся на каждой из них.

Теоретически алгоритм PageRank (названный по фамилии одного из его изобретателей Лари Пейджа (Larry Page)) рассчитывает вероятность того, что человек, случайно переходящий по ссылкам, доберется до некоторой страницы. Чем больше ссылок ведет на данную страницу с других популярных страниц, тем выше вероятность, что экспериментатор чисто случайно наткнется на нее. Разумеется, если пользователь будет щелкать по ссылкам бесконечно долго, то в конце концов он посетит каждую страницу, но большинство людей в какой-то момент останавливаются. Чтобы учесть это, в алгоритм PageRank введен коэффициент затухания 0,85, означающий, что пользователь продолжит переходить по ссылкам, имеющимся на текущей странице, с вероятностью 0,85.

Давайте рассмотрим пример:

Вычисление PageRank страницы A

Каждая из страниц B, C и D ссылается на A, и для них ранг уже вычис- лен. На странице B есть ссылки еще на три страницы, а на странице C – на четыре. D ссылается только на A. Чтобы вычислить ранг A, берем ранги (PR) каждой ссылающейся на A страницы, делим их на общее число ссылок на этой странице, складываем получившиеся значения, затем умножаем результат на коэффициент затухания 0,85 и добавляем минимальную величину 0,15. Вот как производится вычисление PR(A):

PR(A) = 0,15 + 0,85 × (PR(B)/ссылки(B) + PR(C)/ссылки(C) + + PR(D)/ссылки(D))
= 0,15 + 0,85 × (0,5/4 + 0,7/5 + 0,2/1) = 0,15 + 0,85 × (0,125 + 0,14 + 0,2)
= 0,15 + 0,85 × 0,465
= 0,54525

Обратите внимание, что D дает больший вклад в ранг A, чем B или C, хотя ее собственный ранг меньше. Это вызвано тем, что D ссылается только на A и, значит, привносит в результат свой ранг целиком.

Несложно, да? Увы, имеется тут небольшая ловушка – в данном при- мере для всех страниц, ссылающихся на A, уже вычислен ранг. Но невозможно вычислить ранг страницы, пока неизвестны ранги ссылающихся на нее страниц, а эти ранги можно вычислить, только зная ранги страницы, которые ссылаются на них. Так как же вычислить значение PageRank для множества страниц, ранги которых еще неизвестны?

Решение состоит в том, чтобы присвоить всем страницам произвольный начальный ранг (в программе ниже взято значение 1,0, но на самом деле точная величина несущественна) и провести несколько итераций. После каждой итерации ранг каждой страницы будет все ближе к истинному значению PageRank, как бы сходиться к некоему пределу, который и есть действительный PR. Количество необходимых итераций зависит от числа страниц.

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

 # Вычисляем PageRank страниц
 def calculate_page_rank(self, iterations=20):

  START_PR = 1
  self.cur.execute('update url_list set page_rank = %d' % START_PR)
  self.db_commit()

  for i in range(iterations):
   print "Iteration %d" % (i)
   self.cur.execute('select id from url_list')
   for url_id,  in self.cur.fetchall():

    # Конечный PR зависит от START_PR и этого базового pr
    pr = 0.15

    self.cur.execute('select distinct from_id from link where to_id = %d' % url_id)
    # Перебираем все страницы, ссылающиеся на данную
    for linker, in self.cur.fetchall():

     # Получаем PR ссылающейся страницы
     self.cur.execute('select page_rank from url_list where id = %d' % linker)
     linking_pr = self.cur.fetchone()[0]

     # Получаем общее количество ссылок на ссылающейся странице
     self.cur.execute('select count(*) from link where from_id = %d' % linker)
     linking_count = self.cur.fetchone()[0]
     pr += 0.85 * (linking_pr/linking_count)

     self.cur.execute('update url_list set page_rank = %f where id = %d' % (pr, url_id))
    self.db_commit()

Итак, запустили - вычислили, пора написать весовую функцию, использующую данную величину.

 def page_rank_score(self, rows):

  page_ranks = {row[0]: 0 for row in rows}

  for row in rows:
   self.cur.execute('select page_rank from url_list where id = %d' % row[0])
   page_ranks[row[0]] = self.cur.fetchone()[0]

  return self.normalize_scores(page_ranks)

Использование текста ссылки

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

 def link_text_score(self, rows, word_ids):

  link_scores = {row[0]: 0 for row in rows}

  word_ids_string = ','.join(map(str, word_ids))
  url_ids_string =  ','.join(set([str(row[0]) for row in rows]))

  self.cur.execute(''' select sum(u_l.page_rank), l.to_id
        from link l
        join link_words l_w on l.id = l_w.link_id
        join url_list u_l on u_l.id = l.from_id 
        where word_id IN (%s) and l.to_id IN (%s)
        group by l.to_id''' % (word_ids_string, url_ids_string))

  for sum_pr_url_from, url_id in self.cur.fetchall():
   link_scores['url_id'] = sum_pr_url_from

  return self.normalize_scores(link_scores)

Функция выбирает ссылки со словами поиска, которые ведут на новости, в которых они употребляются. Суммирует их PageRank's и возвращет этот навесок.

Вывод в продолжение

Поздравляю, вот мы и написали своего поискового робота!

Не существует стандартных весов для всех рассмотренных метрик, которые были бы одинаково хороши во всех случаях. Даже самые крупные поисковые машины часто изменяют методы ранжирования результатов. Метрики и назначаемые им веса сильно зависят от конкретного приложения.

Стоит заметить, что таких метрик может быть целая уйма (учет жирности написания слов, кол-во времени проведенного на странице и т.д.)! Не зря поисковики и их браузеры, так пристально следят за нашими действиями). Так что и Вы, придумывайте и улучшайте качество поиска! А в следующей статье, мы попробуем его немного поучить.

Подбор предметов

2014-08-12T15:42:00.001-07:00

Теперь вы знаете, как искать похожих людей и рекомендовать предметы данному человеку. Но что если нужно узнать, какие предметы похожи друг на друга? В данном случае вы можете определить степень сходства, выявив людей, которым понравился данный товар, и посмотрев, что еще им понравилось. По существу, это тот же метод, которым мы уже пользовались для определения похожести людей, – нужно лишь вместо людей всюду подставить товары. Излогаясь математическим языком - транспонировать)

Подбор схожих предметов

Произвидя поиск таким образом логика будет следующей: сравниваем 2 фильма и находим всех людей, которые смотрели оба фильма и смотрим оценки выставленные второму, если они хорошие, а лучше все 10ки)

Практика Евклида

select
v1.film_id, v2.film_id,
1/(1+(|/sum((v1.vote-v2.vote)^2))),--евклидово не взвешенное расстояние
count(1)--кол-во общих фильмов(вес для ф-ии)
from votes v1
join votes v2 on v1.user_id=v2.user_id 
where v1.film_id <> v2.film_id 
and v2.film_id=326
group by v1.film_id, v2.film_id
--having count(1)>10
order by 1/(1+(|/sum((v1.vote-v2.vote)^2))) desc, count(1) desc

Для сравнения возьмем фильм "Побег из Шоушенка". Метод Евклида посчитал, что на него больше всего похож фильм "Реал Мадрид". Спросите чем? Отвечу:

select
v1.film_id, v2.film_id,
v1.vote vote1, v2.vote vote2, v1.user_id, v2.user_id 
from votes v1
join votes v2 on v1.user_id=v2.user_id 
where v1.film_id <> v2.film_id 
and v2.film_id=326
and v1.film_id=155080

5 разных людей смотрели оба фильма и поставили не много не мало все 10ки!!! Но конечно, данный алгоритм никак не учитывает жанры, режиссеров или актеров. Однако никто не мешает ввести вам такие дополнительные фильтрующие весовые функции.

Практика Пирсона

select
v1.film_id,
case when ((sum(v1.vote^2)+1)-(sum(v1.vote)^2)/count(1)::float)*((sum(v2.vote^2)+1)-(sum(v2.vote)^2)/count(1)::float) <> 0
then
	(sum(v1.vote*v2.vote)-(sum(v1.vote)*sum(v2.vote))/count(1)::float)/(|/((sum(v1.vote^2)+1)-(sum(v1.vote)^2)/count(1)::float)*((sum(v2.vote^2)+1)-(sum(v2.vote)^2)/count(1)::float))
else
	0
end,
count(1)--кол-во общих критиков(вес для ф-ии)
from votes v1
join votes v2 on v1.user_id=v2.user_id 
where v1.film_id <> v2.film_id 
and v2.film_id=326 --фильм для сравнения
group by v1.film_id, v2.film_id
--having count(1)>10
order by 
case when ((sum(v1.vote^2)+1)-(sum(v1.vote)^2)/count(1)::float)*((sum(v2.vote^2)+1)-(sum(v2.vote)^2)/count(1)::float) <> 0
then
	(sum(v1.vote*v2.vote)-(sum(v1.vote)*sum(v2.vote))/count(1)::float)/(|/((sum(v1.vote^2)+1)-(sum(v1.vote)^2)/count(1)::float)*((sum(v2.vote^2)+1)-(sum(v2.vote)^2)/count(1)::float))
else
	0
end
desc,
count(1) desc

Запустив пирсона, получим совсем другой фильм - "Крезанутые". И это всего при 2х общих критиках. В общем советую Вам обратить внимание на закомментированную строку с having, считаю что нужно ее применить для более точного совпадения)

У коэффициента корреляции Пирсона есть одно интересное свойство, которое можно наблюдать на рисунке – он корректирует обесценивание оценок! Что я имею ввиду? А то, что представьте. 2 человека сравнивают цены и 2й всегда ставит на 1-2 бала ниже(ну пессимист он эдакий)))) А теперь начертите прямую в голове(или листочке)) и увидите, что прямая все равно проходит почти по диагонали, а значит считает, что они могут понравиться друг-другу (сугубо с точки зрения вкусов к фильмам...а может и нет))))!

Проблема нормализации

Но также у данного коэффициента есть одна плохая сторона. Он рассчитан наприменение к данным с нормальным распределением. А что будет, если какой то пользователь ставит всем фильмам одинаковые оценки? Можете подставить в формулу, например за место X и увидите, что в таком случае и знаменатель и числитель вырождаются в 0! Ведь это не правильно! Бывает так, что вы смотрели вместе 10 великолепных картин и он и вы ставили только 10ки и получается, что заместо коэффициента=1 мы получим 0! Геометрически такое поведение можно объяснить вырождением прямой в точку. Не знаю, как эта проблема решается правильно, а я предлагаю сделать искусственную нормализацию распределения оценок. Каким образом, а просто добавим и тому и другому оценку за несуществующий фильм отличную от тех, что они ставят, но одинаковые между собой. Причем опытным путем было замечено. что чем оценка меньше, тем меньше она влияет на коэффициент.

Какой оценкой подобия воспользоваться

Я ознакомил вас с двумя разными метриками, но есть и много других способов измерить подобие двух наборов данных. Какой из них оптимален – зависит от конкретного приложения. Имеет смысл попробовать и коэффициент Пирсона, и евклидово расстояние, и другие методы, а потом посмотреть, какой дает наилучшие результаты.

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

Практика Евклида

Все читали предыдущую статью? Если да то база готова и туда пишутся данные(у меня уже 12000 пользователей Ж) И пока их не много, можно запустить секретный скрипт прям в postgre и получить результатик) Если скрипт запустить как есть, то он будет сравнивать всех со всеми в поисках идеальных пар) Если же закомментить строку 7 и наоборот раскомментить 9(подставив нужный user_id) будем искать идеал только для кого то конкретного (например для себя любимого))))

select
v1.user_id, v2.user_id,
1/(1+(|/sum((v1.vote-v2.vote)^2))),--евклидово не взвешенное расстояние
count(1)--кол-во общих фильмов(вес для ф-ии)
from votes v1
join votes v2 on v1.film_id=v2.film_id 
and v1.user_id < v2.user_id --гениально и просто убираем дубли self джойна))
where v1.user_id <> v2.user_id
--and v2.user_id=113
group by v1.user_id, v2.user_id
order by 1/(1+(|/sum((v1.vote-v2.vote)^2))) desc, count(1) desc

У меня он выдал 197184 результата за 703882 ms. Короче чуть не уснул и это тысячах на 6 юзверях, но если вы подождете, то будете вознаграждены) Поиск же для кого-то конкретного проходит на ура и в миллисекунды :) Нужно сразу сказать, что здесь ф-ия евклида вычисляется для мнений по одному и тому же фильму и по этому эта оценка не взвешенная! Например есть люди, которые идеально друг другу подходят (т.е. 1 выдало ;) и все потому, что у них всего 1 общий фильм из 1000 и каждый поставил по 2 балла)))) Не думаю, что таких людей можно рекомендовать друг-дружке, как братьев по вкусу))) Поэтому результаты нужно взвесть и чем больше общих фильмов оценено - тем лучше(если что count(1) именно это и считает)

#Для ярых питонистов плюющих в души sql ворую код
# на вход prefs - словарь {чел1:{фильм1:оценка1, фильм2:оценка2,...}, чел2:{фильм?:оценка?,...}}
# кто-то может расширить ф-ию сравнения не 2х челов, а N :)
from math import sqrt

def sim_distance(prefs):
    
  person1, person2 = prefs.keys()
    
  # Получаем список фильмов, оцененных обоими
  si={item:1 for item in prefs[person1] if item in prefs[person2]}

  if si:

      # сложить квадраты разностей оценок
      sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2) 
                          for item in prefs[person1] if item in prefs[person2]])

      return 1/(1+sqrt(sum_of_squares))#sqrt добавил сам, кажись автор забыл)

  # если нет ни одной общей оценки, return 0
  return 0

Практика Пирсона

Прочитали описание коэффициента чуть выше? Тогда поехали)

Для начала скрипт sql, без искусственной нормализации!!!

select
    v1.user_id, v2.user_id,
    case when (sum(v1.vote^2)-(sum(v1.vote)^2)/count(1)::float)*(sum(v2.vote^2)-(sum(v2.vote)^2)/count(1)::float) <> 0
    then
        (sum(v1.vote*v2.vote)-(sum(v1.vote)*sum(v2.vote))/count(1)::float)/(|/((sum(v1.vote^2)-(sum(v1.vote)^2)/count(1)::float)*(sum(v2.vote^2)-(sum(v2.vote)^2)/count(1)::float)))
    else
        0
    end,
    count(1)--кол-во общих фильмов(вес для ф-ии)
from votes v1
join votes v2 on v1.film_id=v2.film_id 
where v1.user_id <> v2.user_id 
and v2.user_id=113 --ищем для конкретного пользователя(так быстрее)
group by v1.user_id, v2.user_id
order by 
    case when (sum(v1.vote^2)-(sum(v1.vote)^2)/count(1)::float)*(sum(v2.vote^2)-(sum(v2.vote)^2)/count(1)::float) <> 0
    then
        (sum(v1.vote*v2.vote)-(sum(v1.vote)*sum(v2.vote))/count(1)::float)/(|/((sum(v1.vote^2)-(sum(v1.vote)^2)/count(1)::float)*(sum(v2.vote^2)-(sum(v2.vote)^2)/count(1)::float)))
    else
        0
    end
    desc,
    count(1) desc

Снова сворую чужую функцию для Питонистов, но теперь с решением проблемы нормализации:

#На вход тоже, что и раньше
def sim_pearson(prefs):

  #вспомогательная ф-ия для удаления повторяющейся оценки
  def rem_vote(votes, choice_list):
 vote_for_rem = votes.pop()
 if vote_for_rem in choice_list:
  choice_list.remove(vote_for_rem)
 return choice_list#это не обязательно, т.к. элемент и так удален по ссылке, но явное лучше не явного)))

  # Получаем список фильмов, оцененных обоими
  si={}
  p1, p2 = prefs.keys()

  for item in prefs[p1]: 
    if item in prefs[p2]: si[item]=1

  #делаем нормализацию, если кто-то ставит одинаковые оценки всем фильмам
  #опытным путем пришел к тому, что чем меньше число добавляем, тем меньше его влияние
  votes1 = set([prefs[p1][it] for it in si])
  votes2 = set([prefs[p2][it] for it in si])

  if len(votes1) == 1 or len(votes2) == 1:

   choice_list = range(1, 4)#список возможных оценок от 1 до 4
   #удаляем повторяющиеся оценки
   if len(votes1) == 1:
    choice_list = rem_vote(votes1, choice_list)
   if len(votes2) == 1:
    choice_list = rem_vote(votes2, choice_list)

   it = 0#id несуществующего фильма 
   si[it] = 1#говорим, что оба оценивали фильм с этим id
   rand_vote = random.choice(choice_list)
   prefs[p1][it] = prefs[p2][it] = rand_vote
 ##############################

  # Число общих фильмов
  n=len(si)
        
  # Если общих фильмов нет
  if n==0: return 0
  
  # Суммы всех предпочтений
  sum1=sum([prefs[p1][it] for it in si])
  sum2=sum([prefs[p2][it] for it in si])
  
  # Суммы квадратов предпочтений
  sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
  sum2Sq=sum([pow(prefs[p2][it],2) for it in si]) 
  
  # Сумма произведений
  pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])
  
  # Вычисляем коэффициент
  num=pSum-(sum1*sum2/n)
  den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
  if den==0: return 0

  r=num/den

  return r

Немного о чувствительности критериев

К слову о том, каким критерием пользоваться, не стоит забывать об их чувствительности к деградации. О чем я? Например я сравнил себя с другим пользователем и оказалось, что мы оценили 5 общих фильмов. Причем он всем поставил 10 баллов, а я двум 9ки. Таким образом я потерял 2/50 не взвешенных баллов от 1. Но если мы вычислим реальные коэффициенты, то получим следующие результаты: Евклид=0.414, Пирса=0.981. Таким образом видно, что ф-ия Евклида очень чувствительна при малом кол-ве общих оценок.

Советую почитать

http://forexaw.com/TERMs/Economic_terms_and_concepts/Exchange_Terminology/l675_Корреляция_Correlation_это

Машинное обучение. Начало.

2014-08-10T05:40:00.001-07:00

Предисловие

Итак, начнем цикл статей про машинное обучение) В основном он будет основан на материале из различных книг, но основная идея цикла - это подача!) А подавать будем, попытавшись написать реальный проектик и попрактиковавшись в различных интересных штукенциях)

В поисках данных

Итак, нам нужны данные - много данных!) И желательно интересных. Не знаю, как вы, но я долго думать не стал и воспользовался сайтом kinopoisk.ru, надеюсь сильно бить не будут, ведь мы будем взращивать их будущие кадры(т.е. Вас!)))

Начнем с конфигурации. В разных книгах примеры данных хранятся во всяких rss, plain files и прочей не современной чепухе) Мы то с Вами живем в то время, когда даже слово sql стыдно произносить в приличном обществе, без приставки no!) Но мы произнесем - PostgreSQL! Начнем с установки(ищем, где ищется)) а закончим созданием таблички votes.

CREATE TABLE votes
(
  id serial NOT NULL, --уникальный идентификатор
  user_id integer NOT NULL, --id пользователя с сайта
  film_id integer NOT NULL, --id фильма с сайта
  vote smallint NOT NULL, --оценка фильму пользователем от 1 до 10
  CONSTRAINT vote_id PRIMARY KEY (id)
)

Объяснять столбцы не буду!!!))) Если все получилось, давайте добавим данных. Бить меня не нужно, можно только корректировать, я для Вас написал следующее чудо, запускаем и...не ждем, а приступаем к работе, он и сам справится, за несколько лет)) У меня на момент написания этих строк обработано 9000 пользователей из как минимум 4722023 (спалился:)

import re, psycopg2
from lxml.html import parse
from lxml.cssselect import CSSSelector

def get_user_voites():

 user_start_num = 200
 user_end_num = 4722023

 try:
  conn=psycopg2.connect("dbname='postgres' user='postgres' password='120789' host='localhost'")
  cur = conn.cursor()
  page_num_sel = CSSSelector('div.pagesFromTo')

  for user_num in xrange(user_start_num, user_end_num):

   vote_film_list = []
   loop_bool = True
   page_num = 1

   while loop_bool:
    try:
     page = parse('http://www.kinopoisk.ru/user/%s/votes/list/ord/date/page/%s/' % (user_num, page_num))

     vote_count_div = int(page_num_sel(page)[0].text.split()[-1])

     items = page.xpath("//div[contains(@class, 'item')]")
     for item in items:
      try:
       film_div = item.find("div[@class='info']").find("div[@class='nameRus']").find("a")

       vote_num = int(item.find("div[@class='num']").text)
       film_id = re.search('film\/(\d)+\/$', film_div.values()[0]).group(0)[5:-1]
       film_name = film_div.text
       vote = item.find("div[@class='vote']").text

       if vote and film_id:
        vote_film_list.append({'vote': vote, 'user_id': user_num, 'film_id': film_id})
      except:
       pass

     if vote_num <= vote_count_div:
      page_num += 1

     print vote_num, page_num, vote_count_div, len(vote_film_list)
     cur.executemany("""INSERT INTO votes(user_id, film_id, vote) VALUES (%(user_id)s, %(film_id)s, %(vote)s)""", vote_film_list)
     conn.commit()
     vote_film_list = []

    except Exception, e:
     print e
     loop_bool = False


 except Exception, e:
  print "I am unable to connect to the database.", e

 finally:
  if conn:
   conn.close()

Алгоритм Бойера - Мура

2013-04-25T03:53:00.000-07:00

Алгоритм поиска строки Бойера — Мура считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.

Мы с Вами уже рассмотрели 2 подхода поиска подстроки: в лоб и Кнута - Морриса - Пратта.
И хотя последний можно отнести к правильным, сегодня мы разберем подход, являющийся классикой в решении данной задачи.
Простота, является характеристикой правильного решения и тривиальность данного подхода это подтверждает.

Основная идея алгоритм - начать поиск не с начала, а с конца подстроки. Наткнувшись на несовпадение, мы просто смещаем подстроку до самого правого вхождения данного символа.

Пример можете посмотреть в картинке заголовка :)

Можно заметить, что, как и в случае Кнута-Морриса-Пратта, мы так же можем осуществить предкомпиляцию выражения.

Для этого удобно в словарь заносить пары ключ = числовое значение символа(ord), значение = порядковый номер в подстроке.

А вот и реализация:

def bmPredCompil(x):
    d = {}
    lenX = len(x)
    for i in xrange(len(x)):
        # сколько символов с правого края до этой буквы
        d[ord(x[i])] = lenX - i
    return d

Осталось осуществить сам поиск со сдвигом:

def boyerMurSearch(s, x):
    d = bmPredCompil(x)
    # k - проход по s
    # j - проход по x
    # i - место начала прохода по s
    lenX = i = j = k = len(x)
    while j > 0 and i<=len(s):
     # совпали, двигаемся дальше (от конца к началу)
        if s[k-1] == x[j-1]:
            k -= 1
            j -= 1
        # иначе, продвигаемся по строке на d и начинаем с правого конца подстроки снова
        else:
            i += d[ord(s[i])]
            j = lenX
            k = i
    if j <= 0:# нашли
        return k
    return None # не нашли

Вот собственно и все! :)
Реализация, как и сама идея, достаточно прозрачна.

Задача о путешествии шахматного коня

2013-04-25T02:48:00.002-07:00

Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.

Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (датируется 26 апреля 1757 года).

Когда то давно, мы уже рассматривали пример решения задачи рекурсивным образом, на примере задачи по размену денег. Пришло время вспомнить некоторые классические подходы и начать хотелось бы с задачи о путешествии шахматного коня.

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

Итак, каждый ход мы будем характеризовать 3-мя числами: его порядковым номером i и парой координат x, y. История ходов будет храниться в матрице списков, в соответствующей ячейке записываем порядковый номер хода. Соответственно, если в ячейке 0, значит туда мы еще не ходили.

Важно определиться с вычислением новой координаты. Можно заметить, что у коня есть 8 позиций-кандидатов (u, v) куда может прыгнуть конь.
Будем получать новые координаты прибавляя соответствующие смещения, хранящиеся в 2х списках dx, dy и отслеживать допустимость хода (находимся в пределах доски).

Характерной чертой данного алгоритма является то, что каждый шаг, выполняемый в попытке приблизиться к полному решению, запоминается таким образом, чтобы от него можно было позднее отказаться, если выяснится, что он не может привести к полному решению. Такое действие называется возвратом. А класс алгоритмов, как не трудно догадаться, алгоритмы с возвратом.

Очень советую читать именно алгоритм, тем более Питон в этом сильно помогает. Это даст куда больше толку. чем множество лишних слов!)

#Задача о коняшке
def knightsTour(x0, y0, done, size=5):
    #создаем шахматную доску в виде 2го списка
    h = [[0 for j in xrange(size)] for i in xrange(size)]
    #начальная координата(1го хода)
    h[x0][y0] = 1
    
    #Возможные ходы
    dx = [2, 1, -1, -2, -2, -1, 1, 2]
    dy = [1, 2, 2, 1, -1, -2, -2, -1]

    def CanBeDone(u, v, i):
        h[u][v] = i
        done = tryNextMove(u, v, i)
        if not done:
            h[u][v] = 0
        return done
    
    def tryNextMove(x,y, i):
        
        #eos - показывает все ли варианты возможных 8ми ходов мы рассмотрели
        #done - показывает удачна ли данная ветка решения
        #k - порядковый номер рассмотренной попытки из 8 допустимых
        env = {'done': False, 'eos': False, 'u': x, 'v': y, 'k': -1}

        def next():
            x = env['u']
            y = env['v']
            while env['k'] < 8:
                env['k'] +=1;
                if env['k'] < 8:
                    env['u'] = x + dx[env['k']]
                    env['v'] = y + dy[env['k']]
                if (env['u'] >= 0 and env['u']<size) and (env['v']>=0 and env['v']<size) and h[env['u']][env['v']]==0:
                    break
            env['eos'] = (env['k']==8)

        if i < size**2:#если доска не заполнена
            next()
            while not env['eos'] and not CanBeDone(env['u'], env['v'], i+1):
                next()
            done = not env['eos']
        else:
            done = True
        return done

    tryNextMove(x0, y0, 1)
    print h

Привожу пример заполнения шахматной доски.

Алгоритм Кнута-Морриса-Пратта (КМП)

2013-04-19T06:15:00.000-07:00

Алгоритм был разработан Кнутом (Knuth) и Праттом (Pratt) и независимо от них Моррисом (Morris) в 1977 г.

Он относится к "правильным" подходам решения поставленной задачи, в отличии от тривиального подхода, рассмотренного ранее.

Данный подход хоть и считается достаточно тривиальным, описания, которые нашел я, зачастую пестрят математическими основами и доказательствами, которые сбивают с сути. Так в книге, уважаемого Никлауса Вирта, приводится описание, которое я так и не одолел.
Однако я нашел пару статей, которые достаточно информативны, они приведены в ссылках и рекомендуемы для ознакомления.

Для понимания: Префикс строки A[..i] — это строка из i первых символов строки A. Суффикс строки A[j..] — это строка из |A|-j+1 последних символов. Подстроку из Aбудем обозначать как A[i..j], а A[i] — i-ый символ строки.

В статье http://habrahabr.ru/post/111449/ сказано:

Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.

Многие люди ошибаются в этом пункте, считая, что не надо возвращаться назад, а можно продолжать обработку строки A с текущей позиции. Почему это не так легко продемонстрировать на примере поиска X=«AAAB» в A=«AAAAB». Первая гипотеза нас приведет к четвертому символу A: "AAAAB", где мы обнаружим несоответствие. Если не откатиться назад, то вхождение мы так и не обнаружим, хотя оно есть.

Для реализации данного алгоритма, нам необходимо рассмотреть, так называемую, префикс функцию.

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

Вот пример для «ababcaba»:

суффикс	префикс	p
a	a	0
ab	ab	0
aba	aba	1
abab	abab	2
ababc	ababc	0
ababca	ababca	1
ababcab	ababcab	2
ababcaba	ababcaba	3

Итак, идея ясна? Ну тогда попробум написать префикс функцию в лоб:

def predkompil(x):
    #первый символ всегда 0, поэтому заносим и пропускаем
    d = {0:0}
    for i in xrange(1,len(x)):
     # проходоим от конца к началу
        j = i
        sdvig = 0
        while j>0:
            j -= 1
            if x[j] == x[i-sdvig]:
                sdvig += 1
            else:
                j += sdvig
                sdvig = 0
        d[i] = sdvig
    return d

Вроде работает, но как то много сравнений и проходов. Попробуем оптимизировать.
Начать можно с замены строки j = i, на j = d[i-1]+1.

Что нам это дает? А то, что незачем просматривать каждый раз с конца и до начала. Можно заметить, что если мы на предыдущем шаге (i-1) нашли вхождение > 0 (d[i-1]), то и начинать стоит с данной позиции (d[i-1]).

Пример:

При i=4 ABAAB -> 2, тогда на i+1, т.е. i=5 смотрим не с j=i(5), а с 3! Т.к. либо счетчик вырастет и станет 3 в случае ABAABA, либо сбросится в 0 при любой другой букве.
И хотя мы делаем меньше сравнений(пропускаем середину слова), однако весь совпадающий префикс мы проходим, что не есть хорошо.

Это уже не плохо, однако, мы с Вами так и не научились использовать информацию, полученную на предыдущих итерациях.

Зная длину совпадения префикса с суффиксом по предыдущей букве, мы можем начать поиск сразу с этой позиции (d[j-1]) и продвигаясь вперед либо увеличивать данное значение (суффикс равный префиксу продолжит свой рост), либо обнуляется (нет совпадения).

def predkompil2(x):
    d = {0:0}
    for i in xrange(1,len(x)):
        j = d[i-1]#эту строку мы заменили
        while j > 0 and x[j] <> x[i]:
            j = d[j-1]
        if x[j] == x[i]:
            j += 1
        d[i] = j
    return d

В статье на хабре, вы можете ознакомиться с так называемой z-функцией.
Идея её очень схожа с префикс функцией, поэтому её реализацию я опущу :)

Итак, префикс функция готова, осталось применить её и решить поставленную задачу.

def kmpSearch(s, x):
    d = predkompil2(x)
    i = j = 0
    while i<len(s) and j<len(x):
        if x[j] == s[i]:
            i+=1
            j+=1
        elif j==0:
            i+=1
        else:
            j = d[j-1]
    else:
        if j == len(x):
            return i-j
        return None

Вот такая идея описывается в книге Вирта, зная значения префикс ф-ии сдвигаться на заданное расстояние, однако кто-то мог заметить, что для решения задачи, нам достаточно было использовать только префикс функцию. Для этого достаточно сделать конкатенацию искомой подстроки, со строкой, через разделитель, заведомо уникальный(что-то вроде #) и применив префикс ф-ию. Если она даст значение равное длине искомой подстроки, значит мы нашли это место иначе - нет.

def kmpSearchByCompil(s, x):
    d = {0:0}
    template = x + '#' + s
    for i in xrange(1,len(template)):
        j = d[i-1]#незачем смотреть всю строку, можно посмотреть со сдвига прошлой подстроки
        while j > 0 and template[j] <> template[i]:
            j = d[j-1]
        if template[j] == template[i]:
            j += 1
        d[i] = j
        if j == len(x):
            return i
    return None

Надеюсь, идея понятна.
Мы рассмотрели с Вами один из "правильных" алгоритмов поиска подстроки, однако, классикой данной задачи стал алгоритм Бойера - Мура.
Автор статьи на Хабре утверждает, что он достаточно не тривиален и запутан, однако вынужден с ним не согласиться, что и покажу в следующей заметке.

Поиск первого вхождение подстроки. Решение в лоб.

2013-04-18T06:57:00.002-07:00

Поиск информации — одно из основных использований компьютера. Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах…

С поиском подстроки мы встречаемся постоянно. Всем любимый ctrl+f, это именно то, что нам нужно.
Часто ли вы задумывались, а как оно работает? Многие из Вас, наверняка, скажут, что если потребуется - сделаем.
Большинство, думаю, решат эту задачу в лоб и для наглядности я покажу, как это сделать.

Прямой поиск, или, как еще часто говорят, «просто взять и поискать» - это первое решение, которое приходит в голову неискушенному программисту. Суть проста: идти по проверяемой строке A и искать в ней вхождение первого символа искомой строки X. Когда находим, делаем гипотезу, что это и есть то самое искомое вхождение. Затем остается проверять по очереди все последующие символы шаблона на совпадение с соответствующими символами строки A. Если они все совпали — значит вот оно, прямо перед нами. Но вот если какой-то из символов не совпал, то ничего не остается, как признать нашу гипотезу неверной, что возвращает нас к символу, следующему за вхождением первого символа из X.

Многие люди ошибаются в этом пункте, считая, что не надо возвращаться назад, а можно продолжать обработку строки A с текущей позиции. Почему это не так, легко продемонстрировать на примере поиска X=«AAAB» в A=«AAAAB». Первая гипотеза нас приведет к четвертому символу A: "AAAAB", где мы обнаружим несоответствие. Если не откатиться назад, то вхождение мы так и не обнаружим, хотя оно есть.
Неправильные гипотезы неизбежны, а из-за таких откатываний назад, при плохом стечении обстоятельств, может оказаться, что мы каждый символ в A проверили около |X| раз. То есть вычислительная сложность сложность алгоритма O(|X||A|). Так поиск фразы в параграфе может и затянуться...

Справедливости ради следует отметить, что если строки невелики, то такой алгоритм может работать быстрее «правильных» алгоритмов за счет более предсказуемого с точки зрения процессора поведения.

А вот и реализация:

def stringSearch(s, x):
    i=j=0
    lengthS = len(s)# Длина строки в которой ищем
    lengthX = len(x)# -||- которую ищем
    # пока не достигли одного из концов
    while i<=lengthS - lengthX and j>lengthx:
     # если совпали буквы продвигаемся по обеим строкам
        if li[i+j]==x[j]:
            j+=1
        # иначе двигаемся по строке(+1), начиная с 0 символа подстроки
        else:
            i+=1
            j=0
    # если дошли до конца подстроки - нашли, иначе - нет
    return i if j==lengthX else None

Алгоритм прост и тривиален, а главное, как было замечено выше, зачастую неплохо работает, особенно, когда строка поиска не сильно велика.
Разобравшись с прямым подходм, давайте посмотрим, как решать эту задачу - правильно.
Алгоритм Кнута-Морриса-Пратта (КМП)
Алгоритм Бойера - Мура

Используемая литература:

Линейный поиск

2013-02-12T11:24:00.000-08:00

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

Данный алгоритм приведен здесь, для полноты изложения. Он мало где используется, только если в собственных проектах, которые не накладывают серьезных требований к производительности системы.

Рассматриваем, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. Т.е., в результате каждой проверки область поиска уменьшается на один элемент.

def linearSearch(li, x):
    i = 0
    length = len(li)
    while i<length and x<> li[i]:
        i+=1
    return i if i<length else None

Никлаус Вирт описал модернизацию метода, при которой мы избавляемся от одного сравнения на каждом витке цикла. А именно от проверки окончания строки. Для этого мы добавляем искомый элемент в самый конец, что гарантирует нам остановку по одному условию, а финальная проверка на позицию найденного элемента, покажет подставной он или нет)

def linearSearchVirt(li, x):
    i = 0
    length = len(li)-1
    while x x<> li[i]:
        i+=1
    return i if i<length else None

Вот и весь линейный поиск!)
Но есть более интересный метод - двоичный поиск, милости просим к изучению.

Совершенный код

2012-11-16T14:00:00.001-08:00

Есть такая хорошая книжка - "Совершенный код", автора С. Макконнелл. Кто не читал или не слышал вообще, очень советую. Книга не привязана к конкретному языку, примеры есть на С++, Java, C# и т.д. В ней описано много интересных приемов программирования и разработки проекта в целом.

Для того, чтобы Вас немного заинтересовать данной книгой - приведу интересные выкладки из нее:)

*-Нравится статья? Кликни по рекламе! :)

Проведение аналогий часто приводит к важным открытиям (волновая и корпускулярная теории света -> эфир(среда распространяющая свет как воздух звук))
Метафора - эвристический подход, а не алгоритм (разработка как: литературная, сельскохозяйственная, строительная метафоры и метафора жемчужины)
Не бойтесь комбинировать метафоры
Эвристика - метод помогающий искать ответ
Общая цель подготовки - снижение риска
Если менеджер проекта приказывает Вам немедленно начать программировать...Существует 4 основных подхода, но лучший - найти другую работу, ведь жизнь слишком коротка, чтобы тратить ее на работу в отсталом учреждении
Один из аспектов профессии разработчика - посвящение профанов в особенности процесса разработки ПО
Подготовка к проекту - это дешевле, чем похерить результат и начать все заново
Программисты - последнее звено пищевой цепи разработки ПО. Архитекторы поглощают требования, проектировщики архитектуру, а программисты - проект.
Если на каждом этапе яды, программист получит их все.
Общий принцип прост: исправлять ошибки нужно как можно раньше
И при итеративном и при последовательных подходах разработки общая сумма затрат будет схожей, однако в первом случае она не будет казаться столь крупной, т.к. будет уплачена по частям
Убедитесь, что всем известна цена изменения требований
Хорошая архитекура облегчает конструирование
Архитектура должна производить оценку ресурсов в номинальном и пиковом состоянии,а так же уровень отказоустойчивости системы
В мире ПО цепь не так крепка как, как слабейшее звено; Она так слаба, как все слабые звенья вместе взятые
Изучая архитектуру, Вы должны испытывать удовольствие от того, насколько естественной и простой она получается
Если над данным типом ПО Вы еще не работали - выделите больше времени
Язык программирование - отражение вашего мышления
Различайте программирование "на языке" и "с использованием языка"
Проблему нужно решать дважды: первый , чтобы получить ее ясное определение, второй, для создания работоспособного решения
Задача проектирования - объединение конкурирующих целей в удачном компромиссе
Основные характеристики проекта: минимальнаясложность, простота сопровождения, слабое сопряжение(адекватная абстракция), расширяемость,повторное использование, высокий коэфф. объединения по входу (наличие ядра), низкий коэфф. разветвления на выходе (не большое делегирование), портируемость, отсутствие избыточной функциональности, стратификация (грамотная декомпозиция системы на уровни)
Если все подсистемы могут взаимодействовать (т.е. отсутствие ограничений, что увеличивает по 2-му з-ну термодинамики энтропию системы), выгода от их разделения пропадает. Проще ограничить взаимодействие, а после сделать его свободнее.
Диаграмма систем должна быть ациклическим графом

Выше я привел интересные выводы, советы и это основное, что я выдержал из первых глав) Так что поверьте, там много полезного и переписывать книгу я не буду, однако приведу интересные высказывания различных людей, которыми кишит книга!)

Планируйте выбросить первый экземпляр программы: вам в любом случае придется это сделать. Фред Брукс

Если вы планируете выбросить первый экземпляр программы, вы выбросите и второй. Крейг Зеруни

Требования подобны воде. Опираться на них легче, когда они замарожены. Аноним

Если вы не можете объяснить что-то 6-ти летнему ребенку, значит, вы сами этого не понимаете. Альберт Эйнштейн

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

Есть два способа разработки проекта приложения: сделать его настолько простым, чтобы было очевидно, что в нем нет недостатков, или сделать его таким сложным, чтобы в нем не было очевидных недостатков. Ч.Э.Р. Хоар

Работая над проблемой, я никогда не думаю о красоте. Я думаю только о решении проблемы. Но если полученное решение некрасиво, я знаю, что оно не верно. Р. Бакминстер Фуллер

Прежде всего следует узнать, не что система выполняет, а над чем она это выполняет! Бертран Мейер

Интерфейсы классов должны быть полными и минимальными. Скотт Майерс

Больше беспокоит то, что программист может выполнить одну задачу несколькими способами: иногда не осознанно, но чаще ради изменения или же создания элегантной вариации. А.Р.Браун и У.А.Сэмпсон (такие уж мы педанты))))

Мы пытаемся решить проблему, максимально ускоряя процесс проектирования, чтобы в конце работы над системой у нас осталось достаточно времени для нахождения ошибок, допущенных из-за слишком быстрого проектирования. Гленфорд Майерс

Я никогда не встречал человека, желающего читать 17000 страниц документации, а если бы встретил, то убил бы его, чтобы он не портил генофонд. Джозеф Костелло

Плохие новости заключаются в том, что мы, как нам кажется, никогда не найдем философского камня. Мы никогда не найдем процесса, позволяющего проектировать ПО абсолютно рациональным образом. Но ест и хорошие новости: мы можем его подделать! Дэвид Парнас

Если для понимания того, что происходит, нужно увидеть реализацию, это не абстракция. Ф. Дж. Плоджер

Друзья, придерживайтесь золотых правил, проверенных годами! А для начала, ознакомьтесь с ними в данной книге!)

Сортировка слиянием

2012-01-15T12:28:00.000-08:00

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи. Алгоритм был изобретён Джоном фон Нейманом в 1945 году.

Странно, но мне показалось, что данный алгоритм не так сильно освещён в интернете в целом и на python в частности. А ведь именно этот алгоритм чаще всего применяется для сортировки данных не помещающихся в оперативке, т.е. хранящихся в файлах(внешние сортировки). Как и в случае с быстрой сортировкой Хоара, существует 2 реализации данного алгоритма. Рекурсивная и нет) Скажу по секрету, не рекурсивную реализацию мне предоставил так же мой преподаватель Деон. Более того, она ещё и не требует дополнительной памяти, что в классическом варианте относят к её основным минусам!

Для решения задачи сортировки эти три этапа выглядят так:

Сортируемый массив разбивается на две части примерно одинакового размера;
Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
Два упорядоченных массива половинного размера соединяются в один.

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

Нетривиальным этапом является соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем две стопки карт, лежащих рубашками вниз так, что в любой момент мы видим верхнюю карту в каждой из этих стопок. Пусть также, карты в каждой из этих стопок идут сверху вниз в неубывающем порядке. Как сделать из этих стопок одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из оставшихся стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке.

Пример работы алгоритма на массиве 3 7 8 2 4 6 1 5..

Рекурсивный алгоритм обходит получившееся дерево слияния в прямом порядке. Каждый уровень представляет собой проход сортировки слияния - операцию, полностью переписывающую массив.

Обратим внимание, что деление происходит до массива из единственного элемента. Такой массив можно считать упорядоченным, а значит, задача сводится к написанию функции слияния merge.

Один из способов состоит в слиянии двух упорядоченных последовательностей при помощи вспомогательного буфера, равного по размеру общему количеству имеющихся в них элементов. Элементы последовательностей будут перемещаться в этот буфер по одному за шаг.

Пример работы на последовательностях 2 3 6 7 и 1 4 5

Результатом является упорядоченная последовательность, находящаяся в буфере. Каждая операция слияния требует n пересылок и n сравнений, где n - общее число элементов, так что время слияния: Theta(n).

Ну что же, хватит слов, давайте реализовывать!)

def mergeSort(a, lb=0, ub=-1):
    def merge(a, lb, split, ub):
        #Слияние упорядоченных частей массива в буфер temp
        #с дальнейшим переносом содержимого temp в a[lb]...a[ub]

        #текущая позиция чтения из первой последовательности a[lb]...a[split]
        pos1=lb
        
        #текущая позиция чтения из второй последовательности a[split+1]...a[ub]
        pos2=split+1
        
        #текущая позиция записи в temp
        pos3=0
        
        temp = [i for i in xrange(ub-lb+1)]
        
        #идет слияние, пока есть хоть один элемент в каждой последовательности
        while pos1 <= split and pos2 <= ub:
            if a[pos1] < a[pos2]:
                temp[pos3] = a[pos1]
                pos1+=1
                pos3+=1
            else:
                temp[pos3] = a[pos2]
                pos2+=1
                pos3+=1
        
        #одна последовательность закончилась - 
        #копировать остаток другой в конец буфера 
        while pos2 <= ub:   #пока вторая последовательность непуста 
            temp[pos3] = a[pos2]
            pos3+=1
            pos2+=1
        while pos1 <= split:  #пока первая последовательность непуста
            temp[pos3] = a[pos1]
            pos3+=1
            pos1+=1

        #скопировать буфер temp в a[lb]...a[ub]
        a[lb:ub+1] = temp
        
        del(temp)
        
    if lb < ub:#если есть более 1 элемента
        split = (lb + ub)/2# индекс, по которому делим массив
        mergeSort(a, lb, split)#сортировать левую половину 
        mergeSort(a, split+1, ub)##сортировать правую половину 
        merge(a, lb, split, ub)#слить результаты в общий массив

Оценим быстродействие алгоритма: время работы определяется рекурсивной формулой T(n) = 2T(n/2) + Theta(n).

Ее решение: T(n) = n log n - результат весьма неплох, учитывая отсутствие "худшего случая". Однако, несмотря на хорошее общее быстродействие, у сортировки слиянием есть и серьезный минус: она требует Theta(n) памяти.

Это был классический вариант с сайта алголист. Теперь я приведу пример 2-го алгоритма без дополнительного буфера и рекурсии. Но к сожалению всё вкусно не бывает, поэтому за всё нужно платить. Об этом смотри в результатах. А пока идея:
Она достаточно проста, но не так тривиальна, как в предыдущем алгоритме. Избавившись от рекурсии, мы обязаны следить за следованием промежуточных разбиений самостоятельно. Алгоритм начинает с того, что сравнивает каждые 2 соседних, объединяя их в 1 упорядоченный подмассив. Потом снова 2 соседних(но в каждом из них уже по 2 эл-та), потом так же, но по 4, 8, 16 и т.д. И чтобы не использовать буфер, мы итерационно переставляем элемента прям в памяти, , чтобы упорядочить их(это требует огромного числа перестановок((()

def MergerSort(a):       
    def MergerGroup(a, left, m, right):
        if left >= right: return None
        if m < left or right < m: return None
        t = left
        for j in xrange(m+1, right+1):#подгруппа 2
            for i in xrange(t, j):#цикл подгруппы 1
                if a[j] < a[i]:
                    r = a[j]
                    #итерационно переставляем элементы, чтобы упорядочить
                    for k in xrange(j, i, -1):
                        a[k] = a[k - 1]
                    a[i] = r
                    t = i#проджолжение вставки в группе 1
                    break#к следующему узлу из подгруппы 2
                
    if len(a) < 2: return None
    k=1
    while k<len(a):
       g=0
       while g<len(a):#группы
            z = g + k + k - 1#последний эл-т группы
            r = z if z < len(a) else len(a) - 1#последняя группа
            MergerGroup(a, g, g + k - 1, r)#слияние
            g+=2*k
        k*=2

Еще 1 пример не рекурсивного алгоритма приведён на сайте википедии. Но там всё же вводится дополнительный буфер, равный размеру! массива.

Производительность

Тестирование проводилось на списке из 5000 не повторяющихся элементов(как и в быстрой сортировке Хоара, чтобы можно было сравнить).

первый алгоритм рекурсивный и с дополнительной памятью mergeSort 15002 function calls (5004 primitive calls) in 0.132 seconds
второй алгоритм не рекурсивный и без доп. буфера MergerSort 15057 function calls in 0.736 seconds

Результаты говорят сами за себя. Увы, но люди должны выбирать между доп. памятью и числом доп. итераций(т.е. перестановок - производительностью).

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

Сортировка слиянием является одним из наиболее эффективных методов для односвязных списков и файлов, когда есть лишь последовательный доступ к элементам.

Используемая литература:

Технические задачки

2011-12-14T06:04:00.000-08:00

1. Что будет выведено в результате исполнения программы? Почему?

class A:
     def __init__(self, name):
          self.name = name
     def __del__(self):
          print self.name,
 
aa = [A(str(i)) for i in range(3)]
for a in aa:
    del a

Вывод узнать легко в любой IDE. Это 2 1 0. Вопрос почему? Исходя из порядка(он если что, обратен созданию), можно догадаться, что тут задействован стек, т.е. работает правило LIFO.
При удалении списка - элементы удаляются в обратном порядке созданию.
Но важно понять, что удаление происходит в нашем случае, всего лишь когда скрипт отработал, а инструкция del тут ни при чём!
Вызов инструкции del рвёт связь имени переменной(в нашем случае a) и данных, находящихся в памяти, т.е. в цикле мы создаём ссылку на элемент списка, дём ей название->a, выводим name элемента и рвём связь. Чтобы отработал магический метод __del__ нужно вызывать del напрямую к элементу, т.е. через индекс, например del a[0]

2. Что будет выведено в результате исполнения программы? Почему?

class A:
    def __init__( self ):
        self.__value = 1
    def getvalue( self ):
        return self.__value
 
class B( A ):
    def __init__( self ):
        A.__init__( self )
        self.__value = 2
 
b = B()
print b.getvalue() == b.__value

Ответ: случится Exception, потому что невозможно получить доступ к __value извне класса. Однако самое интересное, здесь другое. В данном случае b.getvalue() возвращает 1, т.к. self.__value различно в каждом контексте. А именно b._A__value и b._B__value!

3. Есть 2 таблицы users и messages

users
UID Name
1 «Вася»
2  «Петя»


messages
UID msg
1 “A”
1 “B”
2 “C”

Напишите SQL-запрос, результатом которого будет таблица из двух полей: «Имя пользователя» и «Общее количество сообщений».

Здесь, могу посоветовать - SELECT INTO
UPD добавил пример)

CREATE TABLE cvc.users(
 uid INT,
 name varchar(100)
);

CREATE TABLE cvc.messages(
 uid INT,
 msg varchar(100)
);

INSERT INTO cvc.users (uid, name) VALUES (1, 'Vasja'), (2, 'Petja');
INSERT INTO cvc.messages (uid, msg) VALUES (1, 'A'), (1, 'B'), (2, 'C');

select name, count(*) as cnt from cvc.users join cvc.messages on users.uid = messages.uid group by users.uid;
select name, count(*) as cnt from cvc.users, cvc.messages where users.uid = messages.uid group by users.uid;

DROP TABLE cvc.users;
DROP TABLE cvc.messages;

Быстрая сортировка(quicksort, сортировка Хоара)

2011-11-02T01:00:00.000-07:00

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков. Например, в худшем случае (на некоторых входных массивах) использует время Ω(n2), что, например, хуже, чем сложность в наихудшем случае алгоритма сортировки слиянием.

Функция QuickSort сводит сортировку данного ей массива к разделению (partitioning) этого массива на две группы элементов и сортировке этих двух групп по отдельности.

Пример рекурсивного алгоритма с детерменированным(определённым) выбором оси:

Пусть нам нужно отсортировать участок массива A с p-го по q-й элемент включительно, будем называть этот участок подмассивом и обозначать как A[p..q].

ШАГ 1: Возьмем элемент A[p] за ось и "раскидаем" остальные элементы A[(p+1)..q] по разные стороны от него стороны — меньшие влево, большие --- вправо, то есть переставим элементы подмассива A[p..q] так, чтобы вначале шли элементы меньше либо равные A[p] потом элементы, больше либо равные A[p]. Назовет этот шаг разделением (partition).

ШАГ 2: Пусть r есть новый индекс элемента A[p]. Тогда, если q - p > 2, вызовем функцию сортировки для подмассивов A[p..(r-1)] и A[(r+1)..q].

Ключевая идея алгоритма заключается в процедуре «partition», которая за линейное время от размера массива, осуществляет такую перестановку элементов, относительно некоторой «оси» — заданного значения, равного одному из значений сортируемого интервала массива, что переставленный массив состоит из трех интервалов, идущих по порядку:

Элементы меньшие «оси»

Элементы равные «оси»

Элементы большие «оси»

Первый и последний из упомянутых интервалов могут быть неупорядоченными, поэтому далее, они рекурсивно сортируются.

Эффективность алгоритма существенно зависит от выбора «оси». Например, если назначать «осью» значение, которое больше или меньше всех элементов, то алгоритм вовсе не будет работать — разбиение никак не будет уменьшать сортируемый интервал и алгоритм зациклится.

Существует много различных вариантов данного алгоритма, отличающихся друг от друга сильно и не очень, в основном функцией партиционирования. Я же предлагаю Вам не сложный и при этом, достаточно оптимальный алгоритм. Прочитал я его в книге «Песни о Паскале» http://oleg-derevenets.narod.ru/ Он уже модифицирован и улучшен тем, что оcь выбирается усредненная по 3-м точкам выборки (приближенная к медиане). Данная модификация алгоритма предусматривает наличие двух указателей в списке. Первый идет снизу, второй - сверху. В основном цикле алгоритма нижний указатель увеличивается до тех пор, пока не будет обнаружен элемент, больший осевого, а верхний уменьшается пока не будет обнаружен элемент, соответственно, меньший. Затем найденные элементы меняются
местами. Этот процесс повторяется пока два указателя не перекроются. Эти внутренние циклы работают очень быстро, поскольку исключаются накладные расходы на проверку конца списка.

def QuickPas(s, aL, aR):
    l, r=aL, aR
    mid = (s[l]+s[(l+r)/2]+s[r])/3
    while lmid:r-=1
        if l<=r:
            if s[l]>s[r]:
                s[l], s[r] = s[r], s[l]
            l+=1
            r-=1
    if r>aL: QuickPas(s, aL, r)
    if l<aR: QuickPas(s, l, aR)

Математический подход

Не строгая оценка

Рассмотрим наихудший случай. Допустим, что нам не везет и в качестве опорного элемента выбирается либо мин. либо макс. элемент. Тогда на след рекурсивном вызове у нас останется ровно n-1 элементов. Следовательно высота нашего дерева будет n-1 и время O(n).

В наилучшем же случае, мы будем делить массив ровно пополам и получим идеально сбалансированное бинарное дерево, т.е. O(log(n)).

Итак, на весах лучший и наихудший случаи, каков же средний?

Вероятность выбора наудачу точно средний элемент довольно низка, а именно равна 1/n. Но допустим, что разделитель является достаточно хорошим, если он находится в центральной части массива, т.е. в диапазоне от n/4 до 3n/4. Таких элементов уже больше и вероятность выбора одного из них равна 1/2.

Оценим наихудший случай теперь. При выборе плохого элемента из достаточно хороших, большая часть массива содержит 3n/4 элементов. Самая длинная ветвь такого дерева проходит через части размером n, 3n/4, (3/4)²n...и т.д. до 1 элемента. Длина этой ветви = высоте дерева

Но только половина выбираемых произвольно разделителей являются достаточно хорошими, а другие плохими. Т.к. вероятность выбора того или иного равна 1/2, то и высота дерева может увеличиться самоее большее в 2 раза

Более подробный анализ показывает, что после n вставок средняя высота дерева составляет приблизительно 2ln(n), что приблизительно равно 1.3861log(n), т.е. всего на 39% больше чем идеально сбалансированное бинарное дерево.

Строгая оценка

Наихудший и наилучший случаи не требуют строгого доказательства и полностью совпадают с рассмотрением выше. Здесь же рассмотрим средний случай.

Для анализа среднего случая рассмотрим каждую из этих возможностей и усредним результаты. При анализе наихудшего случая мы заметили, что процедура разбиения делает N — 1 сравнений, разбивая список из N элементов. Слияние этих списков не требует никаких действий. Наконец, заметим, что когда она возвращает значение оси(P), происходит рекурсивный вызов процедуры Quicksort на списках длины Р — I и N — Р. Проводимый нами анализ среднего случая должен учитывать все N возможных значений .

Если повнимательней посмотреть на сумму, то видно, что аргумент первого слагаемого пробегает значения от 0 до N — 1, а аргумент второго слагаемого — те же значения, но в порядке убывания.

Это означает, что каждое из слагаемых А(г) участвует в сумме дважды, и формулу можно упростить:

теперь давайте посмотрим сразу на 2 формулы для A(N) и для A(N — 1).

Эти два выражения отличаются лишь несколькими членами.

Чтобы избавиться от дробей, подсчитаем A(N)-N и A(N—1)-(N—1).

Путем не сложных преобразований получим окончательное рекуррентное соотношение

Его детальный анализ дает A(N) = 1.4(N +1)log₂N. Таким образом, средняя

сложность алгоритма быстрой сортировки равна O(Nlog₂N).

Улучшаем алгоритм

Вся сложность алгоритма Хоара заключается в процедуре разделения массива на 2 половины, что зависит от правильного выбора оси разбиения и чем она ближе к медиане, тем лучше. Следовательно, если мы найдём метод приблизиться к ней(медиане) тем все станет красочнее и пушистее.

Методы основные следующие:

алгоритм выбора значения наиболее приближенного к медиане
вероятностный выбор оси

Описанный выше алгоритм относится, как раз к 1 пункту. Там мы находим элемент по 3-м точкам и в среднем он оказывается ближе к медиане, чем постоянный выбор оси.

2 пункт реализовать так же не сложно, что описывается в "инженерном подходе". Можно отметить, что данная модификация является не столь эффективной как 1-я, однако спасает нас от деградации алгоритма при граничных случаях (т.е. сводит почти к 0 вероятность выполнения алгоритма за квадратичное время).

Инженерный подход

Рассмотрим простенький вариантик с использованием встроенной в Питон возможностью условной генерации списков вместо использования функции partition.

def qsort1(list):
    if list == []: 
        return []
    else:
        pivot = list[0]
        lesser = qsort1([x for x in list[1:] if x < pivot])
        greater = qsort1([x for x in list[1:] if x >= pivot])
        return lesser + [pivot] + greater

И его однострочная версия

def qsortr2(list):
    return [] if list==[]  else qsortr2([x for x in list[1:] if x < list[0]]) + [list[0]] + qsortr2([x for x in list[1:] if x >= list[0]])

На данных примерах показывается лаконичность и изящность языка, надеюсь вы оценили :)

На сладкое, привожу вам вариант, которому меня научил в университете великий Деон!) Версия избавлена от рекурсии, классическим способом - введением стека, в котором хранятся границы наших интервалов.

def QuickSort(a):
    w = [x for x in xrange(4 + len(a) / 2)]#создаём стек
    k = 0#дно
    w[0] = 0#указатель на позицию левой границы половины
    w[1] = len(a) - 1#-||- правой
    while (k >= 0):
        i = QuickSortPos(a, w[k], w[k + 1])
        if(i != w[k + 1]):RL =i + 1#левая граница правого подъинтервала
        else:RL =w[k + 1]
        RR = w[k + 1]#Правая граница правого подъинтервала
        LL = w[k]#Левая граница левого подъинтервал
        if(i != w[k]):LR =i - 1#Правая граница левого подъинтервал
        else:LR =w[k]
        k -= 2#удалить текущий интервал
        if (RL != RR):k += 2; w[k] = RL; w[k + 1] = RR
        if (LL != LR):k += 2; w[k] = LL; w[k + 1] = LR
    return

def QuickSortPos(a, left, right):
    i = left
    j = right - 1
    while (True):#чтобы поставить разделяющий элемент на свое место
        while (a[i] < a[right]): i+=1
        while (a[j] > a[right] and j > left): j-=1
        if (i >= j): break
        a[i],a[j] = a[j],a[i]
    a[right],a[i]  = a[i],a[right]
    return i

Сразу скажу, что он показывает максимальную производительность из все виденных мной.

Стоит сказать пару слов про использование методов оптимизации и их применимости на практике.

Быстрая сортировка с вероятностным выбором оси

К сожалению, предположение о равномерности распределения «осей» относительно интервалов, может не встречаться на практике. Например, есть вариации детерминированного алгоритма, для которых «плохими» будут уже отсортированные (или почти отсортированные) последовательности, а таковые часто встречаются в реальных задачах. В таких случаях, когда нельзя «сделать случайными» входные данные, можно внести «элемент случайности» непосредственно в сам алгоритм. В частности, чтобы сохранилась оптимальная оценка математического ожидания, достаточно сделать вероятностным выбор осевого элемента из разделяемого интервала.

Вероятностный алгоритм отличается от детерминированного, только строчкой, где задается выбор вероятностный выбор осевого элемента, для первого алгоритма она будет выглядеть следующим образом

(indexLow,indexHigh)=partition(left,right,A[RandomSource.randrange(left, right)])
где RandomSource создаётся перед quicksort_interval(0, len(A)) так
RandomSource = random.Random(6666) # Инициализируем генератор случайных чисел.

К сожалению, реализация Random сама по себе привносит большие задержки. Я так и не нашел входных данных, при которых он выиграл у первого варианта.

В большинстве зарубежных книжных изданиях, представлен данный алгоритм:

def partition(A, left, right):           
#       indexLow  = left+1             # Нижний и текущий индексы                        
#       indexHigh = right-1    
    pivotPoint=left         # Верхний индекс
    pivotVal = A[left]
    i=left+1
    while i <= right:# Пока есть область не просмотренных элементов.
        if A[i] < pivotVal:
            pivotPoint+=1# Если элемент меньше оси
            if i>pivotPoint:#мое улучшение :) убирает перестановки эл-та с самим собой
                A[i], A[pivotPoint]=A[pivotPoint],A[i]# гоним его в начало интервала
#               indexLow = indexLow + 1 # сужаем область слева
        i +=1
#       print A, left, pivotPoint
    A[left],  A[pivotPoint] = A[pivotPoint], A[left]
    return pivotPoint

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

В основном, методы призванные приблизить выполнение алгоритма к оптимальному, за счет поиска более точного положения оси, лишь усложняет логику, что приводит к увеличению числа сравнений, обменов или того и другого одновременно. Если Вы заинтересуетесь данной проблемой, прошу заметить, что операции сравнения дешевле обменов, а следовательно стоит уменьшать кол-во вторых, чаще за счет увеличения первых.

Экспериментально доказано, что в среднем алгоритм быстрой сортировки работает в 2-3 раза быстрее сортировок слиянием и пирамидальной.

Производительность

Тестирование проводилось на списке из 50000 не повторяющихся элементов.

первый алгоритм 54074 function calls in 0.572 seconds
второй алгоритм избавленный от рекурсии 33395 function calls in 0.432 seconds
третий - однострочная Python версия 100004 function calls (4 primitive calls) in 0.708 seconds
Встроенная реализация сортировки list.sort() 4 function calls in 0.004 CPU seconds

Результат показывает, насколько выгодно избавляться от рекурсии, но реализация на чистом С, всё равно рулит и бибикает)

Используемая литература:

Википедия
Традиция
Алгоритмы. Руководство по разработке. Автор: Стивен Скиена
Основы современных алгоритмов. Автор: Макконнелл Дж.

Пузырьковая сортировка

2011-10-03T12:41:00.000-07:00

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).
*-Нравится статья? Кликни по рекламе! :)

Расположим массив сверху вниз, от нулевого элемента - к последнему.

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию.

Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.

Среднее число сравнений и обменов имеют квадратичный порядок роста: O(n²), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать.

Чем мы сейчас и займемся:

Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Что это значит ?Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла(особенно, если массив был отсортирован с самого начала !).Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.
Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.
Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов.

Получившийся алгоритм иногда называют "шейкер-сортировкой".
Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

def shakerSort(a): 
    #lb, ub границы неотсортированной части массива
    k= ub = len(a)-1
    lb=1
    while ( lb < ub ):
        # проход сверху вниз 
        for j in xrange (ub, lb-1, -1):
            if a[j-1] > a[j]: 
                a[j-1], a[j] = a[j], a[j-1]
                k=j
            lb = k
        # проход снизу вверх 
        for j in xrange (lb, ub+1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
                k=j
            ub = k
    return a

Насколько описанные изменения повлияли на эффективность метода ? Среднее количество сравнений, хоть и уменьшилось, но остается O(n²), в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее) количество операций остается квадратичным.

Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.

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

Так же мы создавали сортировку пузырьком, когда рассматривали связный список, но он сортирует 5000 значений 183 сек, в то время, как shaker_sort 3.6 сек.
Интересная статья, не совсем про сортировку и Python, но в тему)

Вычисление времени выполнения

Все операторы присваивания, как и проверки if имеют некоторое постоянное время выполнения О(1). Все операторы в каждом из циклов, в среднем, выполняются n-i раз. А по правилу сложения времен 2n-2i(т.к. 2 цикла). Цикл while в среднем выполняется (n-1)/2 раз. И если мы напишем формулу суммы сократив заранее 2-ки, получим среднее выражение

Тем самым мы показали, что данный алгоритм имеет порядок роста O(n²)

Используемая литература:

Раскраска графа

2011-09-14T08:35:00.000-07:00

Рассмотрим математическую модель, используемую для управления
светофорами на сложном перекрестке дорог. Мы должны создать программу, которая в
качестве входных данных использует множество всех допустимых поворотов на перекрестке (продолжение прямой дороги, проходящей через перекресток, также будем
считать "поворотом") и разбивает это множество на несколько групп так, чтобы все повороты в группе могли выполняться одновременно, не создавая проблем друг для друга. Затем мы сопоставим с каждой группой поворотов соответствующий режим работы
светофоров на перекрестке.

*-Нравится статья? Кликни по рекламе! :)

Рис. 1.1. Сложный перекресток

Желательно минимизировать число разбиений исходного множества поворотов, поскольку при этом минимизируется количество режимов работы светофоров на перекрестке.
Для примера на рис. 1.1 показан перекресток возле Принстонского университета, известный сложностью его преодоления. Обратите внимание, что дороги С и E односторонние, остальные — двухсторонние. Всего на этом перекрестке возможно 13 поворотов. Некоторые-из этих поворотов, такие как АВ (поворот с дороги А на дорогу В) и ЕС, могут выполняться одновременно. Трассы других поворотов, например АО и ЕВ, пересекаются, поэтому их нельзя выполнять одновременно. Режимы работы светофоров должны учитывать эти обстоятельства.

Рис. 1.2. Граф, показывающий несо-
вместимые повороты

Для построения модели этой задачи можно применить математическую структуру, известную как граф. Для решения задачи можно нарисовать граф, где вершины будут представлять повороты, а ребра соединят ту часть вершин-поворотов, которые нельзя выполнить одновременно. Для нашего перекрестка соответствующий граф показан на рис. 1.2, а в табл. 1.1 дано другое представление графа — в виде таблицы(матрицы смежности), где на пересечении строки i и столбца j стоит 1 тогда и только тогда, когда существует ребро между вершинами i и j.

Таблица 1.1. Таблица несовместимых поворотов

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

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

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

Если граф небольшой, можно попытаться найти оптимальное решение, перебрав все возможные варианты раскраски. Однако этот подход не приемлем для больших графов, так как программно трудно организовать эффективный перебор всех вариантов.
Второй подход предполагает использование дополнительной информации об исходной задаче. Желательно найти какие-то особые свойства графа, которые исключали бы необходимость полного перебора всех вариантов раскраски для нахождения оптимального решения.
В третьем подходе мы немного изменяем постановку задачи и ищем не оптимальное решение, а близкое к оптимальному. Если мы откажемся от требования минимального количества цветов раскраски графа, то можно построить алгоритмы раскраски, которые работают значительно быстрее, чем алгоритмы полного перебора.

Алгоритмы, которые быстро находят "подходящее", но не оптимальное решение, называются эвристическими.

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

Выбираем произвольную не закрашенную вершину и назначаем ей новый цвет.
Просматриваем список не закрашенных вершин и для каждой из них определяем, соединена ли она ребром с вершиной, уже закрашенной в новый цвет. Если
не соединена, то к этой вершине также применяется новый цвет.

Рис. 1.3. Граф

Этот алгоритм назван "жадным" из-за того, что каждый цвет применяется к максимально большому числу вершин, без возможности пропуска некоторых из них или перекраски ранее закрашенных. Возможны ситуации, когда, будь алгоритм менее "жадным" и пропустил бы некоторые вершины при закраске новым цветом, мы получили бы раскраску графа меньшим количеством цветов. Например, для раскраски графа на рис. 1.3 можно было бы применить два цвета, закрасив вершину 1 в красный цвет, а затем, пропустив вершину 2, закрасить в красный цвет вершины 3 и 4. Но "жадный" алгоритм, основываясь на порядковой очередности вершин(применив, например структуру Вирта, можно попытаться исправить это), закрасит в красный цвет вершины 1 и 2, для закраски остальных вершин потребуются еще два цвета.

Применим описанный алгоритм для закраски вершин графа нашей задачи (рис.1.2), при этом первой закрасим вершину АВ в синий цвет. Также можно закрасить в синий цвет вершины AC, AD и ВА, поскольку никакие из этих четырех вершин не имеют общих ребер. Вершину ВС нельзя закрасить в этот цвет, так как существует ребро между вершинами АВ и ВС. По этой же причине мы не можем закрасить в синий цвет вершины BD, DA и DB — все они имеют хотя бы по одному ребру, связывающему их с уже закрашенными в синий цвет вершинами. И так, продолжая перебор, закрашиваем все возможные вершины. Теперь применим второй цвет, например красный и повторим всё заново.

Таблица 1.2. Раскраска графа, представленного на рис. 1.2

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

Можно использовать результаты из общей теории графов для оценки качества полученного решения. В теории графов k-кликой называется множество из k вершин, в котором каждая пара вершин соединена ребром. Очевидно, что для закраски k-клики необходимо k цветов, поскольку в клике никакие две вершины не могут иметь одинаковый цвет.

B графе рис. 1.2 множество из четырех вершин AC, DA, BD и ЕВ является 4-кликой.
Поэтому, не существует раскраски этого графа тремя и менее цветами, и,
следовательно, (решение, представленное в табл. 1.2 является оптимальным в том
смысле, что использует минимально возможное количество цветов. В терминах исходной задачи это означает, что для управления перекрестком, показанным на рис; 1.1, необходимо не менее четырех режимов работы светофора.

Теперь привожу реализацию алгоритма, результат которого полностью совпадает с таблицей 1.2!

     # ab ac ad ba bc bd da db dc ea eb ec ed
N =  [[0,0,0,0,1,1,1,0,0,1,0,0,0],# ab
     [0,0,0,0,0,1,1,1,0,1,1,0,0], # ac
     [0,0,0,0,0,0,0,0,0,1,1,1,0], # ad
     [0,0,0,0,0,0,0,0,0,0,0,0,0], # ba
     [1,0,0,0,0,0,0,1,0,0,1,0,0], # bc
     [1,1,0,0,0,0,1,0,0,0,1,1,0], # bd
     [1,1,0,0,0,1,0,0,0,0,1,1,0], # da
     [0,1,0,0,1,0,0,0,0,0,0,1,0], # db
     [0,0,0,0,0,0,0,0,0,0,0,0,0], # dc
     [1,1,1,0,0,0,0,0,0,0,0,0,0], # ea
     [0,1,1,0,1,1,1,0,0,0,0,0,0], # eb
     [0,0,1,0,0,1,1,1,0,0,0,0,0], # ec
     [0,0,0,0,0,0,0,0,0,0,0,0,0]] # ed

#раскраска графа
def graphColoring():
    colored=[[]]
    color=0#№ цвета
    stack=[]#покрашенные узлы
    num2=num1=-1
#функция проверки возможности покраски в используемый сейчас цвет
    def loop(num):
        for t in colored[color]:
            if N[t][num]==1:
                return False
        return True
    
    for a in N:
        num1+=1
        if num1 not in stack:#просматриваем только те, которые еще не покрашены
            if not loop(num1):#значит применяем новый цвет
                colored.append([])
                color+=1
                stack.append(num1)
                colored[color].append(num1)
            num2=num1
            for b in a[num1:]:
                if b==0 and num2 not in stack and loop(num2):
                    stack.append(num2)
                    colored[color].append(num2)  
                num2+=1
    return colored

Подставьте теперь новый граф, на примере которого объяснялась жадность алгоритма и вы увидите доказательство тому.

Думая, по дороге на работу, над тем, как избавиться от жадности алгоритма, я пришёл к следующей идее. А что если нам проходиться начиная с узла максимальной мощности(больше всего связей), окрашивать его и переходить к соседу, так же с макс. мощностью, окрашивая в другой цвет и проверяя в стеке цвета(если их уже окрасили) других своих соседей. Реализацию данной идее вы можите лицезреть в самом низу, под названием VirtGraphColoring2(рекурсивная реализация). Потом я подумал, а почему бы не разработать теорию максимезации энтропии(мощности) узлов графа. Эта идея была навеяна прошлым алгоритмом и стратегическими играми, ну знаете, когда от склада с оружием зависят разные точки и разрушив его мы избавляемся, фактически, и от них. И я не стал следовать к соседу с макс. мощностью, а просто прошёлся по узлам в порядке убывания их мощностей, раскрашивая в разные цвета. Радует, что пока что я не нашёл такого графа, который бы они раскрасили не оптимально))) Просьба, подкинуть!))

Edges = {'1':['8', '5', '6'], '2':['6','7', '9'], '3':['7', '10', '5'], '4':['8','10', '9'], '9':['4','5', '2'], '10':['3', '4', '6'], '5':['1', '9', '3'], '6':['1', '2', '10'], '7':['8', '2', '3'], '8':['7', '1', '4']}

#функция раскраски в порядке мощностей узлов
def VirtGraphColoring(Edges):
    result={}
    colors=[0]
  
    def SortEdges():
        sort={}
        for key in Edges:
            sort[key]=len(Edges[key])
        sort2=sorted(sort.iteritems(), key=lambda (k,v):(v,k), reverse=True)
        return sort2
    
    def colorize():
        def removeColor():
            for color in colors:
                if color not in stackColor: return color
            color=colors[-1]+1
            colors.append(color)
            return color
    
        for key in sort:
            stackColor=[]
            for key2 in Edges[key[0]]:
                if key2 in result:stackColor.append(result[key2])
            color=removeColor()
            result[key[0]]=color
        return result
    
    sort=SortEdges()
    return colorize()

print VirtGraphColoring(Edges)

#рекурсивная функция раскраски в порядке мощностей соседей
def VirtGraphColoring2(Edges):
    result={}# результат
    colors=[0]#стек использованных цветов
    sort1={}# ссловарь ключей с их мощностью(количеством соседей)
  
    def SortEdges(): # сортируем словарь
        for key in Edges:
            sort1[key]=len(Edges[key])
        sort2=sorted(sort1.iteritems(), key=lambda (k,v):(v,k), reverse=True)
        return sort2 # список упорядоченных по мощности кортежей вида (ключ, мощность)
    
    def colorize(key):
        def removeColor(): #возвращает нужный цвет 
            for color in colors:
                if color not in stackColor: return color #если можне выбрать цвет, используемый ранее
            color=colors[-1]+1 # нет, тогда новый цвет
            colors.append(color) # добавляем его в коллекцию
            return color
        
        stackColor=[]
        maxi=-1
        maxkey=None
        for key2 in Edges[key]:
            if key2 not in result and sort1[key2]>maxi: 
                maxi=sort1[key2]
                maxkey=key2
            if key2 in result:stackColor.append(result[key2])
        color=removeColor()
        result[key]=color
        sort.remove((key,sort1[key]))
        if maxkey != None: colorize(maxkey)
        elif len(sort)>0: colorize(sort[0][0])

    sort=SortEdges()
    colorize(sort[0][0])   
    return result

Тут обнаружил, что задача раскраски графа, это решение судоку)) Вот так игры и создаются))

Топологическая сортировка

2011-09-03T00:14:00.000-07:00

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

*-Нравится статья? Кликни по рекламе! :)

Существует несколько способов топологической сортировки — из наиболее известных:

Алгоритм Демукрона
Метод сортировки для представления графа в виде нескольких уровней
Метод топологической сортировки с помощью обхода в глубину

Алгоритм с помощью обхода в глубину

Суть алгоритма

Поиск в глубину или обход в глубину (англ. Depth-first search, сокращенно DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.
Запускаем обход в глубину, и когда вершина обработана, заносим ее в стек. По окончании обхода в глубину вершины достаются из стека. Новые номера присваиваются в порядке вытаскивания из стека.
Цвет: во время обхода в глубину используется 3 цвета. Изначально все вершины белые. Когда вершина обнаружена, красим ее в серый цвет. Когда просмотрен список всех смежных с ней вершин, красим ее в черный цвет.
Думаю будет проще рассмотреть данный алгоритм на примере:

Имеем бесконтурный ориентированный граф.
Изначально все вершины белые, а стек пуст.
Начнем обход в глубину с вершины номер 1.

↑ Переходим к вершине номер 1. Красим ее в серый цвет.

↑ Существует ребро из вершины номер 1 в вершину номер 4. Переходим к вершине номер 4 и красим ее в серый цвет.

↑ Существует ребро из вершины номер 4 в вершину номер 2. Переходим к вершине номер 2 и красим ее в серый цвет.

↑ Из вершины номер 2 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 2 в черный цвет и кладем ее в стек.

↑ Существует ребро из вершины номер 4 в вершину номер 3. Переходим к вершине номер 3 и красим ее в серый цвет.

↑ Из вершины номер 3 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 3 в черный цвет и кладем ее в стек.

↑ Из вершины номер 4 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 1. Красим вершину номер 4 в черный цвет и кладем ее в стек.

↑ Из вершины номер 1 нет рёбер, идущих не в черные вершины. Красим её в черный цвет и кладем в стек. Обход точек закончен.

↑ По очереди достаем все вершины из стека и присваиваем им номера 1, 2, 3, 4 соответсвенно. Алгоритм топологической сортировки завершен. Граф отсортирован.
И всем бы это объяснение было хорошо, если бы не одно НО:
Если мы начнем сортировку с 4-го элемента, то никогда не вернемся в 1-й, т.к. мы в нём еще не были, а из 4-го в 1-й стрелочки не идет) Эта проблема полностью ложится на внутреннюю реализацию алгоритма. Я ввел переменную path=[] дабы отслеживать путь перемещения по графу. Т.е. при переходе к новому эл-ту я ддобавляю его в path, а при возвращении - удаляю. Таким образом, нам останется проверить в момент опустения path все ли эл-ты мы прошли и если нет, то запустить алгоритм для любой из еще не просмотренных элементов.
Я использовал здесь матрицы смежности, т.к. считаю, что разрабатывать алгоритм проще, начиная именно с такого представления графа, а уже после вводить необходимые структуры данных.
Например в данной реализации, я делаю N² проверок связи узлов, в то время, как введя, например, связный список, для точной связи элементов, можно избавиться от if вообще и останется N конкретных действий.

Важно!

Циклы в графе есть тогда и только тогда, когда при обходе в глубину мы 'уткнемся' в свой 'серый хвост'.

Ну а вот вам моя ркурсивная реализация данного чуда!)

roofs=['a', 'b', 'c', 'd', 't']
matrix = {('a', 'c'):1, ('c', 'b'):1, ('d', 'b'):1, ('d', 'c'):1, ('d', 't'):1}
#топологическая сортировка поиском в глубину
def topologicSortDFS(v, roof, firstNode=0):
    path=dict()#для разделения несвязных элементов графа
    result=[]#стек результата
    length=len(roof)
    global col
    col=0
    def topologicSort(v, roof, firstNode=0):
        global col
        path[roof[firstNode]]=1
        col+=1
        for i in range(length):
            if roof[i] not in result and v.get((roof[firstNode],roof[i]),0)==1:
                if path.get(roof[i],0)==1:
                    print "!!!имеется цикл!!!"
                    exit()
                topologicSort(v,roof,i)
            if i==length-1:
                result.append(roof[firstNode])
                col-=1
                if col==0 and len(result)!=length:#для отслеживания несвязанных участков
                    for x in roof:
                        if x not in result:topologicSort(v,roof, roof.index(x))
                return result#номер для занесения в стек
    return topologicSort(v, roof, firstNode)

Я ничего не раскрашиваю тут, а использую фактически 2 стека, но увы эта моя реализация не смогла превзойти классическую функцию, которую я привожу ниже.

#Color — массив, в котором хранятся цвета вершин (0 — белый, 1 — серый, 2 — черный).
#Edges — массив списков смежных вершин.
#Numbers — массив, в котором сохраняются новые номера вершин.
#Stack — стек, в котором складываются вершины после их обработки.
#Cycle — принимает значение true, если в графе найден цикл.
Edges = {'a':['c'], 'c':['b'], 'd':['c', 'b', 't'], 'b':[], 't':[]}
def topologicSortDFS2(Edges):
    Stack=[]
    Color=dict()
    for i in Edges.keys():
        Color[i]=0
    def topological_sort():
        def dfs(v):
#Если вершина серая, то мы обнаружили цикл. 
#Заканчиваем поиск в глубину.
            if Color[v] == 1: return True
            if Color[v] == 2: return False#Если вершина черная, то заканчиваем ее обработку.
            Color[v] = 1#Красим вершину в серый цвет.
#Обрабатываем список смежных с ней вершин.
            for i in range(len(Edges[v])-1):
                if dfs(Edges[v][i]): return True
            Stack.append(v)#Кладем вершину в стек.
            Color[v] = 2#Красим вершину в черный цвет.
            return False;
        
#Вызывается обход в глубину от всех вершин. 
#Заканчиваем работу алгоритма, если обнаружен цикл.
        for i in Edges.keys():
            Cycle = dfs(i)
            if Cycle: 
                print "!!!имеется цикл!!!"
                exit()
                
#Заносим в массив новые номера вершин.    
        Stack.reverse()
        return Stack
    return topological_sort()

Результаты тестов приведу в конце!)

Алгоритм представления графа в виде уровней

Пусть дан бесконтурный ориентированный простой граф

G = (V, E)

.
Через обозначим множество вершин таких, что .
То есть,

A (v)

— множество всех вершин, из которых есть ребро в вершину

v

.
Пусть

P

— искомая последовательность вершин.

пока  $| P | < | V |$ 
  выбрать любую вершину  $v$  такую, что  и 
  
  удалить  $v$  из всех

Наличие хотя бы одного контура в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину

v

Пример работы алгоритма

Пусть задан граф .
В таком случае алгоритм выполнится следующим образом:

шаг	$v$	$A (b)$	$A (c)$	$A (d)$	$A (e)$	$P$
0	$-$	$a$	$a$	$a, b, c$	$a, c, d$
1	$a$			$b, c$	$c, d$	$a$
2	$c$			$b$	$d$	$a, c$
3	$b$				$d$	$a, c, b$
4	$d$					$a, c, b, d$
5	$e$					$a, c, b, d, e$

На втором шаге вместо

c

может быть выбрана вершина

b

, поскольку порядок между

b

c

не задан.

Рассмотрим более подробно.
Каждую вершину можно охарактеризовать числом дуг, входящих в неё (полустепень захода), и числом дуг, исходящих из неё к другим вершинам (полустепень исхода).
Если у вершины нет ни одной входящей дуги, вершина называется источником сети.
Если у вершины нет ни одной исходящей дуги, вершина называется стоком сети.

Сначала опишем, что же мы хотим от нашего алгоритма, а потом приведем код.
Итак, наша цель — создать сеть, состоящую из нескольких уровней.

Из рисунка видно, что задачи внутри одного уровня зависят только от задач на младших уровнях, и независимы друг от друга.
В таком случае, для достижения цели нам сначала надо в любом порядке выполнить все задачи уровня 0, потом, в любом порядке, задачи уровня 1, и т.д., до уровня 3 (последнего).

Для решения задачи, нам понадобится представление графа в виде матрицы (ij элемент = 1, если есть дуга из вершины i в вершину j, и равен 0, если дуги нет).
В строке под таблицей даны полустепени захода для всех вершин. Каждое число отражает сумму единичек в соответствующем столбце матрицы.

На первом шаге алгоритма мы выбираем все вершины с нулевой полустепенью захода, заносим их в нулевой уровень и, мысленно, выкидываем из графа.

В результате, (мы больше не учитываем строки матрицы, соответствующие обработанным вершинам) полустепени захода остальных вершин уменьшатся.

Далее, проделываем тоже самое с оставшимися вершинами, имеющими нулевую полустепень захода и помещаем их в первый уровень:

Последующие шаги выполняются аналогично!

Приведем код реализации, за пример взяв прошлый граф.

#топологическая сортировка уровнями
class Graph:
    def __init__(self):
        self.nodes=[[0,0,0,0,0,0],
                    [1,0,0,1,0,0],
                    [0,1,0,1,0,0],
                    [0,0,0,0,0,0],
                    [0,0,0,1,0,0]
                    ];
        self.count=range(len(self.nodes))
        
    def GetInputNodesArray(self):
        array = []
        for i in self.count: 
            step=0
            for j in self.count:
                if self.nodes[i][j]==1:step+=1
            array.insert(i,step)
        return array;
    
    def TopologicSort(self):
        levels =[];
        workArray = self.GetInputNodesArray();
        completedCounter = 0;
        currentLevel = 0;
        while (completedCounter != len(self.nodes)):
            for i in self.count:
                if (workArray[i] == 0):
                    ind=0
                    #добавляем обработанную вершину
                    levels.insert(completedCounter,i);
                    for node in self.nodes:
                        if node[i]==1:
                            workArray[ind]-=1
                        ind+=1
        
                    workArray[i] = -1; # Помечаем вершину как обработанную
                    completedCounter+=1;
            currentLevel+=1;
        levels.reverse()
        return levels#осталось выбрать в обратном порядке

Данный метод, от 2-х предыдущих примеров отличает то, что используется больше памяти на входе, т.к. мы описываем связь каждого узла с каждым. В предыдущем же алгоритме мы хранили только связи с соседями! Насколько оправдано это, смотри в конце статьи в результатах тестов!)

Топологическая сортировка графа в виде структуры Вирта.

Еще 1 пример сортировки уровнями, но в другой структуре.
О самой структуре Вирта, я писал раньше, в статье "Теория графов и деревьев для Python"
Поэтому перейду сразу к описанию алгоритма.
Для данного графа Edges = {'1':['2','4'], '2':['8'], '4':['8'], '5':['8'], '8':[]}

Рис.1. Структура Вирта

Функция сортировки сначала производит внутреннюю оптимизацию, связывая узлы количество исходящих дуг в которых равно 0, чтобы сразу пройтись по ним, сократив несколько итераций поиска таких элементов.
После оптимизации, в нашем случае, структура видоизменится следующим образом:

Рис.2. Результат оптимизации

def VirtTopSort():
    result=[]
    z=len(Edges)
    head=ceateVirtStructLeader(Edges) 
    #Оптимизация
    #Поиск ведущих с нулевым количеством предшественников.
    p=head
    head=None
    while p!=None:
        q=p
        p=p.Next
        if q.Count==0:
            q.Next=head
            head=q
              
    q = head
    while  q!=None:
            #счетчик z для подсчета ведущих узлов
            #он должен вновь стать равным нулю в конце работы программы
            #или имеем цикл!
            z-=1
            #Занести элемент в результат и исключить его.
            result.append(q.Key)
            t=q.Trail
            q=q.Next
            while  t!=None:
                # Уменьшить счетчик предшественников у всех его  
                # последователей в списке ведомых t; если какой- 
                #либо счетчик стал равен 0, то добавить этот    
                # элемент к списку ведущих q;                    
                # p - вспомогательная переменная, указывающая на 
                # ведущий узел, счетчик которого нужно уменьшить 
                # и проверить на равенство нулю.                  
                p=t.Id
                p.Count-=1
                if  p.Count==0: #Включение p в список ведущих.
                    p.Next = q;
                    q = p;
                t = t.Next;
    if z!=0:
        print "цикл!!!"
        exit()
    result.reverse()
    return result

В зарубежном интернете нашел еще один алгоритм, решил привести его здесь, для полноты картины!

Алгоритм R. E. Tarjan от 1972 года
Алгоритм является модификацией алгоритма с применением обхода в глубину

#Алгоритм R. E. Tarjan от 1972 года
def topological_sort(items, partial_order):

    def add_node(graph, node):
        """Добавить узел в графе если он еще не существует."""
        if not graph.has_key(node): 
            graph[node] = [0] # 0 = число дуг входящих в этот узел.

    def add_arc(graph, fromnode, tonode):
        """Добавить дуги графа. 
        Можно создать несколько дуг. 
        Конечные узлы должны уже существовать."""
        graph[fromnode].append(tonode)
        # Обновление количество входящих дуг в узле.
        graph[tonode][0] = graph[tonode][0] + 1
    
    # Шаг 1 - создание ориентированного графа с дугой b-->a для каждого входа
    # Паре (a, b).
    # Граф представлен словарём.Словарь содержит:
    # Пару item:list для каждого узла в графе. /item/ это значение узла
    # /list/ с первым пунктом является счетчиком входящих дуг, а
    # остальные направления исходящих дуг. Например:
    # {'a':[0,'b','c'], 'b':[1], 'c':[1]} 
    # получим следующий граф: c <-- a --> b 
    graph = {}
    for v in items:
        add_node(graph, v)
    for a,b in partial_order:
        add_arc(graph, a, b)
    
    # Шаг 2 - найти все корни (узлы с нулевым входящих дуг).
    roots = [node for (node,nodeinfo) in graph.items() if nodeinfo[0] == 0]
    
    # Шаг 3 - неоднократно выделяют корень и удаляем его из графа.
    # Удаление узла может преобразовывать некоторые из прямых потомков узла в корни.
    # Всякий раз, когда это произойдет, мы добавляем новые корни в список корней
    sorted = []
    while len(roots) != 0:
        # Если длина (roots) всегда равна 1, когда мы сюда попали, это означает, что
        # вход описывает законченый порядок, и есть только
        # один возможный вывод.
        # Когда длина (roots)> 1, мы можем выбрать любой корень, чтобы отправить
        # на выход; эта свобода представляет несколько полной упорядоченности
        # Мы произвольно принимать один из
        # корней использованием pop(). Заметим, что для алгоритма, чтобы быть эффективным,
        # эта операция должна быть сделана за O(1) времени.
        root = roots.pop()
        sorted.append(root)
        for child in graph[root][1:]:
            graph[child][0] = graph[child][0] - 1
            if graph[child][0] == 0:
                roots.append(child)
        del graph[root]
    if len(graph.items()) != 0:
        # Существует цикл!
        print "цикл!!!"
        exit()
    return sorted

print topological_sort(['a','b','c','d','t'], [('t','d'),('b','d'),('c','d'),('b','c'),('c','a')])

Примеры использования топологической сортировки

Техническая задача разбивается на ряд подзадач, при этом выполнение одних подзадач должно предшествовать выполнению других подзадач. Топологическая сортировка означает выполнение подзадач в таком порядке, чтобы перед началом выполнения каждой подзадачи все необходимые для этого подзадачи были уже выполнены.

В программе некоторые процедуры могут вызывать другие процедуры. Топологическая сортировка предполагает расположение описаний процедур в таком порядке, чтобы вызываемые процедуры описывались раньше тех, которые их вызывают. Сборка приложения

Дуга, идущая из вершины «Код» в вершину «Результирующий файл» говорит о том, что «Код» должен быть обработан прежде, чем будет получен Result.exe
Перед тем, как вершина может быть обработана, следует обработать все вершины, ссылающиеся на неё.

При помощи топологической сортировки строится корректная последовательность выполнения действий, всякое из которых может зависеть от другого: последовательность прохождения учебных курсов студентами, установки программ при помощи пакетного менеджера, сборки исходных текстов программ при помощи Makefile'ов.

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

Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов.

Результаты тестов
Тест проводился путем исполнения 10000 раз определенной функции в profile с использованием функции test.

Мой самодельный алгоритм.
profile.run('test(topologicSortDFS2, 10000, Edges)')
420005 function calls (380005 primitive calls) in 4.598 seconds
Я думаю улучшить его, разбивая на подграфы, но много ли это принесет, увидим позже.
Классический алгоритм поиска в глубину и раскраски.
profile.run('test(topologicSortDFS, 10000, matrix, roofs)')
270005 function calls (250005 primitive calls) in 2.915 seconds
Алгоритм разбиения уровнями, с представлением графа в виде матрицы смежности
profile.run('test(gr.TopologicSort,10000)')
160005 function calls in 1.688 seconds
С алгоритмом использующим структуру Вирта, Всё несколько интереснее.
profile.run('test(VirtTopSort,10000)')
Скорость его выполнения
780005 function calls (750005 primitive calls) in 8.322 seconds
из них 10000 1.227 0.000 6.676 0.001 __init__.py:150(ceateVirtStructLeader)
Уходит на создание самой структуры! Т.е. фактическое время исполнения метода около 1.5 сек, но использовать его нужно там, где используется данная структура сразу, а несоздается специально для данной функции!
Ну и в заключение алгоритм R. E. Tarjan от 1972 года
profile.run("test(topological_sort,10000,['a','b','c','d','t'], [('t','d'),('b','d'),('c','d'),('b','c'),('c','a')])")
430005 function calls in 3.901 seconds
Хоть он и считается модифицированной версией алгоритма номер 2, но почему то он проиграл ему секунду! Может я просто нашел плохую его реализацию?

Используемая литература:

Связные списки

2011-08-27T12:51:00.000-07:00

В информатике, свя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Мы с вами рассмотрим реализацию односвязного (однонаправленного) списка.
*-Нравится статья? Кликни по рекламе! :)

Коли уж я натолкнулся на прелестные статьи Сергея Яковлева, на сайте IBM, которые люди так не заслужено оценили в 2 звезды, давайте обсудим их.
В конечном итоге мы получим реализацию данного рисунка

В одной из статей Sython'а (Cвойство замыкания, на примере list) мы уже создавали похожую структуру, методами функционального программирования. Пришло время задействовать ООП!)

История связных списков
Основной принцип связных списков крайне прост: эта структура данных состоит из последовательности записей, в которой каждая запись хранит помимо самих данных еще и ссылку на следующую запись в этой последовательности. На рисунке 1 изображен связный список из трех записей, каждая запись которого состоит из поля данных - целого числа и ссылки на следующую запись.

Рисунок 1. Пример связного списка

У последней записи на рисунке отсутствует ссылка, но она есть и указывает на NULL. На основе списков можно реализовать структуры данных, такие как стеки, очереди и ассоциативные массивы.
Ранее уже упоминалось, что в массиве все элементы расположены в памяти по порядку, а в списке они в памяти никак не упорядочены. Более того, элемент может быть добавлен в любую позицию в списке. Однако сама операция по вставке элемента в список требует дополнительных ресурсов, так как нужно последовательно просканировать список для поиска нужной позиции.

Основные правила реализации связных списков
Список состоит из элементов, называемых узлами (node). Первый узел списка называется «головным» (head), а последний - «хвостовым» (tail). На рисунке 2 изображен двойной связный список.

Рисунок 2. Двойной связный список

Каждый элемент состоит из 3-х полей, два из которых являются указателями на предыдущий или следующий узел. Элемент может указывать и более чем на два узла, и в этом случае список называется многосвязным.
Помимо упоминавшихся ранее стандартных массивов существуют еще динамические массивы. Размер обычного массива является фиксированной величиной, а в динамический массив можно добавлять или удалять из него элементы. Если элемент добавляется в середину динамического массива, то происходит перераспределение элементов, находящихся справа от него, так как все элементы массива должны быть расположены в памяти строго по порядку. Поэтому вставка элемента в динамический массив требует дополнительных ресурсов, если элемент добавляется не в конец массива. Преимущество связного списка в том, что не требуется перестраивать последовательность узлов, независимо от того, в какую позицию списка вставляется новый элемент. Недостаток связных списков – это последовательный доступ (sequential access) к элементам, тогда как для массивов время доступа постоянно и не зависит от размера - random access. Если приложению требуется быстрый поиск элемента по индексу, то в данном случае списки не подходят, и лучше воспользоваться массивами.
Еще один негативный момент при использовании связных списков связан с нерациональным использованием памяти. Если в узле хранится небольшая порция данных, например, булевское значение, то список становится неэффективными из-за того, что объем памяти, выделяемой под хранение связей, превышает объем памяти, выделяемой под хранение «полезной нагрузки».

Связный список - это рекурсивная структура, так как узел всегда содержит указатель на следующий узел. Это позволяет использовать простой рекурсивный алгоритм для таких операций, как объединение двух списков или изменение порядка элементов на обратный. У односвязных списков есть важное преимущество: если к вершине такого списка добавляется новый элемент, то старый список будет по прежнему доступен по ссылке на только что добавленный узел. Этот прием называется persistent data structure (постоянное хранение данных). У двусвязных списков есть свои преимущества, так как они позволяют выполнять итерацию в обоих направлениях, в отличие от односвязных списков.
Если последний элемент будет указывать на первый элемент списка, то такая структура называется циклическим замкнутым (или кольцевым (circular)) списком. Кольцевые списки можно использовать для списка процессов, в которых применяется «карусельный» (round-robin) алгоритм. Для такого списка достаточно иметь один указатель, который одновременно указывает и на конец, и на начало очереди. Кольцевой список можно разбить на два кольцевых списка или, наоборот, объединить.

Рисунок 3. Кольцевой связный список

Полезно почитать введение, данное в 1-й части цикла
Работа со структурами данных в языках Си и Python: Часть 1. Самое главное, на мой взгляд, написано в конце статьи, а именно:

Преимущества:

Удаление элементов в таком списке более эффективно, нежели удаление элементов из стандартного списка Python, который рассматривался в предыдущем разделе. Так как этот элемент удаляется из середины стандартного списка, то время, необходимое на эту операцию, будет зависеть от нескольких факторов: размера списка, положения удаляемого элемента относительно конца. Чем больше размер списка, тем медленнее будет происходить данная операция. В данном случае со ссылочной организацией списка удаление будет происходить одинаково быстро, независимо от размера списка и относительного положения элемента, так как потребуется всего лишь перевести ссылку в предыдущем элементе на следующий за удаляемым элемент.

То же самое можно сказать и про вставку элементов - она выполняется так же эффективно, как и удаление.

Объединение или разбиение 2-х списков будет выполняться быстрее, нежели в стандартном варианте.

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

Недостатки:

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

Доступ к произвольному элементу для стандартного массива в Си и для стандартного списка в Python есть величина постоянная и не зависящая от величины массива. В случае со ссылочными списками время доступа будет зависеть от величины списка, так как потребуется выполнить итерацию по всему списку.

И в той же статье, еще раз обратите внимание на всем известные, но не теряющие интереса особенности Python'а в отношении ссылок!

Итак, приступим к кодингу)

#класс Node для определения элемента списка
class Node:
    def __init__(self, value = None, next = None):
        self.value = value
        self.next = next

Для определения связного списка потребуется еще один класс – LinkedList, в конструкторе которого будут определяться первый и последний элементы списка и его длина. Также в классе будут использоваться встроенный метод str для распечатки содержимого списка и метод clear для очистки списка.

class LinkedList:
    def __init__(self):
        self.first = None
        self.last = None
        self.length = 0

    def __str__(self):
        if self.first != None:
            current = self.first
            out = 'LinkedList [\n' +str(current.value) +'\n'
            while current.next != None:
                current = current.next
                out += str(current.value) + '\n'
            return out + ']'
        return 'LinkedList []'

    def clear(self):
        self.__init__()

Добавление элементов в конец списка.
Может я чего накрутил, но во первых я не понял, зачем была нужна секция "elif" и вообще я её немного упростил)

def add(self, x):
        self.length+=1
        if self.first == None:
            #self.first и self.last будут указывать на одну область памяти
            self.last = self.first = Node(x, None)
        else:
            #здесь, уже на разные, т.к. произошло присваивание
            self.last.next = self.last = Node(x, None)

Теперь мы можем добавить несколько эл-тов и даже распечатать наш список!)

L = LinkedList()
L.add(1)
L.add(2)
L.add(3)
print(L)

А не научиться ли нам вставлять эл-ты в начало списка?)
В реализации нужно учитывать два варианта: в первом случае список пуст, а во втором создается новый узел, в конструктор которого в качестве второго параметра передается головной элемент списка. Комментарии по коду, те же, что и в предыдущем листинге.

def push(self, x):
            self.length+=1
            if self.first == None:
                self.last = self.first = Node(x,None)
            else:
                self.first = Node(x,self.first)

Давайте усложним себе задачу и вставим новый элемент в место, куда хотим!)
Я посмел чуточку исправить код, чтобы он заработал, а так все как и там. Необходимо сначала проверить, что список не пуст, а затем, что вставка не происходит на нулевую позицию. Если оба условия не выполняются, то происходит итерация по списку до нужной позиции и добавление элемента:

def InsertNth(self,i,x):
        if self.first == None:
            self.last = self.first = Node(x, None)
            return
        if i == 0:
          self.first = Node(x,self.first)
          return
        curr=self.first
        count = 0
        while curr != None:
            count+=1
            if count == i:
              curr.next = Node(x,curr.next)
              if curr.next.next == None:
                self.last = curr.next
              break
            curr = curr.next

Научились добавлять, пора всех их посчитать!)
Я не очень понял, зачем в статье для этого пишется отдельная функция, видимо, чтобы просто поиграть извилинами. Раз уж используем ООП, то просто при добавлении инкриментируем встроенную переменную length, а при удалении дикрементируем, ну или как там?) Что я собственно и сделаю, тогда длина списка всегда будет статична и не нужно будет бегать по списку для её нахождения, хотя это и увеличит добавление и удаление элементов на несколько процессор-итераций.) Но все же приведу ту ф-цию! Для определения длины списка в используется функция len, которая вначале проверяет, не является ли список пустым, а затем выполняет итерацию по элементам списка.

def len(self):
        length =0
        if self.first != None:
            current = self.first
            while current.next != None:
                current = current.next
                length +=1
        return length+1#+1 для учета self.first

Удаление головного элемента
В реализации потребуется проверить список на пустоту и объявить две локальных переменных: первая будет хранить текущий элемент, а вторая - предыдущий. Потом выполняется итерация по списку для поиска удаляемого элемента и проверка того, не является ли он последним в списке. Если удаляемый элемент является последним, то предыдущий узел становится последним, в противном случае предыдущий узел связывается со следующим узлом вместо текущего.

def Del(self,i):
        if (self.first == None):
          return
        curr = self.first
        count = 0
        if i == 0:
          self.first = self.first.next
          return
        while curr != None:
            if count == i:
              if curr.next == None:
                self.last = curr
              old.next = curr.next 
              break
            old = curr  
            curr = curr.next
            count += 1

Вставка элемента в отсортированный список
В данной реализации выполняется проверка списка на пустоту, а затем выполняется итерация с помощью двух временных переменных, как и в прошлом листинге.

def SortedInsert(self,x):
        if self.first == None:
          self.first = Node(x,self.last)
          return
        if self.first.value > x:
          self.first = Node(x,self.first)
          return
        curr = self.first
        while curr != None:
            if curr.value > x:
              old.next = Node(x,curr)
              return
            old = curr
            curr = curr.next       
        self.last = old.next = Node(x,None)

Удаление повторяющихся значений
Сначала напишем данную функцию для общего случая. Она будет проходить по всему списку от начала, до конца, для каждого элемента. Это приблизительно N²/2 проходов!

def RemoveDuplicates(self):
        if (self.first == None):
            return
        old=curr = self.first
        while curr != None:
            if curr.next != None:
                if old.value == curr.next.value:
                    curr.next = curr.next.next
            else:
                old=curr = old.next
            curr=curr.next

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

def RemoveSortedDuplicates(self):
        if (self.first == None):
            return
        curr = self.first
        while curr != None:
            _del = 0 
            if curr.next != None:
                if curr.value == curr.next.value:
                    curr.next = curr.next.next
                    _del = 1
            if _del == 0:
                curr = curr.next

Копирование списков
Это последнее, что мы с вами реализуем!) Если в СИ в реализации данной ф-ии используется три указателя: на первый элемент оригинального списка и на первый и последний элементы скопированного списка и много кода, то в Python для копирования списков можно использовать стандартный модуль copy, как показано ниже.

import copy
L2 = copy.deepcopy(L) // создание копии списка L

Пузырьковая сортировка

def BubbleSort(self):
       a = Node(0,None)
       b = Node(0,None)
       c = Node(0,None)
       e = Node(0,None)
       tmp = Node(0,None)
       
       while(e != self.first.next) :
        c = a = self.first
        b = a.next

        while a != e:
          if a and b:
            if a.value > b.value:
              if a == self.first:
                tmp = b.next
                b.next = a
                a.next = tmp
                self.first = b
                c = b
              else:
                tmp = b.next
                b.next = a
                a.next = tmp
                c.next = b
                c = b
            else:
              c = a
              a = a.next
            b = a.next
            if b == e:
              e = a
          else:
              e = a

По заявкам, добавляю ф-ию получения элемента, обращаться можно по индексу L[n]:

    def __getitem__(self, key):#поддержка обращения по ключу
        length =0
        current=None
        if self.first != None:
            current = self.first
            while key!=length or current.next != None:
                current = current.next
                length +=1
            if key==length:current=current.value
        return current

Тестирование производительности

Было произведено сравение скоростей создания встроенного списка Python(путем list.append()) и созданного выше(list.add()) из 10000 элементов, производительность нашего связного списка ниже.40004 function calls in 0.327 CPU seconds против 30004 function calls in 0.182 CPU seconds

Используемая литература:

Бинарные деревья

2011-07-30T10:41:00.000-07:00

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом. Бинарное дерево
с N узлами имеет не меньше [log₂N + 1] уровней (при максимально плотной упаковке узлов).
Если уровни дерева занумеровать, считая что корень лежит на уровне 1, то на уровне с номером К лежит 2^К-1 узел. У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья лежат на уровне с номером j, и у каждого узла на уровнях с первого по j — 1
в точности два непосредственных потомка. В полном бинарном дереве с j уровнями 2^j — 1 узел.
*-Нравится статья? Кликни по рекламе! :)

Бинарные деревья поиска обычно применяются для реализации множеств и ассоциативных массивов. И применяются для быстрого поиска информации. Например в статье Двоичный (бинарный) поиск элемента в массиве мы искали во встроенной в Python структуре данных, типа list, а могли реализовать бинарное дерево. Двоичные деревья, как и связные списки, являются рекурсивными структурами.
Различные реализации одного и того же бинарного дерева

Существуют следующие разновидности бинарных деревьев:

полное(расширенное) бинарное дерево - каждый узел, за исключением листьев, имеет по 2 дочерних узла;
идеальное бинарное дерево - это полное бинарное дерево, в котором все листья находятся на одной высоте;
сбалансированное бинарное дерево - это бинарное дерево, в котором высота 2-х поддеревьев для каждого узла отличается не более чем на 1. Глубина такого дерева вычисляется как двоичный логарифм log(n), где n - общее число узлов;
вырожденное дерево - дерево, в котором каждый узел имеет всего один дочерний узел, фактически это связный список;
бинарное поисковое дерево (BST) - бинарное дерево, в котором для каждого узла выполняется условие: все узлы в левом поддереве меньше, и все узлы в правом поддереве больше данного узла.

Вычисление путей
Путь - это расстояние от корня дерева до какого либо узла. Если число листьев полного бинарного дерева обозначить как S, а число остальных узлов обозначить как N, то справедлива формула:

S = N +1

Если путь от корневого узла до листа обозначить как внешний путь, а путь от корневого узла до НЕлиста обозначить как внутренний путь, тогда сумма всех внешних путей для дерева, изображенного на рисунке, примере полного дерева, ниже:

E=3+3+2+3+4+4+3+3=25,

а сумма внутренних путей будет равна:

I=2+1+0+2+3+1+2=11.

и тогда будет справедлива формула:

E=I+2n, где n - число узлов.

Пример расширенного дерева

Можно сформулировать следующие задачи:

сконструировать бинарное дерево таким образом, чтобы сумма путей была минимальной, так как это сокращает время вычислений для различных алгоритмов.
сконструировать полное расширенное бинарное дерево таким образом, чтобы сумма произведений путей от корневого узла до листьев на значение листового узла была минимальной.

Давид Хаффман (David Huffman) предложил алгоритм для решения этой проблемы, в котором на каждом шаге выбираются и складываются два наименьших листа, как показано в листинге 1, что приводит к дереву, изображенному на рисунке ниже.

Листинг 1. Пример алгоритма Хаффмана

2 3 5 7 11 13 17 19 23 29 31 37 41
    5 5 7 11 13 17 19 23 29 31 37 41
     10 7 11 13 17 19 23 29 31 37 41
       17    24 17 19 23 29 31 37 41
             24 34 19 23 29 31 37 41
             24 34    42 29 31 37 41
                      42 53 65 37 41
                      42 53 65    78
                         95 65    78
                         95      143
                                 238

Бинарное дерево, построенное по алгоритму Хаффмана

Более полную статью, по кодам Хаффмана читай в моей более ранней статье.

Реализация:
До этого, в своих статьях я показывал силу функционального программирования Python.
Теперь, пришло время, показать ООП в действии, создав новую структуру данных Tree, состоящую из других структур, типа Node.
Сразу скажу, что код взят с сайта IBM с минимальными изменениями и дополнениями. С моей точки зрения данный класс является недееспособным с точки зрения добавления элементов,по причине того, что мы сами должны строить дерево, помня структуру у себя в голове, а ведь мы можем и ошибиться. И позже я напишу так, как мне кажется верным, где добавление элемента является рекурсивным проходом по дереву и поиску подходящего места. А пока, разберем, что есть:

class node:
    def __init__(self, data = None, left = None, right = None):
        self.data   = data
        self.left   = left
        self.right  = right

    def __str__(self):
        return 'Node ['+str(self.data)+']'

#/* класс, описывающий само дерево */  
class Tree:
    def __init__(self):
        self.root = None #корень дерева

# /* функция для добавления узла в дерево */
    def newNode(self, data):
        return node(data,None,None)

Дальше, все функции расширяют класс Tree.

Высота бинарного дерева
Для определения высоты дерева потребуется пройти от корня сначала по левому поддереву, потом по правому, сравнить две этих высоты и выбрать максимальное значение. И не забыть к получившемуся значению прибавить единицу (корневой элемент). Мы реализуем её в привычном уже нам рекурсивном виде.

# /* функция для вычисления высоты дерева */
    def height(self,node):
      if node==None:
          return 0
      else:
        lheight = self.height(node.left)
        rheight = self.height(node.right)
    
        if lheight > rheight:
            return(lheight+1)
        else:
          return(rheight+1)

«Зеркальное» отражение бинарного дерева
Когда два дерева являются зеркальным отражением друг друга, то говорится, что они симметричны. Для получения «зеркальной» копии дерева сначала выполняется проверка на наличие у корня дерева дочерних узлов, и если эти узлы есть, то они меняются местами. Потом эти же действия рекурсивно повторяются для левого и правого дочерних узлов. Если существует только один дочерний узел, тогда можно переходить на один уровень ниже по дереву и продолжать.

#    /* функция для зеркального отражения дерева */
    def mirrorTree(self, node):
      if  node.left and node.right:
        node.left,node.right=node.right,node.left
        self.mirrorTree(node.right)
        self.mirrorTree(node.left)
      else:
        if node.left==None and node.right:
            return self.mirrorTree(node.right)
        if node.right==None and node.left:
            return self.mirrorTree(node.left)

Проверка наличия узла в бинарном дереве
Нужно только учесть, что данная функция не работает для зеркального отображения дерева!

#    /* функция для проверки наличия узла */
    def lookup(self, node, target):
        if node == None:return 0
        else:
            if target == node.data: return 1
            else:
                if target < node.data: return self.lookup(node.left, target)
                else: return self.lookup(node.right, target)

Ширина бинарного дерева
Под шириной дерева понимается максимальное количество узлов, которые расположены на одной высоте. Чтобы определить ширину дерева, достаточно просто добавить счетчик в уже рассмотренный алгоритм для определения высоты дерева.

# /* функция для вычисления ширины дерева */
    def getMaxWidth(self,root):
      maxWdth = 0
      i = 1
      width = 0 ;
      h = self.height(root)
      while( i< h):
        width =   self.getWidth(root, i)
        if(width > maxWdth):
            maxWdth  = width;
        i +=1    
      return maxWdth;

    def getWidth(self, root, level):
      if root == None:
        return 0
      if level == 1: 
        return 1
      elif level > 1:
          return self.getWidth(root.left, level-1) +  self.getWidth(root.right, level-1)

Распечатка дерева:

# /* функция для распечатки элементов на определенном уровне дерева */
    def printGivenLevel(self, root, level):
      if root == None:
        return
      if level == 1:
        print ("%d " % root.data)
      elif level > 1:
          self.printGivenLevel(root.left, level-1);
          self.printGivenLevel(root.right, level-1);


# /* функция для распечатки дерева */
    def printLevelOrder(self, root):
      h = self.height(self.root)
      i=1
      while(i<=h):
        self.printGivenLevel(self.root, i)
        i +=1

Сравнение бинарных деревьев
Вынесите её за пределы класса только)

def sameTree(a, b):
    if a==None and b==None: return 1
    elif a and b:
        return(
                a.data == b.data and
                sameTree(a.left, b.left) and
                sameTree(a.right, b.right)
                )
    return 0

Количество узлов в бинарном дереве
Вычислить количество узлов в бинарном дереве также можно с помощью рекурсии.
Хотя с точки зрения производительности и принципов ООП, правильнее встроить счетчик в сам объект.

def size(node):
    if node==None:return 0;
    return(size(node.left) + 1 + size(node.right));

Немножко о производительности
Я протестировал наш класс на поиск. К сожалению, данная его реализация проиграла бинарному поиску по списку, описанному ранее. Я тестировал, запуская в 100000 цикле поиска элемента со значением 5 и результат нашего класса
400003 function calls (100003 primitive calls) in 3.481 seconds
против
200003 function calls in 1.791 seconds
Я считаю, что причина в рекурсивном исполнении данного метода + реализации на Python, а не Си)

Вывод:
Организация данных с помощью бинарных деревьев часто позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева, т.е. количеству уровней в иерархической структуре дерева.
Вот и все, в заключение хочу сказать, что если какие то вопросы не раскрыты, не понятны или не оптимальны, просьба не стесняться и писать в комментариях!)
Используемая литература:

Дж. Макконнелл - Основы современных алгоритмов.
Структуры данных: бинарные деревья. Часть 1
Работа со структурами данных в языках Си и Python: Часть 6. Двоичные деревья
Может быть полезным Обходы бинарных деревьев

Анализ алгоритма

2011-07-30T05:12:00.000-07:00

Что такое анализ?

Анализируя алгоритм, можно получить представление о том, сколько времени займет решение данной задачи при помощи данного алгоритма. Одну и ту же задачу можно решить с помощью различных алгоритмов. Анализ алгоритмов дает нам инструмент для выбора алгоритма.
Результат анализа алгоритмов — не формула для точного количества секунд или компьютерных циклов, которые потребует конкретный алгоритм. Из статьи Порядок роста мы уже знаем, что разница между алгоритмом, который делает N + 5 операций, и тем, который делает N + 250 операций, становится незаметной, как только N становится очень большим.
*-Нравится статья? Кликни по рекламе! :)

Что подсчитывать и что учитывать?

Аддитивные операции: сложение и вычитание.
Мультипликативные операции: умножение, деление и взятие остатка по модулю.
Особые: целочисленное умножение или деление на степень двойки сводятся к сдвигу, а он по скорости эквивалентен сложению.

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

Наилучший случай

Время выполнения алгоритма в наилучшем случае очень часто оказывается маленьким или просто постоянным, поэтому подобный анализ проводится редко.

Наихудший случай

Анализ наихудшего случая чрезвычайно важен, поскольку он позволяет представить максимальное время работы алгоритма. При анализе наихудшего случая необходимо найти входные данные, на которых алгоритм будет выполнять больше всего работы.

Средний случай

Анализ среднего случая является самым сложным, поскольку он требует учета множества разнообразных деталей. В основе анализа лежит определение различных групп, на которые следует разбить возможные входные наборы данных. На втором шаге определяется вероятность, с которой входной набор данных принадлежит каждой группе. На третьем шаге подсчитывается время работы алгоритма на данных из каждой группы. Время работы алгоритма на всех входных данных одной группы должно быть одинаковым, в противном случае группу следует подразбить. Среднее время работы вычисляется по формуле

где через n обозначен размер входных данных, через m — число групп. через p_i — вероятность того, что входные данные принадлежат группе с номером i, а через t_i — время, необходимое алгоритму для обработки данных из группы с номером i.

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

Нижние границы. Дерево решений.
Алгоритм является оптимальным, если любой любой другой алгоритм, решающий данную задачу, работает не быстрее данного. Как узнать оптимальность алгоритма? Для этого мы должны знать минимальное количество операций, необходимое для решения поставленной задачи, которое называется нижней границей. Но для этого нам нужно изучать именно ЗАДАЧУ, а не конкретный алгоритм!
Как пример, рассмотрим анализ процесса сортировки списка из 3 чисел, воспользовавшись бинарным деревом. Такое дерево называется деревом решений.

Самый длинный путь в данном дереве соответствует наихудшему случаю и наоборот, кратчайший - наилучшему. Средний случай описывается частным от деления числа ребер в дереве на число листов.
Для перестановки 2-х элементов мы имеем 1лист, для N эл-тов, по правилам комбинаторики, N! листов. Число листов на уровне K равно 2^k-1, поэтому в нашем дереве решений буде L -уровней, где L - наименьшее целое число, для которого N! ≤ 2^L-1. Логарифмируя, получим

В конечном итоге, получаем:

Вот мы и узнали, что любой алгоритм сортировки, порядка О(NlgN) является наилучшим и его можно считать оптимальным. Более того, из этого исследования вытекает, что алгоритм, решающий задачу сортировки быстрее О(NlgN) операций, не может работать правильно!

Используемая литература:

Дж. Макконнелл - Основы современных алгоритмов.

Python алгоритмы

Python Profiling

Приступим к профайлингу

Производительность

Память

CherryPy server

Byte Code

Оптимизация с учетом предпочтений

Оптимизация распределения студентов по комнатам

Представление решения

Целевая функция

Оптимизация

Вместо вывода

Задачи оптимизации

Формат данных

Целевая функция

Случайный поиск

Алгоритм спуска с горы

Алгоритм имитации отжига

Генетические алгоритмы

Вместо вывода

Кластеризация данных

Постановка задачи

Иерархическая кластеризация

Кластеризация методом k-средних

Обучение нейронной сети

Проектирование сети отслеживания переходов

Подготовка базы данных

Прямой проход

Обучение с обратным распространением

Подключение к поисковой машине

Поиск и ранжирование

Что такое поисковая машина

Код паука

Построение индекса

Создание схемы

Выделение слов на странице

Добавление в индекс

Запросы

Ранжирование по содержимому

Функция нормализации

Весовые функции

Частота слов

Расположение в документе

Расстояние между словами

Использование внешних ссылок на сайт

Простой подсчет ссылок

Алгоритм PageRank

Использование текста ссылки

Вывод в продолжение

Подбор предметов

Подбор схожих предметов

Практика Евклида

Практика Пирсона

Рекомендование предметов

Рекомендование предметов

Фильтрация по схожести образцов

Выдача рекомендаций

Оценка подобия

Ищем похожих пользователей

Оценка по евклидову расстоянию

Коэффициент корреляции Пирсона

Проблема нормализации

Какой оценкой подобия воспользоваться

Практика Евклида

Практика Пирсона

Немного о чувствительности критериев

Советую почитать

Машинное обучение. Начало.

Предисловие

В поисках данных

Алгоритм Бойера - Мура

Задача о путешествии шахматного коня

Алгоритм Кнута-Морриса-Пратта (КМП)

Поиск первого вхождение подстроки. Решение в лоб.

Линейный поиск

Совершенный код

Сортировка слиянием

Технические задачки

Быстрая сортировка(quicksort, сортировка Хоара)