1

我在做一个硬件问题时发现了一些有趣的东西。

howework 问题要求对中值维护算法进行编码。

正式声明如下：

这个问题的目标是实现“中值维护”算法（在第 5 周的堆应用讲座中介绍）。文本文件包含从 1 到 10000 的整数列表，未排序；您应该将其视为一串数字，一个接一个到达。令x i表示文件的第 i个数字，第 k个中值 m k定义为数字 x 1 ,…,x k的中值。（所以，如果 k 是奇数，那么 m k是 x 1 ,…,x k中第((k+1)/2)个最小的数；如果 k 是偶数，则 m 1是第 (k/2)个最小的数x之间的数字1 ,…,x k .)

为了获得O(n)的运行时间，这显然应该使用堆来实现。无论如何，我使用蛮力进行了编码（截止日期太早，需要立即得到答案）（O(n 2 )），步骤如下：

  1. 读入数据
  2. 排序数组
  3. 查找中位数
  4. 将其添加到运行时间

我通过几个测试用例（具有已知答案）运行该算法并得到正确的结果，但是当我在更大的数据集上运行相同的算法时，我得到了错误的答案。我正在使用 Int64 ro 进行所有操作来表示数据。然后我尝试切换到 Int32，神奇地我得到了正确的答案，这对我来说毫无意义。

代码在下面，也可以在这里找到（数据在 repo 中）。该算法在 3810 索引后开始给出错误结果：

    private static void Main(string[] args)
    {
        MedianMaintenance("Question2.txt");
    }

    private static void MedianMaintenance(string filename)
    {
        var txtData = File.ReadLines(filename).ToArray();
        var inputData32 = new List<Int32>();
        var medians32 = new List<Int32>();
        var sums32 = new List<Int32>();
        var inputData64 = new List<Int64>();
        var medians64 = new List<Int64>();
        var sums64 = new List<Int64>();
        var sum = 0;
        var sum64 = 0f;
        var i = 0;
        foreach (var s in txtData)
        {
            //Add to sorted list
            var intToAdd = Convert.ToInt32(s);

            inputData32.Add(intToAdd);
            inputData64.Add(Convert.ToInt64(s));

            //Compute sum
            var count = inputData32.Count;
            inputData32.Sort();
            inputData64.Sort();
            var index = 0;

            if (count%2 == 0)
            {
                //Even number of elements
                index = count/2 - 1;
            }
            else
            {
                //Number is odd
                index = ((count + 1)/2) - 1;
            }
            var val32 = Convert.ToInt32(inputData32[index]);
            var val64 = Convert.ToInt64(inputData64[index]);
            if (i > 3810)
            {
                var t = sum;
                var t1 = sum + val32;
            }
            medians32.Add(val32);
            medians64.Add(val64);
            //Debug.WriteLine("Median is {0}", val);
            sum += val32;
            sums32.Add(Convert.ToInt32(sum));
            sum64 += val64;
            sums64.Add(Convert.ToInt64(sum64));
            i++;
        }
        Console.WriteLine("Median Maintenance result is {0}", (sum).ToString("N"));
        Console.WriteLine("Median Maintenance result is {0}", (medians32.Sum()).ToString("N"));

        Console.WriteLine("Median Maintenance result is {0} - Int64", (sum64).ToString("N"));
        Console.WriteLine("Median Maintenance result is {0} - Int64", (medians64.Sum()).ToString("N"));
    }

更有趣的是，运行总和（在 sum64 变量中）产生的结果与使用 LINQ 的 Sum() 函数对列表中的所有项目求和产生的结果不同。

结果（第三个是错误的）： 控制台应用程序结果

这些是计算机详细信息： 电脑详情

如果有人能给我一些关于为什么会发生这种情况的见解，我将不胜感激。

谢谢，

4

2 回答 2

1

0f 正在初始化一个 32 位浮点变量，你的意思是 0d 或 0.0 接收一个 64 位浮点数。

至于 linq，如果您使用强类型列表，您可能会得到更好的结果。

new List<int>()
new List<long>()
于 2015-03-09T18:47:34.170 回答
1

我注意到的第一件事是评论者所做的：var sum64 = 0f将 sum64 初始化为浮点数。由于 Int64 集合的中值本身就是 Int64（指定的规则不使用偶基数集合中两个中点值之间的平均值），因此您应该将此变量显式声明为long. 事实上，我会继续替换var此代码示例中的所有用法；var导致类型相关的错误在这里失去了便利。

于 2015-03-09T18:53:30.350 回答