Скрипт для подсчета числа файлов java, xml и др.

Нужно было посчитать статистику по файлам java и др. Вот что получилось:

import os
 
startPath = os.getcwd()
 
java = 0
xmlxsd = 0
 
def findFiles(path):
    global java
    global xmlxsd
    files = os.listdir(path)
    for f in files:
        p = os.path.join(path, f)
        if os.path.isdir(p):
            findFiles(p)
        else:
            fn, fe = os.path.splitext(p)
            print fe
            if fe == '.java':
                java = java+1
            elif fe in ['.xsd', '.xml', '.html', '.xhtml']:
                xmlxsd = xmlxsd + 1 
 
def main():
    findFiles(startPath)
    print 'java = %d ' % java
    print 'xmlxsd = %d' % xmlxsd
 
 
if __name__ == "__main__":
    main()   

Кодировки в MySQL

Хорошо объясняется, как выставлять кодировки в MySQL: MySQL + кодировки В результате, я сделал так: открываем файл my.cnf (/etc/mysql/my.cnf) и добавляем:

[client]
default-character-set=utf8

[mysqld]
default-character-set=utf8

That's all!

MapReduce и MongoDB

Для обработки данных в коллекциях в MongoDB есть замечательный инструмент - map-reduce. Посмотрим, как он работает.

Я это делал на реальном примере по одному проекту - нужно обработать данные по пользовательским покупкам, которые хранятся в монге. Нас интересует два поля: ID пользователя и сумма покупки. В качестве ID пользователя выступает GUID.

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

Если бы мы были в SQL, то табличка с данными о покупках была бы следующие:

CREATE TABLE sales(
  guid varchar(32) NOT NULL PRIMARY KEY,
  price float NOT NULL
);

Запрос, который выводит данный отчет, был бы следующий:

SELECT guid, sum(price) AS summa FROM sales 
GROUP BY guid
ORDER BY summa DESC;

В монге данные хранятся в коллекции stat, вид данных следующий:

> db.stat.findOne();
{ 
  "_id" : ObjectId("4e4c73eb41e5c790a7391848"), 
  "guid" : "346fbb3968c9453d9dc8f8ebe0fa6763", 
  "item" : "Apple MacBook Air MC968LL/A 11.6-Inch", 
  "price" : 78.64, 
  "retailerId" : "COST", 
  "ip" : "0:0:0:0:0:0:0:1", 
  "datetime" : "2011-07-28 10:12:38", 
  "timezone" : "-1", 
  "createDate" : "Thu Aug 18 2011 06:07:39 GMT+0400 (MSK)", 
}

Что ж, приступим в мап-редьюсу...

function salesMap() {
    emit(this.guid, {price: this.price });
}
 
function salesReduce(key, values) {
    var result = { 
        count: 0,
        summa: 0.0
    };
    values.forEach(function(v){
        if (v.price) {
            result.summa += v.price;
            result.count++;
        }
    });
    return result;
}
db.userrep.drop();
db.stat.mapReduce(salesMap,salesReduce,{out:'userrep', verbose: true});
db.userrep.find();

Функция emit(key, value), которую мы использовали в функции salesMap, подает на вход редьюсу пару ключ - значение. Ключом мы выбрали GUID, т.к. по нему идет группировка, а в значение кладем цену товара. Функция salesReduce получает на вход набор объектов, сгруппированных по ключу.

Внутри функции все тривиально:
1) создаем объект с результатами, пока что содержащий нулевые значения var result = { count: 0, summa: 0.0 };
2) пробегаемся по коллекции и заполняем результат
3) возвращаем результат.
4) PROFIT!!!
Вид результатов следующий:

> db.userrep.find().limit(5)
{ "_id" : "01dc299862094450ac232d384d883a5f", "value" : { "count" : 2, "summa" : 245.19 } }
{ "_id" : "0a1afef3b8b27942d9a8d02903ca2c28", "value" : { "count" : 1, "summa" : 30.43 } }
{ "_id" : "0c9d6a05458313b85706548c290991e9", "value" : { "count" : 0, "summa" : 0 } }
{ "_id" : "0f4e595202884408ae4c4c6306d764f9", "value" : { "count" : 1, "summa" : 88.43 } }
{ "_id" : "17a57229a9c14b2cb46337a3d196051c", "value" : { "count" : 1, "summa" : 49.54 } }

Какая жалость - данные не отсортированы.

Монго не умеет сортировать коллекцию данным из составных объектов, т.е. мы не можем написать что-то вроде:

db.userrep.find().sort({value.summa: -1});

Поэтому придется немножко извратиться:

db.userrep.find().forEach(function(v) {
    var s = v.value.summa;
    var c = v.value.count;
    var id = v._id;
    db.userrep.update({_id: id},{$set:{summa:s, count: c}}, true, true);
});

Мы просто скопировали поля summa, count из объекта value в объект-контейнер коллекции. Теперь данные выглядят так:

