获取数组中最后N个元素的最有效方法

Question

对于一个项目，我经常需要获取包含大量数据的数组的最后N个元素。

我尝试使用

myArray.Skip(myArray.Length - toTake).Take(toTake)

但我发现它很慢。

我将其与以下内容进行了比较：

public static int[] TakeLast(this int[] inputArray, int count)
{
    int[] returnArray = new int[count];
    int startIndex = Math.Max(inputArray.Count() - count, 0);
    unsafe
    {
        fixed (int* itemArrayPtr = &(inputArray[startIndex]))
        {
            fixed (int* arrayPtr = &(returnArray[0]))
            {
                int* itemValuePtr = itemArrayPtr;
                int* valuePtr = arrayPtr;

                for (int i = 0; i < count; i++)
                {
                    *valuePtr++ = *itemValuePtr++;
                }
            }
        }
    }
    return returnArray;
}

这个方法很好，但不能通用化（我希望它可以适用于任何基本类型（int、float、double等）。

有没有一种方法能够使用通用/linq/...方法实现相当的性能？对我来说，只需要让它在Array上运行即可，不需要在IEnumerable上工作。

编辑 我目前正在测试您给我的所有方法，目前看来Array.Copy似乎更快：

Generating array for 100000000 elements.
SkipTake: 00:00:00.3009047
Unsafe: 00:00:00.0006289
Array.Copy: 00:00:00.0000012
Buffer.BlockCopy: 00:00:00.0001860
Reverse Linq: 00:00:00.2201143
Finished

- J4N

---

new T[count] 后面跟着 Array.Copy？顺便说一下，如果有一个简短的程序可以演示 Enumerable.Skip / Enumerable.Take 的缓慢之处，那就太好了，这样就可以实际测试建议的替代方案，而不仅仅是猜测。 - user743382

是的，我本以为Array.Copy()和使用指针算术一样快，因为它可能在实现中使用了memcpy等效函数。 - Matthew Watson

我不认为这会有明显的差异，但你对Take()的调用是不必要的。如果你只使用myArray.Skip(myArray.Length - toTake)，性能是否会有很大提升？ - Lance U. Matthews

@hvd：请将此作为答案发布。真是太快了！ - J4N

@BACON 很好的一点，我测试了没有使用 Take() 但仍然感觉很慢。 - J4N

@J4N 当然，已经发布为答案。 - user743382

Answer 1

根据评论：

public static T[] TakeLast<T>(this T[] inputArray, int count)
{
    var result = new T[count];
    Array.Copy(inputArray, inputArray.Length - count, result, 0, count);
    return result;
}

看起来表现良好。值得指出的是，根据具体需求，可能可以避免使用新数组，并迭代原始inputArray。你不能比不复制更快。:)

- user743382

---

我的测试表明这是最好的解决方案，我的观点是如此。也许你应该在开头添加 count = Math.Min(count, inputArray.Length);。 - Matthew Watson

谢谢，经过我的所有测试，这是更好的解决方案。你如何避免使用新数组？（在我的情况下，我可以直接引用基本数组，原始数组和目标数组都不会被更改，只进行只读操作） - J4N

@J4N 你可以创建一个自定义的IEnumerable<T>，它保存对原始数组的引用以及该数组中的索引。这类似于Enumerable.Skip的工作原理，但是首先，由于您知道要处理的是数组，因此可以通过索引访问数组元素，其次，您拥有足够的额外信息以避免不必要的装箱操作。是否比复制数据执行得更好取决于所涉及的数据。 - user743382

你也可以使用 ArraySegment，它实现了 IEnumerable<T>（但我认为你需要 .Net 4.5 版本才能使用 IEnumerable 功能）。 - Matthew Watson

@MatthewWatson 哈哈，我不知道那个存在。那基本上就是我所建议的，唯一的区别可能是根据数据，添加一个返回值类型的 GetEnumerator() 方法可能会更有益。 :) - user743382

我也不知道。但在我的情况下，我必须返回一个数组而不是一个IEnumerable。但原始解决方案的速度已经足够快了;) 谢谢你们两个。 - J4N

Answer 2

这个怎么样？应该相当快：

