NEW

スポンサーサイト

--/--/-- --:--

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

スポンサー広告

C#のListについてのメモ

2015/12/06 12:59

リストの列挙を高速化したくてアルゴリズムを検証しました
単純な列挙ならforeachで良いのですが、これだと列挙中の追加、削除ができません
そこでよく使われるのはforでリストを逆から回していく方法です
これだと列挙中の追加削除は可能になりますが、特にリストのサイズが大きくてリストの前の方の要素を削除するときに時間がかかります
という訳で他に二つのアルゴリズムを用いて以下のコードで検証しました

// ---- ここから ----
using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace SpeedTest
{
class Program
{
// 最初のリストの最大数
const int LIST_MAX = 1000;

// ループを繰り返す回数
const int LOOP_MAX = 100000;

// データを削除する間隔
const int DELETE_SPAN = 3;

// 計測用ストップウォッチ
static Stopwatch stopwatch = new Stopwatch();

// 計測用リスト このリストから要素を削除する時間を測る
static List list = new List(LIST_MAX);

// ここから
static void Main(string[] args)
{
Console.WriteLine("Test1");
stopwatch.Start();
Test1();
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);
ShowList();

Console.WriteLine("Test2");
stopwatch.Restart();
Test2();
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);
ShowList();

Console.WriteLine("Test3");
stopwatch.Restart();
Test3();
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);
ShowList();

Console.ReadKey();
}

// リストの初期化
private static void InitList()
{
list.Clear();
for (int i = 0; i < LIST_MAX; i++)
{
// リストの内部が [0, 1, 2, 0, 1, 2...] となる
list.Add(i % DELETE_SPAN);
}
}

// リストの中身を表示 全部出しても仕方ないので20個だけ表示する
private static void ShowList()
{
for (int i = 0; i < 20; i++)
{
if (list.Count - 1 <= i) break;
Console.Write(list[i] + ", ");
}
Console.WriteLine();
}

// リストを逆回しして、普通に削除する
private static void Test1()
{
for (int i = 0; i < LOOP_MAX; i++)
{
InitList();
for (int j = list.Count - 1; j >= 0; j--)
{
// リスト内の0を削除する
if (list[j] == 0) list.RemoveAt(j);
}
}
}

// リストを逆回しして、削除する要素に対してリストの最後の要素を代入し、リストの最後の要素を削除する
private static void Test2()
{
for (int i = 0; i < LOOP_MAX; i++)
{
InitList();
for (int j = list.Count - 1; j >= 0; j--)
{
if (list[j] == 0)
{
// 消したい要素に対してリストの最後の要素を代入する
list[j] = list[list.Count - 1];
// リストの最後の要素を削除する
list.RemoveAt(list.Count - 1);
}
}
}
}

// 必要な要素を新しいリストに移し替える
private static void Test3()
{
for (int i = 0; i < LOOP_MAX; i++)
{
InitList();
// このリストに移し替える
List result = new List(list.Count);
for(int j = 0; j < list.Count; j++)
{
// 削除する要素以外を新しいリストに入れる
if (list[j] != 0) result.Add(list[j]);
}
// 最後にリストを新しいリストに上書き
list = result;
}
}
}
}
// ---- ここまで ----

簡単に説明すると以下の通りです
共通:[0, 1, 2, 0, 1, 2...]と並んだリストから0を削除する
Test1:普通のList逆回し
Test2:前の方の要素の削除が遅いなら、そこに一番後ろの要素を代入して後ろの要素を消してしまおうという方法
Test3:不要な要素を削除するのではなく、必要な要素を新しいListにまとめてしまおうという方法

でもって実際に走らせた結果が以下の通りです
なおPCはWindows7-64bit/i7-2600/RadeonHD6850/Mem8Gです

Test1
3101
1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2,
Test2
763
2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1,
Test3
849
1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2,

十分に高速化されました
Test2の方が高速ですが、リストの中身がバラバラになるという欠点があります
Test3は少し低速ですがリストの中身はそのままです

また上の実験では全データの1/3を削除したため、削除数がそこそこ多い場面になると思います
なので削除数を減らすためDELETE_SPAN = 100;として走らせた結果が以下の通りです

Test1
777
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
Test2
598
90, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
Test3
946
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,

Test1とTest2がより早くなり、Test3は若干遅くなりました
削除件数が少ない場合はTest2が有効ですが、Test1でも十分であると思われます

