Comments 22
Интересная статья, спасибо — интересная структура. Несколько вопросов (не сочтите за «пинки»):
1. Почему бы не выделить тестирование производительности в отдельный класс? По-моему так правильнее
2. Сравнивали ли вы свою реализацию с этой? github.com/megatherion/Unrolled-linked-list
3. Какая лицензия? (я мало пользуюсь Github — может там везде GPL, но я не в курсе)
Вцелом мне понравилось, хотя действительно было бы еще интересно прикрутить concurrency
1. Почему бы не выделить тестирование производительности в отдельный класс? По-моему так правильнее
2. Сравнивали ли вы свою реализацию с этой? github.com/megatherion/Unrolled-linked-list
3. Какая лицензия? (я мало пользуюсь Github — может там везде GPL, но я не в курсе)
Вцелом мне понравилось, хотя действительно было бы еще интересно прикрутить concurrency
Еще, на счет тестирования производительности. Я бы (доказать не могу, чисто «на всякий случай») вывод времени писал как:
time = System.nanoTime() — time;
System.out.println(" Some time " + time);
Идея: избежать каких-либо задержек от консольного вывода при замере конечной точки.
А вообще, по-хорошему, еще круче померять одно и то же несколько итераций, откинуть мин и макс, а для остального взять среднее. Прошу поправить, если ошибаюсь
time = System.nanoTime() — time;
System.out.println(" Some time " + time);
Идея: избежать каких-либо задержек от консольного вывода при замере конечной точки.
А вообще, по-хорошему, еще круче померять одно и то же несколько итераций, откинуть мин и макс, а для остального взять среднее. Прошу поправить, если ошибаюсь
Если Вы о, например:
то тут проблема не в консольном выводе (сначала аргументы эвалятся, а лишь затем посылаются в функцию вывода), а в создании объекта
long time = System.nanoTime();
....
System.out.println("Unrolled add " + (System.nanoTime() - time));
то тут проблема не в консольном выводе (сначала аргументы эвалятся, а лишь затем посылаются в функцию вывода), а в создании объекта
StringBuilder, используемого для конкатенации строки.Точняк! Я же чувствовал что что-то там не так :)
Пока спал придумал ещё одну вещь!
Вообщем, между
и
может переключится смена контекста, то лучше перед каждым
Вообщем, между
long time = System.nanoTime();
и
System.out.println("Unrolled add " + (System.nanoTime() - time));
может переключится смена контекста, то лучше перед каждым
System.nanoTime() вызывать Thread.yield().
System.nanoTime() нельзя запомнить до println в long timeEnd?Наверное я не правильно изъяснился.
Я имел ввиду что во время замеров может может переключится контекст и это может негативно повлиять на результаты измерений.
И поэтому перед каждым началом замера было бы неплохо сбросить текущий квант и начать исполнение замеров на новом.
Я имел ввиду что во время замеров может может переключится контекст и это может негативно повлиять на результаты измерений.
И поэтому перед каждым началом замера было бы неплохо сбросить текущий квант и начать исполнение замеров на новом.
Во первых — что значит негативно сказаться? А в реальном приложении? Какой смысл замерять что-то имеющее мало отношения к жизни.
Во вторых:
[JavaDoc on]
public static void yield()
A hint to the scheduler that the current thread is willing to yield its current use of a processor. The scheduler is free to ignore this hint.
[JavaDoc off]
Ну и в третих — нельшие по времени операции (десятки (иногда сотни) квантов) нужно мерять статистически — тогда кванты будут по фигу.
Во вторых:
[JavaDoc on]
public static void yield()
A hint to the scheduler that the current thread is willing to yield its current use of a processor. The scheduler is free to ignore this hint.
[JavaDoc off]
Ну и в третих — нельшие по времени операции (десятки (иногда сотни) квантов) нужно мерять статистически — тогда кванты будут по фигу.
Убедительно.
Заинтриговала строка
Интересно, разница только в JavaDoc или в реализации?
Заинтриговала строка
The scheduler is free to ignore this hint. Я так понял что это из 7-й версии. В javadoc на 6-ю версию написано: Causes the currently executing thread object to temporarily pause and allow other threads to execute.Интересно, разница только в JavaDoc или в реализации?
> вызывать Thread.yield().
Боже!
Что вы читали (ели/пили/курили) перед сном? ;)
Боже!
Что вы читали (ели/пили/курили) перед сном? ;)
Сомневаюсь, что в данном случае переключение контекстов сыграет важную роль.
1. Наивная попытка охватить всё одним классом. Недавно мне попадалась на глаза статья про некий фреймворк для микро-бэнчмаркинга, к выходным постараюсь разобраться с ним и поиграться с ним.
2. Нет, не сравнивал, но изучу. Целью статьи было попробовать самому реализовать эту структуру, реализация пока сыровата, но я ещё над ней поработаю.
3. Лицензия конечно GPL, я тоже не знаю какая принята на GitHub, но в данном случае — это определённо так.
В общем, к выходным запланирован небольшой рефакторинг внутренностей, прикручивание бэнчмарков и возможно даже эксперименты по concurrency. C последним правда видимо всё не так оптимистично: если в случае HashMap равномерное распределение ключей обеспечивается hash-функцией, то тут все ключи идут подряд, таким образом потоки работающие с одним и тем же диапазоном ключей или значений всё равно будут мешать друг другу. Но всё покажет эксперимент.
2. Нет, не сравнивал, но изучу. Целью статьи было попробовать самому реализовать эту структуру, реализация пока сыровата, но я ещё над ней поработаю.
3. Лицензия конечно GPL, я тоже не знаю какая принята на GitHub, но в данном случае — это определённо так.
В общем, к выходным запланирован небольшой рефакторинг внутренностей, прикручивание бэнчмарков и возможно даже эксперименты по concurrency. C последним правда видимо всё не так оптимистично: если в случае HashMap равномерное распределение ключей обеспечивается hash-функцией, то тут все ключи идут подряд, таким образом потоки работающие с одним и тем же диапазоном ключей или значений всё равно будут мешать друг другу. Но всё покажет эксперимент.
… а если в ваш UnrolledLinkedList добавить еще один уровень анролла (т.е. UnrolledUnrolledLinkedList), а потом еще и еще, то в пределе мы получим старое доброе В-дерево:) отличающееся логарифмической асимптотой для получения элемента по индексу и возможностью использования строк в качестве индекса.
Именно поэтому в динамических языках, таких как JavaScript и PHP, вообще все структуры данных сделаны на деревьях (массивы, объекты… какая разница, всё равно внутри одно и то же дерево), а в языках, претендующих на бОльшую производительность, классические списки и массивы оставлены именно для использования в специфических, рассчитанных именно на эти структуры алгоритмах.
Именно поэтому в динамических языках, таких как JavaScript и PHP, вообще все структуры данных сделаны на деревьях (массивы, объекты… какая разница, всё равно внутри одно и то же дерево), а в языках, претендующих на бОльшую производительность, классические списки и массивы оставлены именно для использования в специфических, рассчитанных именно на эти структуры алгоритмах.
На базе подобной структуры обычно реализуются двухсторонние очереди (Деки), в частности deque из STL C++.
IMHO, очевиная вещь.
Для новичков это еще может представлять интерес, а старички и так это давно знают.
Кто-то, наверняка, даже изобретал такой велосипед ручками.
Для новичков это еще может представлять интерес, а старички и так это давно знают.
Кто-то, наверняка, даже изобретал такой велосипед ручками.
Нет, очевидной она не выглядит. Конкретно, в пункте удаления элемента. Если делать, как описано у автора (при достижении порога в n/2 забрать n/2 элементов у соседей), то при чередовании удалений и вставок мы рискуем попасть в ситуацию, когда нам придется создавать или удалять массив каждый раз. Очевидно ли Вам, как этого эффективно избежать? Ну, конечно, ситуации, в которой список заполнен меньше, чем на 40% (и содержит больше одного массива), при решении допускать нельзя.
Своя модификация стандартной структуры под особенности программы порой позволяет упростить код. Я использую список с ленивым удалением и хранением индекса прямо в элементе, и синхронизуются такие списки на клиенте и сервере достаточно просто. Один такой список заменяет мне два hashmap-а.
Sign up to leave a comment.
Unrolled linked list на Java