public static class ArrayExt
{
    public static T[] TakeLast<T>(this T[] inputArray, int count) where T: struct
    {
        count = Math.Min(count, inputArray.Length);
        int size = Marshal.SizeOf(typeof(T));

        T[] result = new T[count];
        Buffer.BlockCopy(inputArray, (inputArray.Length-count)*size, result, 0, count*size);

        return result;
    }
}

（我认为这比Array.Copy()在原始类型方面更快。但我不会把它视为理所当然——5分钟内会回来进行一些计时。;)

---

[编辑]计时显示Array.Copy()速度类似，但结果因运行和数组大小而异。

这是一些示例代码:

using System;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;

namespace Demo
{
    internal class Program
    {
        private void run()
        {
            const int ARRAY_SIZE = 10000;
            var array = Enumerable.Range(0, ARRAY_SIZE).Select(x => x).ToArray();
            Stopwatch sw = new Stopwatch();
            const int COUNT = 100000;

            for (int i = 0; i < 8; ++i)
            {
                sw.Restart();

                for (int j = 0; j < COUNT; ++j)
                    array.TakeLastViaArrayCopy(ARRAY_SIZE/2);

                Console.WriteLine("TakeLastViaArrayCopy took " + sw.Elapsed);

                sw.Restart();

                for (int j = 0; j < COUNT; ++j)
                    array.TakeLastViaBlockCopy(ARRAY_SIZE/2);

                Console.WriteLine("TakeLastViaBlockCopy took " + sw.Elapsed);
                Console.WriteLine();
            }
        }

        private static void Main()
        {
            new Program().run();
        }
    }

    public static class ArrayExt
    {
        public static T[] TakeLastViaBlockCopy<T>(this T[] inputArray, int count) where T: struct
        {
            count = Math.Min(count, inputArray.Length);
            int size = Marshal.SizeOf(typeof(T));

            T[] result = new T[count];
            Buffer.BlockCopy(inputArray, (inputArray.Length-count)*size, result, 0, count*size);

            return result;
        }

        public static T[] TakeLastViaArrayCopy<T>(this T[] inputArray, int count) where T: struct
        {
            count = Math.Min(count, inputArray.Length);

            T[] result = new T[count];
            Array.Copy(inputArray, inputArray.Length-count, result, 0, count);

            return result;
        }
    }
}

结果（像往常一样发布版本）：

TakeLastViaArrayCopy took 00:00:00.3028503
TakeLastViaBlockCopy took 00:00:00.3052196

TakeLastViaArrayCopy took 00:00:00.2969425
TakeLastViaBlockCopy took 00:00:00.3000117

TakeLastViaArrayCopy took 00:00:00.2906120
TakeLastViaBlockCopy took 00:00:00.2987753

TakeLastViaArrayCopy took 00:00:00.2954674
TakeLastViaBlockCopy took 00:00:00.3005010

TakeLastViaArrayCopy took 00:00:00.2944490
TakeLastViaBlockCopy took 00:00:00.3006893

TakeLastViaArrayCopy took 00:00:00.3041998
TakeLastViaBlockCopy took 00:00:00.2920206

TakeLastViaArrayCopy took 00:00:00.3115137
TakeLastViaBlockCopy took 00:00:00.2996884

TakeLastViaArrayCopy took 00:00:00.2906820
TakeLastViaBlockCopy took 00:00:00.2985933

Array.Copy()更简单易用，因此应该使用它。

- Matthew Watson

---

不错，但这比Array.Copy更快的原因是什么？目前我的测试并没有显示出它更快。 - J4N

@J4N 它不是更快 - 我刚试过了。Array.Copy() 更快。我会在我的回答中加上免责声明 - 你需要发布你的 Array.Copy() 回答。 :) - Matthew Watson

是的，但我想奖励提供这个解决方案的hvc。所以如果他不发布，我会发布。 - J4N

@J4N 对不起，抱歉，我是说hvd应该发布它（我误称“你”了）。 - Matthew Watson

Answer 3

自从 C#8 版本起，你可以像这样使用一个范围。

var lastN = array[^n..];

- Nechemia Hoffmann

Answer 4

myArray.Reverse().Take(toTake).Reverse();

- w.b

---

似乎比Skip.Take快一点，但仍需要很长时间。 - J4N