はじめに
以下の続きです。
ソースリンク
ソースを読む!
インスタンスメソッド
// Searches a section of the list for a given element using a binary search
// algorithm. Elements of the list are compared to the search value using
// the given IComparer interface. If comparer is null, elements of
// the list are compared to the search value using the IComparable
// interface, which in that case must be implemented by all elements of the
// list and the given search value. This method assumes that the given
// section of the list is already sorted; if this is not the case, the
// result will be incorrect.
//
// The method returns the index of the given value in the list. If the
// list does not contain the given value, the method returns a negative
// integer. The bitwise complement operator (~) can be applied to a
// negative result to produce the index of the first element (if any) that
// is larger than the given search value. This is also the index at which
// the search value should be inserted into the list in order for the list
// to remain sorted.
//
// The method uses the Array.BinarySearch method to perform the
// search.
//
public int BinarySearch(int index, int count, T item, IComparer<T> comparer)
{
if (index < 0)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (count < 0)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
if (_size - index < count)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
return Array.BinarySearch<T>(_items, index, count, item, comparer);
}
public int BinarySearch(T item)
=> BinarySearch(0, Count, item, null);
public int BinarySearch(T item, IComparer<T> comparer)
=> BinarySearch(0, Count, item, comparer);
BinarySearchは、二分検索だから当然ですが、ソート済みでないと正しい結果返ってきません。(本来は存在するのに、存在しないという結果になるんでしょうね。)
存在しない場合は、マイナスが帰ってくるそうです。
.NET Coreのソースは、大事なことをコメントに書いてくれていますね。
1件だけ探し出すときは、LINQのFirstとかFirstOrDefalutとかが簡単なので、LINQで実装してしまいがちですが、もし、性能を求められたときは、BinarySearchも選択枠に入れるべきですね。
ICompareは、ListにあるSortメソッドでも使えるので、同じICompareでSortしてBinarySearchってやれば良いかと思います。ただ、検索するのに並び順を変えてしまってもよいかどうかは、注意が必要ですね。
完全に余談ですが、初心者の頃に、ICompareのようなものでSortが出来ることを理解したときは感動しました。(確かJavaのComparatorだったと思います。)初心者の頃は、引数や戻り値には何かしらのデータを渡すということしか理解できていなかったのですが、「どのように比較するか?」という概念を、引数で渡して、ソートをお任せするなんていうのが出来ることを知って、色々可能性が増えたような気がします。
// Clears the contents of List.
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Clear()
{
_version++;
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
int size = _size;
_size = 0;
if (size > 0)
{
Array.Clear(_items, 0, size); // Clear the elements so that the gc can reclaim the references.
}
}
else
{
_size = 0;
}
}
リストの中身を空にします。
ただ単に、内部で保持している配列を新たに作り直せば簡単なのだけど、さすが標準ライブラリですね。色々考えているようです。
[MethodImpl(MethodImplOptions.AggressiveInlining)]で、コンパイル時にインライン化になりやすくしています。やっぱり、どういう時にこれを指定すべきかのか、私にはまだよくわかりません。
「_version++;」は、マルティスレッド対策のようですね。例えば、ForEachメソッドの中では、ループ中にバージョンが変わったら例外が投げられるようになっていますね。
「RuntimeHelpers.IsReferenceOrContainsReferences()」では、Listで保持しているT型が参照型の値、もしくは、参照型の値を持っている(構造体がクラス型を持つってことのようです)場合はtrueになります。
以下のテストソースを見るとよくわかります。
Listで保持しているT型に参照型のものがあれば、Array.ClearでちゃんとGCレベルで開放されるようにするようです。
私は英語が苦手なので、正確に理解できていませんが、以下のissueでこの処理に変わったようです。
ここで、なんか気持ち悪いとおもったところが、「RuntimeHelpers.IsReferenceOrContainsReferences()」がfalseになったら、_sizeを0にしているだけで、T型のインスタンスを保持している_itemsは初期化していないところです。Listは順次アクセスしかできない(0から順番にしかAdd出来ない)から、_itemsは初期化しなくとも安全なようです。参照型ではないものは、メモリをあまり消費しないから、そのまま保持していても問題なく、それよりも、配列を使いまわした方が効率が良いということでしょうか。
試しに、デバックしてみたら、確かにClearした後も値は保持し続けていました。今後、デバックするときに、騙されないようにしないといけませんね。
今回は、Clearメソッドがヘビーだったので、ここまで。
たった、数行のメソッドでもとても勉強になりますね。
ライセンス
色々ソースを載せているので、念のためライセンスへリンクしておきます。