中值维护算法 - 相同的实现会根据 Int32 或 Int64 产生不同的结果

Question

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

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

正式声明如下：

The goal of this problem is to implement the "Median Maintenance" algorithm (covered in the Week 5 lecture on heap applications). The text file contains a list of the integers from 1 to 10000 in unsorted order; you should treat this as a stream of numbers, arriving one by one. Letting x_i denote the i^th number of the file, the k^th median m_k is defined as the median of the numbers x₁,…,x_k. (So, if k is odd, then m_k is ((k+1)/2)^th smallest number among x₁,…,x_k; if k is even, then m₁ is the (k/2)^th smallest number among x₁,…,x_k.)

为了获得 O(n) 运行时间，这显然应该使用堆来实现。无论如何，我使用 Brute Force 对此进行了编码（截止日期太早，需要立即回答）（O（n²））具有以下内容步骤：

读取
排序数组
求中位数
添加到运行时间

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

代码在下面，也找到了here（数据在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() 函数对列表中的所有项目求和。

结果（第三个是错误的）：

这些是计算机的详细信息：

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

谢谢，

Answer 1

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

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

new List<int>()
new List<long>()

Answer 2

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

中值维护算法 - 相同的实现会根据 Int32 或 Int64 产生不同的结果

Median Maintenance Algorithm - Same implementation yields different results depending on Int32 or Int64

c#

algorithm

integer

int32

int64