Рубрики
1. Языки программирования 2. Теория программирования

Про JavaScript (не для JavaScript программистов).

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

При кажущейся простоте JavaScript не создан для легкого написания надежного кода. Для самопроверки пользуюсь jsLint-ом и периодически запускаю google closure compiler. Тем не менее, это не решает всех проблем. Даже если вы пишете правильный и аккуратный код, указываете комментарии в исходником коде для проверки типов и т.д., все равно приходится время от времени сталкиваться с работами других программистов.

Из своих "полевых наблюдений" за программистами я понял, что у тех несчастных, которые начинают писать на JavaScript-е после других языков, возникает путанное понимание некоторых фундаментальных понятий этого языка.

Рубрики
2. Теория программирования Scala

Поиск. КМП-алгоритм

Недавно на досуге решил написать алгоритм КМП  (КнутаМорриса — Пратта) для Scala.

Изначально, мне нужно было решить простенькую задачку - найти последовательность байт в потоке байтов. Сделал на Java. Потом, решил сделать тоже самое на Scala. Занятно, но в стандартной библиотеке коллекций Scala используется именно КМП поиск.

Вот мой вариант.

Рубрики
4. Полезняшки Java Шаблоны проектирования

Самый лучший Singleton

Из всех существующих на момент написания этого поста реализаций шаблона Singleton (одиночка) мне больше всего нравится эта:

 public class Singleton {
   // Private constructor prevents instantiation from other classes
   private Singleton() {}
 
   /**
    * SingletonHolder is loaded on the first execution of Singleton.getInstance()
    * or the first access to SingletonHolder.INSTANCE, not before.
    */
   private static class SingletonHolder {
     private static final Singleton INSTANCE = new Singleton();
   }
 
   public static Singleton getInstance() {
     return SingletonHolder.INSTANCE;
   }
 }

Эту реализацию придумал  Bill Pugh. Это гениальный и очень простой способ. При помощи элегантного использования внутреннего класса Вы получаете ленивый (объект Singleton не инициализируется до моменты вызова метод getInstance())  и потоко-безопасный Singleton.

Поскольку в классе Singleton нет статических полей которые нужно инициализировать, класс беспрепятственно загрузится. То есть Вам не нужно ждать, пока мы создадим объект Singleton в самом начале, когда загружаются классы.
Смотрим дальше, когда объект INSTANCE будет создан? Тогда, когда мы вызовем метод getInstance(), что повлечет загрузку внутреннего класса SingletonHolder, что спровоцирует создание объекта INSTANCE. Поскольку фаза инициализации класса гарантировано (спецификацией) "не конкурента", то у нас нет необходимости использовать synchronized и volatile. Ура!

Рубрики
2. Теория программирования UML

Как рисовать UML диаграммы классов.

Диаграмма классов.

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

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

От общего к частному...

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

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

Точно так же я советую поступать в работе с диаграммами классов в UML. Мы создаем эскиз. Выделяем основные классы, определяем отношения между ними, затем прорабатываем мультипликаторы, поля, методы и их область видимости, сигнатуру вызовов, вспомогательные классы и так далее...

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

Например так:

Рубрики
2. Теория программирования 3. Инструментарий

Хранение семантических данных. Связка: Jena / Jenabean + Sparql

1. Jena

В поисках средств для работы с семантическими данными (semantic web) на java можно наткнуться на  следующие решения:

  1. Jena
  2. JRDF
  3. Sesame

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

  • он позволяет работать с RDF, RDFS, OWL,
  • осуществлять запросы через  SPARQL,
  • есть возможность читать и писать из N3 и RDF-XML форматов,
  • работать с базами данными Oracle, MySQL, PostgreSQL, HSQLDB, MS SQL Server и Derby.

Исторически, jena является разработкой выращенной в лаборатории Hewlett-Packard в рамках исследований по семантик вебу. Приблизительно с октября 2009 года HP-шники прекратили активные работы над этим проектом и стали его активно опенсорсить (под BSD-подобной лицензией).  Думаю сейчас  разработчики могут спокойно и бесплатно использовать  его без особых проблем.

