Чтобы добавлять сообщения и комментарии, .

@pimiento2:
pimiento2

Реализация 3-way Quicksort выглядит следующим образом. Делаем shuffle для массива (заместо Tukey's median) и устанавливаем pivot-элементом нулевой элемент (указатель lt), указатель i на первый элемнт, указатель gt на последний элемент. Если i < lt, то меняем местами значение под i и значение под lt, сдвигаем i и lt на еденицу (lt вновь указывает на прежнее значение). Если i = lt, то сдвигаем i вправо на единицу (таким образом, между lt и i находятся все элементы равные lt). Если i < gt, то меняем местами значения под i и под gt, сдвигаем gt на единицу влево (декремент). Действуем так до тех пор пока указатели i и gt не пересекутся. Это был partitioning. У нас слева от lt все элементы строго меньше значения под lt, а справа от i — строго больше. Теперь рекурсивно повторяем алгоритм для подмассива слева от lt и подмассива справа от i. Когда алгоритм дойдёт до подмассивов длиной 4-10 элементов, то можно использовать selection sort на таких коротких подмассивах. В среднем, quicksort быстрее mergesort за счёт отсутствия постоянных перестановок данных. Нестабилен. Можно распараллелить обработку подмассивов.

@pimiento2:
pimiento2

Алгоритм Convex hull состоит в нахождении координат наименьшего по площади выпуклого многоугольника, огибающего все заданные точки. Физически это то же что натянуть нитку вокруг множества вбитых в доску гвоздей и найти координаты гвоздей, на которых будет держаться эта нитка. Для нахождения координат огибающей необходимо: 1. Выбрать самую нижнюю и одновременно самую правую точку, взяв её за начало отсчёта (назовём P). 2. Сортируем остальные точки I_n по увеличению угла OxPI_n 3. Обходим точки по порядку увеличения угла и проверяем не нарушилось ли условие, что обход происходит только строго против часовой стрелки, т. е. что нет изменения направления движения вправо или вверх после движения вниз. Проверить направление движения геометрической формулой: (b_x — a_x)(c_y — a_y) — (b_y — a_y)(c_x — a_x) < 0 -> по часовой стрелке; = 0 -> прямая; > 0 -> против часовой стрелки.

@pimiento2:
pimiento2

Перемешивание (shuffling) последовательности необходио производить по алгоритму Кнута. Имеем указатель i, который будет проходить последовательность слева-направо. На каждом шаге генерируем случайное целое число r от 0 до i и переставляем элемент под индексом i с элементом под индексом r. Таким образом, на первом шаге переставляем нулевое элемент с самим собой, на втором шаге мы уже можем переставить первый элемент (i = 1) или с самим собой или с элементом под индексом 0. И так далее. В итоге мы гарантированно получим случайную перестановку элементом последовательности за линейное время.

@pimiento2:
pimiento2

Selection sort — простейшая сортировка с инвариантами: 1. Левее указателя все значения уже отсортированы 2. Правее указателя нет значений меньше любого из значений слева от указателя. На каждом шаге цикла находим самое минимальное значение справа от указателя и помещаем его слева от указателя, таким образом поддерживая инварианты. Требует ~N²/2 сравнений и ~N перестановок. Не зависит от входных данных: отсортированны они или нет.
Insertion sort — имеем два указателя i и j. На каждом шаге сравниваем больше ли значение от i+1 чем от i, и если да, то сохраняем указатель на i в текущей позиции и спускаем значение от i+1 налево, сравнивая его с j-1, передвигая j влево. Требует в среднем ~N²/4 сравнений и ~N²/4 перестановок. Если последовательность уже отсортирована, то потребуется N-1 сравнение и 0 перестановок. Для последовательности в обратном порядке потребуется ~N²/2 сравнение и столько же перестановок. Если значение комбинаторных перестановок для последовательности линейно по отношению к числу элементов, то insertion sort потребует линейного времени работы, поэтому его удобно использовать для почти отсортированных последовательностей. Почти отсортированные последовательности это как раз те последовательности, у которых число комбинаторных перестановок не превосходит c*N.

@pimiento2:
pimiento2

*iterators *comparable
Generics — позволяют создавать классы не зависящие от типа и проверяющие переданный тип во время компиляции, а не выполнения. Для массивов так сделать невозможно, поэтому необходимо использовать cast при получение элемента из массива.
Iterators — реализуют интерфейс Iterable: public class C<T> implements Iterable<T>. Обязаны содержать публичный метод, возвращающий объект итератора: public Iterator<T> iterator() { return new IteratorClass(); }. Объект итератора обязан реализовать метод hasNext: public boolean hasNext(); метод next: public T next(); и метод remove, которым лучше не пользоваться: public void remove(); сам класс итератора должен реализовать интерфейс Iterator: private class IteratorClass implements Iterator<T>.
Comparable — если класс реализует интерфес Comparable<ClassName> то он поддерживает вызов callback-ов для использования в функциях сортировки. Класс, реализующий интерфес Comparable, обязан имплементировать метод compareTo, который возвращет -1 0 1 если переданное значение меньше, равно или больше значению текущего объекта.

@pimiento2:
pimiento2

*Стэк возможно реализовать при помощи связанных списков (linked lists) или при помощи массива переменной длины (resizable array). При использовании связанных списков, необходимо хранить только указатель на начало списка. При вставке нового элемента мы сохраняем копию первого элемента в "oldfirst", создаём новый элемент под именем "first" и его указателем на следующий элемент делаем "oldfirst". Если использовать расширяемые массивы, то встаёт вопрос с изменением длины массива. При изменении длины на каждую вставку (push) мы получим квадратичное время вставки в стэк. Увеличивать массив надо вдвое, если массив уже заполнен. Во избежание такого явления как "биение" (thrashing), когда мы при уменьшении размера (делая pop) массива вдвое урезаем его так же вдвое, а затем добавляем новый элемент и так по кругу — в результате размер массива изменяется при каждой вставке или удалении туда-сюда; уменьшать размер массива вдвое следует лишь когда он заполнен на четверть от своей длины.
Время работы стэка на linked lists всегда константно, на resizable arrays будет асимптотически константно, за исключением O(N) для случаев увеличения/уменьшения массива и переноса оригинальных данных в новый массив.
*Очередь легко реализовать на связанном списке, если мы сохраняем указатели на начало и конец списка. Очередь поддерживает операции unqueue — вставить в начало очереди и dequeue — вынуть из конца очереди. Реализация очереди на массиве не такая простая как реализация стэка на массиве, по причине того, что очередь изменяется с обоих концов.

@qnikst:
qnikst

Чего-то сильно туплю и не могу правильно "задизайнить" алгоритм.

Есть дерево, можно считать, что rose tree, узлы в дереве могут быть протегированы (т.е. ему сопоставляется булевый флаг).
"интересной областью" назовём поддерево между двумя соседними тегированными узлами при проходе сверху-вниз-слева-направо (depth-first в общем-то). Нужно построить список поддеревьев, такой, чтобы в каждом поддереве была только одна "интересная область" + периферия — узлы не входящие ни в одну интересную область. Вот это делается достаточно просто.

Но оказалось, что это не совсем то, что нужно, а на самом деле интересует "интересная область"* — эта область между двумя тегированными узлами находящимися на одной и той же глубине. И вот как эффективно получить такое представление мне не понятно.

Идеи? Картинки могу нарисовать в принципе, но лень.

Принимаются: словесное описание алгоритма, ссылки на конкретные главы конкретной книги, работающий код, петросянство.

@qrilka:
qrilka

допустим есть такая задача: есть множество М каких-то элементов, их можно упорядочить по определённому приоритету. из этого множества надо иметь N подмножеств (по каким-то критериям, отличным от приоритета) и делать pop в этих подмножествах (как обычно выбирать наиболее приоритетный), а после использования делать push того же элемента с обновлённым приоритетом. Вести N очередей и обновлять элемент в каждой, куда он входит, кажется довольно мрачным. Другой вариант — общая очередь и pop с фильтрацией в виде обычного перебора. Может есть какие-то варианты иметь priority queue с поддержкой фильтрации?

@segfault:
segfault

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

@segfault:
segfault

Есть у нас произвольный направленный взвешенный граф. Задача: разложить его оси (на одном измерении, тобиш) так, чтобы сумма квадратов разностей междц весом дуг и их реальными длинами была минимальна
То есть, для простейшего графа из двух вершин имеем:
первая точка — кордината = 0
вторая точка — кордината = x
вес дуги = 1
направление дуги от первой точки ко второй
Тогда:
квадрат разности у нас будет (1 — (x — 0))^2 = (1-x)^2
Тут мы дифференцируем по x и все зашибись, решаем уравненице линейное.
Но когда у нас 3 и более вершины, то все сложнее, там вылезают произведения вида x1*x2 + x2*x3 и так далее

В связи с этим вопрос: есть ли готовые решение по подобному раскладыванию графа, ну не первый же я решаю такое? И второе: если такого нет, то как решать многочлены вида
A*x1^2 + B*x1*x2 + C*x2*x3 + D*x2^2 ..... = 0
?

@segfault:
segfault

Вот смотри, жуик, есть задача генерации файлов определенного формата. Формат я уже разгадал, с этим проблем нет, осталось придумать алгоритм генерации случайных данных.
Данные представляют из себя 4 потока цифр — показания датчиков на некотором участке длины. Нужно сформировать случайные данные "похожие на правду".
Правда заключается в следующем: на всем участке датчики обычно показывают прямую линию, в которую подмешан некоторый шум, но шум не просто белый, а как-бы кгадкий, чем-то похожий на графики цен акций, или типа того, то есть, есть некоторое блуждание. Также, встречаются "деффекты", заключающиеся в резких скачках-впадинах, также обладающих определенным паттерном. Есть еще обрывы, в которых датчик непрерывно показывает 0xFFFF. Все это должно генерироваться случайным образом в большом количестве и быть "похожи на правду". Вобщем, какие есть идеи, может на эту тему есть статейки/паперы, она ведь наверно давно изучена? Прозреваю, что генерация карт и окружений для игор имеет много общего с этим.
Сделать мне это надо за выхи.

@fmap:
fmap

citeseerx.ist.psu.edu

@fmap:
fmap

iti.fh-flensburg.de

@qrilka:
qrilka

вот как раз для собеседования к @dmzhighscalability.com :)

