Общее·количество·просмотров·страницы

Java Dev Notes - разработка на Java (а также на JavaScript/Python/Flex и др), факты, события из АйТи

четверг, 21 октября 2010 г.

Коэффициент корреляции Пирсона (Pearson)

При рассмотрении одной задачки пришлось вспомнить статистику, а именно - что такое коэффициент корреляции Пирсона (Pearsons's correlation coefficient). Пользовался при этом двумя ссылками: Wikipedia: (Pearson product-moment correlation coefficient) и MachineLearning.ru: Коэффициент корреляции Пирсона.

Итак, коэффициент корреляции Пирсона - мера корреляции (линейной зависимости) между двумя выборками X и Y, принимающая значения от +1 до −1 включительно. Другими словами, коэффициент корреляции Пирсона характеризует существование линейной зависимости между двумя величинами. Равенство коэффициента "+1" указывает на строгую прямую линейную зависимость, "-1" - на обратную. Если коэффициент равен нулю, то выборки линейно независимы.

Пусть даны две выборки:

Коэффициент корреляции Пирсона рассчитывается по формуле:

где - это средние значения выборок X и Y.

Слабые стороны этой метрики:

  • неустойчивость к выбросам

  • С помощью коэффициента корреляции можно определить линейную зависимость между величинами, другие взаимосвязи выявляются методами регрессионного анализа

  • Необходимо понимать различие понятий "независимость" и "некоррелированность". Из первого следует второе, но не наоборот


Ниже показаны примеры выборок и значения коэффициента Пирсона для каждой и зних. Картинка взята из Википедии:

Интерпретация величины коэффициента некоторыми исследователями:




КорреляцияОтрицательноеПоложительное
Отсутствуетот -0.09 до 0.0от 0.00 до 0.09
Малаяот -0.3 до -0.1от 0.1 до 0.3
Средняяот -0.5 до -0.3от 0.3 до 0.5
Большаяот -1.0 до -0.5от 0.5 до 1.0

среда, 20 октября 2010 г.

Паттерн Строитель (Builder)

Строитель (Builder) - порождающий шаблон проектирования, который выделяет процесс создания сложного объекта так, чтобы различные реализации строителя могли бы создавать различные реализации объекта. UML диаграмма паттерна Строитель представлена ниже (взято из Wikipedia):



Объекты на диаграмме:

  • Builder - абстрактный строитель, определяющий интерфейс

  • Concrete Builder - предоставляет конкретную реализацию строителя. Конкретный строитель создает и собирает части объекта в единое целое.

  • Director - класс Директора отвечает за задание корректной последовательности конструирования объекта. Класс получает Конкретного Строителя, как параметр, и выполняет необходимые операции с ним.

  • Product - конечный продукт. Создается Директором с помощью Коннкретного Строителя


Мотивы применения паттерна:

  • алгоритм создания сложного объекта не должен зависеть от того, из каких частей состоит объект и как они стыкуются между собой

  • процесс конструирования должен обеспечивать различные представления конструируемого объекта


Плюсы применения паттерна Строитель:

  • изолирует код, реализующий конструирование и представление

  • предоставляет полный контроль над процессом создания объекта

  • позволяет независимо изменять ход процесса создания объекта



Пусть имеется код создания некоторого объекта. Со временем, объект меняется, добавляются новые вариации объекта, появляются новые методы. Без данного паттерна пришлось бы переписывать код создания объекта и его последующего использования столько раз, сколько произошло изменений и во всех местах, где этот объект создается. При использовании паттерна Строитель код и порядок создания объекта инкапсулирован в класс Конкретного Строителя. При изменении процесса создания изменить код придется только в одном месте - в этом Конкретном Строителе. При добавлении новой вариации объекта придется лишь добавить еще одного Конкретного Строителя.

Для чего нужен Директор? Опишем это на примере. Пусть подрядчик (Строитель) строит дом. Подрядчик знает, как нужно делать фундамент, возводить стены, делать стропила и класть крышу. Директор (распорядитель) говорит подрядчику, в какой последовательности это делать: сначала нужно заложить фундамент, затем стены, а после этого сделать крышу. В коде это будет выглядеть так:

public class HouseBuilder {
protected House house;
 
public House getHouse() {
return house;
}
 
public void createHouse() {
house = new House();
}
 
public abstract void buildFoundation();
public abstract void buildWalls();
public abstract void buildRoof();
}
 
public class Director {
public House constructHouse(HouseBuilder builder) {
builder.createHouse();
builder.buildFoundation();
builder.buildWalls();
builder.buildRoof();
return builder.getHouse();
}
}


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

public class HouseBuilder {
protected House house;
 
public House getHouse() {
return house;
}
 
public void createHouse() {
house = new House();
buildFoundation();
buildWalls();
buildRoof();
}
 
protected abstract void buildFoundation();
protected abstract void buildWalls();
protected abstract void buildRoof();
}
 
public class Director {
public House constructHouse(HouseBuilder builder) {
builder.createHouse();
return builder.getHouse();
}
}


В заключении можно добавить, что Строитель часто используется вместе с паттерном Компоновщик (Composite).

суббота, 16 октября 2010 г.

Создание поискового плагина для Mozilla FireFox - на примере CrunchBase

Так как часто смотрю проекты на сайте CrunchBase, то мне удобно вводить свой запрос в поисковый плагин для FireFox. Я хотел было установить себе поисковый плагин для CrunchBase, но с удивлением обнаружил, что такого плагина нет.

Что ж, раз его нет, то что мешает написать его самим? Тем более, что "написание поискового плагина" - это всего лишь создание XML-файла из нескольких строчек.

Итак, создаем файл crunchbase.xml со следующим содержанием:
<SearchPlugin xmlns="http://www.mozilla.org/2006/browser/search/" xmlns:os="http://a9.com/-/spec/opensearch/1.1/">
<os:ShortName>CrunchBase</os:ShortName>
<os:Description>CrunchBase - free directory of technology companies, people, and investors.</os:Description>
<os:InputEncoding>UTF-8</os:InputEncoding>
<os:Url type="text/html" method="GET" template="http://crunchbase.com/search">
<os:Param name="query" value="{searchTerms}"/>
</os:Url>
</SearchPlugin>

Помещаем этот файл в каталог с остальными поисковыми плагинами. У меня на Ubuntu этот каталог находится по следующему пути: ~/.mozilla/firefox/ph10gejb.default/searchplugins, после чего перезапускаем FireFox. Вуаля - в списке поисковых систем появилась еще одна строчка с CrunchBase.

Эти ссылки могут быть полезны по теме "Разработка поискового плагина":
Build Your Own Firefox Search Engine
Learn to make a FireFox Search Plugin, and how to install it! Detailed Tutorial! - Publishing - Pixel2Life

понедельник, 11 октября 2010 г.

Паттерн Одиночка (Singleton)

Шаблон (паттерн) проектирования "Одиночка" реализует математическую концепцию синглетона. В математике, синглетон - множество с одним элементом. Например, {10} - это синглетон, т.е. множество, состоящее из одного элемента - числа 10.

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

Рассмотрим варианты реализации одиночки на Java. При этом будем обращать внимание на многопоточность и связанные с ней возможные проблемы. Изложенное ниже следует статье в англоязычной Википедии Singleton pattern. Также использовались некоторые другие источники.

Самая простая реализация:
public class Singleton {
 
private static final Singleton INSTANCE = new Singleton();
 
// Private constructor prevents instantiation from other classes
private Singleton() {
}
 
public static Singleton getInstance() {
return INSTANCE;
}
}

Эта реализация потокобезопасна. Объект INSTANCE создается тогда, когда класс инициализируется. Например, это может произойти, когда будет вызван какой-нибудь статический метод класса. Конструктор объявляется private, доступ к экземпляру класса возможен только через getInstance(). Такая реализация, однако, может не подойти, если создание экземпляра класса требует много ресурсов. В этом случае нужно подумать об отложенной инициализации синглетона.

Вариант Уильяма Пу (William Pugh)
Это вариант отложенной инициализации (или еще говорят: ленивой инициализации)
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 {
public static final Singleton INSTANCE = new Singleton();
}
 
public static Singleton getInstance() {
return SingletonHolder.INSTANCE;
}
 
}