> db.userrep.find().limit(5);
{ "_id" : "01dc299862094450ac232d384d883a5f", "count" : 2, "summa" : 245.19, "value" : { "count" : 2, "summa" : 245.19 } }
{ "_id" : "0a1afef3b8b27942d9a8d02903ca2c28", "count" : 1, "summa" : 30.43, "value" : { "count" : 1, "summa" : 30.43 } }
{ "_id" : "0c9d6a05458313b85706548c290991e9", "count" : 0, "summa" : 0, "value" : { "count" : 0, "summa" : 0 } }
{ "_id" : "0f4e595202884408ae4c4c6306d764f9", "count" : 1, "summa" : 88.43, "value" : { "count" : 1, "summa" : 88.43 } }
{ "_id" : "17a57229a9c14b2cb46337a3d196051c", "count" : 1, "summa" : 49.54, "value" : { "count" : 1, "summa" : 49.54 } }

Теперь, наконец, можно получить отсортированные данные:

> db.userrep.find().sort({summa:-1}).limit(5);
{ "_id" : "cb1332aed05d48fd9c51d0c5be584156", "count" : 4, "summa" : 496.72999999999996, "value" : { "count" : 4, "summa" : 496.72999999999996 } }
{ "_id" : "ade1efffe9d3fb116f33c320bf9b447e", "count" : 3, "summa" : 412.45000000000005, "value" : { "count" : 3, "summa" : 412.45000000000005 } }
{ "_id" : "ef98c2c430c4486394bc2b85ec5b1a77", "count" : 3, "summa" : 408.5, "value" : { "count" : 3, "summa" : 408.5 } }
{ "_id" : "5295f9b927c59dacdd3fb20d8173a19b", "count" : 4, "summa" : 367.08, "value" : { "count" : 4, "summa" : 367.08 } }
{ "_id" : "01dc299862094450ac232d384d883a5f", "count" : 2, "summa" : 245.19, "value" : { "count" : 2, "summa" : 245.19 } }

Установка MongoDB на RHEL

Довелось мне недавно устанавливать MongoDB на RHEL и настраивать репликацию (Replica sets). Про репликацию я напишу в другом посте, а вот про установку - здесь. Машина - 64х битный linux Amazon Image for EC2. Итак, по шагам: 1) Добавляем репозиторий

     sudo touch /etc/yum.repos.d/10gen.repo
    

и в файл добавляем следующее:

     [10gen]
     name=10gen Repository
     baseurl=http://downloads-distro.mongodb.org/repo/redhat/os/x86_64
     gpgcheck=0
     

2) Устанавливаем

    sudo yum install mongo-10gen mongo-10gen-server
    

3) Редактируем конфиг:

    sudo vi /etc/mongod.conf
    

Например, можем отредактировать порт, расположение логов и файлов с данными:

    logpath=/var/log/mongo/mongod.log
    port=27017
    dbpath=/var/lib/mongo
    

4) Запускаем!

    sudo /etc/init.d/mongod start
    

java.text.SimpleDateFormat и потоки

Использование класса java.text.SimpleDateFormat, не является потокобезопасным.

Например, вот такой код:

import java.text.*;



class MiscUtils {

  public final static DateFormat fmt = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");



  public static String formatDate(Date date) {

    return fmt.format(date);

  }

}



//

// usage: 

//

  void anyMethod() {

    Date date = getDate();

    String s = MiscUtils.formatDate(date);

    // now we have formatted date here!

  }

может вызвать проблемы, если метод MiscUtils.formatDate будет одновременно вызван из нескольких потоков.

Вот выдержка со страницы Java Docs SimpleDateFormat:

Date formats are not synchronized. It is recommended to create separate format instances for each thread. If multiple threads access a format concurrently, it must be synchronized externally. 

Решение 1.
Всякий раз, когда нужно отформатировать (или пропарсить) дату, создавать новый экземпляр java.text.SimpleDateFormat

Решение 2.
Создать свою, потокобезопасную реализацию форматтера с блэкджеком и шлюхами с синхронизацией:

public class ThreadSafeSimpleDateFormat {



 private DateFormat df;



 public ThreadSafeSimpleDateFormat(String format) {

     this.df = new SimpleDateFormat(format);

 }



 public synchronized String format(Date date) {

     return df.format(date);

 }



 public synchronized Date parse(String string) throws ParseException {

     return df.parse(string);

 }

}

Решение 3.
Заюзать какую-нибудь стороннюю бибилиотечку наподобие JodaTime или класс FastDateFormat из Apache Commons.

Эффективное копирование файлов в NIO

Эффективное копирование файлов в NIO:

 // Getting file channels

 FileChannel in = new FileInputStream(source).getChannel();

 FileChannel out = new FileOutputStream(target).getChannel();

 

 // JavaVM does its best to do this as native I/O operations.

 in.transferTo (0, in.size(), out);

 

 // Closing file channels will close corresponding stream objects as well.

 out.close();

 in.close();

Установка Postgres-9.0 на Ubuntu 10.10

Сделаем установку Postgres-9.0 на Ubuntu 10.10.

1) В репах по-умолчанию нет пакета Postgres-9.0, поэтому добавим репозиторий, откуда будем качать пакеты:

deb http://ppa.launchpad.net/pitti/postgresql/ubuntu maverick main
deb-src http://ppa.launchpad.net/pitti/postgresql/ubuntu maverick main

добавляем в файл /etc/apt/sources.list. В итоге должны получить что-то вроде

