iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 25
0
Software Development

深入探索LINQ系列 第 25

C#的利器LINQ-Skip的原碼探索

本章會說明及分析SkipSkipLastSkipWhile三個方法的原始碼實作測試案例欣賞

原始碼分析

Source Code: Skip.csPartition.cs

Skip

Skip有一個公開方法的實作如下:

public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> source, int count)
{
    if (source == null)
    {
        throw Error.ArgumentNull(nameof(source));
    }

    if (count <= 0)
    {
        // Return source if not actually skipping, but only if it's a type from here, to avoid
        // issues if collections are used as keys or otherwise must not be aliased.
        if (source is Iterator<TSource> || source is IPartition<TSource>)
        {
            return source;
        }

        count = 0;
    }

    else if (source is IPartition<TSource> partition)
    {
        return partition.Skip(count);
    }

    if (source is IList<TSource> sourceList)
    {
        return new ListPartition<TSource>(sourceList, count, int.MaxValue);
    }

    return new EnumerablePartition<TSource>(source, count, -1);
}

此公開方法做了下面幾件事情:

  • 判斷source是否為空,空的話拋出ArgumentNull例外
  • 判斷count是否小於0,小於0的話將count設成0
  • 前面已經是IPartition型別,也就是已經有執行過LINQ了,直接call之前method實作的Skip
  • 如果是IList就用ListPartition實作
  • 其餘的叫用EnumerablePartition實作

看到Enumerable就會想到MoveNext(),所以接下來會介紹ListPartitionEnumerablePartition的定義及MoveNext()

ListPartition

public ListPartition(IList<TSource> source, int minIndexInclusive, int maxIndexInclusive);

傳入一個List,設好第一個元素及最後個元素的index,他會把這區間內的元素集合輸出。

這裡要注意的是如果只要忽略前面的元素的話只需要設定minIndexInclusivemaxIndexInclusive設為int.MaxValue就好。

下面是MoveNext()的實作:

public override bool MoveNext()
{
    // _state - 1 represents the zero-based index into the list.
    // Having a separate field for the index would be more readable. However, we save it
    // into _state with a bias to minimize field size of the iterator.
    int index = _state - 1;
    if (unchecked((uint)index <= (uint)(_maxIndexInclusive - _minIndexInclusive) && index < _source.Count - _minIndexInclusive))
    {
        _current = _source[_minIndexInclusive + index];
        ++_state;
        return true;
    }

    Dispose();
    return false;
}

上面的程式有幾個重點:

  • _state當作索引,初始值是1,所以index = _state - 1
  • 這裡要輸出的元素是由_minIndexInclusive起算,可以想成_minIndexInclusive是個起點,而index則是由這個起點數來第幾個的變數
  • 判斷index有沒有超出最大索引值集合數量
  • 如果超出則return false,結束迭代
  • 如果沒有超出,則把目前的元素附給_current,然後_state1,回傳true

這裡我們注意到一件事,因為_maxIndexInclusive的用法是index <= _maxIndexInclusive - _minIndexInclusive,所以只要把_maxIndexInclusive設為int.MaxValue_maxIndexInclusive就不會影響判斷,因此Skip才會將其設為int.MaxValue

EnumerablePartition

internal EnumerablePartition(IEnumerable<TSource> source, int minIndexInclusive, int maxIndexInclusive);

傳入一個IEnumerable,設好第一個元素及最後個元素的index,他會把這區間內的元素集合輸出。

如果只要忽略由第一個數來第N個元素的話只需要設定minIndexInclusivemaxIndexInclusive設為-1就好。

這裡有一個地方跟ListPartition不同,只要忽略前面的元素maxIndexInclusive的設定一個是int.MaxValue,一個是-1,我們等下從實作上看為什麼會不同。

下面是MoveNext()的實作:

public override bool MoveNext()
{
    // Cases where GetEnumerator has not been called or Dispose has already
    // been called need to be handled explicitly, due to the default: clause.
    int taken = _state - 3;
    if (taken < -2)
    {
        Dispose();
        return false;
    }

    switch (_state)
    {
        case 1:
            _enumerator = _source.GetEnumerator();
            _state = 2;
            goto case 2;
        case 2:
            if (!SkipBeforeFirst(_enumerator))
            {
                // Reached the end before we finished skipping.
                break;
            }

            _state = 3;
            goto default;
        default:
            if ((!HasLimit || taken < Limit) && _enumerator.MoveNext())
            {
                if (HasLimit)
                {
                    // If we are taking an unknown number of elements, it's important not to increment _state.
                    // _state - 3 may eventually end up overflowing & we'll hit the Dispose branch even though
                    // we haven't finished enumerating.
                    _state++;
                }
                _current = _enumerator.Current;
                return true;
            }

            break;
    }

    Dispose();
    return false;
}

