Python Profiling

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендование предметов

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

Оценка подобия

Ищем похожих пользователей

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

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

Предисловие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Википедия
2. Algolist

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

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

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

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

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