$ cat /etc/apt/sources.list
deb http://ru.archive.ubuntu.com/ubuntu/ maverick main restricted
deb http://ru.archive.ubuntu.com/ubuntu/ maverick multiverse
deb http://archive.canonical.com/ubuntu maverick partner
deb http://archive.canonical.com/ maverick partner
deb http://ru.archive.ubuntu.com/ubuntu/ maverick-updates restricted main multiverse universe
deb http://security.ubuntu.com/ubuntu/ maverick-security restricted main multiverse universe
deb http://extras.ubuntu.com/ubuntu maverick main #Third party developers repository
# for postgres 9.0
deb http://ppa.launchpad.net/pitti/postgresql/ubuntu maverick main
deb-src http://ppa.launchpad.net/pitti/postgresql/ubuntu maverick main

:~$


2) Идем сюда: https://launchpad.net/~pitti/+archive/postgresql, смотрим значение ключа (сейчас это 8683D8A2) и добавляем ключ:

sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 8683D8A2

3) Апдейтим репы:
sudo apt-get update

4) Останавливаем сервис Postgres 8:
~$ sudo service postgresql-8.4 stop

5) Пуржим пакеты:
sudo apt-get purge postgresql*

6) Устанавливаем postgres 9.0
sudo apt-get install postgresql-9.0

7) Заходим в psql:
sudo -u postgres psql

Ссылки:
Install PostgreSQL 9 on Ubuntu Linux
Postgres 9.x installation in Ubuntu
Установка Postgresql 9, pgAdmin III в Ubuntu 10.04
Installing PostgreSQL 9.0 on Ubuntu 10.04

Как узнать, какую версию Ubuntu вы используете

user1:~$ cat /etc/issue
Ubuntu 10.10 \n \l

user1:~$


или через GUI: System -> Administration -> System Monitor

или:


user1:~$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 10.10
Release: 10.10
Codename: maverick

Установка пароля админа в Glassfish 3

Как установить админский пароль в Glassgish v3:

1. Запустить Glassfish - GF_HOME/glassfish/bin/startserv


2. Вызвать скрипт asadmn: GF_HOME/bin/asadmin change-admin-password

~/dev/glassfishv3/bin$ ./asadmin change-admin-password
Enter admin user name [default: admin]> admin
Enter admin password>
Enter new admin password>
Enter new admin password again>

Command change-admin-password executed successfully.
~/dev/glassfishv3/bin$

Определение страны пользователя в Google App Engine

Теперь в заголовке X-AppEngine-country пользовательского запроса передается двухбуквенный код страны.

HashMap, LinkedHashMap и TreeMap в Java

Вкратце, чем различаются между собой HashMap, LinkedHashMap и TreeMap из пакета java.util?

Все три класса имплементируют интерфейс java.util.Map. Но в каждой реализации есть всякие "плюшечки":

• HashMap - не дает никаких гарантий по поводу порядка итерации по элементам. Скорость доступа: O(1).


• LinkedHashMap - итерация по элементам в том же порядке, в котором они были вставлены в коллекцию, т.е. в insertion order. Скорость доступа: O(1).


• TreeMap - держит коллекцию отсортированной по ключам (используется либо метод compareTo() либо предоставленный компаратор), поэтому итерация по элементам будет в порядке сортировки по ключам - natural ordering. Скорость доступа: O(log(n)).

Небольшой скрипт на python для удаления .svn директорий

Скрипт, который рекурсивно удаляет каталоги .svn из дерева директорий:

import os
import shutil
 
startPath = 'C:\\usr\\dbTracer\\fennel-webapp-OBO\\FENNEL_OBO'
 
def findDeleteSvn(path):
    files = os.listdir(path)
    for f in files:
        p = os.path.join(path, f)
        if os.path.isdir(p):
            print p
            if f == '.svn':
                shutil.rmtree(p, True)
            else:
                findDeleteSvn(p)
 
def main():
    findDeleteSvn(startPath)
 
if __name__ == "__main__":
    main()        

Builder и natures проекта в Eclipse

Каждый проект в Eclipse имеет ассоциированные с ним билдеры (builders) и natures. Что это такое?

Builder - внутри Eclipse билдеры используются чтобы взять некий вход и сгенерировать по нему некий выход (output). Билдеры могут быть инкрементальными - это положительно влияет на производительность, т.к. такой билдер перестраивает только ту часть проекта, которая изменилась с последнего билда.

Nature - используется, чтобы ассоциировать проект с каким-либо плагином, или другим функционалом, например, билдером.

Файл проекта .project c билдерами и natures может выглядеть так:

<?xml version="1.0" encoding="UTF-8"?>
<projectDescription>
    <name>super-project</name>
    <comment></comment>
    <projects>
    </projects>
    <buildSpec>
        <buildCommand>
            <name>org.eclipse.jdt.core.javabuilder</name>
            <arguments>
            </arguments>
        </buildCommand>
    </buildSpec>
    <natures>
        <nature>org.eclipse.jdt.core.javanature</nature>
        <nature>org.maven.ide.eclipse.maven2Nature</nature>
    </natures>
</projectDescription>
 

Устройство java.util.HashMap. Часть 4.

Рассмотрим, как объекты кладутся в хеш-таблицу и получаются из нее. Для начала рассмотрим функцию хеширования:

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Эта функция применяется к хеш-кодам ключей - она защищает от плохого хеширования.

Теперь рассмотрим функцию, которая получает индекс в массиве бакетов:

static int indexFor(int h, int length) {
    return h & (length-1);
}

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

Теперь рассмотрим функцию получения объекта по ключу:

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