@4DA:
4DA

Прекрасная вводная статья в сложность алгоритмов.
discrete.gr

@4DA:
4DA

Лучшие препринты статей по алгоритмам за 2011 год:

* Решение проблем связности, параметризованных шириной дерева за single EXP time. arxiv.org

* Уникальные оценки выполнимости (SAT) для алгоритма PPSZ действительны в общем случае. arxiv.org

* Константа Гротендика строго меньше оценки Кирвина. arxiv.org

* Субэкспоненциальный параметризированный алгоритм для минимального заполнения. arxiv.org

* Циклы и треугольники с минимальным весом: эквивалентности и алгоритмы. arxiv.org

* О сливающейся персисентость для структур данных. arxiv.org

* Распознавание круговых графов за O(m+n) α(n + m). arxiv.org

* Максимальный поток со множеством стоков и истоков в планарных оргафах за почти-линейное время. arxiv.org

* Вычисление совершенных паросочетаний со скоростью алгоритма Райзера. arxiv.org

* 13/9 аппроксимация для геометрической задачи коммивояжера. arxiv.org

Перевел как сумел, оригинал там -> 11011110.livejournal.com

@4DA:
4DA

А задача с восстановлением дерева из предыдущего поста, тем временем имеет более простое решение.

int post[] = {0, -1, 1, 3, 2, 7, 6, 5, 4};
int pre[]  = {4,  2, 1, 0, -1, 3, 5,  7, 6};
int n;

