一次两次递归添加数组中元素的最小和

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

不，这是多相合并的最小值：其中 N 是带宽（您可以同时合并的文件数），那么您希望在每一步合并最小的 (N-1) 个文件.但是，对于这个更普遍的问题，您希望尽可能长时间地延迟较大的文件——您可能希望早期的一两个步骤合并少于 (N-1) 个文件，有点像 "bye"淘汰赛。您希望后面的所有步骤都涉及完整的 (N-1) 个文件。

例如，给定 N=4 和文件 1, 6, 7, 8, 14, 22:

早期合并：

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

后期合并：

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

Answer 2

一旦你有了排序列表，因为你只是删除了两个最少的项目并用一个替换它们，所以进行排序插入并将新项目放在正确的位置而不是 re-sorting 整个列表。但是，这只节省了一小部分时间 - 大约快了 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
Return 列表中的唯一元素。也就是说，这将是您处理每个项目所花费的最短时间。

如果您觉得有帮助，可以关注我的 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

正如在其他答案中已经讨论的那样，最好的策略是始终以每次迭代的最小成本处理这两个项目。那么剩下的唯一问题就是每次如何高效的取两个最小的item了。

既然你要求最好的性能，我厚颜无耻地从 NetMage 中获取算法并修改它以将我的测试用例加速大约 40%（感谢和 +1 到 NetMage）。

我们的想法是主要在单个阵列上就地工作。每次迭代将起始索引增加 1 并移动数组中的元素以使当前迭代的总和为 space。

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 之间切换），random-seed、元素计数和初始项的最大值有几个不同的值。

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

我的 CostOfMerge2：

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

当然，详细数字取决于硬件，差异可能会更大或更小，具体取决于负载量。

一次两次递归添加数组中元素的最小和

Minimum sum of recursive adding of elements in an array two a time

c#

algorithm

recursion

recursive-datastructures

data-structures