Здесь все просто: для получения значения по null-ключу мы используем специальный метод: getForNullKey. Затем получаем индекс в массиве бакетов и проходимся по списку Entry в данной ячейке списка.

Рассмотрим метод getForNullKey:

private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) return e.value;
    }
    return null;
}

Как видно из кода, мы просто проходимся по списку Entry в первой ячейке массива бакетов, до тех пор, пока не встретили Entry с нулевым ключом.

Теперь рассмотрим метод для записи объекта в хеш-таблицу:

public V put(K key, V value) {
    if (key == null) return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
 
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

Здесь для добавления объекта в null-ключом вызывается специальный метод - putForNullKey. Далее, просматривается список в массиве бакетов по данному хешу. Если в этом списке нет такого ключа, то для добавления объекта в этот список вызывается метод addEntry, заодно увеличивается счетчик modCount - который подсчитывает количество структурных модификаций.

Рассмотрим метод addEntry:

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

Этот метод добавляет новый объект в начало списка, и также увеличивает размер массива бакетов, если достигнуто пороговое значение.

Мы рассмотрели основные аспекты java.util.HashMap - все остальное можно легко посмотреть по исходникам.

Устройство java.util.HashMap. Часть 1.
Устройство java.util.HashMap. Часть 2.
Устройство java.util.HashMap. Часть 4.

Устройство java.util.HashMap. Часть 3.

Здесь мы рассмотрим варианты создания хеш-таблицы: ее конструкторы, включая и неявные конструкторы (т.е. clone).

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
 
    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
 
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
    table = new Entry[capacity];
    init();
}

Здесь все довольно просто. Сначала мы проверяем аргументы на валидность в этом блоке кода:

if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);

Затем находим ближайшую ступень двойки и записываем ее в capacity. Устанавливаем loadFactor и threshold = (int)(capacity * loadFactor), а также массив бакетов:
table = new Entry[capacity];
Затем вызываем метод init(), который является хуком для классов, наследующих от HashMap. В данной реализации это просто пустой метод.

Теперь рассмотрим конструктор без аргументов:

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
}

Здесь все то же самое, за исключением проверки аргументов. Это и логично, т.к. аргументов в конструкторе нет. Они могли бы вызвать конструктор с аргументами вот так:

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

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

Теперь рассмотрим конструктор, который создает хеш-таюлицу по другой хеш-таблице:

public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAllForCreate(m);
}

Здесь также все просто - выбираются значения initialCapacity и loadFactor, после этого все элементы копируются из одной таблицы в другую, используя метод putAllForCreate. Этот же метод используется в методе clone.

А вот и метод clone:

public Object clone() {
    HashMap<K,V> result = null;
    try {
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        // assert false;
    }
    result.table = new Entry[table.length];
    result.entrySet = null;
    result.modCount = 0;
    result.size = 0;
    result.init();
    result.putAllForCreate(this);
 
    return result;
}

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

Устройство java.util.HashMap. Часть 1.
Устройство java.util.HashMap. Часть 2.
Устройство java.util.HashMap. Часть 4.

Устройство java.util.HashMap. Часть 2.

Здесь мы рассмотрим поля класса java.util.HashMap.

Итак:

static final int DEFAULT_INITIAL_CAPACITY = 16;
Начальная емкость хеш-таблицы

static final int MAXIMUM_CAPACITY = 1 << 30;
Максимальная емкость хеш-таблицы - составляет 2^29

static final float DEFAULT_LOAD_FACTOR = 0.75f;
Фактор загрузки по умолчанию

transient Entry[] table;
Массив бакетов. Его длина всегда должна быть степенью двойки. Этот массив автоматически увеличивается вдвое, если фактор загрузки превышен.

transient int size;
Количество мэппингов, которые содержатся в данной хеш-таблице.

int threshold;
Пороговое значение, следующее значение размера количества мэппингов, по достижении которого размер хеш-таблицы (а точнее, размер массива бакетов) будет увеличен. Рассчитывается как (емкость * фактор_загрузки).

final float loadFactor;
Значение фактора загрузки для данной хеш-таблицы.

transient volatile int modCount;
Количество структурных модификаций, которые произошли над данной хеш-таблицей. Это поле используется итераторами, чтобы отследить, когда нужно будет выкинуть ConcurrentModificationException.

private transient Set<Map.Entry<K,V>> entrySet = null;
Представление хеш-таблицы в виде множества Entry.

Как видим, полей не очень много.

Устройство java.util.HashMap. Часть 1.
Устройство java.util.HashMap. Часть 3.
Устройство java.util.HashMap. Часть 4.

Устройство java.util.HashMap. Часть 1.

Одним из важнейших классом в Java Collections Framework является java.util.HashMap. Этой структура данных и ее реализация заслуживает отдельного разговора. В данном посте я хочу разобрать назначение HashMap и некоторые его особенности без погружения в исходный код. В основном, это будет перевод javadocs к классу java.util.HashMap.

java.util.HashMap - это реализация интерфейса java.util.Map на основе хеш-таюлицы. Эта реализация поддерживает также null-значения в качестве значений, а также и в качестве ключей. Не дается никаких гарантий по поводу внутреннего порядка данных. Особенно, не гарантируется, что порядок членов коллекции будет все время один и тот же.

