c# - オーバーフロー例外のない平均関数

Question

.NET フレームワーク 3.5。
かなり大きな数の平均を計算しようとしています。
例えば：

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var items = new long[]
                        {
                            long.MaxValue - 100, 
                            long.MaxValue - 200, 
                            long.MaxValue - 300
                        };
        try
        {
            var avg = items.Average();
            Console.WriteLine(avg);
        }
        catch (OverflowException ex)
        {
            Console.WriteLine("can't calculate that!");
        }
        Console.ReadLine();
    }
}

明らかに、数学的な結果は 9223372036854775607 ( long.MaxValue - 200) ですが、そこで例外が発生します。これは、.NET Reflector によって検査されるように、Average 拡張メソッドへの (私のマシンでの) 実装が次のとおりであるためです。

public static double Average(this IEnumerable<long> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    long num = 0L;
    long num2 = 0L;
    foreach (long num3 in source)
    {
        num += num3;
        num2 += 1L;
    }
    if (num2 <= 0L)
    {
        throw Error.NoElements();
    }
    return (((double) num) / ((double) num2));
}

BigInt ライブラリを使用できることは知っています (そうです、.NET Framework 4.0 に含まれていることは知っていますが、3.5 に縛られています)。

しかし、外部ライブラリなしで整数の平均を計算するかなり単純な実装があるかどうかはまだ疑問です。そのような実装についてたまたま知っていますか？

ありがとう！！

アップデート：

前の 3 つの大きな整数の例は、オーバーフローの問題を説明するための単なる例です。問題は、タイプの最大値を超える大きな数になる可能性のある数値のセットの平均を計算することです。この混乱について申し訳ありません。さらに混乱を避けるために、質問のタイトルも変更しました。

皆さんありがとう！！

score 18 · Accepted Answer

この回答は、商と剰余 (mod カウント) を別々に保存することを提案していました。そのソリューションは、スペース効率が低く、コードがより複雑です。

平均を正確に計算するには、合計を追跡する必要があります。精度を犠牲にするつもりがない限り、これを回避する方法はありません。巧妙な方法で合計を保存しようとすることはできますが、アルゴリズムが正しい場合、最終的には追跡する必要があります。

シングルパスアルゴリズムの場合、これは簡単に証明できます。これらのアイテムを処理した後のアルゴリズム全体の状態を考えると、先行するすべてのアイテムの合計を再構築できないとします。しかし、待ってください。アルゴリズムをシミュレートし、シーケンスを終了するまで一連の 0 アイテムを受け取ることができます。次に、結果にカウントを掛けて合計を取得できます。矛盾。したがって、シングルパスアルゴリズムは、何らかの意味で合計を追跡する必要があります。

したがって、最も単純な正しいアルゴリズムは、アイテムを合計してカウントで割るだけです。必要なのは、合計を格納するのに十分なスペースを持つ整数型を選択することだけです。BigInteger を使用すると問題が発生しないことが保証されるため、使用することをお勧めします。

var total = BigInteger.Zero
var count = 0
for i in values
    count += 1
    total += i
return total / (double)count //warning: possible loss of accuracy, maybe return a Rational instead?

score 13 · Accepted Answer

算術平均だけを探している場合は、次のように計算できます。

public static double Mean(this IEnumerable<long> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }

    double count = (double)source.Count();
    double mean = 0D;

    foreach(long x in source)
    {
        mean += (double)x/count;
    }

    return mean;
}

編集：

コメントに応じて、多数の分割と追加を実行するため、この方法では確実に精度が失われます。質問で示された値については、これは問題にはなりませんが、考慮すべき事項です。

score 7 · Accepted Answer

次のアプローチを試すことができます。

要素の数をNとし、数をarr[0]、..、arr[N-1] とします。

2 つの変数を定義する必要があります。

平均と残り。

最初はmean = 0, remainder = 0.

