遅い→起動時

http://d.hatena.ne.jp/pmint/

先頭集団を求めるアルゴリズム (2)

d:id:pmint:20130528の続き。


まとめようと思ったけれど、駄目だったよ。

コード(C#)
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication2013_05_28
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<int, float> func = (d => (float)d);
            var data = new List<int> { 10, 9, 8, 5, 4, 3, -1, -2 };
            //Func<string, float> func = (d => float.Parse(d));
            //var data = new List<string> { "10", "9", "8", "5", "4", "3", "-1", "-2" };

            Console.Out.WriteLine("data:\t\t{{ {0} }}\t({1})", string.Join(", ", data), data.Count());

            var topGroup = TopGroupOf<int>(data, func);
            //var topGroup = TopGroupOf<string>(data, func);
            Console.Out.WriteLine("topGroup:\t\t{{ {0} }}\t({1})", string.Join(", ", topGroup), topGroup.Count());
        }

        static private IEnumerable<Tuple<T, float>> _scores<T>(IEnumerable<T> target, Func<T, float> toScoreFunc)
        {
            var ret = new List<Tuple<T, float>> { };
            {
                var sorted = target.OrderByDescending(d => toScoreFunc(d));
                var _datum = sorted.First();
                foreach (var datum in sorted)
                {
                    float diff = toScoreFunc(_datum) - toScoreFunc(datum);
                    ret.Add(new Tuple<T, float>(datum, diff));
                    _datum = datum;
                }
            }
            return ret;
        }

        static IEnumerable<T> TopGroupOf<T>(IEnumerable<T> group, Func<T, float> toScoreFunc)
        {
            var scores = _scores<T>(group, toScoreFunc);
                Console.Out.WriteLine("scores :\t{{ {0} }}\t({1})", string.Join(", ", scores), scores.Count());

            var diffs = scores.Select(e => e.Item2);
            var scores2 = _scores<float>(diffs, (d => (float)d));
                Console.Out.WriteLine("scores2:\t{{ {0} }}\t({1})", string.Join(", ", scores2), scores2.Count());

            var threshould2 = scores2.OrderByDescending(d => d.Item2).ToList().First();         //// Max()
            var topgroup2 = scores2.TakeWhile(e => !e.Equals(threshould2)).Select(e => e.Item1);
                Console.Out.WriteLine("scores2-threshould:\t{0}", threshould2);

            var threshould = scores.First(e => topgroup2.Contains(e.Item2));                          //// Find
            var topgroup = scores.TakeWhile(e => !e.Equals(threshould)).Select(e => e.Item1);
                Console.Out.WriteLine("scores-threshould:\t{0}", threshould);

            return topgroup;
        }
    }
}


実行結果。

data:           { 10, 9, 8, 5, 4, 3, -1, -2 }   (8)
scores :        { (10, 0), (9, 1), (8, 1), (5, 3), (4, 1), (3, 1), (-1, 4), (-2, 1) }   (8)
scores2:        { (4, 0), (3, 1), (1, 2), (1, 0), (1, 0), (1, 0), (1, 0), (0, 1) }      (8)
scores2-threshould:     (1, 2)
scores-threshould:      (5, 3)
topGroup:               { 10, 9, 8 }    (3)

{ 10, 9, 8, 5, 4, 3, -1, -2 } (要素数8)の先頭集団は { 10, 9, 8 } の3つ。

メモ

以下、まとまらなかったメモ。

再帰はしないほうがいい。繰り返しても結果は一緒だし。


「先頭集団を求めること」を抽象化すると…トップクラス(最大級)の部分集合を選び出すということ。
つまり曖昧な最大値判定。


ソートした数列の「前要素との差」を求めて、その先頭集団を求めると…差の開いているところが網羅できると。
で、それらのうちの(ソート前の数列上で)先頭に近い位置にある「差の開き」で数列を分割すると、より人の感覚に近い先頭集団判定ができると。


入力データをソートしてから「前要素との差」を算出

(前要素との)差を入力データにする

入力データをソートしてから「前要素との差」を算出(差の差)、最大の差(差の差のうちの最大)を探す

最大''級''の隔たり

…のうちのもっとも先頭にある1件…までが入力データの先頭集団


「ソートして差を求める」というのは元々の差ではないので、入力データ上に存在しない差(隔たり)になっている。無意味。