void ptree2()
{
	int root = pre[indPre];
	printf("%d", root);

	indPre++;

	if (root != post[indPost]) {
		printf (" {");
		ptree2();

		printf(",");

		ptree2();
		printf ("} ");
		
	}

	indPost++;
}

@4DA:
4DA

Хорошая задачка на бинарное дерево, для неолимпиадников всяких.

Дан preorder traversal (корень, левый, правый) и postorder traversal (левый, правый, корень) некоторого бинарного дерева. Надо восстановить структуру дерева.
antilamer.livejournal.com

Решил за O(n^2)
За O(n) переделывать уже лень.
gist.github.com

@4DA:
4DA

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

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

На ум приходит python, C++/QT (с оговорками), Adobe ActionScript, java (с апплетами), JS, Mathematica/matlab/octave, Racket...

Что еще?

Твои варианты.

@folex:
folex

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

Здесь я буду всё это структурировать, что-то будет тут, что-то в /n+1.
Тред скорее всего потом удалю, и создам отдельный структурированный пост, в котором соберу всё, что писал.
Если кто-то что-то сюда будет писать — прочитаю, и если там будет что-то полезное — учту. Конечно же буду благодарен этим самым полезностям.

Итак:

--Some
1) Binary search algolist.net
2) Ternary search e-maxx.ru

