Pull to refresh
0
0
Влад @Onmyoji

User

Send message

Алгоритм сортировки Timsort

Reading time6 min
Views155K
Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.



Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.

Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.
Читать дальше →
Total votes 292: ↑285 and ↓7+278
Comments63

Маленькие хитрости Java. Часть 2

Reading time5 min
Views109K
В продолжение первой статьи я добавлю еще несколько штрихов о наиболее часто встречающихся ошибках и просто плохом коде, с которым часто приходится иметь дело при работе с уже написанными проектами. Я не выносил это в первую часть, так как эти ситуации встречаются гораздо реже, но поскольку первая часть вызвала много позитивных отзывов, решил продолжить. Спасибо всем комментаторам, отзывам и замечаниям. Я постараюсь избежать допущенных ошибок. Итак, продолжим:

Buffered Streams

//медленно
InputStream is = new FileInputStream(file);
int val;
while ((val = is.read()) != -1) {
}
//быстро
InputStream is = new BufferedInputStream(new FileInputStream(file));
int val;
while ((val = is.read()) != -1) {
}

Казалось бы — очевидная истина, неправда ли? Но как показал чужой код и опыт собеседования кандидатов, часть разработчиков определенно не понимает в чем преимущество буферизованных стримов. Кто до сих пор не разобрался — метод read() класса FileInputStream:
public native int read() throws IOException;

Согласитесь, каждый раз делать системный вызов, чтобы считать один байт несколько расточительно. Собственно для того, чтобы избежать этой проблемы и были созданы оболочки-буферы. Все что они делают — при первом вызове системного read() считывают несколько больше (в зависимости от указанного размера буфера, котрый по умолчанию равен 8 кб) и при следующем вызове read() считывают данные уже из буфера. Прирост производительности — на порядок. Системные вызовы, на самом деле, это не всегда плохо, например:
System.arraycopy(src, srcPos, dest, destPos, length);

В случае копированния массива — системный метод будет гораздо быстрей реализованного на java. И еще — считывайте данные порциями, а не по байтам, это тоже позволит прилично сэкономить.
Читать дальше →
Total votes 93: ↑84 and ↓9+75
Comments91

Маленькие хитрости Java

Reading time4 min
Views270K
Я уже достаточно много лет занимаюсь разработкой на java и повидал довольно много чужого кода. Как это не странно, но постоянно от одного проекта к другому я вижу одни и те же проблемы. Этот топик — попытка ликбеза в наиболее часто используемых конструкциях языка. Часть описанного — это довольно банальные вещи, тем не менее, как показывает мой опыт, все эти банальности до сих пор актуальны. Надеюсь, статья пригодится многим java программистам. Итак, поехали:

new vs valueOf

//медленно
Integer i = new Integer(100);
Long l = new Long(100);
String s = new String("A");

//быстро
Integer i = Integer.valueOf(100);
Long l = 100L;//это тоже самое что Long.valueOf(100L);
String s = "A";


Старайтесь всегда использовать метод valueOf вместо конструктора в стандартных классах оболочках примитивных типов, кроме случаев, когда вам нужно конкретно выделить память под новое значение. Это связано с тем, что все они, кроме чисел с плавающей точкой, от Byte до Long имеют кеш. По умолчанию этот кеш содержит значения от -128 до 127. Следовательно, если ваше значение попадает в этот диапазон, то значение вернется из кеша. Значение из кеша достается в 3.5 раза быстрее чем при использовании конструктора + экономия памяти. Помимо этого, наиболее часто используемые значения могут также быть закэшированы компилятором и виртуальной машиной. В случае, если ваше приложение очень часто использует целые типы, можно увеличить кеш для Integer через системное свойство «java.lang.Integer.IntegerCache.high», а так же через параметр виртуальной машины -XX:AutoBoxCacheMax=<size>.
Читать дальше →
Total votes 141: ↑126 and ↓15+111
Comments166

Information

Rating
Does not participate
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
Date of birth
Registered
Activity