ステップiで、次の方法で平均と剰余を変更する必要があります。

mean += arr[i] / N;
remainder += arr[i] % N;
mean += remainder / N;
remainder %= N;

Nステップ後、平均変数で正しい答えが得られ、残り/ Nは答えの小数部分になります(必要かどうかはわかりませんが、とにかく)

score 2 · Accepted Answer

LINQによる簡単な答え...

var data = new[] { int.MaxValue, int.MaxValue, int.MaxValue };
var mean = (int)data.Select(d => (double)d / data.Count()).Sum();

セットされたデータのサイズに応じて、強制するdata .ToList()か.ToArray()、プロセスの前にこのメソッドを実行して、パスごとにカウントを再クエリできないようにすることができます。（または、前に呼び出すことができます.Select(..).Sum()。）

score 2 · Accepted Answer

この問題が発生した場合の対処方法を次に示します。まず、被除数と除数の 2 つのプロパティと、2 つの複素数を加算する演算子を含む非常に単純な RationalNumber クラスを定義しましょう。これがどのように見えるかです：

public sealed class RationalNumber
{
    public RationalNumber()
    {
        this.Divisor = 1;
    }


    public static RationalNumberoperator +( RationalNumberc1, RationalNumber c2 )
    {
        RationalNumber result = new RationalNumber();

        Int64 nDividend = ( c1.Dividend * c2.Divisor ) + ( c2.Dividend * c1.Divisor );
        Int64 nDivisor = c1.Divisor * c2.Divisor;
        Int64 nReminder = nDividend % nDivisor;

        if ( nReminder == 0 )
        {
            // The number is whole
            result.Dividend = nDividend / nDivisor;
        }
        else
        {
            Int64 nGreatestCommonDivisor = FindGreatestCommonDivisor( nDividend, nDivisor );

            if ( nGreatestCommonDivisor != 0 )
            {
                nDividend = nDividend / nGreatestCommonDivisor;
                nDivisor = nDivisor / nGreatestCommonDivisor;
            }

            result.Dividend = nDividend;
            result.Divisor = nDivisor;
        }

            return result;
    }


    private static Int64 FindGreatestCommonDivisor( Int64 a, Int64 b)
    {
        Int64 nRemainder;

        while ( b != 0 )
        {
            nRemainder = a% b;
            a = b;
            b = nRemainder;
        }

        return a;
    }


    // a / b = a is devidend, b is devisor
    public Int64 Dividend   { get; set; }
    public Int64 Divisor    { get; set; }
}

2番目の部分は本当に簡単です。数値の配列があるとしましょう。それらの平均は Sum(Numbers)/Length(Numbers) によって推定されます。これは Number[ 0 ] / Length + Number[ 1 ] / Length + ... + Number[ n ] / Length と同じです。これを計算できるようにするために、各 Number[ i ] / Length を整数と有理数部分 ( 注意 ) として表します。これがどのように見えるかです：

Int64[] aValues = new Int64[] { long.MaxValue - 100, long.MaxValue - 200, long.MaxValue - 300 };

List<RationalNumber> list = new List<RationalNumber>();
Int64 nAverage = 0;

for ( Int32 i = 0; i < aValues.Length; ++i )
{
    Int64 nReminder = aValues[ i ] % aValues.Length;
    Int64 nWhole = aValues[ i ] / aValues.Length;

    nAverage += nWhole;

    if ( nReminder != 0 )
    {
        list.Add( new RationalNumber() { Dividend = nReminder, Divisor = aValues.Length } );
    }
}

RationalNumber rationalTotal = new RationalNumber();

foreach ( var rational in list )
{
    rationalTotal += rational;
}

nAverage = nAverage + ( rationalTotal.Dividend / rationalTotal.Divisor );

最後に、有理数と整数のリストがあり、それらを合計して、オーバーフローなしでシーケンスの平均を取得します。オーバーフローのない任意の型に対して同じアプローチを採用でき、精度が失われることはありません。

