将唯一数组元素移动到前面并对数组进行切片的最快方法

Question

我有一个函数可以获取指向大小为 4（始终）的数组的指针，并且必须仅对唯一元素和 return 进行切片。此函数每秒被调用 100k 次，这就是为什么它需要快速并且不会对 GC 造成太大压力（这就是为什么缓冲区变量是指针 - stackalloc）。

private const int BufferLength = 4;
private static unsafe ReadOnlySpan<int> SliceUnique(int* buffer)
{
   // TODO: move the unique elements to the front
   // and get the last unique index

   return new ReadOnlySpan<int>(buffer, lastUniqueIndex + 1);
}

// Example: 
// input: [1, 3, 2, 1]                      | [1, 4, 4, 4]
// output: [1, 3, 2] (order doesn't matter) | [1, 4]

Answer 1

对于数组 [a,b,c,d]:

if (a==b)
    if (b==c)
        if (c==d)
            return (a,1)
        else
            return (a,d,2)
    else
        if (c==d)
            return (a,c,2)
        else
            if (a==d)
                return (a,c,2)
            else
                return (a,c,d,3)
else
    if (b==c)
        if (c==d)
            return (a,b,2)
        else
            if (a==d)
                return (a,b,2)
            else   
                return (a,b,d,3)
    else
        if (c==d)
            if (a==c)
                return (a,b,2)
            else
                return (a,b,c,3)
        else
            if (a==c)
                if (b==d)
                    return (a,b,2)
                else
                    return (a,b,d,3)
            else
                if (b==d)
                    return (a,b,c,3)
                else
                    if (a==d)
                        return (a,b,c,3)
                    else
                        return (a,b,c,d,4)

...你明白了...只是从我脑海中浮现出来，所以最好对所有可能的输入进行单元测试:-)

Answer 2

这是我想出的（当问题是关于整数数组时，但我确信它可以被修改以处理 ReadOnlySpan<int>（无论那是什么......））。
在我的计算机上测试，1,000,000 个数组（包括数组的创建）的平均执行时间为 195 毫秒：

int[] RemoveDuplicates(int[] array)
{
    bool remove1 = array[1] == array[0];
    bool remove2 = array[2] == array[1] || array[2] == array[0];
    bool remove3 = array[3] == array[2] || array[3] == array[1] || array[3] == array[0];

    if (remove1 && remove2 && remove3)
        return new int[] { array[0] };
    if (remove1 && remove2)
        return new int[] { array[0], array[3] };
    if (remove1 && remove3)
        return new int[] { array[0], array[2] };
    if (remove2 && remove3)
        return new int[] { array[0], array[1] };
    if (remove1)
        return new int[] { array[0], array[2], array[3] };
    if (remove2)
        return new int[] { array[0], array[1], array[3] };
    if (remove3)
        return new int[] { array[0], array[1], array[2] };
    return new int[] { array[0], array[1], array[2], array[3] };
}

测试代码：

static void Main(string[] args)
{
    long sum = 0;
    var stopwatch = new System.Diagnostics.Stopwatch();
    var numberOfTimes = 1000 * 1000;
    for (int i = 0; i < 100; i++)
    {
        stopwatch.Restart();
        for (int j = 0; j < numberOfTimes; j++)
        {
            var a = new int[] { j % 2, j % 3, j % 4, j % 5 };
            var r = RemoveDuplicates(a);
        }
        stopwatch.Stop();
        sum += stopwatch.ElapsedMilliseconds;
        // Console.WriteLine(string.Format("{0} => {1}", string.Join(",", a), string.Join(",", r)));
    }
    double avg = sum / 100;
    Console.WriteLine("Average execution time (100 executions) is {0}", avg);
    Console.ReadKey();
}

Answer 3

@ZoharPeled 回答 - 使用 ReadOnlySpan

优化

    private static unsafe ReadOnlySpan<int> SliceUniqueZoharPeledOptimized(int* buffer)
    {
        bool remove1 = buffer[1] == buffer[0];
        bool remove2 = buffer[2] == buffer[1] || buffer[2] == buffer[0];
        bool remove3 = buffer[3] == buffer[2] || buffer[3] == buffer[1] || buffer[3] == buffer[0];

        if (remove1 && remove2 && remove3)
        {
            return new ReadOnlySpan<int>(buffer, 1);
        }

        if (remove1 && remove2)
        {
            buffer[1] = buffer[3];
            return new ReadOnlySpan<int>(buffer, 2);
        }

        if (remove1 && remove3)
        {
            buffer[1] = buffer[2];
            return new ReadOnlySpan<int>(buffer, 2);
        }

        if (remove2 && remove3)
        {
            return new ReadOnlySpan<int>(buffer, 2);
        }

        if (remove1)
        {
            buffer[1] = buffer[3];
            return new ReadOnlySpan<int>(buffer, 3);
        }

        if (remove2)
        {
            buffer[2] = buffer[3];
            return new ReadOnlySpan<int>(buffer, 3);
        }

        if (remove3)
        {
            return new ReadOnlySpan<int>(buffer, 3);
        }

        return new ReadOnlySpan<int>(buffer, 4);
    }

将唯一数组元素移动到前面并对数组进行切片的最快方法

Fastest way to move unique array elements to the front and slice the array

c#

arrays

performance

pointers

unsafe