さらにリストの要素数が多い場合を検証します
LIST_MAX = 10000;LOOP_MAX = 10000;DELETE_SPAN = 3;として走らせた結果が以下の通りです

Test1
19182
1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2,
Test2
773
2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1,
Test3
825
1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2,

DELETE_SPAN = 100;とします

Test1
1547
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
Test2
595
99, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
Test3
960
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,

共にTest1は非常に低速となりました
一方Test2とTest3はLIST_MAX = 1000;の場合とあまり変わりません

以上を踏まえて私の結論です
Test1:
・利点
削除件数と全体の要素数が少ない場合高速
・欠点
削除件数や全体の要素数が多い場合低速

Test2:
・利点
削除件数や全体の要素数にかかわらず高速
・欠点
リストの中の順番が入れ替わる

Test3:
・利点
削除件数が多い場合高速
全体の要素数にかかわらず高速
・欠点
削除件数が少ない場合低速

総評:
汎用的なのはTest3
リストの中身の順番が入れ替わって良い場合はTest2
削除件数が少なく、要素数も少ない場合はTest1

という検証結果になりました
何か変なところがあるとか、もっと高速なアルゴリズムが有るとかあればコメント下さるとありがたいです
あとこのブログは頭のスペース削除されるんですね、見にくい

スポンサーサイト

プログラム  | コメント : 0  | トラックバック : 0 |

2015/10/17 12:28

ブログの存在を忘れること一年
今後は製作中の画像とか載せていきたいですね、忘れなければ

11/1の東方紅楼夢にてゲームを出します
す-07a さくらもち製作所にて頒布予定です
体験版を公開しましたのでぜひ遊んでみてください

http://sakurasumizome.web.fc2.com/game_kurenai.html



サークル情報  | コメント : 0  | トラックバック : 0 |

風 バージョン1.1

2014/11/02 22:03

早速で恐縮ですが、"風"のアップデートのご案内です

http://sakurasumizome.web.fc2.com/game_kaze.html

コントローラーの十字キーが効かない不具合を修正しました
原因はコントローラーのアナログ入力を受け付けていなかったためだと思われます
また、コントローラーを二つ以上繋いでいる場合も入力情報がおかしくなりますので、お手数ですがパッドを一つだけ接続した状態でお試しください

もしこれでも十字キーが効かない方がおられましたら、宜しければ使用OSとパッドの型番をメールなどでご連絡頂けませんでしょうか?
できる限り対応させていただきたいと思います

以上アップデートのご案内でした
ご不便をおかけして申し訳ございませんでした

サークル情報  | コメント : 0  | トラックバック : 0 |

文々。新聞友の会 無事終了

2014/11/02 20:52

本日の文々。新聞友の会にサークル参加させていただきました
お越しくださった皆様、手に取ってくださった皆様、本当にありがとうございました
連絡先書き忘れたり途中でPCの電池が切れたり色々反省すべき点はありますので、次回以降気をつけていこうと思います

さて、早速ですが不具合報告を頂きました
どうやらコントローラーの十字キーが効かない事があるようです
原因が判明次第パッチを出しますので、同現象が発生している方は申し訳ございませんが少々お待ちください

サークル情報  | コメント : 0  | トラックバック : 0 |

文々。新聞友の会 緋-04

2014/11/01 21:56

前回の記事が半年前だと…
すみません完全に放置してました

明日の文々。新聞友の会にてゲームを出します
DSC_0069.jpg

kaze0.jpg

タイトルは漢字一文字の"風"
中身は東方二次創作ゲームの弾幕STGとなっています
主人公の射命丸文とともに異常な風の原因を探りましょう

特徴的なシステムとしてウインドショットがあります
これを敵の弾に当てると弾を押し返す事ができます
さらに押し返した弾を敵に当てると大きなダメージを取れます
一見すると回避不能な弾幕も、ウインドショットによって道を切り開く事ができます

kaze3.jpg

こんな避ける場所の無い弾幕も

kaze4.jpg

ウインドショットで押し返せば道ができます

こんな感じで敵弾を押し返していくゲームになっています
ウインドショットのコツを掴むまでは大変ですが、一度判ってしまえば難易度はぐっと下がると思います

5~10分程度のステージが8ステージ+隠しステージという構成です
また、1ステージごとに攻略していくスタイルなので結構気楽に遊べます
弾幕を切り開いていく感じがなかなか爽快ですので、宜しければ緋-04へお越しください

サークル情報  | コメント : 0  | トラックバック : 0 |

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。