編集：

これが機能する理由:

定義: 一連の数字。

もし平均( A ) = SUM( A ) / LEN( A ) =>

Average( A ) = A[ 0 ] / LEN( A ) + A[ 1 ] / LEN( A ) + A[ 2 ] / LEN( A ) + ..... + A[ N ] / LEN( 2 ) =>

An を次を満たす数として定義すると、An = X + ( Y / LEN( A ) ) になります。A を B で割ると、X が有理数 ( Y / B ) のリマインダ付きで得られるため、これは本質的にそうです。 .

=>そう

Average( A ) = A1 + A2 + A3 + ... + AN = X1 + X2 + X3 + X4 + ... + リマインダー 1 + リマインダー 2 + ...;

部分全体を合計し、リマインダーを有理数の形式に保つことで合計します。最終的に、1 つの整数と 1 つの有理数が得られ、それらを合計すると Average( A ) が得られます。必要な精度に応じて、これを最後の有理数にのみ適用します。

score 2 · Accepted Answer

平均がおよそどのくらいになるかがわかっている場合 (または、少なくとも、すべての数値のペアの最大差が < であることがわかっている場合)、代わりにその値から平均差をlong.MaxValue計算できます。数値が小さい例を取り上げますが、数値が大きい場合でも同様に機能します。

// Let's say numbers cannot exceed 40.
List<int> numbers = new List<int>() { 31 28 24 32 36 29 }; // Average: 30

List<int> diffs = new List<int>();

// This can probably be done more effectively in linq, but to show the idea:
foreach(int number in numbers.Skip(1))
{
    diffs.Add(numbers.First()-number);
}
// diffs now contains { -3 -6 1 5 -2 }

var avgDiff = diffs.Sum() / diffs.Count(); // the average is -1

// To get the average value, just add the average diff to the first value:
var totalAverage = numbers.First()+avgDiff;

もちろん、これを再利用しやすい方法で実装することもできます。たとえば、への拡張メソッドとして実装できますIEnumerable<long>。

score 1 · Accepted Answer

すべての数値が「大きい」(「ゼロよりもはるかに近い」という意味で) になることが事前にわかっている場合は、からの距離の平均を計算できます。数値の平均はそれより小さくなります。long.MaxValuelong.MaxValuelong.MaxValue

ただし、このアプローチは、(m)いずれかの数値がから離れている場合は失敗するため、long.MaxValueコースの馬です...

score 1 · Accepted Answer

実際の実装では BigInteger の助けを借りることをお勧めしますが、その数値型のみを使用しながら安全な方法で特定の数値型の数値を平均化することは実際には可能です。オーバーフローなしで最大 2^32 の int32 を合計できる小さな構造 (Int32WithBoundedRollover) を持つ安全な数値計算用のプロジェクトを作成しました(構造はこれを行うために内部で 2 つの int32 フィールドを使用するため、より大きなデータ型は使用されません)。

この合計を取得したら、合計/合計を計算して平均を取得する必要があります。これは、Int32WithBoundedRollover の別のインスタンスを作成して合計でインクリメントすることで実行できます (お勧めしませんが)。各増分の後、平均の整数部分がわかるまで、それを合計と比較できます。そこから残りをはがして小数部を計算できます。これをより効率的にするための巧妙なトリックがいくつかある可能性がありますが、この基本的な戦略は、より大きなデータ型に頼る必要がなくても確実に機能します。

そうは言っても、現在の実装はこのために構築されていません (たとえば、Int32WithBoundedRollover には比較演算子はありませんが、追加するのはそれほど難しくありません)。その理由は、最後に BigInteger を使用して計算を行う方がはるかに簡単だからです。パフォーマンスに関しては、これは一度しか実行されないため、平均が大きい場合はそれほど重要ではありません。また、クリーンで理解しやすいため、何か賢いことを考え出すことを心配する必要はありません (少なくとも今のところは...)。