Данная реализация обеспечивает постоянное время выполнения для базовых операций - get и put, т.е. время порядка O(1). При этом делается предположение, что хеш-функция равномерно распределяет элементы по бакетам (buckets). Бакет - элемент хеш-таблицы, который содержит список данных, положенных в хеш-таблицу. Остаток от деления хеш-кода каждого из этих данных на размер хеш-таблицы (точнее, на количество бакетов) один и тот же.

Итерация по хеш-таблице пропорционально количеству бакетов + их размер. Поэтому, если важна производительность итерации, важно не делать количество бакетов (т.е. емкость хеш-таблицы) очень большим.

Каждый экземпляр класса java.util.HashMap имеет два параметра для настройки производительности - начальная емкость (initial capacity) и фактор загрузки (load factor). Емкость хеш-таблицы - это количество бакетов в ней, а начальная емкость - это то количество бакетов, с которым хеш-таблица создается. Фактор загрузки определяет, насколько должна быть заполнена хеш-таблица перед тем, как автоматически увеличить ее емкость.

По умолчанию, начальная емкость равна 16, а фактор загрузки = 0.75. Начальная емкость должна быть всегда степенью двойки. Если в конструктор передается начальная емкость, которая не является степенью двойки, то устанавливается не эта неправильная емкость, а ближайшая степень двойки, которая больше этого числа. Это все легко посмотреть по исходникам. Степень двойки для емкости хеш-таблица позволяет некоторые оптимизации, которые положительно влияют на производительность хеш-таблицы.

Когда фактор загрузки превышен, то хеш-таблица автоматически увеличивает свою емкость вдвое.

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

Если нет внешнего объекта, по которому синхронизируется такое совместное использование хеш-таблицы, то следует "обернуть" ее следующим методом:

Map m = Collections.synchronizedMap(new HashMap(...));

Итераторы, которые возвращаются в таком случае, имеют поведение fail-fast: если хеш-таблица структурно модифицируется иным образом, кроме как через методы remove или add этого итератора, то итератор выкидывает ConcurrentModificationException.

Устройство java.util.HashMap. Часть 2.
Устройство java.util.HashMap. Часть 3.
Устройство java.util.HashMap. Часть 4.

Ай да Рид, ай да сукин сын!!!

Отличная статья про IPO LinkedIn. См: http://dennydov.blogspot.com/2011/05/blog-post_20.html

Вышел ExtJS 4.0.1

Выпущен ExtJS 4.0.1 - Ext JS 4.0.1 Released: Improved Performance and Bug Fixes.

Это первый патч-релиз к ExtJS 4.0.0. Исправлены многочисленные ошибки, а также улучшена производительность. Улучшена производительность грида, а также и других компонентов (например, лэйаутов форм).

Ed Spencer также написал в посте, что релиз ExtJS 4.0.2 можно ожидать через одну-две недели. И это гут.

Баг-репорт ExtJS 4.0.0

Сегодня утром отправил баг-репорт на форум Sencha. См. Null error (Null Pointer Exception) in Ext.data.Connection.

Ошибка заключается в следующем: иногда xhr.getAllResponseHeaders() возвращает null. А возвращаемое значение не проверяется и используется сразу.

Вот сниппет из класса Ext.data.Connection:

/**
 * Create the response object
 * @private
 * @param {Object} request
 */
createResponse : function(request) {
    var xhr = request.xhr,
        headers = {},
        lines = xhr.getAllResponseHeaders().replace(/\r\n/g, '\n').split('\n'),
        count = lines.length,
        line, index, key, value, response;
 
    // other code goes here....
}

Несложно догадаться, что строка

lines = xhr.getAllResponseHeaders().replace(/\r\n/g, '\n').split('\n'),
 

приведет к ошибки, если xhr.getAllResponseHeaders() возвратит null. Что и происходит в данном случае.

Фикс этого безобразия следующий:

lines = xhr.getAllResponseHeaders() ? xhr.getAllResponseHeaders().replace(/\r\n/g, '\n').split('\n') : '',

Ключевое слово volatile

Ключевое слово volatile применяется к полям класса и в общем означает, что данное поле будет использоваться (модифицироваться) несколькими потоками.

Применение этого модификатора к полю класса означает:

• Значение этого поля никогда не будет кэшироваться потоками в свою локальную область памяти. Все чтения и записи будут идти напрямую в "главную" память, т.е. ту, в которой и размещено поле класса
• Доступ к переменной действует как будто бы она была заключена в блок synchronized, который синхронизируется по самому полю

Поясним первый пункт. Java позволяет потокам, которые имеют доступ к зашаренным переменным сохранять локальные копии этих переменных в своей области памяти для более эффективной работы. Точнее, это позволяет сделать саму реализацию многопоточности более эффективной. Эти "рабочии копии" должны быть синхронизированы с мастер-копией только лишь в заранее определенных точках, которые обусловлены синхронизацией - а именно, когда объект лочится (locks) и разлочивается (unlocks). Как правило, чтобы убедиться, что разделяемая переменная целостно и надежно (reliably) обновляется, поток должен быть уверенным, что он имеет эксклюзивный доступ к такой переменной. Это делается получением лока на переменную, который и обеспечивает взаимное исключение для доступа к этой переменной.

