|
Java форум JavaTalks
форум программистов
|
|
|
|
| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
stolzen : 422
Бывалый
Откуда: Нижний Новгород
|
 Окт 20, 2011 11:50 |
 |
|
| Jean писал(а): |
Вот, если бы исключить эти ребалансировку и все-таки начать измерения вемени со второго раза, результаты были бы вернее.
Возьметесь проверить? |
Вы имеете ввиду, что нужно заранее подготовить несбалансированное множество записей, а затем на нем запустить балансировку? Думаю что не выйдет.
В методе addAll происходит проверка, отсортированное ли множество подставляется с помощью (c instanceof SortedSet), и если нет, то вызывается тоже самое - поочередное добавление элементов коллекции с помощью add
| Код: |
final String[] strings = prepareStrings();
long forSet = timeIt(new Lambda() {
@Override
public void apply() {
new TreeSet<String>(Arrays.asList(strings));
}
});
System.out.println("time: " + forSet); |
Получилось даже больше - time: 2351714714
| Код: |
final String[] strings = prepareStrings();
final Set<String> set = new TreeSet<String>(Arrays.asList(strings));
set.clear();
long forSet = timeIt(new Lambda() {
@Override
public void apply() {
for (String string : strings) {
set.add(string);
}
}
});
System.out.println("time: " + forSet); |
Как и ожидалось, этот код выполняется точно так же долго, как и просто добавление без "разогрева": time: 1947486586
Я может не совсем понял мысль? |
|
|
|
 |
