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.
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 если переданное значение меньше, равно или больше значению текущего объекта.
Время работы стэка на linked lists всегда константно, на resizable arrays будет асимптотически константно, за исключением O(N) для случаев увеличения/уменьшения массива и переноса оригинальных данных в новый массив.
*Очередь легко реализовать на связанном списке, если мы сохраняем указатели на начало и конец списка. Очередь поддерживает операции unqueue — вставить в начало очереди и dequeue — вынуть из конца очереди. Реализация очереди на массиве не такая простая как реализация стэка на массиве, по причине того, что очередь изменяется с обоих концов.
Есть дерево, можно считать, что rose tree, узлы в дереве могут быть протегированы (т.е. ему сопоставляется булевый флаг).
"интересной областью" назовём поддерево между двумя соседними тегированными узлами при проходе сверху-вниз-слева-направо (depth-first в общем-то). Нужно построить список поддеревьев, такой, чтобы в каждом поддереве была только одна "интересная область" + периферия — узлы не входящие ни в одну интересную область. Вот это делается достаточно просто.
Но оказалось, что это не совсем то, что нужно, а на самом деле интересует "интересная область"* — эта область между двумя тегированными узлами находящимися на одной и той же глубине. И вот как эффективно получить такое представление мне не понятно.
Идеи? Картинки могу нарисовать в принципе, но лень.
Принимаются: словесное описание алгоритма, ссылки на конкретные главы конкретной книги, работающий код, петросянство.
Мог бы просто копить сумму замеров и их количество, а в конце тупо посчитать среднее (с помощью технологии вещественного деления) но боюсь, что аккумулятор переполниться может, вернее в конце он начнет принимать большие значения и нормально прибавлять к нему замеры уже не получится (без большой потери точности).
Как такое большие дядьки делают?
То есть, для простейшего графа из двух вершин имеем:
первая точка — кордината = 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
?
Данные представляют из себя 4 потока цифр — показания датчиков на некотором участке длины. Нужно сформировать случайные данные "похожие на правду".
Правда заключается в следующем: на всем участке датчики обычно показывают прямую линию, в которую подмешан некоторый шум, но шум не просто белый, а как-бы кгадкий, чем-то похожий на графики цен акций, или типа того, то есть, есть некоторое блуждание. Также, встречаются "деффекты", заключающиеся в резких скачках-впадинах, также обладающих определенным паттерном. Есть еще обрывы, в которых датчик непрерывно показывает 0xFFFF. Все это должно генерироваться случайным образом в большом количестве и быть "похожи на правду". Вобщем, какие есть идеи, может на эту тему есть статейки/паперы, она ведь наверно давно изучена? Прозреваю, что генерация карт и окружений для игор имеет много общего с этим.
Сделать мне это надо за выхи.
@dmz — highscalability.com :)
вот как раз для собеседования к * Решение проблем связности, параметризованных шириной дерева за 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
А задача с восстановлением дерева из предыдущего поста, тем временем имеет более простое решение. 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++; }
Дан preorder traversal (корень, левый, правый) и postorder traversal (левый, правый, корень) некоторого бинарного дерева. Надо восстановить структуру дерева.
antilamer.livejournal.com
Решил за O(n^2)
За O(n) переделывать уже лень.
gist.github.com
То есть, язык, с одной стороны должен обладать набором фич, позволяющем максимально отвлечься от специфики языка, а с другой стороны, должен иметь легкодоступный GUI (кроссплатформенный).
На ум приходит python, C++/QT (с оговорками), Adobe ActionScript, java (с апплетами), JS, Mathematica/matlab/octave, Racket...
Что еще?
Твои варианты.
//Андрей, это то, что рассказывал мне Константин.
Здесь я буду всё это структурировать, что-то будет тут, что-то в /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(data_structure)#Representations
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 нельзя — потеряются.
А тут будет хороший, годный список, никакого выбора: дали — учи.
Надеюсь, всем понятно, какие именно алгоритмы нужно советовать, если уж хочется.
Заранее спасибо за советы.
horicky.blogspot.com . Рекомендуе. Кстати, никто, случаем не щупал движок SUGGEST (http://glaros.dtc.umn.edu/gkhome/suggest/overview ), как оно?
Интересный обзор по recommendation engines: Кратко: Что мне нужно сделать, что бы найти похожие последовательности данных в общей куче и изолировать их?
Пример: Скажем у меня есть пяток экземпляров игры (и пяток тестеров). Они играют против компьютера и данные отсылается на сервер. Сервер хранит целые битвы. Задача – найти в чем то похожие (но маловероятно в чем то идентичные) действия – и абстрагировать их от контекста?
Собственно вопрос от Pseudo-AI разработчика, разработчикам AI настоящих ^_^. Но что то мне подсказывает, что можно справится и чисто математически.