Для пояснения второго пункта приведем табличку для сравнения volatile и synchronized. Не зря во втором пункте использовано слово "как будто": Доступ к переменной действует как будто бы она была заключена в блок synchronized. Т.к. явно в коде монитор, по которому синхронизируется доступ к переменной, не используется....

Итак, табличка:

Свойство	synchronized	volatile
Тип переменной	Только объект	Объект или примитив
Разрешен ли null	нет	да
Может ли быть блокировка	да	нет
Когда происходит синхронизация	Когда явно происходит вход в блок synchronized	Каждый раз при доступе к переменной

Дополнительно см: The volatile keyword in Java

Ключевое слово transient

В Java есть ключевое слово transient. Оно применяется к полям класса и означает, что данное поле не входит в персистентное состояние класса. Т.е. при сериализации данное поле не будет записываться. И, соответственно, при де-сериализации оно не будет восстанавливаться из потока байтов.

Применение:
private transient <member-variable>;
или
transient private <member-variable>;

Пример кода:

public class Foo {
   private String saveMe;
   private transient String dontSaveMe;
   private transient String password;
   //...
}

Снятие наличных с карты Payoneer

Есть такая контора - Payoneer, которая выпускает предоплаченные дебетовые карты, которые используются всякими фрилансерскими сайтами для перечисления заработанных средств. Я пользуюсь карточкой Payoneer, и вот настало время, когда мне понадобилось снять некоторую сумму с этой карты. Карта номинирована в USD, и снимать я также хотел не рубли, а доллары.

В Питере (особенно, в центре) есть много мультивалютных банкоматов, которые позволяют снять не только рубли, но и доллары. Сначала я попробовал СитиБанк (угол Литейного и Невского проспекта - Невский, 45) - за одну транзакцию банк позволяет снять не более 500 долларов. Отмечу, что суточный лимит на карте - всего лишь тысяча долларов. Окей, значит мне пришлось два раза совать карту в банкомат, чтобы снять штуку. СитиБанк с каждой транзакции снял по 11.15 USD, т.е. на 1000 долларов расходы составили 22.30 - что составляет 2.2 %. В общем неплохо, но я также решил попробовать и другие банки.

В следующий раз я пошел в банк Barclays, Невский, 3 (второй дом по Невскому проспекту от Дворцовой площади). Там максимум за транзакцию - 800 долларов. Ладно, снял я 800 долларов и стал ждать отчета от Payoneer о комиссии банка. Отчет меня не обрадовал - свех 800 баксов Барклайс еще снял 32.84 USD как комиссию. Напомню, что Сити с 1000 долларов снял 22.15.

Пока что наш выбор - Сити =)

Кто-нибудь знает еще другие банкоматы в Питере с низкой комиссией?

Отпишитесь в комментах, плиз!

Регулярное выражение для проверки списка регионов

По работе возникла необходимость написать регулярное выражение для проверки списка регионов. Регион - это последовательность из трех прописных букв английского алфавита. Т.е.

[A-Z]

Пример названий регионов: NYC, TOK, LON, SYN и т.д.

Поле ввода регионов должно содержать один или более регион, отделенный друг от друга запятыми без пробелов. Пример корректного ввода:

• NYC


• NYC,TOK,LON,SYN

Требуется написать регулярное выражение для проверки ввода. Это регулярное выражение будет следующим:

^([A-Z]{3},)*([A-Z]{3}$)

Наш ввод можно разделить на две группы. Одна группа - это когда в поле ввода всего лишь один регион. Пример такого ввода: NYC. Регулярное выражение для проверки следующее:

^[A-Z]{3}$

Вторая группа: список регионов, разделенный запятыми. Пример ввода: NYC,TOK,LON,SYN. Составим регулярку для проверки такого ввода.

Такую строку (NYC,TOK,LON,SYN) можно представить следующим образом: сначала идет 1 или больше регионов, после которых ставится запятая. Последний регион прибавляется в конце. После него не ставится запятая. Например, для строки NYC,TOK,LON,SYN это выглядит следующим образом: сначала идут три региона, после которых ставится запятая: NYC,TOK,LON,. Затем добавляется регион, после которого запятая не стоит: SYN.

Для такой строки NYC,TOK,LON,SYN регулярное выражение будет следующим:

([A-Z]{3},)+

Для строки SYN регулярка такова:

[A-Z]{3}

Теперь совместим эти две регулярки, и получим:

^([A-Z]{3},)+([A-Z]{3}$)

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

*

, который значит 0 или более вхождений паттерна. Ставим * вместо +, и получаем:

^([A-Z]{3},)*([A-Z]{3}$)

что нас вполне устраивает. Ну и, разумеется, добавляем символы начала и конца строки.

Загрузка исходного кода приложения Google App Engine

Допустим, у вас на GAE развернуто приложение. И вы хотите скачать его исходный код. Делается это следующей командой:

appcfg.py download_app -A <application-id> -V <application-version> <output-dir>

Например:

appcfg.py download_app -A mysuperapp -V 1 demos/mysuperapp

См. также: Загрузка данных из Google App Engine Datastore

Также см. источник: Downloading Source Code

Регулярное выражение для проверки времени

Задача: написать регулярное выражение для проверки введенного времени в формате hh:mm (24-часовой формат!). Регулярное выражение следующее:

^(([0,1][0-9])|(2[0-3])):[0-5][0-9]$

Теперь давайте разберем его "по косточкам".