Pahan : 745
Постоянный посетитель
Откуда: Минск
|
| Окт 20, 2011 12:04 |
| |
|
| А что значит log(n), какое основание у этого логарифма? |
|
|
|
|
stolzen : 422
Бывалый
Откуда: Нижний Новгород
|
| Окт 20, 2011 12:13 |
| |
|
| Pahan писал(а): |
| А что значит log(n), какое основание у этого логарифма? |
[url]http://минимулин.рф/2/7.html[/url] Тут основание роли вообщем-то не играет (оценка приблизительная) |
|
|
|
|
abch-98-ru : 38
Новичок
|
| Окт 20, 2011 12:17 |
| |
|
| Jean писал(а): |
| Сортировка коллекции, если это quick sort (кажется именно такой алгоритм реализован во встроенных коллекциях в Java), |
не флейма ради, точности для.
в Collections.sort - merge sort. подозреваю из-за худшего случая.
по задаче " на скорость сортировки": тоже кажется, что сортирующая сеть побыстрее будет на компе, где больше одного процессора ) |
|
|
|
|
Jean : 1992
JavaTalks Team Member
Откуда: Санкт-Петербург
|
| Окт 20, 2011 12:40 |
| |
|
| Pahan писал(а): |
| А что значит log(n), какое основание у этого логарифма? |
2
_________________
Всякое решение плодит новые проблемы |
|
|
|
|
Jean : 1992
JavaTalks Team Member
Откуда: Санкт-Петербург
|
| Окт 20, 2011 13:03 |
| |
|
| stolzen писал(а): |
| Jean писал(а): |
Вот, если бы исключить эти ребалансировку и все-таки начать измерения вемени со второго раза, результаты были бы вернее.
Возьметесь проверить? |
Вы имеете ввиду, что нужно заранее подготовить несбалансированное множество записей, а затем на нем запустить балансировку? Думаю что не выйдет.
|
Хм... а ведь получается, что без перебалансировки-то дерево действительно не построишь.
Что ж, все мои аргументы побиты (они были ошибочными, вы это доказали). У меня других нет. =)
Видимо, результаты верные. Что означает, что все-таки для TreeMap вставка элемента стоит несколько дороже, чем logN. Из-за перебалансировки.
Другие мнения есть?
_________________
Всякое решение плодит новые проблемы |
|
|
|
|
Pahan : 745
Постоянный посетитель
Откуда: Минск
|
| Окт 20, 2011 13:04 |
| |
|
| Jean писал(а): |
| OneHalf писал(а): |
| Не думаю, что сложность та же. Ведь когда добавляются элементы, то Log N надо считать от текущего значения N, а не от того, до которого коллекция должна вырасти. |
Верно, но это записывается формулой Sum (log i), где i = от 1 до N. А сама эта формула приблизительно равна (NlogN - 1.5). То есть сложность все-таки NlogN. |
Мне кажется что сума эта посчитана неверно, почему (N log N - 1.5)?
У нас n = 1000000.
1000000 log(1000000) запишем как сумму
log(1000000) + log(1000000) + log(1000000) + ... и так 1000000 раз
а сума запишется как
log(1) + log(2) + log(3) + ... и так до log(1000000)
Уже первые три члена сумы различаются намного больше чем на 1,5. |
|
|
|
|
Pahan : 745
Постоянный посетитель
Откуда: Минск
|
| Окт 20, 2011 13:19 |
| |
|
Мне кажется если прилично увеличить число строк, то в тесте который выше делали начнет побеждать TreeSet.
Проверьте кто-нить у ого под рукой Java. |
|
|
|
|
stolzen : 422
Бывалый
Откуда: Нижний Новгород
|
| Окт 20, 2011 13:54 |
| |
|
| Pahan писал(а): |
Мне кажется если прилично увеличить число строк, то в тесте который выше делали начнет побеждать TreeSet.
Проверьте кто-нить у ого под рукой Java. |
| Код: |
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
public class SomeClass {
public static void main(String[] args) {
final Integer[] ints = prepareInts();
System.out.println("generated ints, sorting...");
long forSet = timeIt(new Lambda() {
@Override
public void apply() {
Set<Integer> set = new TreeSet<Integer>();
for (Integer str : ints) {
set.add(str);
}
}
});
System.out.println("red-black tree: " + forSet);
final List<Integer> list = new ArrayList<Integer>(Arrays.asList(ints));
long forList = timeIt(new Lambda() {
@Override
public void apply() {
Collections.sort(list);
}
});
System.out.println("merge stable sort: " + forList);
}
private static Integer[] prepareInts() {
int len = 10 * 1000 * 1000;
final Integer[] ints = new Integer[len];
Random random = new Random();
for (int i = 0; i < len; ++i) {
ints[i] = random.nextInt();
}
return ints;
}
static long timeIt(Lambda lambda) {
long start = System.nanoTime();
lambda.apply();
long end = System.nanoTime();
return end - start;
}
}
interface Lambda {
void apply();
}
|
generated ints, sorting...
red-black tree: 28315646410
merge stable sort: 6719941981 |
|
|
|
|
Pahan : 745
Постоянный посетитель
Откуда: Минск
|
| Окт 20, 2011 15:08 |
| |
|
Добавил к тесту подсчет использования операции сравнения.
| Код: |
package my;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
public class Tester {
public static void main(String[] args) {
System.out.println("Generating of initial data.\n");
final Integer[] ints = prepareInts();
System.out.println("Testing of TreeSet...");
long result = timeIt(new Lambda() {
public void apply() {
ComparatorCounter comparator = new ComparatorCounter();
Set<Integer> set = new TreeSet<Integer>(comparator);
for (Integer str : ints) {
set.add(str);
}
System.out.println("Number of compaison: " + comparator.count() + ".");
}
});
System.out.println("Time spent: " + result / 1000000000d + " sec\n");
System.out.println("Testing of ArrayList + quicksort...");
result = timeIt(new Lambda() {
@Override
public void apply() {
ComparatorCounter comparator = new ComparatorCounter();
List<Integer> list = new ArrayList<Integer>(Arrays.asList(ints));
Collections.sort(list, comparator);
System.out.println("Number of compaison: " + comparator.count());
}
});
System.out.println("Time spent: " + result / 1000000000d + " sec\n");
}
private static Integer[] prepareInts() {
int len = 1000 * 1000;
final Integer[] ints = new Integer[len];
Random random = new Random();
for (int i = 0; i < len; ++i) {
ints[i] = random.nextInt();
}
return ints;
}
static long timeIt(Lambda lambda) {
long start = System.nanoTime();
lambda.apply();
long end = System.nanoTime();
return end - start;
}
}
interface Lambda {
void apply();
}
class ComparatorCounter implements Comparator<Integer> {
private int counter;
@Override
public int compare(Integer a, Integer b) {
counter++;
return a.compareTo(b);
}
public int count() {
return counter;
}
} |
Результат при 1 000 000 записей:
| Цитата: |
Generating of initial data.
Testing of TreeSet...
Number of compaison: 18904363.
Time spent: 3.195978582 sec
Testing of ArrayList + quicksort...
Number of compaison: 18981114
Time spent: 1.4209246 sec
|
Запускал раз 10 количество операций сравнения всегда приблизительно равное, причем у TreeSet немножко меньше. |
|
|
|
|
Vurn : 1122
Java Developer
|
| Окт 20, 2011 17:49 |
| |
|
| Pahan писал(а): |
| Запускал раз 10 количество операций сравнения всегда приблизительно равное, причем у TreeSet немножко меньше. |
неудивительно. TreeSet постоянно при добавлении подсортировывает. При этом там реализовано B-Tree дерево, что вынуждает тратить дополнительное время на балансировку. |
|
|
|
|
Jean : 1992
JavaTalks Team Member
Откуда: Санкт-Петербург
|
| Окт 21, 2011 3:19 |
| |
|
| Pahan писал(а): |
| Jean писал(а): |
| OneHalf писал(а): |
| Не думаю, что сложность та же. Ведь когда добавляются элементы, то Log N надо считать от текущего значения N, а не от того, до которого коллекция должна вырасти. |
Верно, но это записывается формулой Sum (log i), где i = от 1 до N. А сама эта формула приблизительно равна (NlogN - 1.5). То есть сложность все-таки NlogN. |
Мне кажется что сума эта посчитана неверно, почему (N log N - 1.5)? |
http://www.imgup.ru/images/gz8x7561210.png
Взято из книги Макконнел - Основы современных алгоритмов, 2004. Страница (примерно) 26.
_________________
Всякое решение плодит новые проблемы |
|
|
|
|
HalfKorean : 88
Новичок
|
| Окт 27, 2011 16:37 |
| |
|
Сравнение функций.
Логарифмический масштаб
Частное функций
Правильная формула с суммой не NlogN - 1.5, а N(logN - 1.5). Что и дает разницу в 1.5N.
Видно, что массив в целом проигрывает, но чем больше количество объектов, тем разница менее существенна.
Результат тестов обратный потому, что эти функции показывают только количество операций сравнения. А у дерева много накладных расходов.
Для объектов со сложной функцией сравнения (или сложным компаратором) все было бы примерно так.
Мне кажется, деревья надо использовать для динамики. Для статичной одноразовой сортировки - классические методы.
Кстати, можно еще обратить внимание на то, что результат в виде массива эффективнее для вывода куда бы это ни было. |
|
|
|
|
den295 : 3
Новичок
|
| Апр 03, 2012 20:27 |
| |
|
Мне кажется что в Java вообще не актуально сравнивать какой из алгоритмов быстрее, так как в дело вмешивается GC, и не изветсно к в какой конкретно момент времени и сколько раз за каждый из циклов работы.
ИМХО в данном вопросе оптимальным решением было бы использовать Merge Sort, так доступ к строкам файла получается последовательно. |
|
|
|
|
abix : 12
Новичок
|
| Апр 05, 2012 10:53 |
| |
|
| да уж. а что на собеседовании то отвечать? |
|
|
|
|
|
|
|
