Преобразование LinkedList в ArrayList для более быстрого параллельного итерации

Question

Я хорошо осведомлен о стоимости итерации LinkedList с внешним индексом (for). Заглядывая в исходный код для ListIterator, возвращаемый LinkedList#listIterator, я замечаю, что он значительно ускоряет процесс, отслеживая узел, который он использует в настоящее время.

Тем не менее, я недавно натолкнулся на this question, что в основном касалось итерации по двум или более спискам одновременно, но это необходимо для отслеживания индекса для передачи значений в массив. На мой взгляд, это сделало использование итераторов немного избыточным и более подверженным человеческой ошибке, поскольку индивидуальные декларации были необходимы для каждого итератора, поверх цикла и вызова каждого метода next. Вот почему я попытался избежать компиляции iterator-loop. Вот возможное решение проблемы:

List<Integer> listOne = new ArrayList<>(); 
List<Integer> listTwo = new ArrayList<>(); 
int[] combined = new int[(listOne.size() < listTwo.size() ? listOne.size() : listTwo.size())]; 
for (int i = 0; i < combined.length; i++) { 
    combined[i] = listOne.get(i) + listTwo.get(i); 
} 

Это хорошо для ArrayList, но это будет довольно медленная работа с LinkedList.

Одним из возможных решений было бы использовать конструктор преобразования ArrayList, чтобы получить все ссылки из LinkedList:

//convert linkedlists to arraylists 
ArrayList<Integer> arrayListOne = new ArrayList<>(listOne); 
ArrayList<Integer> arrayListTwo = new ArrayList<>(listTwo); 
//iterate with an efficient get() operation 
for (int i = 0; i < combined.length; i++) { 
    combined[i] = listOne.get(i) + listTwo.get(i); 
} 

Так как это будет вызывать только итератор каждого LinkedList один раз, а затем использовать более эффективный ArrayList#get метод, это жизнеспособное решение? Не повлияют ли накладные расходы на конверсию эффективности? Есть ли другие недостатки этого метода?

Answer 1

[...] повторение нескольких или более списков одновременно, но это необходимо для отслеживания индекса для передачи значений в массив, что предотвращает использование итераторов.

Просто потому, что вы также нужен индекс, не означает, что вы не можете использовать Iterator, поэтому «предотвращение использования итераторов» это совершенно неправильное утверждение.

Вы просто делаете простую 3-полосную параллельную итерацию (2 итераторов и 1 индекс):

List<Integer> listOne = new LinkedList<>(); 
List<Integer> listTwo = new LinkedList<>(); 
int[] combined = new int[Math.min(listOne.size(), listTwo.size())]; 
Iterator<Integer> iterOne = listOne.iterator(); 
Iterator<Integer> iterTwo = listTwo.iterator(); 
for (int i = 0; i < combined.length; i++) { 
    combined[i] = iterOne.next() + iterTwo.next(); 
} 

---

UPDATE(ответить на конкретные вопросы)

Поскольку это вызывало бы только итератор каждого из LinkedList один раз, а затем использовать более эффективный метод get ArrayList # get, это viab ли решение?

Да, это определенно более жизнеспособное решение. По мере увеличения списков время экспоненциального отклика get(index) для LinkedList делает использование get() действительно плохим решением.

Могут ли накладные расходы от конверсии отрицать эффективность?

No.Даже при небольших размерах списка производительность последовательного поиска get(index) на LinkedList намного превосходит любые потери производительности при копировании списка.

Есть ли другие недостатки этого метода?

Копирование списка первым повышают требования к памяти, и требует дополнительной (ненужных) итерации данных.

---

UPDATE(реагировать на изменения в вопросе)

[...] На мой взгляд, это сделало использование итераторов слегка избыточными и более склонны к человеческой ошибки

Использование нескольких итераторов параллельно не является избыточным.

Кроме того, все программирование подвержено человеческим ошибкам. Обычно вы должны использовать алгоритм, который является наиболее подходящим/правильным, а не считать (очень слабый). увеличивает потенциальную ошибку программирования, вызванную повышенной сложностью. Конечно, если один алгоритм безумно сложный, а другой - легкий, вы, скорее всего, захотите использовать простой, , если не улучшит алгоритм комплексного алгоритма. Но есть причина, по которой никто не использует bubble sort, хотя это очень просто: производительность очень плохая. В вашем случае сложность параллельной итерации незначительна.

Сравнение использования нескольких параллельных итераторов, а также копирование на ArrayList, которое является более избыточным? Копирование на ArrayList - это то, что вы в итоге повторяете данные дважды, и для этого требуется больше памяти.

Параллельная итерация - лучшее решение вашей проблемы. Он использует предполагаемый механизм итерации предоставленного List, не зная характеристик списка. Итерация List по индексу по своей сути ошибочна. Списки (и другие коллекции) всегда должны быть повторены с помощью прилагаемого Iterator (или ListIterator или Spliterator).

Также обратите внимание, что параллельная итерация иногда является единственной опцией, например. в merge-sort, где вы не итерируете два входа с одинаковой скоростью.

Answer 2

Я думаю, вы могли бы использовать итераторы на LInkedLists и индекс для массива:

Iterator<Integer> i1 = listOne.iterator(); 
    Iterator<Integer> i2 = listTwo.iterator(); 
    for (int i = 0; i < combined.length; i++) { 
     combined[i] = i1.next() + i2.next(); 
    } 

Answer 3

Я знаю, что это не ответ на ваш вопрос конкретно, но я чувствую, вы можете извлечь выгоду из этой части информации.

Начиная с версии Java 1.6 существует новый тип коллекции, называемый ArrayDeque, который имеет быстрый случайный доступ, такой как массив, но также имеет быструю добавку/удаление на концах.

LinkedList все еще выигрывает при добавлении/удалении посередине, если список.