Итак, время в 24-часовом формате может принимать, например, следующие значения: 06:00, 11:15, 23:59 и т.д. Первые две цифры (hh) обозначают часы с ведущим нулем (т.е. пишем 06, а не 6). Значение часов может быть от 0 (т.е. 00) до 23. Поэтому мы пишем следующее выражение:

[0,1][0-9]

- что означает, что первый символ может быть 0 или 1, а следующий символ может принимать значение от 0 до 9 (т.е. любая цифра). т.е. любые значения от 00 до 19 подходят под эту регулярку.

Теперь рассмотрим значения часов от 20 до 23. Если первый символ - двойка, то следующий символ может быть цифрой от 0 до 3. Это нас приводит к выражению

2[0-3]

- под него подходят числа 20, 21, 22, 23. Объединяя эти два выражения (с помощью логического "ИЛИ" - |)для часов, получаем первую часть нашей регулярки (для проверки только часов):

([0,1][0-9])|(2[0-3])

Идем дальше: теперь нужно поставить двоеточие и проверять минуты. Первую часть регулярки (проверка часов) заключим в круглые скобки и после них поставим двоеточие:

(([0,1][0-9])|(2[0-3])):(здесь_будет_проверка_минут)

С минутами все просто - минуты принимают значение от 0 (т.е. 00) до 59. Мы это опишем следующей регуляркой:

[0-5][0-9]

Смысл регулярки таков: первый символ принимает значения от 0 до 5, а второй символ - от 0 до 9 (т.е. любая цифра).

Надо отметить, что конечная версия регулярки выглядит так:

^(([0,1][0-9])|(2[0-3])):[0-5][0-9]$

, т.е. имеются символы начала и конца строки (^ и $, соответственно), которые мы еще не разобрали. Рассмотрим их.

Если бы не было символа начала строки, т.е. регулярное выражение выглядело бы следующим образом:

(([0,1][0-9])|(2[0-3])):[0-5][0-9]

, то тогда проходили бы валидацию следующие строки: abc23:50, здесь был Вася в 16:40 и т.п. Символ начала строки позволяет указать, что сравнение с образцом должно начинаться с начала строки.

Аналогично с символом конца строки: $. Если бы его не было, т.е. регулярное выражение выглядело бы следующим образом

^(([0,1][0-9])|(2[0-3])):[0-5][0-9]

то тогда валидацию бы проходили следующие строки: 12:15 - время обеда, 13:10 eeeee и так далее. Использование символа конца строки позволяет эти строки отсечь.

Регулярные выражения - очень мощный инструмент, которым нужно уметь пользоваться.

См. библиотеку регулярных выражений: http://www.regxlib.com/DisplayPatterns.aspx

См. также онлайн-тестер регулярных выражений: http://regexpr.ru/

К сожалению, долго не писал в блог

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

Из новостей: по работе я теперь занимаюсь GWT + server-side Java (активно юзается Spring Framework). Работаю в команде, у которой есть чему поучиться, что большой плюс =)
Также активно юзал MongoDB, python и т. п. В общем, рассказать есть что.

Графы. Класс ориентированного графа.

Рассмотрим Java-класс, который представляет ориентированный граф. Также как и посте Графы. Простой класс графа (неориентированного), класс имеет такие же особенности:

• Внутреннее представление графа - список смежности


• Вершины однозначно идентифицируются строковыми идентификаторами (именами). Не допускается двух вершин с одинаковым именем


• Список смежных вершин держится отсортированным, так чтобы можно было быстро найти вершину в списке по имени (для поиска в отсортированном списке используется двоичный поиск)


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

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

import java.util.Map;
import java.util.List;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;
 
public class DirectedGraph {
 
    private HashMap<String, List<String>> vertexMap = new HashMap<String, List<String>>();
 
    public void addVertex(String vertexName) {
        if (!hasVertex(vertexName)) {
            vertexMap.put(vertexName, new ArrayList<String>());
        }
    }
 
    public boolean hasVertex(String vertexName) {
        return vertexMap.containsKey(vertexName);
    }
 
    public boolean hasEdge(String vertexName1, String vertexName2) {
        if (!hasVertex(vertexName1)) return false;
        List<String> edges = vertexMap.get(vertexName1);
        return Collections.binarySearch(edges, vertexName2) != -1;
    }
 
    public void addEdge(String vertexName1, String vertexName2) {
        if (!hasVertex(vertexName1)) addVertex(vertexName1);
        if (!hasVertex(vertexName2)) addVertex(vertexName2);
        List<String> edges1 = vertexMap.get(vertexName1);
        edges1.add(vertexName2);
        Collections.sort(edges1);
    }
 
    public Map<String, List<String>> getVertexMap() {
        return vertexMap;
    }
}

Графы. Поиск в глубину (depth-first search, DFS)

Рассмотрим алгоритм поиска в глубину в графе (depth-first search). Поиск в глубину - один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в следующих задачах:

• алгоритмы поиска одно- и двусвязных компонент


• топологическая сортировка


• поиск путей в графе


• поиск лексикографически первого пути в графе


• проверка графа на ацикличность и нахождение цикла


• поиск мостов (мостом называется такое ребро, удаление которого делает граф несвязным)

Рассмотрим следующий граф:


