検証 - ヽ｜∵｜ゝ(Fantom) の開発blog？

このページの記事一覧

【Unity】【C#】StartsWith, EndsWith が遅いのなら、Equals も遅いのか？

2021/04/18 Sun [edit]

　Unity の公式マニュアルにも掲載されているのだが（ただし、情報が少し古い[Unity5]）、文字列比較の StartsWith, EndsWith は遅いというのは以前から言われていた。実際に、そのページにある「CustomStartsWith」と「CustomEndsWith」と、標準ライブラリの StartsWith, EndsWith の速度比較をしてみると、かなり遅い。

・文字列とテキスト - 非効率的なビルトイン String API

　ただ、その理由を読んでいたら「比較にはローカライズ用のデフォルトカルチャが効いているから」という事らしい（解説には Equals では "encyclopedia", "encyclopædia" のような表記違いは等価とみなすとある）。

　「あれ？それなら Equals も CustomEquals を作った方が良いのでは？」と思ったので、試しに作ってみた。といっても CustomStartsWith とほぼ同じなんだけどね。そしてその速度比較の結果を残しておこう。

(※) Unity 2019.4.21f1 [.NET 4.x] / Windows10(x64) で確認

●公式の CustomStartsWith を真似した単純な Equals

using System;

public static class Extentions  //※名前は任意
{
    /// <summary>
    /// 公式の CustomStartsWith を真似した単純な Equals.
    /// https://docs.unity3d.com/ja/current/Manual/BestPracticeUnderstandingPerformanceInUnity5.html
    /// </summary>
    public static bool CustomEquals(this string a, string b)
    {
        int aLen = a.Length;
        if (aLen != b.Length)
            return false;

        int ap = 0;
        while (ap < aLen && a [ap] == b [ap])
        {
            ap++;
        }

        return (ap == aLen);
    }
}

　また比較には、公式の解説にある「ローカライズ用の調整を必要としない文字列比較に StringComparison.Ordinal を推奨」ともあったので、ついでに加えてみた（また Equals ではオペレータの "==" も加えてある）。以下に比較結果を載せておこう。

●StartsWith, EndsWith, Equlas の標準と Ordinal オプションと Custom～を 100000 回×10回実行して、平均値を計測

●StartsWith
[StandardStartsWith] ave : 0.1930909 [sec]
[StandardStartsWithOrdinal] ave : 0.08576998 [sec]
[CustomStartsWith] ave : 0.08573665 [sec]

●EndsWith
[StandardEndsWith] ave : 1.135096 [sec]
[StandardEndsWithOrdinal] ave : 0.08583274 [sec]
[CustomEndsWith] ave : 0.0840721 [sec]

●Equals
[StandardEquals] ave : 0.09371759 [sec]
[StandardEqualsOrdinal] ave : 0.09588816 [sec]
[OperatorEquals] ave : 0.09638711 [sec]
[CustomEquals] ave : 0.09519003 [sec]

　コンパイルは「.NET 4.x」でやってるからか、意外なことに、特に Equals では誤差範囲くらいしか変わらなかった（ただし、半角英数や日本語だけの場合。他の言語では違いは出るのかも？）。

　Custom～のメソッドには null チェックも付いてないので、それを追加したとしても大して変化は無い。結果を見てみると、どうやら .NET 4.x で日本語や英字ぐらいの範囲なら、StringComparison.Ordinal オプションを付ければ、実行速度は速いらしい。

　もちろん文字列の内容や長さにもよるだろうが、私が試した限りでは、10～100文字程度で日本語・英語混合くらいなら、ほとんど誤差範囲でしか変わらない。なので「a.StartsWith(b, StringComparison.Ordinal)」「a.EndsWith(b, StringComparison.Ordinal)」「a.Equals(b, StringComparison.Ordinal) (※a.Equlas(b) でもなぜか変わらない)」を機械的に使っても、実質問題無いようだ。

　まぁ、標準ライブラリ自体も改修されているからね。Unity の公式マニュアルは Unity5 時代で .NET 3.5 だったので、多少は変わったのかも知れない（実際に .NET 4.x になって GC 発生やコルーチンなども改修されてるとか何とか…）。

・GCの発生要因を減らす

　特に古い情報の場合、一度現在のバージョン・環境で試してみるのも良いかもね。ちなみに Android でやってみても、同じような結果だった。現バージョンでは普段使いなら、Ordinal オプションを付けておけば、Custom～は必要ないようだ。

関連記事

スポンサーサイト

category: Unity

thread: プログラミング

janre: コンピュータ

tag: C#ライブラリ文字列操作検証

tb: 0 cm: --

【Unity】【C#】LINQとfor, ListとArray(配列)での実行速度を比較してみる

2018/11/04 Sun [edit]

　LINQ や List はとても便利だけど、実行速度が遅いという欠点があるので、改めてよく使いそうなコードで比較してみたのを記録しておく。

　私はよくこういう実験をするのだが、気をつけて欲しいのは実行環境やマシンスペック、言語などによっても結果は異なるという点だ。また、コンパイラ等もバージョンによって最適化が入ったりして、高速になる場合もある。今回は C# で Unity 上（主にエディタ上）での実験になってるが、実機ではまた異なる結果が出る場合があるので、あくまでも目安として考えて欲しい。

　ちなみに元ネタではないが、以下の記事でも通常の for, foreach 構文と LINQ の ForEach を実験しているが、特に ForEach が遅かったのが記憶に残っていたので、改めて調べたキッカケだったりする（記事のバージョンが古いので）。だがしかし、現64bitバージョンでも値は２倍速くらいになっているが、結果（比率）は同じだった。例えば for に対してLNQ の ForEach はやはり２倍くらい遅い。こういったデータを公開してくれるのは非常に有り難い。

（参考）
・【Unity】ループ構文の処理速度の検証結果
・CPU のパフォーマンスに関する推奨事項：コストのかかる操作を避ける - LINQ を使わないようにする

■LINQ と for 構文で比較
　●LINQ の ForEach と for の単純アクセス（値取り出し）比較
　●LINQ と for でフィルタ（抽出）の比較
　●LINQ と for で全要素文字列変換の比較
■List と Array(配列)で比較
　●単純なアクセス（値取り出し）の比較
　●ソートの比較
　●シャッフル（Fisher-Yates shuffle）の比較
■結果一覧

(※) Unity 2018.2.1f1（エディタ上）.NET 3.5 / Windows10(x64), Intel Core i5 x64 2.9GHz で確認

■LINQ と for 構文で比較

　ここでは簡単な数値計算でのフィルタと、全要素の文字列を LINQ と単純な for で比較してみよう。データには List を使っているが、Array（配列）にした方が速くなるのはとりあえず置いておいて欲しい(笑)。

　実際の測定方法は以下のコードを１つのメソッドにして、11回実行し、はじめの1回の結果を捨て、残りの10回の平均を出している。なぜはじめの1回を捨ててるかというと、アプリを起動したときには色々な初期化処理が動くので重くなり、測定値が不安定になるからだ（だいたい通常より値が大きくなる）。Unity に限らず、他のプラットフォームでも同じことがよく起こるので、その辺は覚えておくと良いかも知れない。

●LINQ の ForEach と for の単純アクセス（値取り出し）比較

　例えば、順次アクセスしていって、値を取り出すだけのコードを比較してみた。通常はその値を何らかで利用すると考えて欲しい。

①LINQ で書いた場合

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

//前準備
int num = 100000;
List<int> list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

list.ForEach(i => {
    int value = list[i];
});

float elapsed = Time.realtimeSinceStartup - startTime;

