Эффективно объединить много коротких отсортированных списков в длинный отсортированный список

Question

Я неоднократно объединяю 10000 отсортированных списков в один длинный отсортированный список. Каждый список содержит около 5000 doubles.

double[] result;// this is the single long sorted list
void merge(double[] x){
    double[] newList=new double[x.length+result.length];
    int i=0,j=0;
    while(i<x.length && j<result.length){
        insert the smaller one
        increment i or j;
    }
    if(i<x.length){
        add the rest
    }
    if(j<result.length){
        add the rest
    }
    result=newList;
}

Этот метод каждый раз выделяет новый массив. По мере роста result[] это неэффективно. Любой совет?

Answer 1

У вас явно достаточно памяти, чтобы вместить весь результат (400Мб, не так ли?), Так что, вероятно, вы могли бы вместить весь источник слишком 800Мб - это большое, но не слишком большое? Затем вы можете быстро выделить весь буфер ответов прямо в начале.

Если вы готовы использовать еще больше памяти, вы можете воспользоваться методом «удвоения».

Объедините 1 и 2, чтобы сформировать А1, 3 и 4, чтобы сформировать А2 и т. Д. До A2500 (теперь вы можете сбросить массивы первого уровня)

Затем объедините A1 и A2, чтобы сформировать B1; A3 и A4 для формирования B2 до B1250 (теперь вы сбрасываете массивы A)

И так далее получим C1-C625, D1-D313, E1-E157 ... M1, что является окончательным ответом

Таким образом, любое заданное число перемещается 15 раз, тогда как в настоящее время вы перемещаетесь каждое число 5000 раз.

Answer 2

Вы можете обрабатывать это так же, как ArrayList, и удваивать длину вашего массива каждый раз, когда вам нужно перераспределить, а затем перераспределять только тогда, когда вам не хватает места. Хотя у вас может быть достаточно свободного места в конце, вы сэкономите время на обработку благодаря меньшему количеству выделенных ресурсов. Затем просто выполните слияние с Result и X.

Answer 3

Рассматривайте вашу проблему как часть слияния сортировки слиянием . Создайте 2 массива, достаточно больших, чтобы вместить содержимое всех маленьких списков. Затем используйте их попеременно для исходного и целевого хранилища на этапах слияния.