Учитывая n файлов с их длинами, делите общее количество байтов поровну между d потоками в равной степени так, чтобы любые два потока отличались не более чем на 1 байт.

Question

Вам дан список имен файлов и их длины в байтах.

Пример:

Файл1: 200 Файл2: 500 Файл3: 800

Вам дано число N. Мы хотим запустить N потоков, чтобы читать все файлы параллельно, чтобы каждый поток примерно считывал равное количество байтов. Вы должны вернуть N списков. Каждый список описывает работу одного потока: Пример, когда N = 2, есть два потока. В приведенном выше примере всего 1500 байт (200 + 500 + 800). Фарватер для деления - для каждого потока читать 750 байт. Итак, вы вернетесь:

Два списка

Список 1: Файл1: 0 - 199 Файл2: 0 - 499 Файл3: 0-49 ---------------- Всего 750 байт

Список 2: Файл3: 50-799 -------------------- Всего 750 байт

Реализуйте следующий метод

List<List<FileRange>> getSplits(List<File> files, int N) 
Class File { 
String filename; long length } 
Class FileRange { 
String filename Long startOffset Long endOffset } 
I tried with this one but it's not working any help would be highly appreciated.
List<List<FileRange>> getSplits(List<File> files, int n) {
        List<List<FileRange>> al=new ArrayList<>();
        long s=files.size();
        long sum=0;
        for(int i=0;i<s;i++){
            long l=files.get(i).length;
            sum+=(long)l;
        }
        long div=(long)sum/n; // no of bytes per thread
        long mod=(long)sum%n;
        long[] lo=new long[(long)n];
        for(long i=0;i<n;i++)
        lo[i]=div;
        if(mod!=0){
            long i=0;
            while(mod>0){
                lo[i]+=1;
                mod--;
                i++;
            }
        }
        long inOffset=0;
        for(long j=0;j<n;j++){
            long val=lo[i];
        for(long i=0;i<(long)files.size();i++){
            String ss=files.get(i).filename;
            long ll=files.get(i).length;
                if(ll<val){
                    inOffset=0;
                    val-=ll;
                }
                else{
                    inOffset=ll-val;
                    ll=val;
                }
                al.add(new ArrayList<>(new File(ss,inOffset,ll-1)));
            }
        }

    }

У меня проблема с startOffset и endOffset с соответствующим файлом. Я попытался, но мне не удалось извлечь из List и добавить в виде требуемого типа возвращаемого значения List>.

Answer 1

Суть проблемы в том, чтобы одновременно пройтись по двум спискам:

• список ввода, представляющий собой список файлов
• список вывода, представляющий собой список потоков (где каждый поток имеет список диапазонов)

Я считаю, что самый простой подход к таким проблемам - это бесконечный цикл, который выглядит примерно так:

while (1)
{
    move some information from the input to the output
    decide whether to advance to the next input item
    decide whether to advance to the next output item
    if we've reached (the end of the input _OR_ the end of the output)
        break
    if we advanced to the next input item
        prepare the next input item for processing
    if we advanced to the next output item
        prepare the next output item for processing
}

Чтобы отслеживать ввод, нам нужна следующая информация

• fileIndex указатель в список файлов
• fileOffset смещение первого неназначенного байта в файле, изначально 0
• fileRemain количество байтов в файле, которые не были назначены, изначально размер файла

Чтобы отслеживать вывод, нам нужно

• threadIndex индекс потока, над которым мы сейчас работаем (который является первым индексом в List<List<FileRange>>, который генерирует алгоритм)
• threadNeeds количество байтов, которое еще нужно потоку, изначально base или base+1

Примечание: я использую base в качестве минимального числа байтов, назначенных каждому потоку (sum/n), и extra в качестве количества потоков, которые получают дополнительный байт (sum%n).

Итак, теперь мы добрались до сути алгоритма: какую информацию перемещать от входа к выходу:

• если fileRemain меньше threadNeeds, тогда остальная часть файла (который может быть всем файлом) будет присвоена текущей нити, и мы перейдем к следующему файлу
• если fileRemain больше threadNeeds, то часть файла присваивается текущей нити, и мы переходим к следующей нити
• если fileRemain равно threadNeeds, то остальная часть файла назначается потоку, и мы переходим к следующему файлу и следующему потоку

Эти три случая легко обрабатываются путем сравнения fileRemain и threadNeeds и выбора byteCount, который является минимумом из двух.

Имея все это в виду, вот несколько псевдокодов, которые помогут вам начать:

base  = sum/n;
extra = sum%n;

// initialize the input control variables
fileIndex  = 0
fileOffset = 0
fileRemain = length of file 0

// initialize the output control variables
threadIndex = 0
threadNeeds = base
if (threadIndex < extra)
    threadNeeds++

while (1)
{
    // decide how many bytes can be assigned, and generate some output
    byteCount = min(fileRemain, threadNeeds)
    add (file.name, fileOffset, fileOffset+byteCount-1) to the list of ranges

    // decide whether to advance to the next input and output items
    threadNeeds -= byteCount
    fileRemain  -= byteCount
    if (threadNeeds == 0)
        threadIndex++
    if (fileRemain == 0)
        fileIndex++

    // are we done yet?
    if (threadIndex == n || fileIndex == files.size())
        break

    // if we've moved to the next input item, reinitialize the input control variables
    if (fileRemain == 0)
    {
        fileOffset = 0
        fileRemain = length of file
    }

    // if we've moved to the next output item, reinitialize the output control variables
    if (threadNeeds == 0)
    {
        threadNeeds = base
        if (threadIndex < extra)
            threadNeeds++
    }
}

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