|
Java форум JavaTalks
форум программистов
|
|
|
|
| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
John77 : 3
Новичок
|
 Окт 16, 2011 20:43 |
 |
|
Здравствуйте. Тут в теме про вопросы на собеседовании выкладывали задачу на скорость сортировки:
5. Нужно остсортировать миллион строк (java.lang.String). Что будет быстрее: добавить их в TreeSet, добавить их в коллецию и потом отсортировать, что-то другое?
Подскажите что будет быстрее? |
|
|
|
 |
Jean : 1992
JavaTalks Team Member
Откуда: Санкт-Петербург
|
| Окт 17, 2011 3:31 |
| |
|
Сортировка коллекции, если это quick sort (кажется именно такой алгоритм реализован во встроенных коллекциях в Java), выполняется за NlogN.
Добавление элемента в TreeSet стоит logN, таких элементов - N. Очевидно, что сложность та же.
Я бы предложил использовать многопоточность - разбиваем весь миллион на несколько подсписков (по числу процессоров с учетом гипертрединга и т.д.) и выполняем одновременно. Затем, один поток собирает все отсортированные подсписки и сортирует их между собой.
_________________
Всякое решение плодит новые проблемы |
|
|
|
|
OneHalf : 103
Новичок
|
| Окт 17, 2011 8:03 |
| |
|
| Не думаю, что сложность та же. Ведь когда добавляются элементы, то Log N надо считать от текущего значения N, а не от того, до которого коллекция должна вырасти. |
|
|
|
|
stolzen : 422
Бывалый
Откуда: Нижний Новгород
|
| Окт 17, 2011 10:26 |
| |
|
| Сложность в обоих случаях N log N, но фактически просто сортировка должна быть быстрее. А почему бы просто не проверить? |
|
|
|
|
Jean : 1992
JavaTalks Team Member
Откуда: Санкт-Петербург
|
| Окт 19, 2011 1:37 |
| |
|
| stolzen писал(а): |
| Сложность в обоих случаях N log N, но фактически просто сортировка должна быть быстрее. А почему бы просто не проверить? |
Если сложность описывается одной формулой, то как просто сортировка может быть быстрее?
Проверять желательно уже после того, как получатся какие-нибудь предположения. Особенно в данном случае, когда анализ относительно простой.
_________________
Всякое решение плодит новые проблемы |
|
|
|
|
Jean : 1992
JavaTalks Team Member
Откуда: Санкт-Петербург
|
| Окт 19, 2011 1:52 |
| |
|
| OneHalf писал(а): |
| Не думаю, что сложность та же. Ведь когда добавляются элементы, то Log N надо считать от текущего значения N, а не от того, до которого коллекция должна вырасти. |
Верно, но это записывается формулой Sum (log i), где i = от 1 до N. А сама эта формула приблизительно равна (NlogN - 1.5). То есть сложность все-таки NlogN.
_________________
Всякое решение плодит новые проблемы |
|
|
|
|
stolzen : 422
Бывалый
Откуда: Нижний Новгород
|
| Окт 19, 2011 8:15 |
| |
|
| Код: |
public static void main(String[] args) {
final String[] strings = prepareStrings();
long forSet = timeIt(new Lambda() {
@Override
public void apply() {
Set<String> set = new TreeSet<String>();
for (String str : strings) {
set.add(str);
}
}
});
System.out.println("red-black tree: " + forSet);
final List<String> list = new ArrayList<String>(Arrays.asList(strings));
long forList = timeIt(new Lambda() {
@Override
public void apply() {
Collections.sort(list);
}
});
System.out.println("merge stable sort: " + forList);
}
private static String[] prepareStrings() {
int len = 1000000;
final String[] strings = new String[len];
for (int i = 0; i < len; ++i) {
strings[i] = UUID.randomUUID().toString();
}
return strings;
}
static long timeIt(Lambda lambda) {
long start = System.nanoTime();
lambda.apply();
long end = System.nanoTime();
return end - start;
} |
Вывод:
red-black tree: 1920975506
merge stable sort: 1257984920
Последний раз редактировалось: stolzen (Окт 20, 2011 8:20), всего редактировалось 1 раз |
|
|
|
|
John77 : 3
Новичок
|
| Окт 19, 2011 10:42 |
| |
|
Всем спасибо за ответы!
| Цитата: |
| Думаю тут еще дело в том, что для TreeSet внутри при возрастании кол-ва элементов постоянно идет перемещение элементов в новый массив |
у treeset внутри не массив а бинарное дерево. о каком перемещении идет речь? |
|
|
|
|
stolzen : 422
Бывалый
Откуда: Нижний Новгород
|
| Окт 19, 2011 20:31 |
| |
|
Дезинформация
Почистил )
Последний раз редактировалось: stolzen (Окт 20, 2011 8:20), всего редактировалось 1 раз |
|
|
|
|
kamre : 329
Бывалый
|
| Окт 19, 2011 20:51 |
| |
|
| stolzen писал(а): |
| думаю, что и TreeSet внутри имеет что-то похожее - только элементы в массиве упорядочены и добавление туда происходит по правилам черно-красного дерева. |
Весьма странное предположение  |
|
|
|
|
John77 : 3
Новичок
|
| Окт 19, 2011 22:42 |
| |
|
| stolzen писал(а): |
| John77 писал(а): |
| у treeset внутри не массив а бинарное дерево. о каком перемещении идет речь? |
Ну а сами данные TreeSet (правильнее сказать TreeMap) где-то же должен хранить. Они хранятся в массиве. Так как зараннее не известно, сколько элементов будет в множестве, размер массива постепенно увеличивается с ростом кол-ва элементов. Сначала выделяется память под n елементов, когда кол-во элементов достигает n, создается новый массив размера, например, 2n, в который копируются все элементы со старого. По крайней мере так устроен ArrayList, думаю, что и TreeSet внутри имеет что-то похожее - только элементы в массиве упорядочены и добавление туда происходит по правилам черно-красного дерева. |
нет массива а есть объекты Entry в которых есть ссылки (left,right,parent) на такие же Entry.
Интересно почему добавление в TreeSet занимает почти в 2 раза больше времени чем сортировка коллекции, ведь сложность и у того и у того как мы выяснили одинаковая - NlogN |
|
|
|
|
stolzen : 422
Бывалый
Откуда: Нижний Новгород
|
| Окт 20, 2011 8:18 |
| |
|
Да действительно, перепутал с кучей.
Надо было хоть сурц глянуть перед предположениями (facepalm) |
|
|
|
|
Jean : 1992
JavaTalks Team Member
Откуда: Санкт-Петербург
|
| Окт 20, 2011 8:23 |
| |
|
| John77 писал(а): |
| stolzen писал(а): |
| John77 писал(а): |
| у treeset внутри не массив а бинарное дерево. о каком перемещении идет речь? |
Ну а сами данные TreeSet (правильнее сказать TreeMap) где-то же должен хранить. Они хранятся в массиве. Так как зараннее не известно, сколько элементов будет в множестве, размер массива постепенно увеличивается с ростом кол-ва элементов. Сначала выделяется память под n елементов, когда кол-во элементов достигает n, создается новый массив размера, например, 2n, в который копируются все элементы со старого. По крайней мере так устроен ArrayList, думаю, что и TreeSet внутри имеет что-то похожее - только элементы в массиве упорядочены и добавление туда происходит по правилам черно-красного дерева. |
нет массива а есть объекты Entry в которых есть ссылки (left,right,parent) на такие же Entry.
Интересно почему добавление в TreeSet занимает почти в 2 раза больше времени чем сортировка коллекции, ведь сложность и у того и у того как мы выяснили одинаковая - NlogN |
Потому что есть накладные расходы на создание энтри в мапе, бакетов для мапы, на переупорядочивание данных в новых бакетах и пр. Для того, чтобы мерить перфоманс, нужно создавать мапу сразу на 2 млн элементов либо, что надежнее, первый раз прогонять "вхолостую", а замеры начинать только со второго захода.
_________________
Всякое решение плодит новые проблемы |
|
|
|
|
stolzen : 422
Бывалый
Откуда: Нижний Новгород
|
| Окт 20, 2011 8:31 |
| |
|
| Jean писал(а): |
| Потому что есть накладные расходы на создание энтри в мапе, бакетов для мапы, на переупорядочивание данных в новых бакетах и пр. Для того, чтобы мерить перфоманс, нужно создавать мапу сразу на 2 млн элементов либо, что надежнее, первый раз прогонять "вхолостую", а замеры начинать только со второго захода. |
А пример можно?
(а если нужно _просто_ отсортировать, каждый раз вхолостую прогонять?)
| Цитата: |
| Для того, чтобы мерить перфоманс, нужно создавать мапу сразу на 2 млн элементов |
Кстати не нашел способа как этого добиться для TreeMap. Видимо (как меня уже поправили) потому что там ссылки, а не массив. |
|
|
|
|
Jean : 1992
JavaTalks Team Member
Откуда: Санкт-Петербург
|
| Окт 20, 2011 11:22 |
| |
|
| stolzen писал(а): |
| Jean писал(а): |
| Потому что есть накладные расходы на создание энтри в мапе, бакетов для мапы, на переупорядочивание данных в новых бакетах и пр. Для того, чтобы мерить перфоманс, нужно создавать мапу сразу на 2 млн элементов либо, что надежнее, первый раз прогонять "вхолостую", а замеры начинать только со второго захода. |
А пример можно?
(а если нужно _просто_ отсортировать, каждый раз вхолостую прогонять?)
| Цитата: |
| Для того, чтобы мерить перфоманс, нужно создавать мапу сразу на 2 млн элементов |
Кстати не нашел способа как этого добиться для TreeMap. Видимо (как меня уже поправили) потому что там ссылки, а не массив. |
Да, вы правы, для TreeMap этого всего нельзя сделать - нельзя задать ей размер и т.д.
Если нужно просто сортировать, то нужно выбирать оптимальный способ.
Все-таки при использовании TreeMap создаются Entry. Для миллиона строк будет создано миллион Entry. Хотя сама по себе операция дешевая, она все-таки напрочь отсутствует для простой сортировки. После каждой вставки в TreeSet (что тоже самое, что TreeMap) происходит балансировка дерева (что должно быть самым дорогим). Плюс при вставке в TreeSet происходят тьма разных проверок дополнительных к непосредственному compare.
Вот, если бы исключить эти ребалансировку и все-таки начать измерения вемени со второго раза, результаты были бы вернее.
Возьметесь проверить?
_________________
Всякое решение плодит новые проблемы |
|
|
|
|
|
|
|