Для него нужно выполнить следующее:
1) сделать поиск в глубину. На каждом шаге из нескольких доступных вершин выбирать лексикографически первую вершину.
2) проставить для каждой вершины время входа и время выхода из нее
3) распечатать вершины в порядке входа (т.е. отсортировать по возрастанию времени входа), указав для каждой вершины время входа и выхода

Сначал создадим этот граф:

graph = new UndirectedGraph();
graph.addEdge("A", "B");
graph.addEdge("A", "E");
graph.addEdge("B", "C");
graph.addEdge("B", "E");
graph.addEdge("C", "F");
graph.addEdge("E", "F");
graph.addEdge("F", "I");
 
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("G", "H");

Затем, поскольку нужно выбирать лексикографически первую вершину, возьмем список вершин и отсортируем их по имени по возрастанию. В результате, список vertexList будет содержать имена всех вершин графа, отсортированные лексикографически:

Map<String, List<String>> vm = graph.getVertexMap();
List<String> vertexList = new ArrayList<String>(vm.size());
vertexList.addAll(vm.keySet());
Collections.sort(vertexList); 
 

Теперь пришло время выполнить поиск в глубину:

for (String v : vertexList) {
    dfs(v);
}

Наконец, выполняем последний пункт задания - распечатываем вершины в порядке входа:

for (Map.Entry<String, Mark> entry : visitedMap.entrySet()) {
    Mark m = entry.getValue();
    System.out.format("%1$s : (%2$d, %3$d)\n", entry.getKey(), m.pre, m.post);
}

Здесь мы используем вспомогательный класс Mark, который содержит время входа и выхода:

static class Mark {
    public Mark(int pre, int post) {
        this.pre  = pre;
        this.post = post;
    }
    public int pre;
    public int post;
};

Хеш-таблица visitedMap содержит посещенные вершины графа и соотвествующее время входа/выхода. В качестве реализации visitedMap мы выбрали java.util.LinkedHashMap. Эта реализация позволяет перебрать все добавленные в хеш-таблицу элементы в том порядке, в котором они были добавлены (а не в произвольном порядке, как обычная java.util.HashMap). Это как раз и дает нам возможность распечатать вершины графа в порядке входа.

Теперь рассмотрим сам алгоритм поиска в глубину:

static void dfs(String vertexName) {
    if (visitedMap.containsKey(vertexName)) return;
 
    // set pre (time of enter)
    visitedMap.put(vertexName, new Mark(counter,-1));
    counter++;
 
    // retrieve adjacent vertices
    Map<String, List<String>> vm = graph.getVertexMap();
    List<String> adjacentVertices = vm.get(vertexName);
 
    for (String v : adjacentVertices) {
        if (visitedMap.containsKey(v)) continue;
        dfs(v);
    }
 
    // set post (time of exit)
    Mark m = visitedMap.get(vertexName);
    m.post = counter++;
}

Мне кажется, что код и комментарии в нем говорят сами за себя :-)

Наконец, приведем полный исходный код решения задачи (Problem1.java):

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.List;
import java.util.Map;
 
public class Problem1 {
 
    static class Mark {
        public Mark(int pre, int post) {
            this.pre  = pre;
            this.post = post;
        }
        public int pre;
        public int post;
    };
 
    // our graph
    static UndirectedGraph graph;
    // map of visited vertices
    static Map<String, Mark> visitedMap = new LinkedHashMap<String, Mark>();
    // time counter
    static int counter = 1;
 
    public static void main(String[] args) {
 
        graph = new UndirectedGraph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "E");
        graph.addEdge("B", "C");
        graph.addEdge("B", "E");
        graph.addEdge("C", "F");
        graph.addEdge("E", "F");
        graph.addEdge("F", "I");
 
        graph.addEdge("D", "G");
        graph.addEdge("D", "H");
        graph.addEdge("G", "H");
 
        Map<String, List<String>> vm = graph.getVertexMap();
 
        List<String> vertexList = new ArrayList<String>(vm.size());
        vertexList.addAll(vm.keySet());
        Collections.sort(vertexList);   
 
        for (String v : vertexList) {
            dfs(v);
        }
 
        for (Map.Entry<String, Mark> entry : visitedMap.entrySet()) {
            Mark m = entry.getValue();
            System.out.format("%1$s : (%2$d, %3$d)\n", entry.getKey(), m.pre, m.post);
        }
    }    
 
    static void dfs(String vertexName) {
        if (visitedMap.containsKey(vertexName)) return;
 
        // set pre (time of enter)
        visitedMap.put(vertexName, new Mark(counter,-1));
        counter++;
 
        // retrieve adjacent vertices
        Map<String, List<String>> vm = graph.getVertexMap();
        List<String> adjacentVertices = vm.get(vertexName);
 
        for (String v : adjacentVertices) {
            if (visitedMap.containsKey(v)) continue;
            dfs(v);
        }
 
        // set post (time of exit)
        Mark m = visitedMap.get(vertexName);
        m.post = counter++;
    }
}

При запуске получаем следующий вывод:

$>java Problem1
A : (1, 12)
B : (2, 11)
C : (3, 10)
F : (4, 9)
E : (5, 6)
I : (7, 8)
D : (13, 18)
G : (14, 17)
H : (15, 16)


Или, в графическом виде:


Дополнительные ссылки:
Поиск в глубину - Википедия
Поиск в глубину в графе - MAXimal