-
деревья и реляционные базы данных. вложенные множества.
Для работы с древовидными (иерархическими) структурами в первую очередь следует постараться понять какие действия будут осуществляться часто, а какие эпизодически. Цель статьи не описать все возможные способы хранения таких данных, а в сжатом виде виде описать два часто встречающихся подхода и область их наилучшего применения. 1. Узел хранит информацию о родителе. Это классика. CREATE TREE_NODE (ID INT …, PARENT_ID INT, …); Все очень просто — узел хранит идентификатор родительского узла. Самая простая схема. Такую схему удобно использовать когда: Добавление и удаление детей происходит чаще, чем поиск по деревьям. Структура дерева постоянно меняется. Например идет процесс моделирования какой-то древовидной структуры и…
-
Сортировка за O(N)-время
Случайно наткнулся на статью — Fast O(n) Integer Sorting Algorithm. Всегда считал, что O(n*log(n)) это уже очень хороший показатель, а тут ещё быстрее. Например, стандартная реализация сортировки в Java 6 является слегка модифицированным вариантом merge sort, которая дает время n*log(n). Получить ультраускорение сортировки можно только благодаря дополнительным хитростям — использовать знания о самих объектах, которые мы сортируем, и учитывая ограничения на возможные их значения. Другими словами, это не универсальное решение. Оно работает только на определённых типах данных. Если верить википедии Гарольд Сьюард (Harold H. Seward) в 1954 году из MIT изобрел ультра крутой способ сортировки — radix sort (поразрядная сортировка), а также разработал counting…
-
шаблоны проектирования
GoF Шаблоны проектирования При работе с шаблонами мне интересен был в первую очередь практический аспект. Сейчас в 2010 году уже существует достаточно много информации и учебников по шаблонам проектирования как в интернете, так и в печатных изданиях. «Классикой жанра» считается книжка «банды четырех» (англ: «Gang Of Four» или просто GoF) — книга написанная Эрихом Гаммой и соавторами в 1995 году и посвященная шаблонам проектирования. Из книг по шаблоном именно для Java-программистов читал «Применение шаблонов Java». Описание шаблонов, которые я здесь привожу построено на следующем принципе. Название шаблона — ссылка на статью в википдеии. Пример — фрагмент java-кода, где этот шаблон может…
android (11) blog (2) coworking (3) database (5) dce vm (1) design (2) design pattern (2) excel (1) gradle (1) groovy (1) gwt (3) gwt-ext (2) hibernate (2) image (3) Jar (1) Java (79) JavaScript (4) json (1) lambda (1) linux (6) maven (6) multimedia (2) mustache (1) mysql (4) netbeans (10) pdf (1) rdf (2) rmi (1) Scala (17) security (1) svg (1) svn (4) template system (1) Tomcat (4) tv (1) uml (9) web (1) xml (1) архитектор (3) дизайн (1) комикс (1) компьютер (1) места (2) программирование (59) работа (7)