Комментарии 29
Возможно корректность способа замера оставляет желать лучшегоJMH, конечно, не гарантирует вам корректности бенчмарка, но избавиться от самых типичных проблем поможет. Добавить его не трудно, посмотрите хоты бы вот этот пример.
Очень хотелось бы увидеть результаты, полученные с помощью него. Также было бы хорошо увидеть полученный бенчмарк в вашем репозитории, чтобы можно было легко его запустить у себя.
2)Кроме того вы забыли об операции вставки (insert). Она может быть через увеличение размера конкретной «корзины» (а значит по «сложностям» мы возвращаемся к ArrayList), тогда надо переписать вашу реализацию get(idx) чтобы она учитывала переменный размер массивов в списке. Либо вставку можно реализовать через добавление-в-начале/удаление-в-конце для каждой из корзин после той в которую добавился элемент, что ясное дело сводит на нет всё возможное преимущество.
В сухом остатке: предвижу, что в «реальном софте» в зависимости от профиля нагрузки ваше преимущество будет чуть более чем никакое. Да и в конечном итоге — внутри ArrayList — массив указателей на объекты. Лежат в памяти хорошим таким цельным понятным куском байт. Если еще и хип маленький, то с compressedOOPs — в 2 раза меньше. И вот это вот всё хозяйство нативный arraycopy через DMA и всё такое прочее сделает ну очень быстро. Гораздо быстрее чем ваша «очень умная логика».
Да и + если где-то увеличение ArrayList станет узким местом — наверняка аккуратный выбор начального размера и инкремента по эффективности опять же сможет обойти ваше решение.
Векторизация в лучшем случае поделит время выполнения на константу. На асимпотику это никак не повлияет (если, конечно, не рассматривать какие-то гипотетические вычислительные устройства с неограниченным количеством SIMD потоков).
Векторизация кода не улучшает оценки алгоритма.
Векторизация копирования же при этом дает ускорение не более чем в 8 раз в лучшем случае (всего 1 порядок!)
Куда больший эффект дает уменьшение количества операций косвенной адресации, и улучшение локальности при работе с памятью, особенно если памяти мало и используется своп. Но разницу между N и log N даже это не покрывает.
Во-первых, "на рассматриваемом отрезке" асимптотическая оценка алгоритма не имеет смысла. Если входные данные ограничены, то любой алгоритм формально работает за О(1).
Во-вторых, на любом отрезке поведение O(N) ни разу не близко к поведению O(Log N). В первом случае увеличение инпута в 10 раз в те-же 10 раз увеличит и время выполнения, какой бы маленькой не была константа. Во втором же случае время исполнения увеличится всего лишь на некоторую константу.
Ну и в третьих, Integer.MAX_VALUE — это довольно много. Даже для самого векторизированного линейного алгоритма время обработки такого объема входных данных на современных CPU будет измеряться сотнями миллисекунд, а то и секундами. В то время как самый дохлый и не оптимизированный логарифм отработает мгновенно.
Если нужно добавление и удаление только в начало, конец то да. А при вставке удалении произвольных будет чуток хуже чем ArrayList.
Вы переизобрели Unrolled Linked List?
Проблема ArrayList — у него есть начальный размер по умолчанию DEFAULT_CAPACITY или заданный размер initialCapacity, при превышении этого размера, создается новый массив большего размера, при этом туда копируются данные из старого массива, что по времени очень затратно и именно это дает в наихудшем случае алгоритмическую сложность O(n)
проблема LinkedList это то что тратится память на обьекты в массив можно примитивных значений иметь.
однажды в качестве теста я для избавления от копирования сделал немного иначе — просто массив из массивов, при наполнении одного создаётся другй без перекопирования, так оно работало хуже ArrayListа даже при ЗАПОЛНЕНИИ почему-то, так что мораль — нечего выдумывать.
Я не из мира Java, но любопытство есть. Так что у меня такой вопрос: в том же методе get используются this.level, this.current. Вопрос потоконебезопасности даже при чтении не смущает в данном случае? В моем мире задача читателей/писателей довольно актуальна, и не иметь возможности корректно читать из нескольких потоков кажется странным.
Что будет если объединить ArrayList и LinkedList?