配列内の最も多い要素の個数を返す【C#】

Nov. 25, 2022, 12:26 p.m. edited Nov. 26, 2022, 2:21 a.m.

#C# 

きっかけ：

競プロまでいかずとも、アルゴリズムの授業でよくやりそうな気がしたので試しに書いてみた。

// ぽにさんのリプ欄・引用リツイート欄のコードを参考にしました。皆さんありがとうございます。
// https://twitter.com/PonixNews/status/1595992175497867264

using System;
using System.Collections.Generic;
using System.Linq;

namespace Wandbox
{
    class Program
    {
        const int LENGTH = 8000000; // =: n
        const int MAX_VALUE = 8000000; // =: m

        static int CountMaxNum1(IEnumerable<int> l) {
            // 時間計算量は O(n) か。ただし、辞書が最悪の場合は遅くなることがあるらしい
            // （参考: https://qiita.com/takutoy/items/37e81b916271bf43b527#dictionarytkey-tvalue ）
            // 速いがコードが長い・・・（どうにか LINQ 化できないか？）

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            var countDict = new Dictionary<int, int>();
            foreach(var elem in l) {
                if(!countDict.ContainsKey(elem)) {
                    countDict[elem] = 0;
                }
                ++countDict[elem];
            }

            var result = countDict.Values.Max();

            sw.Stop();

            Console.WriteLine($"CountMaxNum1 time: {sw.ElapsedMilliseconds} msec.");
            Console.WriteLine($"result: {result}");
            return result;
        }

        static int CountMaxNum2(IEnumerable<int> l) {
            // 時間計算量は O(mn)
            // 長さ m の配列それぞれに時間計算量 O(n) の Count() を実行しているため
            // 参考. Count() の計算量: https://qiita.com/aka-nse/items/e3d9eeef884d7ad7733c#%E9%9B%86%E8%A8%88%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            var result = l.Distinct().Select(a=>l.Count(x=>x==a)).Max();

            sw.Stop();

            Console.WriteLine($"CountMaxNum2 time: {sw.ElapsedMilliseconds} msec.");
            Console.WriteLine($"result: {result}");
            return result;
        }

        static int CountMaxNum3(IEnumerable<int> list) {
            // 時間計算量は O(n) + O(m × 重複した要素の数) か？
            // GroupBy が O(n)
            // その後、できた O(m) の長さの配列それぞれの要素について O(重複した要素の数) だけかかる Count() を実行しているため

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            var result = list.GroupBy(l => l).Select(l => l.Count()).Max();

            sw.Stop();

            Console.WriteLine($"CountMaxNum3 time: {sw.ElapsedMilliseconds} msec.");
            Console.WriteLine($"result: {result}");
            return result;
        }

        static void Main(string[] args)
        {
            //var l = new int[] {0,1,1,2,2,2,2,3,3,4,5}; // もともとのぽにさん配列

            var l = new List<int>();
            var rnd = new Random();
            for(var i = 0; i < LENGTH; ++i) {
                l.Add(rnd.Next(MAX_VALUE));
            }

            //for(var i = 0; i < 10; ++i) { // 念のための乱数列チェック
            //    Console.WriteLine(l[i]);
            //}

            CountMaxNum1(l);
            //CountMaxNum2(l); // n, m を大きくしすぎると終わらなくなる
            CountMaxNum3(l);
        }
    }
}

書いたのは CountMaxNum1。最もシンプルな方法は配列のインデックスに要素の値を入れて、同じ要素が出るたびに +1 するというもの。これなら時間計算量は配列の長さ \(O(n)\) で済む。ただ、入れる値の大きさにより色々工夫が必要で面倒なので、今回は C# なので Dictionary を使用した。今回は遅くなるケースに該当しないだろうと踏んでいる。多分。（一応、 var countDict = new Dictionary<int, int>(MAX_VALUE * 2); でも実験したが大して速度は変わらなかった）

LINQ 実装は思いついたら追記する。

速度比較結果

コメントに軽く書いたように、配列の長さを \(n\)、取りうる乱数（整数）の範囲を \([0,m)\) とする。

実験環境は wandbox。

\(n=1000,m=1000\)

CountMaxNum1 CountMaxNum2 CountMaxNum3
5 msec. 6 msec. 1 msec.

\(n=50000,m=50000\)

CountMaxNum1 CountMaxNum2 CountMaxNum3
8 msec. 9870 msec. 8 msec.

\(n=8000000,m=8000000\)

CountMaxNum1 CountMaxNum2 CountMaxNum3
1354 msec. 時間超過で kill された 6241 msec.

\(n=1000000,m=10\)

CountMaxNum1 CountMaxNum2 CountMaxNum3
40 msec. 89 msec. 23 msec.

\(n=100000000,m=10\)

CountMaxNum1 CountMaxNum2 CountMaxNum3
3379 msec. 8664 msec. メモリ不足で例外を出して終了

ツイート

以上。

< Pell's Equatio…

#Quantum Zoo #量子情報 #量子力学 
MathJaxの描画がプレビ… >

#LaTeX 

Tags