Эта реализация "ленива" настолько, насколько это возможно. Здесь используется идиома Initialization on demand holder idiom - т.е. отложенная инициализация с использованием объекта-холдера.

Несмотря на отсутствие synchronized в коде, эта реализация потокобезопасна. Такая реализация Одиночки работает на всех версиях Java. Здесь используются та часть спецификации Java (см. 8.3.1.1 static Fields и 12.4.2 Detailed Initialization Procedure), в которой описывается порядок инициализации класса. При инициализации класса Java-машина сама заботится о синхронизации, т.к. нет нужды подставлять использовать synchronized.

Т.к. на внутренний класс SingletonHolder нет ссылок нигде, кроме метода getInstance, то и инциализирован он будет не ранее, чем метод getInstance будет вызван. При такой инициализации Java-машина сама позаботится о синхронизации. Так что этот вариант - пример отличной потокобезопасной реализации паттерна Одиночка.

Реализация с double-checked locking (DCL)
Рассмотрим еще одну реализацию. Эта реализация использует двойную проверку блокировки. Она будет корректно работать в многопоточной среде только начиная с версии Java 5, т.к. в Java 5 была изменена модель памяти. Ранее существовавшая модель памяти не позволяла корректно выполняться такой реализации в многопоточной среде. Вот код:
public class Singleton {
 
// volatile is needed so that multiple thread can reconcile the instance
// semantics for volatile changed in Java 5.
private volatile static Singleton singleton;
 
private Singleton() {
 
}
 
// synchronized keyword has been removed from here
public static Singleton getSingleton() {
// needed because once there is singleton available no need to acquire
// monitor again & again as it is costly
if(singleton==null) {
synchronized(Singleton.class){
// this is needed if two threads are waiting at the monitor at the
// time when singleton was getting instantiated
if(singleton == null) {
singleton = new Singleton();
}
}
}
return singleton;
}
}

