Внешнее слияние K-way. Итератор с целочисленными потоками ⇐ JAVA

[Anonymous]

Итератор работает не так, как ожидалось.

Это k-образный алгоритм слияния

У нас есть большой входной файл (1024 байта для теста) со случайно сгенерированными целыми числами, и этот файл разделен на n меньших фрагментов, размер которых составляет 256 байт (для теста), числа в фрагментах уже отсортированы. Затем каждый файл преобразуется в Stream, и каждый поток имеет собственный итератор, каждый итератор имеет собственное целочисленное значение. Set состоит из этих итераторов, первый элемент которого является итератором с наименьшим значением.

import java.io.*; импортировать java.nio.ByteBuffer; импортировать java.nio.file.Files; импортировать java.nio.file.Path; импортировать java.nio.file.StandardOpenOption; импортировать java.time.temporal.Temporal; импортировать java.util.ArrayList; импортировать java.util.Arrays; импортировать java.util.Iterator; импортировать java.util.List; импортировать java.util.stream.Collectors; публичный класс MergeFileSorter реализует FileSorter { // количество элементов частный int chunkSize; частный строковый файл; // Количество прогонов, которые нужно объединить частный int NumberOfRuns; //Чтение файла частный FileSplitter fileSplitter = новый FileSplitter(); частный FileReader FileReader; public MergeFileSorter (String file, int run, int chunkSize) { этот.файл = файл; this.numberOfRuns = работает; this.chunkSize = chunkSize; } @Override общественная недействительная сортировка (String inputPath, String outPath) { пытаться { fileSplitter.readChunks(inputPath, (int) chunkSize); mergeAndSort (inputPath, outPath, chunkSize); } catch (IOException e) { выдать новое RuntimeException(e); } } Private void mergeAndSort (String inputPath, String outPath, int chunkSize) выдает IOException { Путь chunkFolder = fileSplitter.getChunkFolder(inputPath); Чанки List = Files.walk(chunkFolder).filter(path -> !Files.isDirectory(path)).toList(); IteratortreeSetMergedIterator = новый TreeSetMergedIterator(куски); Путь путь = Path.of(outPath); Files.write(путь, новый байт[0]); интервал intCount = 0; List целые числа = новый ArrayList(); внутренний индекс = 0; в то время как (treeSetMergedIterator.hasNext()) { // System.out.println("Int Count: " + (++intCount)); Целочисленное значение = TreeSetMergedIterator.next(); целые числа.add(значение); if (integers.size() >= chunkSize/Integer.BYTES){ Files.write(путь, ConvertIntegersToByteArray(целые числа), StandardOpenOption.APPEND); целые числа.очистить(); } } если (!integers.isEmpty()){ Files.write(путь, ConvertIntegersToByteArray(целые числа), StandardOpenOption.APPEND); } } public static List ConvertIntegersToStrings(List IntegerList) { вернуть целое числоList.stream() .map(Объект::toString) .collect(Коллекторы.toList()); } public static List ConvertIntegersToStrings(int[]integerList) { return Arrays.stream(integerList) // Потоковая передача массива .mapToObj(Integer::toString) // Преобразуем каждое целое число в строку .collect(Коллекторы.toList()); // } public static byte[] ConvertIntegersToByteArray(List целые числа) { Буфер ByteBuffer = ByteBuffer.allocate(integers.size()*Integer.BYTES); for (Целое число: целые числа) { буфер.putInt(целое число); } вернуть буфер.массив(); } public static byte[] ConvertIntegersToByteArray(int[] целые числа) { Буфер ByteBuffer = ByteBuffer.allocate(целые числа.длина * Integer.BYTES); for (int целое число: целые числа) { буфер.putInt(целое число); } вернуть буфер.массив(); } } Этот цикл добавляет значения итераторов в массив Integer и записывает его в выходной файл с отсортированными фрагментами.

Проблема в том, что размер выходного файла не совпадает с размером входного файла и всегда варьируется (400–500 байт), а если размер чанка составляет 4 байта (меньше), выходной файл может достигать 1000 байт.
>
Когда я читаю файл размером 32 байта и меньше (а размер фрагмента составляет 32/16/8/4), все работает нормально. Чтение файлов в treeMergedIterator кажется правильным, поскольку размер буфера всегда полон и соответствует размеру файла фрагмента.

Но treeSetMergedIterator.hasNext() всегда неожиданно возвращает false и алгоритм перестает работать, но числа остаются.

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

import java.io.IOException; импортировать java.nio.ByteBuffer; импортировать java.nio.file.Files; импортировать java.nio.file.Path; импортировать java.util.*; импортировать java.util.stream.Collectors; импортировать java.util.stream.Stream; публичный класс TreeSetMergedIterator реализует Iterator { частные финальные итераторы Set; public TreeSetMergedIterator (пути List) { итераторы = paths.stream() .map(this::streamLines) .map(Stream::итератор) .map(IteratorInfo::new) .collect(Collectors.toCollection(TreeSet::new)); } частный StreamstreamLines(Path path) { пытаться { byte[] байты = Files.readAllBytes(путь); вернуть bytesToIntList(bytes).stream(); } catch (IOException ex) { выбросить новое RuntimeException(ex); } } @Override общедоступное логическое значение hasNext() { return iterators.stream().anyMatch(iteratorInfo -> { если (iteratorInfo.getIterator().hasNext()) { вернуть истину; } еще { вернуть iteratorInfo.value != null; } }); } @Override публичное целое число next() { Информация IteratorInfo = iterators.iterator().next(); Целое значение = info.value; iterators.remove(информация); если (info.iterator.hasNext()) { iterators.add(info.next()); } возвращаемое значение; } частный List bytesToIntList(byte[] байты) { Буфер ByteBuffer = ByteBuffer.wrap(байты); List целые числа = новый ArrayList(); /* int[] целые числа = new int[buffer.capacity()/Integer.BYTES];*/ while (buffer.remaining() >= 4) { целые числа.add(buffer.getInt()); } /* while (buffer.hasRemaining()){ целые числа [buffer.position()/Integer.BYTES] = buffer.getInt(); }*/ возвращать целые числа; } статический класс IteratorInfo реализует Comparable { частный окончательный итератор Iterator; частное целочисленное значение; public IteratorInfo (итератор Iterator) { this.iterator = итератор; значение = итератор.следующий(); } общественный IteratorInfo следующий () { значение = итератор.следующий(); верните это; } @Override public int CompareTo (информация IteratorInfo) { return Integer.compare(значение, info.value); } общественный Iterator getIterator() { вернуть итератор; } } } Я также реализовал более простую реализацию (класс MergedIterator) с массивом итераторов вместо set, но проблема осталась той же.

import java.io.IOException; импортировать java.nio.ByteBuffer; импортировать java.nio.file.Files; импортировать java.nio.file.Path; импортировать java.util.ArrayList; импортировать java.util.Iterator; импортировать java.util.List; импортировать java.util.stream.Stream; публичный класс MergedIterator реализует Iterator { частные окончательные итераторы List; частный окончательный Integer [] currentData; public MergedIterator (пути List) { итераторы = paths.stream() .map(this::streamLines) .map(Stream::итератор) .к списку(); текущиеДанные = итераторы.поток() .map(Итератор::следующий) .toArray(Integer[]::new); } частный StreamstreamLines(Path path) { пытаться { byte[] байты = Files.readAllBytes(путь); вернуть bytesToIntList(bytes).stream(); } catch (IOException ex) { выбросить новое RuntimeException(ex); } } @Override общедоступное логическое значение hasNext() { вернуть iterators.stream().anyMatch(Iterator::hasNext); } @Override публичное целое число next() { int minValue = Integer.MAX_VALUE; интервал мининдекс = -1; for (int i = 0; i = 4) { целые числа.add(buffer.getInt()); } возвращать целые числа; } } Куча памяти JVM составляет 100 МБ

Вот основной класс: (количество запусков не учитывается)
import java.util.logging.Logger; общественный класс Main { общедоступный статический окончательный длинный GENERATED_FILE_SIZE = 1024; общественный статический окончательный int chunkSize = 256; public static void main(String[] args) { Строка filePath = «случайный_файл.dat»; Строка resultPath = "result.dat"; FileGenerator fileGenerator = новый FileGenerator (); fileGenerator.generateRandomFile(filePath, GENERATED_FILE_SIZE, chunkSize); MergeFileSorter fileSorter = новый MergeFileSorter (filePath, 2, chunkSize); fileSorter.sort(filePath, resultPath); } }