這段程式碼有下面幾個重點:

  • 這裡的_state回歸原本的用法: 狀態的設置
  • _state=1: 初始_source,轉為Enumerator
  • _state=2: 判斷設置的minIndexInclusive是否超過集合總長度並且將_enumerator_current推至minIndexInclusive的位置
  • _state=3: 判斷是否超過最大長度,沒有的話將_current往後再推一個至目標位置然後傳回true

我們可以在HasLimit找到為什麼maxIndexInclusive要設-1:

private bool HasLimit => _maxIndexInclusive != -1;

EnumerablePartition是用_maxIndexInclusive != -1判斷是否有設定最大值,所以如果沒有設定最大值的話要設為-1

SkipLast

SkipLast有一個公開方法,其實作為:

  • 判斷參數是否為空,如果為空則拋出ArgumentNull例外
  • 參數判斷合法後叫用SkipLastIterator

下面為SkipLastIterator的實作:

private static IEnumerable<TSource> SkipLastIterator<TSource>(IEnumerable<TSource> source, int count)
{
    Debug.Assert(source != null);
    Debug.Assert(count > 0);

    var queue = new Queue<TSource>();

    using (IEnumerator<TSource> e = source.GetEnumerator())
    {
        while (e.MoveNext())
        {
            if (queue.Count == count)
            {
                do
                {
                    yield return queue.Dequeue();
                    queue.Enqueue(e.Current);
                }
                while (e.MoveNext());
                break;
            }
            else
            {
                queue.Enqueue(e.Current);
            }
        }
    }
}

SkipLast是用yield return實作,有下面幾個重點:

  • 維護一個Queue,用來存放集合的元素
  • 叫用MoveNext()Queue的元素數量塞到跟要Skip的元素數量一樣為止
  • 當Queue的元素數量跟要Skip的數量相同時,做以下動作
    1. 從Queue裡抓出第一個元素做yield return
    2. 將目前的元素在塞到Queue裡
    3. 叫用MoveNext()做下一輪的判斷

第三點的處理會讓Queue裡一直保持最後count數的元素,代表到巡覽結束時在Queue中的元素就不會被輸出,所以就可以做到最後count數的元素Skip的處理。

SkipWhile

SkipWhlie有兩個公開方法,差別在predicate參數上:

SkipWhile<TSource>(...Func<TSource, bool> predicate);

SkipWhile<TSource>(...Func<TSource, int, bool> predicate);

一個有傳入index的參數,另一個沒有傳入。

兩個方法都做了以下的處理:

  • 判斷參數是否為空,如果為空則拋出ArgumentNull例外
  • 參數判斷合法後叫用SkipWhileIterator

我們兩種Iterator一起看,直接看有index參數的predicateSkipWhileIterator:

private static IEnumerable<TSource> SkipWhileIterator<TSource>(IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
{
    using (IEnumerator<TSource> e = source.GetEnumerator())
    {
        int index = -1;
        while (e.MoveNext())
        {
            checked
            {
                index++;
            }

            TSource element = e.Current;
            if (!predicate(element, index))
            {
                yield return element;
                while (e.MoveNext())
                {
                    yield return e.Current;
                }

                yield break;
            }
        }
    }
}

這段有下列的重點:

  • 每次MoveNext()index就加1
  • 判斷predicate的結果,如果是true代表要繼續Skip
  • 如果是false的話代表要輸出這個元素之後的所有元素

測試案例賞析

Source Code: SkipTests.csSkipLastTests.csSkipWhileTests.cs

SkipTests.cs

SkipExcessive

[Fact]
public void SkipExcessive()
{
    Assert.Equal(Enumerable.Empty<int>(), NumberRangeGuaranteedNotCollectionType(0, 20).Skip(42));
}

count超過元素數量的話會傳回Empty

SkipOnEmpty

[Fact]
public void SkipOnEmpty()
{
    Assert.Equal(Enumerable.Empty<int>(), GuaranteeNotIList(Enumerable.Empty<int>()).Skip(0));
    Assert.Equal(Enumerable.Empty<string>(), GuaranteeNotIList(Enumerable.Empty<string>()).Skip(-1));
    Assert.Equal(Enumerable.Empty<double>(), GuaranteeNotIList(Enumerable.Empty<double>()).Skip(1));
}

sourceEmpty並不會拋出ArgumentNull的例外,而是回傳Empty的集合。

SkipNegative

[Fact]
public void SkipNegative()
{
    Assert.Equal(Enumerable.Range(0, 20), NumberRangeGuaranteedNotCollectionType(0, 20).Skip(-42));
}

count負數時不會Skip任何元素。

結語

Skip的原始碼中,我們可以觀察到Skip是用什麼方式達成目標的,其中最特別的是SkipLast,用了一個Queue存入跟要Skip數量相同的元素,在巡覽到想同數量時開始把Queue中的第一個元素吐出,最後Queue中只會剩下要Skip的元素,剩餘的都已經巡覽了。

參考


上一篇
C#的利器LINQ-Skip的應用
下一篇
C#的利器LINQ-Take的應用
系列文
深入探索LINQ30

尚未有邦友留言

立即登入留言