1

HW の質問をしているときに興味深いものを見つけました。

Howework の質問では、Median Maintenance アルゴリズムをコーディングするように求められます。

正式な声明は次のとおりです。

この問題の目標は、"Median Maintenance" アルゴリズムを実装することです (第 5 週のヒープ アプリケーションに関する講義で取り上げます)。テキスト ファイルには、1 から 10000 までの整数のリストがソートされていない順序で含まれています。これは、1 つずつ到着する数値のストリームとして扱う必要があります。ファイルの i番目の番号を x 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に切り替えてみましたが、魔法のように正しい答えが得られましたが、意味がありません。

コードは以下にあり、ここにもあります(データはリポジトリにあります)。アルゴリズムは、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

私が最初に気付くのは、コメント投稿者が行ったことvar sum64 = 0fです。つまり、sum64 を float として初期化します。Int64 のコレクションの中央値自体が Int64 になるため (指定された規則では、カーディナリティが偶数のコレクション内の 2 つの中間値の平均は使用されません)、代わりに、この変数を として明示的に宣言する必要がありますlong。var実際、このコード例の の使用箇所をすべて置き換えます。varここでは、型関連のバグを引き起こすことで利便性が失われています。

于 2015-03-09T18:53:30.350 に答える