Минимальная сумма рекурсивного добавления элементов в массив два раза

Question

У меня есть массив целых чисел.Значение каждого элемента представляет время, затраченное на обработку файла.Обработка файлов состоит из объединения двух файлов одновременно.По какому алгоритму можно найти минимальное время, которое можно потратить на обработку всех файлов.Например - {3,5,9,12,14,18}.

Время обработки может быть рассчитано как - Случай 1) -

a) [8],9,12,14,18
b) [17],12,14,18
c) [26],17,18
d) 26,[35]
e) 61

Таким образом, общее время обработки61 + 35 + 26 + 17 + 8 = 147

Случай 2) -

a) [21],5,9,12,14
b) [17],[21],9,14
c) [21],[17],[23]
d) [40],[21]
e) 61

На этот раз общее время составляет 61 + 40 + 23 + 17 + 21 = 162

Мне кажется, что непрерывная сортировка массива и добавление как минимум двух элементов является лучшей ставкой для минимума, как в случае 1. Правильна ли моя логика?Если нет, то какой правильный и самый простой способ добиться этого с максимальной производительностью?

Answer 1

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

Поскольку вы просили о лучшей производительности, я бесстыдно взял алгоритм из NetMage и изменил его, чтобы ускорить его примерно на 40% для моего теста (спасибо и +1 к NetMage ).

Идея состоит в том, чтобы работать в основном на одном массиве. Каждая итерация увеличивает начальный индекс на 1 и перемещает элементы в массиве, чтобы освободить место для суммы из текущей итерации.

public static long CostOfMerge2(this IEnumerable<int> psrc)
{
    long total = 0;

    var src = psrc.ToArray();
    Array.Sort(src);

    var i = 1;
    int length = src.Length;
    while (i < length)
    {
        var sum = src[i - 1] + src[i];

        total += sum;

        // find insert position for sum
        var index = Array.BinarySearch(src, i + 1, length - i - 1, sum);
        if (index < 0)
            index = ~index;
        --index;

        // shift items that come before insert position one place to the left
        if (i < index)
            Array.Copy(src, i + 1, src, i, index - i);

        src[index] = sum;

        ++i;
    }

    return total;
}

Я проверил следующий код вызова (переключение между CostOfMerge и CostOfMerge2), с несколькими различными значениями для случайного начального числа, числа элементов и максимального значения начальных элементов.

static void Main(string[] args)
{
    var r = new Random(10);

    var testcase = Enumerable.Range(0, 400000).Select(x => r.Next(1000)).ToList();
    var sw = Stopwatch.StartNew();
    long resultCost = testcase.CostOfMerge();
    sw.Stop();
    Console.WriteLine($"Cost of Merge: {resultCost}");
    Console.WriteLine($"Time of Merge: {sw.Elapsed}");
    Console.ReadLine();
}

Результат для показанной конфигурации для NetMage CostOfMerge:

Cost of Merge: 3670570720
Time of Merge: 00:00:15.4472251

My CostOfMerge2:

Cost of Merge: 3670570720
Time of Merge: 00:00:08.7193612

Конечно, подробные числа зависят от аппаратного обеспечения, и разница может быть больше или меньше в зависимости от загруженности.

Answer 2

После того, как у вас есть отсортированный список, поскольку вы удаляете только два минимальных элемента и заменяете их одним, имеет больше смысла сделать отсортированную вставку и поместить новый элемент в правильное место, а не заново сортировать весьсписок.Тем не менее, это экономит лишь часть времени - примерно на 1% быстрее.

Мой метод CostOfMerge не предполагает, что входное значение равно List, но если это так, вы можете удалить преобразование ToList шаг.

public static class IEnumerableExt {
    public static int CostOfMerge(this IEnumerable<int> psrc) {
        var src = psrc.ToList();
        src.Sort();
        while (src.Count > 1) {
            var sum = src[0]+src[1];
            src.RemoveRange(0, 2);

            var index = src.BinarySearch(sum);
            if (index < 0)
                index = ~index;
            src.Insert(index, sum);

            total += sum;
        }
        return total;
    }
}

Answer 3

Здесь вы можете применить следующую логику для получения желаемого результата.

1. Получить первые два минимальных значения из списка.
2. Удалить первые два минимальных значения из списка.
3. Добавить сумму первых двух минимальных значений в списке
4. И продолжайте, пока список не станет размером 1
5. Возвращает единственный элемент из списка. т. е. это будет минимальное время, необходимое для обработки каждого элемента.

Вы можете следить за моим Java-кодом, если вы найдете это полезным .. :)

public class MinimumSums {
   private static Integer getFirstMinimum(ArrayList<Integer> list) {
    Integer min = Integer.MAX_VALUE;

    for(int i=0; i<list.size(); i++) {
        if(list.get(i) <= min)
            min = list.get(i);
    }

    return min;
}

private static Integer getSecondMinimum(ArrayList<Integer> list, Integer firstItem) {
    Integer min = Integer.MAX_VALUE;

    for(int i=0; i<list.size(); i++) {
        if(list.get(i) <= min && list.get(i)> firstItem)
            min = list.get(i);
    }
    return min;
}
public static void main(String[] args) {
    Integer[] processes = {5, 9, 3, 14, 12, 18};

    ArrayList<Integer> list = new ArrayList<Integer>();
    ArrayList<Integer> temp = new ArrayList<Integer>();

    list.addAll(Arrays.asList(processes));

    while(list.size()!= 1) {
        Integer firstMin = getFirstMinimum(list); // getting first min value
        Integer secondMin = getSecondMinimum(list, firstMin); // getting second min

        list.remove(firstMin);
        list.remove(secondMin);

        list.add(firstMin+secondMin);
        temp.add(firstMin + secondMin);
    }

    System.out.println(temp); // prints all the minimum pairs.. 
    System.out.println(list.get(0)); // prints the output

}

}

Answer 4

Нет, это минимум для многофазного слияния: где N - пропускная способность (количество файлов, которые вы можете объединить одновременно), тогда вы хотите объединить наименьшие (N-1) файлы на каждом шаге. Однако, с этой более общей проблемой, вы хотите отложить большие файлы как можно дольше - вы можете захотеть, чтобы один или два ранних шага объединили меньше, чем (N-1) файлов, что-то вроде «пока» в исключении турнир. Вы хотите, чтобы все последние шаги включали полные (N-1) файлы.

Например, для N = 4 и файлов 1, 6, 7, 8, 14, 22:

Раннее слияние:

[22], 14, 22
[58]
total = 80

Позднее объединение:

[14], 8, 14, 22
[58]
total = 72