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

#C# 

きっかけ：

C＃で、{0,1,1,2,2,2,2,3,3,4,5}みたいに数値が入ってて、一番多い個数を返す方法ってないのだろうか...
上の場合2の数は4って返すのは
mylist.Count(n => n == 2));でできるみたいだけども

— ぽに@Unityで「あの頃のMMO風ソロRPG」制作中 (@PonixNews) November 25, 2022

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

// ぽにさんのリプ欄・引用リツイート欄のコードを参考にしました。皆さんありがとうございます。
// 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\)

\(n=50000,m=50000\)

\(n=8000000,m=8000000\)

\(n=1000000,m=10\)

\(n=100000000,m=10\)

ツイート

ブログネタになるなぁと思いながら要素数 8000000 で速度の比較実験してみました（CountMaxNum1 が Count() を使わずに書いてみたもの）： https://t.co/9lVfETM0Ef
やはりメソッドの Count() を使うとボトルネックになることが多そうですねー（時と場合による）

— オークル (@orclecle) November 25, 2022

以上。