Для Jena имеется неплохой набор учебных материалов как на самом сайте, так и на других различных ресурсах (например на ibm-ком developerWorks: Introduction to Jena). Структура базовых классов простая и интуитивно понятная. Для примера, привожу краткий набор некоторых основных сущностей в библиотеке:

  • RDFNode - базовый интерфейс для ресурсов или литералов
  • Resource - RDF-ный ресурс (например <http://somewhere/JohnSmith>)
  • Literal - RDF литерал ("John Smith")
  • Property - свойство или предикат (VCard.FN)
  • Statement - триплет "субъект" - "предикат" - "объект"
  • Model - множество триплетов

Неплохую вводную по работе с Jena, можно прочитать на сайте  www.semantictools.ru. Также этом на сайте находится множество полезной информации для людей увлеченных семантическими технологиями.

2. Jenabean

Для связки между JavaBean и RDF хранилищем можно использовать библиотеку jenabean . Способ привязки базируется на аннотациях и чем-то напоминает работу с JPA -- аннотациями даются указания каким образом связываются поля класса и данные в хранилище.

Примеры, документацию и саму библиотеку можно скачать на официальной странице  проекта - http://code.google.com/p/jenabean

Также там имеется замечательный скринкаст, в котором показано по шагам (с нуля) работа под NetBeans'e с этой библиотекой. Так что здесь какие-либо мои пояснения по установке и работе библиотеки уже не нужны, достаточно просмотреть видео на сайте.

Далее хотелось уделить особое внимание работе  Jenabean и SPARQL.

SPARQL - язык запроса для выгребания данных из RDF.  С его помощью можно осуществлять довольно хитрые выборки.

Для работы через SPARQL в jenabean можно использовать класс Sparql, который может получать данные из Jena-вской модели (Model - множество триплетов) .

Важно! В jenabean-овском  SPARQL-запросе обязательно должна быть переменная ?s, которая ссылается на требуемый вами объект. Зачем они решили сделать такую жесткую завязку  на ?s мне не понятно, может в следующих версиях придумают что-нибудь покрасивее.

В качестве примере, можно рассмотреть кусок кода -- получение списка из 10 (LIMIT 10) статей в порядке их публикации (ORDER BY ?d)  начиная с 20-ой (OFFSET 20) .

String query = "SELECT ?s ?d WHERE " +
"{ ?s a <http: //programador.ru/Article> . ?s </http:><http: //programador.ru/postDate> ?d } " +
"ORDER BY ?d LIMIT 10 OFFSET 20";
LinkedList<article> list = Sparql.exec(model, Article.class, query);
</article></http:>
Рубрики
2. Теория программирования

деревья и реляционные базы данных. вложенные множества.

Для работы с древовидными (иерархическими) структурами в первую очередь следует постараться понять какие действия будут осуществляться часто, а какие эпизодически.

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

1.  Узел хранит информацию о родителе. Это  классика.

CREATE TREE_NODE (ID INT ..., PARENT_ID INT, ...);

Все очень просто -  узел хранит идентификатор родительского узла. Самая простая схема.

Такую схему удобно использовать когда:

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

Другой вариант использования, когда в основном  требуются выборки на уровне одного поколения - получить список  "детей" у данного узла или получить информацию о родителе. Например, если мы используем асинхронное получение узлов в дереве.  Тогда дерево отображается не сразу, а после нажатия пользователем на соответствующий узел, после которого идет обращение к веб-серверу на получение данных. Например, как это выглядит в  Ext GWT (GXT).

Кстати, в некоторых базах данных существует уже готовые механизмы для работы с деревьями. В частности в ORACLE это CONNECT BY.

2. Вложенные множества.  Узел хранит в себе информацию о своем расположение в дереве.

CREATE TREE_NODE (ID INT ...,  LEFT INT...,  RIGHT INT...) ;

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

и следующего SQL запроса (получение всей ветки для C.1):

SELECT id FROM tree WHERE left <= 5  AND right => 6 ORDER BY left; -- в итоге получим узлы A, B.2, C.1
Рубрики
2. Теория программирования Java

Сортировка за O(N)-время

Случайно наткнулся на статью на java.dzone.com - 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 sort (сортировка подсчетом).
При такой сортировки мы не используем Comparator, т.е. сравнение и перестановка элементов как в обычной сортировки не происходит. С другой стороны, такой метод требует дополнительной памяти и
особо эффективен в тех случаях, когда мы сортируем большое количество натуральных чисел ограниченных по возможным принимаемым значениям. Например: массив из 1000000 целых чисел, которые принимают значения от 0 до 1000.

Рубрики
2. Теория программирования Шаблоны проектирования

шаблоны проектирования

GoF Шаблоны проектирования

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

Приемы объектно-ориентированного проектирования. Паттерны проектирования Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес

"Классикой жанра" считается книжка "банды четырех" (англ: "Gang Of Four" или просто GoF) - книга написанная Эрихом Гаммой и соавторами в 1995 году и посвященная шаблонам проектирования.

Стивен Стелтинг, Олав Маассен. Применение шаблонов Java. Библиотека профессионала

Из книг по шаблоном именно для Java-программистов читал "Применение шаблонов Java".

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

Название шаблона - ссылка на статью в википдеии. Пример - фрагмент java-кода, где  этот шаблон может встречаться в стандартном Java API или в каком-то "бытовом" случае.

Для шаблонов, примеры которых я не смог найти место в стандартной реализации, приводиться просто его краткое описание. Другими словами там, где можно обойтись от использования "оригнальных" и "понятных" примеров ООП - CarFactory, Car, Ford или Fruit, Apple или Person, Student, Prepod и так далее, я старался использовать привычные для программиста StringBuilderMouseAdapter, Reader. Т.е. классы, объекты которых мы используем каждый день.

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

Creational/Порождающий

AbstractFactory

// Создает DOM Document Builder в зависимости от используемого парсера
DocumentBuilderFactory documentBuilderFactory = ...;
documentBuilderFactory.newDocumentBuilder();
Рубрики
2. Теория программирования

Нефункциональные требования к проектируемому ПО.

Краткий справочник по  Non-functional Requirement.

Перед разработкой архитектуры системы или на ранней стадии ее проектирования,
всегда следует уделять внимание так называемым нефункциональным показателям (Non-functional QoS). Они определяют характеристики, которые не связаны с конкретным поведением системы, но при этом задают требования с точки зрения бизнеса.
Как и для любых показателей, которые определяются на этапе проектирования, кроме  желаемых характеристик, следует также, в первую очередь, выявить их минимально допустимые значения. Например, если система будет доступна в рабочем состоянии меньше 100 часов в неделю (Availability = 100/168 ~ 59.52%), то такая система для бизнеса будет не интересна (убыточна, не приносить никакой пользы). Зачем это нужно?
Дело в том, что далеко не все базы данных, сервера приложений или технологические платформы могут обеспечить необходимые показатели доступности (availability), масштабируемости, надежности и т.д.. Выбор тех или иных решений должен зависеть от этих характеристик.

Краткий список нефункциональных показатели системы (Non-functional QoS):
Scalabitlity - Масштабируемость. Возможность увеличивать производительность системы пропорционально выделенным ресурсам. Бывает горизонтальная и вертикальная. Вертикальная - докупаем более быструю память, более шустрый жесткий диск или переносим всё на один еще более мощный сервер. Горизонтальная - покупаем еще один сервер и запускаем приложения  в кластерном режиме, в случае необходимости - докупаем еще один сервер и втыкаем к двум уже работающим и так далее.
Extensibility - Расширяемость. Возможность добавление дополнительного функционала.
Flexibility - Гибкость. Возможность менять существующую архитектуру (например в зависимости от ценовой политики). В отличие от Extensibility, речь идет только об изменениях без дополнительного функционала. Например у заказчика нет денег на нормальную СУБД (допустим ORACLE). Наша задача сделать систему настолько гибкой, чтобы в случае необходимости мы смогли её подпилить так, чтобы она смогла  бы обойтись чем-нибудь бесплатным (MySQL или PostgreSQL).
Насколько должна уметь прогибаться система, желательно, по мере возможности, определить по-раньше...
Maintainablity - Поддерживаемость, ремонтопригодность. Способность поддерживать систему в работоспособном состоянии. Показатель определяет насколько легко (или сложно) вносить исправления в работающую систему, возможно ли повторное развертывание и запуск системы после сбоя, возможность восстановить из резервных хранилищ и т.д.
Availability - коэффициент доступности(готовности). Процент времени проведенного  системой в работоспособном состоянии к общему времени работы системы.

часто высоко доступные (High Availability) системы меряются девятками:

  • 99,9 % (три девятки) = система недоступна не более 8,76 часов/год
  • 99,99 %  (четыре девятки)= не более 52,6 минуты/год
  • 99,999 % (пять девяток) = не более 5,26 минуты/год

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