Debug.Log("1 : " + elapsed + " [s]"); //0.002561998 [s]

②for で書いた場合

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

//前準備
int num = 100000;
List<int> list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

for (int i = 0; i < num; i++)
{
    int value = list[i];
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]"); //0.001707292 [s]

1 : 0.002561998 [s]
2 : 0.001707292 [s]

　ただ値を取り出しただけで何もしてないが、実行速度は LINQ に比べて for は約1.5倍くらい速かった。要素数が少ないとき（50以下とか）にはあまり気にすることはないとは思うが、要素数が大きくなるほど、その差は大きく出る。大量のデータをスキャン、または変換など処理を施すのには LINQ はとても遅いので気をつけよう（プロコン問題などに使うとタイムアウトすることが多い(笑)）。
※List を配列にした方がもっと速い（約3.1倍：0.0008201599 [s]）。

●LINQ と for でフィルタ（抽出）の比較

　例えば、連続した値の要素から、偶数だけを抽出するコードを比較してみた。

①LINQ で書いた場合

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

//前準備
int num = 10000;
List<int> list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

List<int> list2 = list.Where(e => e % 2 == 0).ToList();

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("1 : " + elapsed + " [s]"); //0.0007956981 [s]

②for で書いた場合

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

//前準備
int num = 10000;
List<int> list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

List<int> list2 = new List<int>(num);
for (int i = 0; i < num; i++)
{
    int value = list[i];
    if (value % 2 == 0)
        list2.Add(value);
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]"); //0.0002808333 [s]

1 : 0.0007956981 [s]
2 : 0.0002808333 [s]

　測定部分では、LINQ はとてもシンプルで、for 文は長々と書いている感じだが、実行速度は LINQ に比べて、単純な for の方が約2.8倍くらい速かった(笑)。特に要素数が大きいときにはこの傾向は強くなる。for 文は昔ながらのとてもダサい(笑)文に見えるが、実は高速なので、Unity のようなフレームアプリケーションには向いているかも知れない(笑)。

●LINQ と for で全要素文字列変換の比較

　例えば、一定の文字列があり、それらを全部小文字にするコードを比較してみた（100個書くのが面倒くさい(笑)ので 10個x10=100個にしている）。

①Linq で書いた場合

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

//前準備
string[] words = {
    "Apple", "Banana", "Candy", "Doughnut", "Egg",
    "Fish", "Grape", "Honey", "IceCream", "Jelly"
};
List<string> list = Enumerable.Repeat(words, 10).SelectMany(a => a).ToList(); //10x10=100個
int num = 1000;

//以下を測定
float startTime = Time.realtimeSinceStartup;

for (int i = 0; i < num; i++)
{
    List<string> list2 = list.Select(e => e.ToLower()).ToList();
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("1 : " + elapsed + " [s]"); //0.04769385 [s]

②for で書いた場合

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

//前準備
string[] words = {
    "Apple", "Banana", "Candy", "Doughnut", "Egg",
    "Fish", "Grape", "Honey", "IceCream", "Jelly"
};
List<string> list = Enumerable.Repeat(words, 10).SelectMany(a => a).ToList(); //10x10=100個
int num = 1000;

//以下を測定
float startTime = Time.realtimeSinceStartup;

for (int i = 0; i < num; i++)
{
    int length = list.Count;
    List<string> list2 = new List<string>(length);
    for (int j = 0; j < length; j++)
    {
        list2.Add(list[j].ToLower());
    }
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]"); //0.03735647 [s]

1 : 0.04769385 [s]
2 : 0.03735647 [s]

　測定部分では、for 文の方では list.Count を length に入れて使っているが、こうすると、ループのたびにプロパティを読み出しに行かなくて済むため、ほんのわずかだが速くなる。生成された list2 の方は特に何も使ってないが、通常は何か処理が入ると考えて欲しい。

　結果はだいたい、LINQ より for で書いたほうが約1.3倍くらい速くなった。思ったより速度は変わらないね。要素数が少ないなら、どちらを使っても良さそう。

　ちなみに for の例で List を全て Array で書き直すとわずかに速くなる（約1.4倍：0.03489325 [s]）。

■List と Array（配列）で比較

　ここではデータ格納先となる List と Array（配列）で速度を比較してみよう。

　これも同じ様に、11回実行し、はじめの1回の結果を捨て、残りの10回の平均を出した測定値だ。単純なものしか書いてないが、実際には何らかの処理が他に入ると考えて欲しい。

●単純なアクセス（値取り出し）の比較

　例えば、順次アクセスしていって、値を取り出すだけのコードを比較してみた。通常はその値を何らかで利用すると考えて欲しい。

①List で書いた場合

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

//前準備
int num = 100000;
List list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

for (int i = 0; i < list.Count; i++)
{
    int value = list[i];
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("1 : " + elapsed + " [s]"); //0.00246439 [s]

②Array で書いた場合

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

//前準備
int num = 100000;
int[] array = Enumerable.Range(0, num).ToArray();

//以下を測定
float startTime = Time.realtimeSinceStartup;

for (int i = 0; i < array.Length; i++)
{
    int value = array[i];
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]"); //0.0008202791 [s]

1 : 0.00246439 [s]
2 : 0.0008202791 [s]

　ただ値を取り出しただけで何もしてないが、実行速度は List に比べて Array（配列）は約3.1倍くらい速かった(笑)。これも要素数が大きくなるほど、その傾向が強くなる。ライブラリ関数も配列を返すものが多いが、もしかしたらその利用の実行速度のためであるかも知れない(笑)。

　ちなみに、二分探索の Array.BinarySearch と List.BinarySearch を比較してみると、要素数が多くなっても、ほとんど違いが出ないようだ。つまりアクセス回数に比例して速度が落ちていることがわかる。

●ソートの比較

　例えば、標準関数にあるソートで比較してみた。

①List で書いた場合

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

//前準備
int num = 100000;
List<int> list = Enumerable.Range(0, num).ToList();
list.Reverse();

//以下を測定
float startTime = Time.realtimeSinceStartup;

list.Sort();

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("1 : " + elapsed + " [s]");  //0.00460794 [s]

②Array（配列）で書いた場合

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

//前準備
int num = 100000;
int[] array = Enumerable.Range(0, num).ToArray();
Array.Reverse(array);

//以下を測定
float startTime = Time.realtimeSinceStartup;

Array.Sort(array);

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]");  //0.002492619 [s]

1 : 0.00460794 [s]
2 : 0.002492619 [s]

　結果は List に比べて Array（配列）でのソートの方が約1.8倍くらい速かった。

　実際には C# のソートは要素数によってアルゴリズムが変わると聞いたことがあるので（例えばクイックソートは要素数が多いときはパフォーマンス良いが、要素数が少ないときは、それほど良くないと言われているので、アルゴリズムを変えるのは有効である）、利用する場合は一度実験しておく方が良いかも知れない。

・50以下挿入ソート、5万以下マージソート、あとはクイックソート

　ちなみに、Reverse（要素の反転）の代わりに、後述するシャッフルを使った場合、以下のようになった。

1 : 0.007369685 [s]
2 : 0.003433919 [s]

　比率としては約2.1倍である。誤差を含めて約2倍と考えても良いだろう。

●シャッフル（Fisher-Yates shuffle）の比較

　例えば、Fisher-Yates アルゴリズムを用いたシャッフル関数を定義し、それを利用して比較してみた。

①List で書いた場合

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

//前準備
int num = 100000;
List<int> list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

list.Shuffle();

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("1 : " + elapsed + " [s]");  //0.00126977 [s]


//拡張メソッドを定義
public static class Extensions
{
    //リストの要素をシャッフルする (Fisher-Yates shuffle)
    public static void Shuffle<T>(this List<T> list)
    {
        for (int i = list.Count - 1; i > 0; i--)
        {
            int j = Random.Range(0, i + 1);  //[0]～[i]
            list.Swap(i, j);
        }
    }

    //要素のスワップ
    public static void Swap<T>(this List<T> list, int i, int j)
    {
        T tmp = list[i];
        list[i] = list[j];
        list[j] = tmp;
    }
}

②Array（配列）で書いた場合

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

//前準備
int num = 100000;
int[] array = Enumerable.Range(0, num).ToArray();

//以下を測定
float startTime = Time.realtimeSinceStartup;

array.Shuffle();

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]");  //0.0006387234 [s]


