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

@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

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

@pimiento2:
pimiento2

*abstact_classes
Конструкторы при наследовании класса вызываются следующим образом:
1. Если в начале конструктора подкласса нет вызова super() или this(), то будет вызван дефолтный конструктор родительского класса (если нет дефолтного, то будет ошибка (?)).
2. Если происходит вызов super(...) (обязательно в начале конструктора), то будет вызван определённый родительский конструктор.
3. Если происходит вызов this(...) (обязательно в начале конструктора), то будет вызван другой конструктор этого класса, в котором будет либо явно либо неявно вызван родительский конструктор.

Абстрактные классы это классы, объявленные с сигнатурой abstract. Эти классы не могут быть инстацированны, а все их подклассы обязаны реализовать указанные методы или сами быть abstract (если реализуют не все методы).

@pimiento2:
pimiento2

— переопределение метода родительского класса в подклассе. Overriding не предполагает изменение количества и тип аргументов. Для принудительного указания компилятору, что здесь происходит overriding а не overloading, — используется аннотация @Override перед определением метода. Переопределённые методы (overrided) не имеют такого же поведения как shadowed аттрибуты: если мы присвоим объект подкласса переменной родительского класса, то мы будем иметь доступ к методу подкласса, а не родительского класса. Если использовать сигнатуру final для метода, то такой метод не может быть переопределён в подклассах. Методы подкласса обязаны кидать те же эксепшены или подклассы этих эксепшенов, так же и указывать о возможных возвращаемых эксепшенах (... throws Exception): того же класса или подклассы. Переопределённые методы обязаны возвращать значение того же класса, что и родительский метод или подкласса.

@pimiento2:
pimiento2

Существует возможность "скрыть" унаследованную переменную новой переменной в дочернем классе. Например, в классе A есть переменная int x, мы наследуем класс B от класса A и определяем в B переменную double x. Все методы, наследованные от A будут иметь дело с int x, а сама переменная int x никуда не исчезнет, а будет доступна через super.x, например. Так же, если присвоить значение объекта класса B переменной типа A:
B b = new B();
A a = b;
то при обращении к переменной объекта x, получим int x объекта класса A. "Shadowing" очень плохая затея, лучше этим не пользоваться, а использовать абстрактные классы.

@pimiento2:
pimiento2

По мотивам чтения книги JavaScript Enlightment. Конструктор объекта есть функция, которая оперирует внутри атрибутом this не как this своего скоупа, а как this скоупа нового экземпляра. Таким образом, вызывая функцию с new мы получаем в результате новый объект. Есть встроенные (built-in) глобальные конструкторы String(), Number(), Boolean(), Object(), Array(), Function(). Math не является конструктором, а является глобальным объектом Math, поэтом недопустимо делать math = new Math();

@pimiento2:
pimiento2

По мотивам прочтения chimera.labs.oreilly.com и javapractices.com

В Java присутствует тип Enum, который наследуется от java.lang.Enum. Этот тип позволяет хранить глобальные переменные без указания их значения (впрочем, можно задавать значения, используя синтаксис типа enum E { A(1), B(14), C(46) }). Могут быть объявлены вне класса или внутри. Вне класса не могут иметь никаких квалификаторов, типа static, final и т.п. Новый объект enum-а создаётся при обращении к объявленной переменной класса. Не поддерживает публичный конструктор new. Можно создать внутри enum-а метод-конструктор, можно даже сделать его публичным, но смысла это иметь не будет, так как не поддерживается вызов new. Можно внутри методов enum-а обращаться к текущему значению через this: enum Q {A, B; public boolean isA() { return this == A; }}.

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

@pimiento2:
pimiento2

По мотивам статьи pymotw.com
В Python есть модуль weakref, который позволяет использовать слабые ссылки, аналогичные WeakReference в Java.
Нет "soft" или "phantom" ссылок. wr = weakref.ref(obj) создаёт слабую ссылку на obj, значение obj можно получать через вызов этой ссылки: wr().value # -> obj.value Если использовать метод proxy вместо метода ref, то получим прокси-объект слабую ссылку: wr = weakref.proxy(obj); wr.value # obj.value. В случае если исходный объект был уже удалён, то ref_ref() вернёт None, а proxy_ref() возбудит ReferenceError. Существуют несколько структур данных поверх weakref. Дикт с weakref реализован поверх обычно дикта, поэтому вполне может произойти изменение его размеров во время итерации по нему по причине срабатывания GC.

@pimiento2:
pimiento2

По мотивам статьи weblogs.java.net
"strong reference" — обычная ссылка на объект, создаваемая конструктором объекта. "weak reference" — ссылка на объект, наличие которой не защищает объект от сборки его GC. То есть, если кроме слабы ссылок на объект не осталось больше "strong" ссылок — объект будет собран GC. Используется для создания WeakHashMap, например. Позволяет не задумываться о том, что кроме удаления оригинальной ссылки на объект, надо удалять и все его использования в структуре данных хэш. "weak" ссылка возвращает по методу .get() сам объект или null если объект уже был удалён GC. "soft reference" — аналогично "weak" ссылке, но объект реально будет удалён только когда на него не осталось "strong" ссылок и при этом память подходит к концу. "phantom reference" — всегда возвращает null из метода .get(). Нужна для выяснения когда объект был реально удалён из памяти. "weak" и "soft" ссылки могут возродить объект в методе finalize, "phantom" ссылка так не может, потому что не имеет никаких реальных ссылок на объект. ReferenceQueee будет записывать слабые ссылки при удалении реального объекта, при этом "soft" и "weak" ссылки будут добавлены в очередь при выполнении метода finalize и при этом могут возродить объект, а "phantom" ссылка будет добавлена в очередь только при реальном удалении объекта из памяти.

@pimiento2:
pimiento2

Метод finalize вызывается перед тем как объект попадёт под колёса GC. Не определено время вызова finalize, он просто может быть однажды вызван перед сборкой объекта. В Java есть reference-объекты, они живут в java.lang.ref. Существуют WeakReference и SoftRefernce. Вторый будут собраны GC только при нехватке памяти.

@pimiento2:
pimiento2

"Пакеты знаний" — набор связанных фактов, который мы заучили как истинну. Рефликсия (фантазии, обдумывание) над пакетами знаний ведёт к построению карт, построение карт к пониманию, понимание к разумным действиям.

@pimiento2:
pimiento2

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

@pimiento2:
pimiento2

По прочтении статьи sites.google.com

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

@pimiento2:
pimiento2

По прочтении статьи lucumr.pocoo.org выяснил, что импорт модуля вызывает код в модуле только один раз, затем этот инициализированный объект модуля помещается в sys.modules и берётся оттуда при каждом новом импорте такого модуля. Это создаёт проблему с реимпортом и так же с импортом нескольких одинаковых модулей разных версий.