long データ型に関する元の質問に関する限り、int32WithBoundedRollover は、int32 参照を長い参照に交換するだけで LongWithBoundedRollover に変換でき、まったく同じように機能するはずです。Int32 の場合、パフォーマンスにかなり大きな違いがあることに気付きました (興味がある場合)。BigInteger のみの方法と比較して、私が作成した方法は、テストしていた大規模な (データポイントの総数など) サンプルで約 80% 高速です (このコードは、Int32WithBoundedRollover クラスの単体テストに含まれています)。これは主に、BigInteger 操作のようにソフトウェアではなくハードウェアで実行される int32 操作の違いによるものと思われます。

score 1 · Accepted Answer

どこかで妥協する必要があると思います。数値が実際に非常に大きくなっている場合、下位の数桁 (下位 5 桁など) は結果にそれほど影響しない可能性があります。

もう 1 つの問題は、特にストリーム/リアルタイムの場合に、入ってくるデータセットのサイズがよくわからない場合です。ここでは、 (previousAverage*oldCount + newValue) / (oldCount <- oldCount+1) 以外の解決策はありません

ここに提案があります：

*LargestDataTypePossible* currentAverage;
*SomeSuitableDatatypeSupportingRationalValues* newValue;

*int* count;
addToCurrentAverage(value){
 newValue = value/100000;
 count = count + 1;
 currentAverage = (currentAverage * (count-1) + newValue) / count;
}

getCurrentAverage(){
 return currentAverage * 100000;
}

score 0 · Accepted Answer

0

大きな数ごとに1回更新するローリング平均を維持できます。

于 2010-05-24T08:13:10.013 に答える

score 0 · Accepted Answer

0

CodePlex でIntXライブラリを使用します。

于 2010-05-24T08:29:00.893 に答える

score 0 · Accepted Answer

0

NextAverage = CurrentAverage + (NewValue - CurrentAverage) / (CurrentObservations + 1)

于 2013-02-26T00:58:12.390 に答える

score 0 · Accepted Answer

0

Visual J# のBigIntegerはどうですか。

于 2010-05-24T08:03:21.747 に答える

score 0 · Accepted Answer

おそらく、調整された値の平均を計算してから、コレクション内の要素の数を掛けることで、すべてのアイテムを減らすことができます。ただし、浮動小数点演算の数が少し異なります。

var items = new long[] { long.MaxValue - 100, long.MaxValue - 200, long.MaxValue - 300 };
var avg = items.Average(i => i / items.Count()) * items.Count();

score 0 · Accepted Answer

精度を犠牲にしたい場合は、次のようにすることができます。

long num2 = 0L;
foreach (long num3 in source)
{
    num2 += 1L;
}
if (num2 <= 0L)
{
    throw Error.NoElements();
}
double average = 0;
foreach (long num3 in source)
{
    average += (double)num3 / (double)num2;
}
return average;

score 0 · Accepted Answer

これは、これに役立つ拡張メソッドの私のバージョンです。

    public static long Average(this IEnumerable<long> longs)
    {
        long mean = 0;
        long count = longs.Count();
        foreach (var val in longs)
        {
            mean += val / count;
        }
        return mean;
    }

score 0 · Accepted Answer

Avg(n) を最初の n 番目の数値の平均とし、data[n] を n 番目の数値とします。

Avg(n)=(double)(n-1)/(double)n*Avg(n-1)+(double)data[n]/(double)n

値のオーバーフローは回避できますが、n が非常に大きい場合は精度が失われます。

score 0 · Accepted Answer

2 つの正の数 (または 2 つの負の数) の場合、ここから非常にエレガントなソリューションを見つけました。

ここで、の平均計算は(a+b)/2に置き換えることができますa+((b-a)/2。

c# - オーバーフロー例外のない平均関数

18 に答える 18

Related

Reference