Сортировка больших объёмов данных, реализация на Java

[@Devgru]

Почему в конструктор передаёте итератор без дженерика?

[@dzmitryc]

Упс. Наверное потому, что дженерики начал копать позавчера :)
«Виноват, сейчас исправлюсь»

[@Timmmm]

Вместо Listitems = new ArrayList(); нужно использовать LinkedList. Мы же с вами знаем что вставка в список намного быстрее ArrayList. А ArrayList мы используем когда нам нужен быстрый доступ к элементу по индексу.

Вам не кажется что такой предор и вставка не очень красивый код?
for (FileSortStorage f: partFiles) {
iterators.add(f.iterator());
}

Я бы на вашем месте посмотрел в сторону Collection класса или утилит по работе с коллекциями.

И почему вы не стали пользоваться коллекциями которые предназначены для сортировки?

[@Timmmm]

*перебор

[@dzmitryc]

ArrayList я использовал, т.к. к этому списку (хоть он и не слишком большой) идут частые обращения к случайному элементу ( iterators.get(minIdx) и items.set(minIdx, iterators.get(minIdx).next()) ).
Я не тестировал и опыта у меня пока «кот наплакал», но предположил, что оно сработает лучше :)

Перебор… Можно было воспользоваться итератором и здесь (да, они мне очень нравятся), но код получился бы длиннее.

Классы по работе с коллекциями я как раз использовал. Да, совсем чуть-чуть. А есть специализированные классы, которые позволяют сортировать большие объёмы данных (для которых памяти совсем не хватает)?

[@Timmmm]

Перебор… вообще нехорошо. Мы же просто берем из одного списка и вставляем в другой. Это «узкое место». У коллекций есть метод addAll.

Первым делом я стал бы смотреть в сторону коллекций которые предназначены для сортировки SortedSet, TreeSet.

java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html

[@Devgru]

А смысл этих сортирующих коллекций тут?

[@Timmmm]

эммм мы же про «Сортировку больших объёмов данных» тут разговариваем. Может строить нашу сортировку на основе этих коллекций?

[@dzmitryc]

Set'ы ведь уникализируют содержимое. А у нас произвольный список.

И, мне кажется, Вы несколько не поняли алгоритм. AddAll здесь помочь никак не может, т.к. в переменной(списке) items хранятся по одному минимальному на текущий момент значению из файлов подкачки (доступных через переменную(список итераторов :)) iterators). Добавив минимальное значение из одного из них необходимо подтянуть из использованного источника следующее значение. Вдруг оно окажется меньшим остальных имеющихся в пуле?

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

ВотЪ

[@Devgru]

> Я бы на вашем месте посмотрел в сторону Collection класса или утилит по работе с коллекциями.
Не совсем понятно о чём вы. Collection — абстрактный класс и он там, строго говоря, используется. Может вы имели в виду класс Collections?

[@Timmmm]

Да, вы правы. Редко его использую.

[@iZENfire]

В JavaTest есть разнообразные алгоритмы сортировки.

[@dzmitryc]

Есть. Но у Вас несколько не то. Насколько я понял, там примеры реализации алгоритмов, сделанные «для себя» и «чтобы понять». Некоторые даже переведены с паскаля, ах, ностальгия :)
Такие примеры можно (и мне кажется удобно) смотреть в той же википедии ( Категория: Алгоритмы_сортировки — описания с примерами реализации на различных языках ).
А здесь я пытался привести пример универсальной реализации внешней сортировки (т.е. той, оперирует большим объёмом данных, который обычной сортировкой обработать нельзя).