//拡張メソッドを定義
public static class Extensions
{
    //配列の要素をシャッフルする (Fisher-Yates shuffle)
    public static void Shuffle<T>(this T[] arr)
    {
        for (int i = arr.Length - 1; i > 0; i--)
        {
            int j = Random.Range(0, i + 1);  //[0]～[i]
            arr.Swap(i, j);
        }
    }

    //要素のスワップ
    public static void Swap<T>(this T[] arr, int i, int j)
    {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

1 : 0.00126977 [s]
2 : 0.0006387234 [s]

　このシャッフルは以前に書いたコードそのままである。

　結果は List に比べて Array（配列）でのソートの方が約1.9倍くらい速かった。

　これも誤差を含めて約2倍と考えても良いだろう。

■結果一覧

　以上をまとめると表のようになる。

●LINQ と for 構文での比較

処理内容	実装方法	測定時間	備考
単純なアクセス	LINQ	0.002561998 [s]
単純なアクセス	for	0.001707292 [s]	LINQ より約1.5倍速い
フィルタ(抽出)	LINQ	0.0007956981 [s]
フィルタ(抽出)	for	0.0002808333 [s]	LINQ より約2.8倍速い
全要素文字列変換	LINQ	0.04769385 [s]
全要素文字列変換	for	0.03735647 [s]	LINQ より約1.3倍速い

●List と Array(配列)で比較

処理内容	実装方法	測定時間	備考
単純なアクセス	List	0.00246439 [s]
単純なアクセス	配列	0.0008202791 [s]	List より約3.1倍速い
ソート	List	0.00460794 [s]
ソート	配列	0.002492619 [s]	List より約1.8倍速い
シャッフル	List	0.00126977 [s]
シャッフル	配列	0.0006387234 [s]	List より約1.9倍速い

　今回は単純な反復での比較しかしてないが、他にもアルゴリズムも絡めると実行速度はまた変わる。しかしそれらは言語でも異なるので注意しよう。例えば C#, Java などは文字列操作は遅いが、Ruby, PHP, Perl などは文字列操作はとても速い（=変換も速い）。実際に「数値の桁数を求める」問題があったとして、C#, Java などでは「10で割って数をかぞえる」アルゴリズムが速いが、Ruby, PHP などは「文字列に変換して長さで数える」方が速かったりする。こういったものは測定してみないとわからない。

　プロコン問題（競技プログラミング：AtCoderとか）とか見てても、上のランクほど、for, while, 配列だけで解いている場合が多いのも納得がいく。やはり 0.1秒で合否が分かれる問題などでは（10万件のデータを2秒以内に処理するプログラムとか普通なので）、LINQ や List では遅すぎるというのは体験的に知っているのだろう（事実、大量のデータを処理するには LINQ は向いてないと思う※今後のバージョンアップで改善されるかも知れないが）。

　この結果だけ見ると「LINQ は使わないで単純な構文に」「List は使わないで配列に」のように思えてしまうが、要素数が少ないときはそれほど大差ないので（1000個を超えると結構差が出てくるが、50個以下で１回きりとかなら、それほど差は出ない）、実行速度が欲しいときに、改めて見直すのもヒントとして考えるのも良いだろう。

　Unity 公式ブログにも IL2CPP について『もしあなたが10000個の要素をもつリストをイテレートしたい場合は、Listの代わりに配列を使う方がよいでしょう。なぜならその方が生成されるC++コードがよりシンプルになり、また配列アクセスの方が単純に高速だからです。』とも書いてあるね。長さを変化させる必要が無いなら、機械的に配列にするのも良いかもね。

・Update()を10000回呼ぶ

　またそのうち色々実験したら、追加しておく(笑)。

関連記事

category: Unity

thread: プログラミング

janre: コンピュータ

tag: C# 検証

tb: 0 cm: --

【Unity】【C#】UniRx で「1フレームごと待機して処理」してみる

2018/10/19 Fri [edit]

　今まで「VRM Live Viewer」では非同期処理に「Await Extensions」というライブラリを使っていたのだが、「UniRx」の非同期処理関連の資料を見てたら、同じようなことができるとわかったので、移行してみようと考えた。

　ただ注意しなくてはならないのは、「UniRx」の非同期処理は Scripting Runtime を「.NET 4.x」にすることと、C# 7.0が必須のため、現時点（Unity2018.2.x）では「Incremental Compiler」を導入する必要があるとのことだ。

・UniTask - Unity + async/awaitの完全でハイパフォーマンスな統合

　「Incremental Compiler」はまだ Preview 版のため、商用利用は控えたほうが良いともあるね。まぁ、「VRM Live Viewer」はフリーなのと、色々実験してみたが、安定性にも問題無いようなので（どちらかというと Stable[安定版] が出たら、メソッドの仕様（引数など）が変わって、書き換え必須となることの方が辛いね(笑)）、導入を試みてみたら成功した。実際「UniRx」上で使える「UniTask」は「async/await/Task」の上位互換で、現在私が使っている機能もそのまま移行できたので、基本的な使い方ならば、バージョンアップ・正式版が出てもそれほど問題ないとも思う。また今後UI処理などを少し強化したいしね。そういったものは「UniRx」はとても強い(笑)。

　なので、現時点では導入する人は少ないかも知れないが、「.NET 4.x」の非同期処理「async/await/Task」が使えるようになると、コルーチンで書いていたものがスッキリする上に、別スレッドでバックグラウンド処理などもとても簡単になるので、いずれは誰しも使うようになるだろう(笑)。そしてはじめに使いたいのはやはり、今までコルーチンなどで書いていた「1フレーム待機して処理」かなと(笑)。ググったらなぜかあまりハッキリとした答えがなかったので、ちょっと実験してみた感じ。たぶん他の人も同じことを調べるだろうしね。

(※) Unity 2018.2.1f1 / UniRx 6.2.2 / Incremental Complier 0.0.42(Preview) / Windows10(x64) で確認

■「1フレームごとに待機して処理」っぽくなりそうなものを、色々やってみる

　まずは今まで通り、コルーチンで「1フレームごとに待機して処理」をしてみる。処理自体はただのログ出力なので、実際の処理の重さは考慮に入れてない。ちなみに「Await Extensions」では「yield return new WaitForEndOfFrame()」の代わりに「await new WaitForEndOfFrame()」が使える（そしてメソッドに async が使えるので非同期処理が簡潔に書ける。StartCoroutine() もいらない）。

●コルーチンで1フレームごとに待機して処理（ログ出力のみ。動作の基準）

using System.Collections;
using UnityEngine;

public class EachFrameTest : MonoBehaviour {

    // Use this for initialization
    void Start () {
        Debug.Log("(Start) frame : " + Time.frameCount); //1

        StartCoroutine(WaitForEndOfFrameCoroutineTest());
    }

    IEnumerator WaitForEndOfFrameCoroutineTest()
    {
        Debug.Log("frame : " + Time.frameCount); //1
        yield return new WaitForEndOfFrame();
        Debug.Log("frame : " + Time.frameCount); //2
        yield return new WaitForEndOfFrame();
        Debug.Log("frame : " + Time.frameCount); //3
        yield return new WaitForEndOfFrame();
        Debug.Log("frame : " + Time.frameCount); //4
        yield return new WaitForEndOfFrame();
        Debug.Log("frame : " + Time.frameCount); //5
    }
}

(Start) frame : 1
frame : 1
frame : 2
frame : 3
frame : 4
frame : 5

　なんてことはないコルーチンで順次処理していくときのようなコード（本来は同じ処理ならループにするだろうが、これはあくまでサンプルなので、実際には別々の処理が入ると考えて欲しい）。これを基準として「UniRx」でオペレータなども使って色々試してみよう。なお、ここでは「yield return new WaitForEndOfFrame()」を使っているが、実行タイミングを気にしないなら「yield return null」でも良い。

・イベント関数の実行順

●Observable.NextFrame() で1フレームごとに待機して処理？

using System.Collections;
using UnityEngine;
using UniRx;

public class EachFrameTest : MonoBehaviour {

    // Use this for initialization
    void Start () {
        Debug.Log("(Start) frame : " + Time.frameCount); //1

        ObservableNextFrameTest();
    }

    async void ObservableNextFrameTest()
    {
        Debug.Log("frame : " + Time.frameCount);    //1
        await Observable.NextFrame();
        Debug.Log("frame : " + Time.frameCount);    //3
        await Observable.NextFrame();
        Debug.Log("frame : " + Time.frameCount);    //5
        await Observable.NextFrame();
        Debug.Log("frame : " + Time.frameCount);    //7
        await Observable.NextFrame();
        Debug.Log("frame : " + Time.frameCount);    //9
    }
}

(Start) frame : 1
frame : 1
frame : 3
frame : 5
frame : 7
frame : 9

　UniRx で一番始めに目についたのは「Observable.NextFrame()」だったが、どうやら await で1フレーム、NextFrame() で1フレーム待機のようだ。フレームが１つ飛びになっていた。期待していた処理とは違う。

●Observable.TimerFrame() で1フレームごとに待機して処理（引数＝1）？

using System.Collections;
using UnityEngine;
using UniRx;

public class EachFrameTest : MonoBehaviour {

    // Use this for initialization
    void Start () {
        Debug.Log("(Start) frame : " + Time.frameCount); //1

        ObservableTimerFrameTest();
    }

    async void ObservableTimerFrameTest()
    {
        Debug.Log("frame : " + Time.frameCount);    //1
        await Observable.TimerFrame(1);
        Debug.Log("frame : " + Time.frameCount);    //3
        await Observable.TimerFrame(1);
        Debug.Log("frame : " + Time.frameCount);    //5
        await Observable.TimerFrame(1);
        Debug.Log("frame : " + Time.frameCount);    //7
        await Observable.TimerFrame(1);
        Debug.Log("frame : " + Time.frameCount);    //9
    }
}

(Start) frame : 1
frame : 1
frame : 3
frame : 5
frame : 7
frame : 9

　Observable.NextFrame() と結果は同じになった。ではちょっと引数を０にしてみようと実験してみると…

●Observable.TimerFrame() で1フレームごとに待機して処理（引数＝０）

using System.Collections;
using UnityEngine;
using UniRx;

public class EachFrameTest : MonoBehaviour {

    // Use this for initialization
    void Start () {
        Debug.Log("(Start) frame : " + Time.frameCount); //1

        ObservableTimerFrameTest();
    }

    async void ObservableTimerFrameTest()
    {
        Debug.Log("frame : " + Time.frameCount);    //1
        await Observable.TimerFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //2
        await Observable.TimerFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //3
        await Observable.TimerFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //4
        await Observable.TimerFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //5
    }
}

(Start) frame : 1
frame : 1
frame : 2
frame : 3
frame : 4
frame : 5

　いけた(笑)。これは期待していた処理と合致する。

●Observable.ReturnUnit().DelayFrame() で1フレームごとに待機して処理（引数＝1）？

using System.Collections;
using UnityEngine;
using UniRx;

public class EachFrameTest : MonoBehaviour {

    // Use this for initialization
    void Start () {
        Debug.Log("(Start) frame : " + Time.frameCount); //1

        ObservableDelayFrameTest();
    }

    async void ObservableDelayFrameTest()
    {
        Debug.Log("frame : " + Time.frameCount);    //1
        await Observable.ReturnUnit().DelayFrame(1);
        Debug.Log("frame : " + Time.frameCount);    //3
        await Observable.ReturnUnit().DelayFrame(1);
        Debug.Log("frame : " + Time.frameCount);    //5
        await Observable.ReturnUnit().DelayFrame(1);
        Debug.Log("frame : " + Time.frameCount);    //7
        await Observable.ReturnUnit().DelayFrame(1);
        Debug.Log("frame : " + Time.frameCount);    //9
    }
}

(Start) frame : 1
frame : 1
frame : 3
frame : 5
frame : 7
frame : 9

　これも Observable.NextFrame() と結果は同じになった。では引数を０にしてみると…

●Observable.ReturnUnit().DelayFrame() で1フレームごとに待機して処理（引数＝０）

using System.Collections;
using UnityEngine;
using UniRx;

public class EachFrameTest : MonoBehaviour {

    // Use this for initialization
    void Start () {
        Debug.Log("(Start) frame : " + Time.frameCount); //1

        ObservableDelayFrameTest();
    }

    async void ObservableDelayFrameTest()
    {
        Debug.Log("frame : " + Time.frameCount);    //1
        await Observable.ReturnUnit().DelayFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //2
        await Observable.ReturnUnit().DelayFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //3
        await Observable.ReturnUnit().DelayFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //4
        await Observable.ReturnUnit().DelayFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //5
    }
}

(Start) frame : 1
frame : 1
frame : 2
frame : 3
frame : 4
frame : 5

　これもいけた。これは期待していた処理と合致する。実装自体は Observable.TimerFrame() とは違うみたいだけどね。

●UniTask.DelayFrame() で1フレームごとに待機して処理？

using System.Collections;
using UnityEngine;
using UniRx;
using UniRx.Async;

public class EachFrameTest : MonoBehaviour {

    // Use this for initialization
    void Start () {
        Debug.Log("(Start) frame : " + Time.frameCount); //1

        UniTaskDelayFrameTest();
    }

    async void UniTaskDelayFrameTest()
    {
        Debug.Log("frame : " + Time.frameCount);    //1
        await UniTask.DelayFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //1
        await UniTask.DelayFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //2
        await UniTask.DelayFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //3
        await UniTask.DelayFrame(0);
        Debug.Log("frame : " + Time.frameCount);    //4
    }
}

(Start) frame : 1
frame : 1
frame : 1
frame : 2
frame : 3
frame : 4

　せっかくのなで、UniTask も試してみた。するとあれ？なぜか初めの１回は待機されてない。なんか理由があるのだろうけど、今回は放おっておこう（←誰か調べて(笑)）。こちらは「using UniRx.Async;」が必要。

●UniTask.WaitUntil() で1フレームごとに待機して処理？

using System.Collections;
using UnityEngine;
using UniRx;
using UniRx.Async;

public class EachFrameTest : MonoBehaviour {

    // Use this for initialization
    void Start () {
        Debug.Log("(Start) frame : " + Time.frameCount); //1

        UniTaskWaitUntilTest();
    }

    async void UniTaskWaitUntilTest()
    {
        Debug.Log("frame : " + Time.frameCount);    //1
        await UniTask.WaitUntil(() => true);
        Debug.Log("frame : " + Time.frameCount);    //1
        await UniTask.WaitUntil(() => true);
        Debug.Log("frame : " + Time.frameCount);    //2
        await UniTask.WaitUntil(() => true);
        Debug.Log("frame : " + Time.frameCount);    //3
        await UniTask.WaitUntil(() => true);
        Debug.Log("frame : " + Time.frameCount);    //4
    }
}

(Start) frame : 1
frame : 1
frame : 1
frame : 2
frame : 3
frame : 4

　UniTask.DelayFrame() と同じ結果になった。これもはじめの１回が待機されてない…？ま、まぁ、今回はコルーチンでの表記をそのまま代替できる書き方を探していただけなので（パフォーマンスなども考慮に入れてない）、これで勘弁してやろう(笑)。誰かそのうち調べてくれるだろうと期待してる（←投げっぱなし(笑)）。

●UniTask.Yield() で1フレームごとに待機して処理？

using System.Collections;
using UnityEngine;
using UniRx;
using UniRx.Async;

public class EachFrameTest : MonoBehaviour {

    // Use this for initialization
    void Start () {
        Debug.Log("(Start) frame : " + Time.frameCount); //1

        UniTaskYieldTest();
    }

    async void UniTaskYieldTest()
    {
        Debug.Log("frame : " + Time.frameCount);    //1
        await UniTask.Yield();
        Debug.Log("frame : " + Time.frameCount);    //1
        await UniTask.Yield();
        Debug.Log("frame : " + Time.frameCount);    //2
        await UniTask.Yield();
        Debug.Log("frame : " + Time.frameCount);    //3
        await UniTask.Yield();
        Debug.Log("frame : " + Time.frameCount);    //4
    }
}

(Start) frame : 1
frame : 1
frame : 1
frame : 2
frame : 3
frame : 4

　これも UniTask.DelayFrame() と同じ結果になった。これもはじめの１回が待機されてない？
　本来はメインスレッドに切り替えたり、PlayerLoopに同期したりするのに使うみたいだが、次のフレームになるので、近い動作になるっぽい。

[追記] 以降のバージョンでは以下のようなことが書かれてます。

yield return null and UniTask.Yield are similar but different. yield return null always returns next frame but UniTask.Yield returns next called. That is, call UniTask.Yield(PlayerLoopTiming.Update) on PreUpdate, it returns same frame. UniTask.NextFrame() guarantees return next frame, you can expect this to behave exactly the same as yield return null.

簡単に言えば「UniTask.NextFrame()」を使えば、「yield return null」と同じように、確実に次のフレームになる、だそうです。

■とりあえず「1フレームごとに待機して処理」を簡単に（実験してみた結果）

　他にも色々実験している記事もあったが、単純に面倒なので、とりあえず「Observable.TimerFrame(0)」または「Observable.ReturnUnit().DelayFrame(0)」を代替として使うことにしてみた。もしからしたら正しい使い方ではないかも知れないので、static な関数（WaitForFrame）にしておいて、後で書き換えられるようにしておけば、修正も楽かも知れない。「Observable.TimerFrame(0)」は UniRx 特有の「マイクロコルーチン」というものを使っているので（負荷が軽いらしい）、今回はこちらで書いておこう。まぁ、戻値の型の問題はあるが、あくまでコルーチンでの「yield return null」みたいな使い方を想定しているので、今回は気にしないとする(笑)。Observable のように拡張メソッドにしても良いと思うけど（「Observable_Joins.cs」に書くとか）、その辺はご自由に。

●とりあえず1フレームごとに待機して処理

using System.Collections;
using UnityEngine;
using UniRx;
using UniRx.Async;

public class EachFrameTest : MonoBehaviour {

    // Use this for initialization
    void Start () {
        Debug.Log("(Start) frame : " + Time.frameCount); //1

        WaitForFrameTest();
    }

    async void WaitForFrameTest()
    {
        Debug.Log("frame : " + Time.frameCount);    //1
        await WaitForFrame();
        Debug.Log("frame : " + Time.frameCount);    //2
        await WaitForFrame();
        Debug.Log("frame : " + Time.frameCount);    //3
        await WaitForFrame();
        Debug.Log("frame : " + Time.frameCount);    //4
        await WaitForFrame();
        Debug.Log("frame : " + Time.frameCount);    //5
    }

    public static IObservable<long> WaitForFrame()
    {
        return Observable.TimerFrame(0);
    }
}

(Start) frame : 1
frame : 1
frame : 2
frame : 3
frame : 4
frame : 5

　「Observable.TimerFrame()」だと戻値の型が long となっているので、Unit にしたいなら、以下のようにしても良いかも知れない（まぁ、今回の使い方のように、捨て値なら無駄な処理が増えるだけだが…）。

●戻値を Unit に変えた例

public static IObservable<Unit> WaitForFrame()
{
    return Observable.TimerFrame(0).AsUnitObservable();
}

　こちらの記事にも書いてあるけど「コルーチンをほぼ駆逐」できると表記がすっきりし、しかもコルーチンと違って、別スレッド動作や非アクティブなオブジェクトでも動くので（というより、MonoBehaviour に依存しないで動作できるので）、いずれは「async/await」的な書き方の方が主流になるかもね。「VRM Live Viewer」は商用アプリにするつもりは無いし、実験的にやってみることに意義があると思ってるので（ファイルドロップ→非同期なファイル読み込みは既に実装されてる）、前のめりで新しい機能を導入していきたい(笑)。

（参考）
・Unity UniRxとasync/awaitでフレーム管理
・UniRx.Async機能紹介
・UniTask - Unity + async/awaitの完全でハイパフォーマンスな統合
・Unityにおけるコルーチンの省メモリと高速化について、或いはUniRx 5.3.0でのその反映

関連記事

category: Unity

thread: ゲーム開発

janre: コンピュータ

tag: Unityオープンソースライブラリ Unityライブラリ検証

tb: 0 cm: --

【Java】フィボナッチ数(数列)を求める

2016/07/10 Sun [edit]

　「エラトステネスの篩(ふるい)」同様、数列的なテーマとしてもよく取り上げられる「フィボナッチ数」。「黄金比(黄金数)」とも深い関係があり、実は日常的にもよく使われているとも言われている（自然現象からデザイン的なものまで）。

　まぁ、それはさておき(笑)、プログラミングで計算するのは意外と簡単だったりする。せっかくなので、いくつかの方法で求めてみよう。

■動的計画法
■再帰（メモ化再帰）
■ビネの公式
■任意精度を使う

■動的計画法でフィボナッチ数列を求める

　まずは漸化式を確認してみよう。Wikipedia にも載っているが、もう少しプログラミング用に変形した方がわかりやすいかも知れない。

(漸化式)
F₀ = 0,
F₁ = 1,
F_n = F_n-1 + F_n-2 (n ≧ 0)

●動的計画法でフィボナッチ数列を作る

import java.util.Arrays;

int n = 20;    //n 上限

//動的計画法
long[] dp = new long[n + 1];

dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

//F(n)を表示
System.out.println("F(" + n + ") = " + dp[n]);

//数列を表示
System.out.println(Arrays.toString(dp));

F(20) = 6765
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

　一般的には自然数（0 は含まない整数）で書かれているものも多いが、コンピュータで数列を作る場合は 0 も入れておいた方が何かと便利だろう。インデクスに対応できる利点もある。漸化式をそのままコーディングした感じになるので、説明はいらないだろう。

　気をつけないといけないのは、フィボナッチ数は非常に大きな値となるので、long 型で実装した場合、n = 93 でオーバーフローすることだ。それ以上の値の場合は、後述する BigDecimal（任意精度実数）を使うのも良いだろう。ちなみに、BigInteger（任意精度整数）でも構わないが、BigDecimal の方がわずかに速いようだ。

■再帰でフィボナッチ数(数列)を求める

　次に再帰でフィボナッチ数 F(n) を求めてみよう。再帰でもとてもシンプルに書けることがわかる。

●再帰でフィボナッチ数を求める

int n = 20;

//F(n)を表示
System.out.println("F(" + n + ") = " + fibonacci(n));

//再帰関数
long fibonacci(int n) {
    if (n <= 1) {
        return  n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

F(20) = 6765

　ただ、上記の方法だと n = 40 ほどになると非常に重くなる。なぜなら、再帰で足しあわせている部分「fibonacci(n - 1) + fibonacci(n - 2)」は入れ子になっていて、同じ計算を何度も繰り返しているため、無駄が多いからだ。この関数は引数が同じなら戻値も同じになるので、メモ化することで高速化を図れる。またメモは数列にもなるので表示してみよう。

●メモ化再帰でフィボナッチ数列を作る

import java.util.Arrays;

int n = 20;

long[] fib = new long[n + 1];  //メモ(グローバルに置く)

//F(n)を表示
System.out.println("F(" + n + ") = " + fibonacci(n));

//数列を表示
System.out.println(Arrays.toString(fib));

//メモ化再帰
long fibonacci(int n) {
    if (n <= 1) {
        return fib[n] = n;
    }
    if (fib[n] > 0) {
        return fib[n];
    }
    return fib[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

F(20) = 6765
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

　この方法なら n = 40 以上でも一瞬で求められる。

　ただし、上記の動的計画法でも再帰でも、long で実装した場合、 n = 93 でオーバーフローになるので気をつけよう。

■ビネの公式でフィボナッチ数を求める

　もう１つ、一般項を求める式（ビネの公式）を用いてフィボナッチ数を求めてみよう。

●ビネの公式でフィボナッチ数を求める

final double GOLDEN_RATIO = 1.618033988749895;  //黄金比
final double SQRT5 = Math.sqrt(5);  //√5

int n = 20;

//ビネの公式
//(上の式) n = 72 から誤差が出る
double ans1 = (Math.pow(1.0 + SQRT5, n) - Math.pow(1.0 - SQRT5, n)) / (Math.pow(2, n) * SQRT5);
System.out.println("F(" + n + ") = " + (long)ans1 + " (" + ans1 + ")");

//(下の式) n = 71 から誤差が出る
double ans2 = Math.floor(Math.pow(GOLDEN_RATIO, n) / SQRT5 + 0.5);
System.out.println("F(" + n + ") = " + (long)ans2 + " (" + ans2 + ")");

F(20) = 6765 (6765.000000000005)
F(20) = 6765 (6765.0)

　ただし、これらは近似式のため誤差が出るので注意しよう。 double で実装した場合、上の式では n = 72 から、下の式では n = 71 から誤差が出る。式の解説は Wikipedia に載っているので参照して欲しいが、プログラミングするなら下の方の式が使いやすい。カッコの上の部分が無いような記号は床関数の記号で、小数点切り捨てと考えれば、Math.floor() でも整数型のキャストでも良いだろう（正の整数の場合）。よくわからない記号は「数学記号の表」などで調べると良い。

　ビネの公式での誤差の出る範囲を抑える１つの方法は、BigDecimal のような任意精度実数を使って、桁の精度を上げることである。試しに黄金比や √5 の値を 50 桁まで上げて、先ほどの式（下の方の式、上の方の式は上手くいかない）を BigDecimal に書き換えてみると、n = 231 までは誤差が出ない。

●ビネの公式を BigDecimal で書いてみる(小数点以下 50桁)

import java.math.BigDecimal;
import java.math.RoundingMode;

int n = 231;  //232 から誤差が出る

/** 任意精度実数の黄金比 (50桁) */
final BigDecimal BIG_DECIMAL_GOLDEN = new BigDecimal("1.61803398874989484820458683436563811772030917980576");

/** 任意精度実数の √5 (50桁) */
final BigDecimal BIG_DECIMAL_SQRT5 = new BigDecimal("2.23606797749978969640917366873127623544061835961152");

BigDecimal ans = BIG_DECIMAL_GOLDEN.pow(n).divide(BIG_DECIMAL_SQRT5, 50, RoundingMode.FLOOR).add(new BigDecimal(0.5));

System.out.println("F(" + n + ") = " + ans.setScale(0, RoundingMode.FLOOR) + " (" + ans + ")");

F(231) = 844617150046923109759866426342507997914076076194 (844617150046923109759866426342507997914076076194.15703878686668096410036906990688047595887460281556)

　ビネの公式も黄金比や √5 の精度を上げれば、もっと大きな n でも誤差が出ないようにできると思うが、実際には計算が非常に重くなるのであまり実用的ではないかも知れない。その場合、はじめに書いた動的計画法を BigDecimal に書き換えた方が実行速度も速く、誤差もない。

●はじめの動的計画法を BigDecimal に書き換えたもの

import java.math.BigDecimal;
import java.util.Arrays;

int n = 100;

BigDecimal[] dp = new BigDecimal[n + 1];

dp[0] = BigDecimal.ZERO;
dp[1] = BigDecimal.ONE;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1].add(dp[i - 2]);
}

//F(n)を表示
System.out.println("F(" + n + ") = " + dp[n]);

//数列を表示
System.out.println(Arrays.toString(dp));

F(100) = 354224848179261915075
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075]

　最後に long, double (ビネの公式：下の式), BigDecimal で計算した結果をダンプしてみよう。オーバーフローや誤差を確認しておけば、どれを使うかの目安になるかも知れない。値を確認するには以下のようなサイトを参考にすれば良い。

（参考）[数列]
・１００番目までのフィボナッチ数列
・１番目から１０００番目までのフィボナッチ数列

F(0)
long       = 0
double     = 0
BigDecimal = 0
F(1)
long       = 1
double     = 1
BigDecimal = 1
F(2)
long       = 1
double     = 1
BigDecimal = 1
F(3)
long       = 2
double     = 2
BigDecimal = 2
F(4)
long       = 3
double     = 3
BigDecimal = 3
F(5)
long       = 5
double     = 5
BigDecimal = 5
F(6)
long       = 8
double     = 8
BigDecimal = 8
F(7)
long       = 13
double     = 13
BigDecimal = 13
F(8)
long       = 21
double     = 21
BigDecimal = 21
F(9)
long       = 34
double     = 34
BigDecimal = 34
F(10)
long       = 55
double     = 55
BigDecimal = 55
F(11)
long       = 89
double     = 89
BigDecimal = 89
F(12)
long       = 144
double     = 144
BigDecimal = 144
F(13)
long       = 233
double     = 233
BigDecimal = 233
F(14)
long       = 377
double     = 377
BigDecimal = 377
F(15)
long       = 610
double     = 610
BigDecimal = 610
F(16)
long       = 987
double     = 987
BigDecimal = 987
F(17)
long       = 1597
double     = 1597
BigDecimal = 1597
F(18)
long       = 2584
double     = 2584
BigDecimal = 2584
F(19)
long       = 4181
double     = 4181
BigDecimal = 4181
F(20)
long       = 6765
double     = 6765
BigDecimal = 6765
F(21)
long       = 10946
double     = 10946
BigDecimal = 10946
F(22)
long       = 17711
double     = 17711
BigDecimal = 17711
F(23)
long       = 28657
double     = 28657
BigDecimal = 28657
F(24)
long       = 46368
double     = 46368
BigDecimal = 46368
F(25)
long       = 75025
double     = 75025
BigDecimal = 75025
F(26)
long       = 121393
double     = 121393
BigDecimal = 121393
F(27)
long       = 196418
double     = 196418
BigDecimal = 196418
F(28)
long       = 317811
double     = 317811
BigDecimal = 317811
F(29)
long       = 514229
double     = 514229
BigDecimal = 514229
F(30)
long       = 832040
double     = 832040
BigDecimal = 832040
F(31)
long       = 1346269
double     = 1346269
BigDecimal = 1346269
F(32)
long       = 2178309
double     = 2178309
BigDecimal = 2178309
F(33)
long       = 3524578
double     = 3524578
BigDecimal = 3524578
F(34)
long       = 5702887
double     = 5702887
BigDecimal = 5702887
F(35)
long       = 9227465
double     = 9227465
BigDecimal = 9227465
F(36)
long       = 14930352
double     = 14930352
BigDecimal = 14930352
F(37)
long       = 24157817
double     = 24157817
BigDecimal = 24157817
F(38)
long       = 39088169
double     = 39088169
BigDecimal = 39088169
F(39)
long       = 63245986
double     = 63245986
BigDecimal = 63245986
F(40)
long       = 102334155
double     = 102334155
BigDecimal = 102334155
F(41)
long       = 165580141
double     = 165580141
BigDecimal = 165580141
F(42)
long       = 267914296
double     = 267914296
BigDecimal = 267914296
F(43)
long       = 433494437
double     = 433494437
BigDecimal = 433494437
F(44)
long       = 701408733
double     = 701408733
BigDecimal = 701408733
F(45)
long       = 1134903170
double     = 1134903170
BigDecimal = 1134903170
F(46)
long       = 1836311903
double     = 1836311903
BigDecimal = 1836311903
F(47)
long       = 2971215073
double     = 2971215073
BigDecimal = 2971215073
F(48)
long       = 4807526976
double     = 4807526976
BigDecimal = 4807526976
F(49)
long       = 7778742049
double     = 7778742049
BigDecimal = 7778742049
F(50)
long       = 12586269025
double     = 12586269025
BigDecimal = 12586269025
F(51)
long       = 20365011074
double     = 20365011074
BigDecimal = 20365011074
F(52)
long       = 32951280099
double     = 32951280099
BigDecimal = 32951280099
F(53)
long       = 53316291173
double     = 53316291173
BigDecimal = 53316291173
F(54)
long       = 86267571272
double     = 86267571272
BigDecimal = 86267571272
F(55)
long       = 139583862445
double     = 139583862445
BigDecimal = 139583862445
F(56)
long       = 225851433717
double     = 225851433717
BigDecimal = 225851433717
F(57)
long       = 365435296162
double     = 365435296162
BigDecimal = 365435296162
F(58)
long       = 591286729879
double     = 591286729879
BigDecimal = 591286729879
F(59)
long       = 956722026041
double     = 956722026041
BigDecimal = 956722026041
F(60)
long       = 1548008755920
double     = 1548008755920
BigDecimal = 1548008755920
F(61)
long       = 2504730781961
double     = 2504730781961
BigDecimal = 2504730781961
F(62)
long       = 4052739537881
double     = 4052739537881
BigDecimal = 4052739537881
F(63)
long       = 6557470319842
double     = 6557470319842
BigDecimal = 6557470319842
F(64)
long       = 10610209857723
double     = 10610209857723
BigDecimal = 10610209857723
F(65)
long       = 17167680177565
double     = 17167680177565
BigDecimal = 17167680177565
F(66)
long       = 27777890035288
double     = 27777890035288
BigDecimal = 27777890035288
F(67)
long       = 44945570212853
double     = 44945570212853
BigDecimal = 44945570212853
F(68)
long       = 72723460248141
double     = 72723460248141
BigDecimal = 72723460248141
F(69)
long       = 117669030460994
double     = 117669030460994
BigDecimal = 117669030460994
F(70)
long       = 190392490709135
double     = 190392490709135
BigDecimal = 190392490709135
F(71)
long       = 308061521170129
double     = 308061521170130      //← ここから誤差が出る
BigDecimal = 308061521170129
F(72)
long       = 498454011879264
double     = 498454011879265
BigDecimal = 498454011879264
F(73)
long       = 806515533049393
double     = 806515533049395
BigDecimal = 806515533049393
F(74)
long       = 1304969544928657
double     = 1304969544928660
BigDecimal = 1304969544928657
F(75)
long       = 2111485077978050
double     = 2111485077978055
BigDecimal = 2111485077978050
F(76)
long       = 3416454622906707
double     = 3416454622906716
BigDecimal = 3416454622906707
F(77)
long       = 5527939700884757
double     = 5527939700884772
BigDecimal = 5527939700884757
F(78)
long       = 8944394323791464
double     = 8944394323791488
BigDecimal = 8944394323791464
F(79)
long       = 14472334024676221
double     = 14472334024676260
BigDecimal = 14472334024676221
F(80)
long       = 23416728348467685
double     = 23416728348467744
BigDecimal = 23416728348467685
F(81)
long       = 37889062373143906
double     = 37889062373144008
BigDecimal = 37889062373143906
F(82)
long       = 61305790721611591
double     = 61305790721611752
BigDecimal = 61305790721611591
F(83)
long       = 99194853094755497
double     = 99194853094755776
BigDecimal = 99194853094755497
F(84)
long       = 160500643816367088
double     = 160500643816367552
BigDecimal = 160500643816367088
F(85)
long       = 259695496911122585
double     = 259695496911123328
BigDecimal = 259695496911122585
F(86)
long       = 420196140727489673
double     = 420196140727490880
BigDecimal = 420196140727489673
F(87)
long       = 679891637638612258
double     = 679891637638614270
BigDecimal = 679891637638612258
F(88)
long       = 1100087778366101931
double     = 1100087778366105090
BigDecimal = 1100087778366101931
F(89)
long       = 1779979416004714189
double     = 1779979416004719360
BigDecimal = 1779979416004714189
F(90)
long       = 2880067194370816120
double     = 2880067194370824700
BigDecimal = 2880067194370816120
F(91)
long       = 4660046610375530309
double     = 4660046610375544800
BigDecimal = 4660046610375530309
F(92)
long       = 7540113804746346429
double     = 7540113804746369000
BigDecimal = 7540113804746346429
F(93)
long       = -6246583658587674878      //← ここでオーバーフロー
double     = 12200160415121914000
BigDecimal = 12200160415121876738
F(94)
long       = 1293530146158671551
double     = 19740274219868283000
BigDecimal = 19740274219868223167
F(95)
long       = -4953053512429003327
double     = 31940434634990200000
BigDecimal = 31940434634990099905
F(96)
long       = -3659523366270331776
double     = 51680708854858490000
BigDecimal = 51680708854858323072
F(97)
long       = -8612576878699335103
double     = 83621143489848690000
BigDecimal = 83621143489848422977
F(98)
long       = 6174643828739884737
double     = 135301852344707190000
BigDecimal = 135301852344706746049
F(99)
long       = -2437933049959450366
double     = 218922995834555900000
BigDecimal = 218922995834555169026
F(100)
long       = 3736710778780434371
double     = 354224848179263100000
BigDecimal = 354224848179261915075

（関連記事）
【Java】任意精度整数(多倍長整数)で演算する

■参考になる書籍

関連記事

category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数数列動的計画法検証

tb: 0 cm: --

【Java】1000000!のような巨大な階乗計算をする [任意精度整数(多倍長整数)]

2016/01/28 Thu [edit]

　桁あふれ(オーバフロー)をすぐしてしまうのはやはり階乗の計算。前回せっかく任意精度整数（BigInteger の計算をまとめたので、簡単な例として100!～1000000! くらいの巨大な階乗を求めてみよう。コードの書き方はいくつかあると思うが、一番簡単で高速だった for ループを用いた方法で書いてみる。

●任意精度整数(多倍長整数)[BigInteger]での階乗計算

import java.math.BigInteger;

/**<h1>任意精度整数で、階乗 (n!) を求める</h1>
 * <p>負の値は 1 (不正値) となる。</p>
 * @param n ： n! (負の値は不可)
 * @return<b>BigInteger</b> ： 階乗 (n!) [toString()で文字列になる]
 */
public static final BigInteger factorial(final int n) {
    BigInteger sum = BigInteger.ONE;
    for (int i = 2; i <= n; i++) {
        sum = sum.multiply(new BigInteger(String.valueOf(i)));
    }
    return sum;
}


//メインでは...
int n = 10000;
BigInteger b = factorial(n);
System.out.println(b);    //文字列[toString()]で表示

　コードに関する説明はあまり必要ないだろう。for ループで 2～n (1は変わらないので除外) までを掛けあわせているだけだ。ちなみに同じコードを long などのプリミティブ型で書くと、20! までしか計算できない。21! を計算するとオーバフローを起こし、負の値になってしまう(Java には unsigned もない)。double で計算すれば負の値は回避できるが、上から17桁より以降は丸められ、下の桁はすべて 0 になってしまう(指数形式で大まかな値で良ければ使える)。

　また、負の階乗は計算できない。特に例外処理を入れてないが、必要あれば、n < 0 のときに、ArithmeticException などをスローするように付け加えても良いだろう。

　あと、階乗計算のコード例として再帰を用いたものも多いが、あれは「再帰とはどういうものか？」というような学習用コードなので、実際の階乗計算のような、単純な計算には使わない方が良いだろう。再帰で書いた場合の欠点として、無駄にスタックメモリを喰うことと（つまり携帯[スマホ]などメモリの少ない端末には向かない）、実行時間がかかることが考えられる。ちなみに上記の階乗計算をそのまま再帰で書き直すと、13800! 以上の計算でオーバフロー(Stack Overflow)を起こし、計算時間は約２倍かかる。

　参考までに私の環境（Windows10/Intel Core i5 x64 2.9GHz）での BigInteger の階乗計算にかかった時間を挙げておこう。オンラインジャッジでもあまり変わらない（オンラインジャッジの方が 100ms ほど速いくらい）。

100! で、0 [ms] (測定不可)
1000! で、3 [ms]
10000! で、46 [ms]
100000! で、2822 [ms]
1000000! で、356593 [ms] (約6分)

　非常に重いので、10万回を超える演算には注意した方が良いかもしれない。プロコンには向かないかも。もし、20! 以内の計算で良ければプリミティブ型で階乗計算した方が良いだろう（プロコン問題の場合は桁数がカットできる条件が含まれていたら、除算や剰余を使ってオーバフローを防げば100万回行ける）。測定してみたら、プリミティブ型の方が任意精度整数より約35倍速かった(笑)。また、任意精度符号付き10進数の「BigDecimal」の方が BigInteger より3割くらい速いようだ。

　計算結果は BigInteger.toString() で表示できるが、10000! を超えると非常に大きな値になるので、コンソールでは表示できない。値を確認したければ、ファイルなどに出力すると良いだろう。以前に作った「ローカルシステムにテキストファイルを保存」を使えば簡単に出力できる。

　実際に出力してみると、

100! (158桁)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

1000! (2568桁)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

10000! (35660桁)
100000! (456574桁)
1000000! (5565709桁)
・・・
となる。

　ググってみると計算速度を上げるために、マルチコアやマルチスレッド、複数台の並列処理などをやっている例もあったが…、まぁ、別のアルゴリズムも含めて、色々やってみると面白いと思う。そういう研究結果を公開してくれると、勉強になるので非常に有り難い(笑)。

（関連記事）
【Java】プリミティブ型での階乗計算
【Java】任意精度整数(多倍長整数)で演算する
【Java】順列の数を求める
【Java】組合せの数を求める
【Java】パスカルの三角形を使って組合せを求める

関連記事

【Java】最大公約数・最小公倍数を求める（ユークリッドの互除法）
【Java】ベルマン-フォード法[単一始点最短経路] (Bellman-Ford algorithm, Single Source Shortest Path)
【Java】プリム法[最小全域木] (Prim's algorithm, Minimum Spannig Tree)
【Java】interface を使って簡単なコールバック機能を作る
【Java】1000000!のような巨大な階乗計算をする [任意精度整数(多倍長整数)]

category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数検証

tb: 0 cm: --

| h o m e | n e x t »

ヽ｜∵｜ゝ(Fantom) の開発blog？

とりあえず何でもやってみる人。色々試した結果などの記録的な何か(笑)。参考にでもなれば嬉しい。コードやアセットなどの使用はご自由に。著作者明記、使用報告・許諾なども不要。特に利用制限はありません。

【Unity】【C#】StartsWith, EndsWith が遅いのなら、Equals も遅いのか？

【Unity】【C#】LINQとfor, ListとArray(配列)での実行速度を比較してみる

【Unity】【C#】UniRx で「1フレームごと待機して処理」してみる

【Java】フィボナッチ数(数列)を求める

【Java】1000000!のような巨大な階乗計算をする [任意精度整数(多倍長整数)]

プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

Release App By Fantom

PR

PR

Unity Asset Store Campaign

PR

ヽ｜∵｜ゝ(Fantom) の 開発blog？

とりあえず何でもやってみる人。色々試した結果などの記録的な何か(笑)。参考にでもなれば嬉しい。コードやアセットなどの使用はご自由に。著作者明記、使用報告・許諾なども不要。特に利用制限はありません。

【Unity】【C#】StartsWith, EndsWith が遅いのなら、Equals も遅いのか？ nw(2021,04,18,00)

【Unity】【C#】LINQとfor, ListとArray(配列)での実行速度を比較してみる nw(2018,11,04,20)

【Unity】【C#】UniRx で「1フレームごと待機して処理」してみる nw(2018,10,19,17)

【Java】フィボナッチ数(数列)を求める nw(2016,07,10,12)

【Java】1000000!のような巨大な階乗計算をする [任意精度整数(多倍長整数)] nw(2016,01,28,00)

プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

Release App By Fantom

PR

PR

Unity Asset Store Campaign

PR

ヽ｜∵｜ゝ(Fantom) の開発blog？

【Unity】【C#】StartsWith, EndsWith が遅いのなら、Equals も遅いのか？

【Unity】【C#】LINQとfor, ListとArray(配列)での実行速度を比較してみる

【Unity】【C#】UniRx で「1フレームごと待機して処理」してみる

【Java】フィボナッチ数(数列)を求める

【Java】1000000!のような巨大な階乗計算をする [任意精度整数(多倍長整数)]