Однако, лучше не использовать double-checked locking. Это старый прием, который был вызван особенностями ранних JVM. Теперь его иногда даже рассматривают как анти-паттерн.

Подводя итоги, можно рекомендовать релализацию синглетона с помощью с использованием объекта-холдера.

Разница в synchronized(this) и synchronized(SomeClass.class)

Рассмотрим, в чем разница между
synchronized(this) {
//some stuff
}
и
synchronized(SomeClass.class) {
//some stuff
}

В Java каждый объект имеет ассоциированный с ним монитор (или lock - объект блокировки). Когда мы пишем такой код:
synchronized(this) {
//some stuff
}

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

Когда мы пишем такой код:
synchronized(SomeClass.class) {
//some stuff
}
мы получаем блокировку, ассоциированную с объектом SomeClass.class. Такую блокировку имеет смысл использовать, если мы изменяем данные (переменные) уровня класса, т.е. статические переменные.

суббота, 2 октября 2010 г.

Чтение всего файла в массив байтов

Нужно прочитать файл целиком в массив байтов. Например, для текстовых файлов такое нужно, чтобы затем из байтов сделать строку с нужной кодировкой: public String(byte[] bytes, String encoding).

Далее, код функции, которая позволяет считать файл целиком в массив байтов (взято отсюда: Reading a File into a Byte Array):

public static byte[] getBytesFromFile(File file) throws IOException {
InputStream is = new FileInputStream(file);
long length = file.length();
if (length > Integer.MAX_VALUE) {
return null;
}
 
byte[] bytes = new byte[(int)length];
 
// Read in the bytes
int offset = 0;
int numRead = 0;
while (offset < bytes.length && (numRead=is.read(bytes, offset, bytes.length-offset)) >= 0) {
offset += numRead;
}
 
// Ensure all the bytes have been read in
if (offset < bytes.length) {
throw new IOException("Could not completely read file "+file.getName());
}
 
// Close the input stream and return bytes
is.close();
return bytes;
}

пятница, 1 октября 2010 г.

Задачка: наибольшая возрастающая непрерывная подпоследовательность (longest increasing contiguous subsequence)

Требуется в заданной последовательности найти наибольшую возрастающую непрерывную подпоследовательность. Например, дана последовательность {1,2,3,-1,2,3,4,5}. В этой последовательности наибольшая возрастающая непрерывная подпоследовательность начинается с позиции 4 и имеет длину 4, т.е. это подпоследовательность {-1,2,3,4,5}.

Запишем всю последовательность в массив. Будем последовательно проходить массив. Если элемент массива больше предыдущего, то увеличим счетчик длины последовательности на 1. Если элемент массива меньше или равен предыдущему, то поставим счетчик длины в 1 (т.к. последовательность), и метку начала подпоследовательности поставим равной текущему индексу. При этом проверим, если длина только что окончившейся подпоследовательности больше предыдущей максимальной, то максимальную длину меняем.

Входные данные передаются так: на первой строчке файла стоит кол-во чисел в последовательности. На всех остальных строчках в начале стоит следующее число в последовательности. Пример входного файла:

8
1
2
3
-1
2
3
4
5

Код:

import java.io.*;
public class Problem1 {
 
static int[] a;
static int startIndex;
static int maxLength;
 
static void findMaxIncrSubseq() {
if (a.length==1) {
startIndex = 0;
maxLength = 1;
return;
}
int start = startIndex = 0;
int length = maxLength = 1;
for (int i=1; i<a.length; i++) {
if (a[i] > a[i-1]) {
length++;
} else {
if (length > maxLength) {
maxLength = length;
startIndex = start;
}
length = 1;
start = i;
}
}
}
 
public static void main(String[] args) throws Exception {
FileInputStream fstream = new FileInputStream("in.txt");
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String strLine;
strLine = br.readLine();
int size = Integer.parseInt(strLine);
a = new int[size];
int i=0;
while ((strLine = br.readLine()) != null) {
a[i] = Integer.parseInt(strLine);
i++;
}
in.close();
findMaxIncrSubseq();
System.out.println("Longest increasing contiguos subsequence starts from " + startIndex + " and is of length " + maxLength);
System.out.println("Longest increasing contiguos subsequence:");
for (i=startIndex; i<startIndex+maxLength; i++) {
System.out.println(a[i]);
}
}
}


Пример файла in.txt:

12
1
2
3
-10
5
6
7
8
9
0
1
2


Пример вывода:

>java Problem1
Longest increasing contiguos subsequence starts from 3 and is of length 6
Longest increasing contiguos subsequence:
-10
5
6
7
8
9

Постоянные читатели