--Number theory
1)Binary power e-maxx.ru
2)Euclid GCD e-maxx.ru
3)Euclid-extended GCD e-maxx.ru
4)Discrete logarithm e-maxx.ru
5)Diofant equation e-maxx.ru
6)Eratosphenes sieve e-maxx.ru
7)Euler function e-maxx.ru
8)Element inverse e-maxx.ru
9)Eratosphenes sieve with linear asimptotics e-maxx.ru

--Graphs
1)Graphs data structures en.wikipedia.org
2)DFS e-maxx.ru
3)BFS e-maxx.ru
4)Topological sort e-maxx.ru
5)Connected components searching e-maxx.ru
6)Ford-Bellman's shortest path searching e-maxx.ru
7)Kruskal's minimal spanning tree searching algorithm e-maxx.ru
8)Kruskal with SOME FUCKING MAGIC that gives us O(~5) e-maxx.ru
9)Dijkstra's shortest path searching e-maxx.ru
10)Bipartite checking e-maxx.ru
11)Kun`s maximal matching search e-maxx.ru
12)Strong connected components searching e-maxx.ru

--Graphs TODO:
1)Add some clever graph representation from "Черкасский Б.В. Комбинаторные алгоритмы (№ 644)"

--Stringology
1)KMP prefix function e-maxx.ru
2)Karp`s substring searching e-maxx.ru
3)Some hash functions on strings e-maxx.ru


--Additional
1)Network flows. e-maxx.ru ;; Кто ищет — тот найдет.
2)Graham's convex hull e-maxx.ru


Пока что всё.
Если есть вопрос "А зачем ты сюда тупо переписал e-maxx?", отвечаю:
Дело в том, что некоторые люди не научились ещё сами искать и отсеивать информацию, и поэтому тупо кинуть их на e-maxx нельзя — потеряются.
А тут будет хороший, годный список, никакого выбора: дали — учи.

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

@alsmirn:
alsmirn

Интересный обзор по recommendation engines: horicky.blogspot.com . Рекомендуе. Кстати, никто, случаем не щупал движок SUGGEST (http://glaros.dtc.umn.edu/gkhome/suggest/overview ), как оно?

@roolebo:
roolebo

кстати читаю тут неплохую книжку по прикладному AI в вебе и не только — Programming Collective Intelligence, Toby Segaran @ O'Reilly 2007

@netneladno:
netneladno

как алгоритмически наименее затратно сделать отрицание двух сетов

@alsmirn:
alsmirn

MapReduce для школьников: blog.basho.com ;)

@netneladno:
netneladno

youtube.com

@nirthfurzahad:
nirthfurzahad

Господа математики, у меня вопрос. Я не совсем понимаю, как сформулировать вопрос, так что опишу кратко, и на конкретном примере:
Кратко: Что мне нужно сделать, что бы найти похожие последовательности данных в общей куче и изолировать их?
Пример: Скажем у меня есть пяток экземпляров игры (и пяток тестеров). Они играют против компьютера и данные отсылается на сервер. Сервер хранит целые битвы. Задача – найти в чем то похожие (но маловероятно в чем то идентичные) действия – и абстрагировать их от контекста?

Собственно вопрос от Pseudo-AI разработчика, разработчикам AI настоящих ^_^. Но что то мне подсказывает, что можно справится и чисто математически.

@nirthfurzahad:
nirthfurzahad

Для тех кому интересны темы AI, Data Mining, Telecommunication – очень рекомендую книгу Профессора Yoav Shoham и Kevin Leyton Brown – Multiagent Systems: Algorithmic, Game-Theoretic and Logical Foundations

@zeabrah:
zeabrah

youtube.com

@superbobry:
superbobry

поглощаю тут на досуге пару книжечек по алгоритмам: Introduction to algorithms от товарищей из MIT и A programmer's companion to algorithm analysis и поражаюсь тому как вторая книжка проигрывает по сравнению с первой в __понятности__ для обычных людей. временная и пространственная сложности вводятся постольку поскольку — никакими формальными определениями автор себя не утруждает, как впрочем и простыми примерами по теме. some people just aren't made for teaching. не представляю как по такой книжке можно чему то научиться. будем надеятся что это только поверхностное впечатление, и в процессе погружения оно рассеется. вопрос случайным читателям: с чем еще посоветуете ознакомиться, в качестве introduction?

@alsmirn:
alsmirn

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

@sergray:
sergray

amazing #javascript stackulator.com

@alsmirn:
alsmirn

огромное количество полезных алгоритмов ориентированных на работу с большими массивами данных: massivedatasets.wordpress.com