c# - C＃Forループ、Whileループ、LastIndexOf、IndexOf、なぜ最後の2つが速いのですか？

Question

比較検索を行うために、ArrayListのForループとWhileループを使用して、C＃でいくつかのパフォーマンステストを実行しました。

二次時間の消費があるようです。

ただし、LastIndexOfまたはを使用IndexOfしてリストを検索すると、「予想よりも速い」速度になります。

誰かが理由を知っていますか？

Answer 1

ILSpy を使用して、LastIndexOf/IndexOf メソッドの内部を見てみましょう。なぜ彼らが速いのかについてのあなたの答えがあります。

List が内部的に B ツリーまたは log(n) のルックアップを持つ他のツリーを使用しているという予感があります。for/foreach で行っていることは、余分なオーバーヘッドを伴うリニア ルックアップを実行することです。数学のクラスを覚えていれば、log(n) は直線よりも平坦であるため、ルックアップが高速になることがわかります...

Answer 2

私は C# をまったく知りませんが、ありそうな答えを提示できます。

プログラミング言語のメソッドは、一般に、それらが実行されるプロセッサによって利用可能になったショートカットを利用する方法で記述されます。独自に記述されたコードはそうではありません (たとえば、スタックに保持する必要があるローカル変数を宣言する必要があります)。一時的なレジスタ変数ではなく、ルックアップ時間が遅くなります)。したがって、言語がネイティブに行うことは、通常、独自のコードよりも高速です。