.NET Coreのソースを読む!第一回 List<T> パート4

More than 1 year has passed since last update.


はじめに

以下の続きです。


ソースリンク

https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Collections/Generic/List.cs


ソースを読む!


インスタンスメソッド

        // 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になります。

以下のテストソースを見るとよくわかります。

https://github.com/dotnet/corefx/blob/59915687bb261efeae70565d0ca8990ac45ceb9c/src/System.Runtime/tests/System/Runtime/CompilerServices/RuntimeHelpersTests.netcoreapp.cs#L74

Listで保持しているT型に参照型のものがあれば、Array.ClearでちゃんとGCレベルで開放されるようにするようです。

私は英語が苦手なので、正確に理解できていませんが、以下のissueでこの処理に変わったようです。

https://github.com/dotnet/corefx/issues/14047

ここで、なんか気持ち悪いとおもったところが、「RuntimeHelpers.IsReferenceOrContainsReferences()」がfalseになったら、_sizeを0にしているだけで、T型のインスタンスを保持している_itemsは初期化していないところです。Listは順次アクセスしかできない(0から順番にしかAdd出来ない)から、_itemsは初期化しなくとも安全なようです。参照型ではないものは、メモリをあまり消費しないから、そのまま保持していても問題なく、それよりも、配列を使いまわした方が効率が良いということでしょうか。

試しに、デバックしてみたら、確かにClearした後も値は保持し続けていました。今後、デバックするときに、騙されないようにしないといけませんね。

1.png

今回は、Clearメソッドがヘビーだったので、ここまで。

たった、数行のメソッドでもとても勉強になりますね。


ライセンス

色々ソースを載せているので、念のためライセンスへリンクしておきます。

https://github.com/dotnet/corefx/blob/master/LICENSE.TXT