Сортировка файлов с несколькими потоками

Question

Я сортирую большой файл, читая по блокам (Arraylist), сортирую каждый массив с помощью Collections.sort с помощью специального компаратора и записываю отсортированные результаты в файлы, а затем применяю алгоритм сортировки слиянием ко всем файлам.

Я делаю это в одном потоке.

Получу ли я какое-либо повышение производительности, если я начну новый поток для каждого Collections.sort ()?

Под этим я подразумеваю следующее:
Я читаю из файла в List, когда List заполняется, я начинаю новый поток, где сортирую этот List и записываю во временный файл.

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

Еще один вопрос, который у меня есть:

Что лучше для сортировки:
1) Arraylistчто я заполняю, и когда он полон, применяем collection.sort ()
2) TreeMap, который я заполняю, мне не нужно его сортировать.(сортирует, когда я вставляю элементы)

ПРИМЕЧАНИЕ: я использую JAVA 1.5

ОБНОВЛЕНИЕ: это код, который я хочу использовать, проблема в том, что я повторно использую массив данных, который используетсяпо темам, а также мне нужно дождаться завершения всех потоков.как мне исправить?

int MAX_THREADS = Runtime.getRuntime().availableProcessors();
ExecutorService executor = Executors.newFixedThreadPool(MAX_THREADS);
List datalines = ArrayList();       
try {
   while (data != null) {
       long currentblocksize = 0;

    while ((currentblocksize <= blocksize) && (data = getNext()) != null) {
                                        datalines.add(data);
    currentblocksize += data.length();
   }                
    executor.submit(new Runnable() {                
       public void run() {
    Collections.sort(datalines,mycomparator);
    vector.add(datalines);
       }
   });

Answer 1

Распараллеливание последовательной операции улучшит производительность в трех случаях:

1. У вас есть приложение с привязкой к процессору и несколько ядер, которые могут работать без координации. В этом случае каждое ядро ​​может выполнять свою работу, и вы увидите линейное ускорение. Однако, если у вас нет нескольких ядер, многопоточность действительно замедлит вас.
2. У вас есть приложение, связанное с IO, в котором вы выполняете IO по независимым каналам. Это тот случай, когда сервер приложений взаимодействует с несколькими сокетами. Данные в данном сокете относительно не зависят от того, что происходит в других сокетах. Обычно это , а не в случае дискового ввода-вывода, если только вы не можете гарантировать, что ваши дисковые операции будут выполняться на отдельных шпинделях и, возможно, на отдельных контроллерах. Как правило, вы не увидите здесь большого ускорения, потому что приложение все еще будет тратить много времени на ожидание. Однако это может привести к гораздо более чистой модели программирования.
3. Вы чередуете IO и CPU. В этом случае один поток может выполнять нагрузку на процессор, в то время как другой поток ожидает ввода-вывода. Ускорение, если оно есть, зависит от баланса между процессором и вводом-выводом в приложении; во многих (большинстве) случаях вклад ЦП незначителен по сравнению с IO.

Вы описываете случай № 3, и для определения ответа вам нужно будет сравнить ваш ЦП с IO. Один из способов сделать это с помощью профилировщика: если 90% вашего времени занято в FileInputStream.read(), то вы вряд ли получите ускорение. Однако, если 50% вашего времени там, а 50% в Arrays.sort(), вы будете.

Однако я видел один из ваших комментариев, где вы сказали, что анализируете строки внутри компаратора. Если это так, и Arrays.sort() занимает значительное количество времени, то я готов поспорить, что вы получите больше прироста скорости, анализируя чтение.

Answer 2

Я предлагаю вам реализовать следующую схему, известную как ферма:

             worker0
reader  -->  worker1  -->  writer
             ...
             workerN

Таким образом, один поток считывает кусок из файла, передает его рабочему потоку (рекомендуется использовать рабочие в качестве ExecutorService) для его сортировки, а затем каждый рабочий отправляет свой вывод потоку записи для во временном файле.

Редактировать : Хорошо, я посмотрел ваш код. Чтобы устранить проблему с общим datalines, у вас может быть закрытый член для каждого потока, в котором хранится текущий массив datalines, который поток должен отсортировать:

public class ThreadTask implements Runnable {
    private List datalines = new ArrayList();

    public ThreadTask(List datalines) {
        this.datalines.add(datalines);
    }

    public void run() {
       Collections.sort(datalines,mycomparator);
       synchronized(vector) {
           vector.add(datalines); 
       }
    }
}

Вам также необходимо синхронизировать доступ к общей коллекции vector.

Затем, чтобы дождаться окончания использования всех потоков в ExecutorService:

executor.awaitTermination(30, TimeUnit.SECONDS);

Answer 3

Ответ на первый вопрос - да.Вы получите повышение производительности, если внедрите параллельную версию сортировки слиянием.Подробнее об этом в этой статье Dr.Dobbs: http://drdobbs.com/parallel/229400239.

Answer 4

Если ваш процесс связан с процессором (что я подозреваю, что нет), вы можете увидеть улучшение, используя несколько потоков. Если ваш процесс связан с вводом-выводом, вам нужно улучшить пропускную способность ввода-вывода и скорость работы.

Answer 5

Ускорение использования потоков зависит от того, ограничены ли вы дисковым вводом-выводом или скоростью процессора. Это зависит от того, насколько быстры ваши диски (SSD намного быстрее, чем вращающиеся жесткие диски), и от того, насколько сложна ваша функция сравнения. Если пределом является дисковый ввод / вывод, то нет смысла добавлять потоки или беспокоиться о структурах данных, потому что они не помогут вам быстрее считывать данные с диска. Если ограничение скорости процессора, сначала вы должны запустить профилировщик, чтобы убедиться, что функция сравнения не делает ничего медленного и глупого.