C# самый быстрый способ сместить массив

Не могли бы вы использовать System.Collections.Generic.Queue вместо массива?

Я чувствую, что вам нужно выполнить действия с вашим значением отказаться от него, поэтому использование очереди кажется более подходящим:

// dummy initialization
        System.Collections.Generic.Queue<int> queue = new Queue<int>();
        for (int i = 0; i < 7; ++i ) { queue.Enqueue(i); }// add each element at the end of the container

        // working thread
        if (queue.Count > 0)
            doSomething(queue.Dequeue());// removes the last element of the container and calls doSomething on it

Вот мой тестовый комплект ...

var source = Enumerable.Range(1, 100).Cast<int?>().ToArray();
var destination = new int?[source.Length];

var s = new Stopwatch();
s.Start();
for (int i = 0; i < 1000000;i++)
{
    Array.Copy(source, 1, destination, 0, source.Length - 1);
}
s.Stop();
Console.WriteLine(s.Elapsed);

Вот результаты производительности для 1 миллиона итераций каждого решения (8 Core Intel Xeon E5450 @ 3,00 ГГц)

                       100 elements  10000 elements
For Loop                     0.390s         31.839s 
Array.Copy()                 0.177s         12.496s
Aaron 1                      3.789s         84.082s
Array.ConstrainedCopy()      0.197s         17.658s

Выбирайте сами :)

Копирование массива - это операция O (n), при которой создается новый массив. Хотя копирование массива, безусловно, может быть выполнено быстро и эффективно, указанная вами проблема может быть решена совершенно другим способом без (как вы и просили) создание новой структуры массива / данных и создание только одного небольшого экземпляра объекта-оболочки для каждого массива:

using System;
using System.Text;

public class ArrayReindexer
{
    private Array reindexed;
    private int location, offset;

    public ArrayReindexer( Array source )
    {
        reindexed = source;
    }

    public object this[int index]
    {
        get
        {
            if (offset > 0 && index >= location)
            {
                int adjustedIndex = index + offset;
                return adjustedIndex >= reindexed.Length ? "null" : reindexed.GetValue( adjustedIndex );
            }

            return reindexed.GetValue( index );
        }
    }

    public void Reindex( int position, int shiftAmount )
    {
        location = position;
        offset = shiftAmount;
    }

    public override string ToString()
    {
        StringBuilder output = new StringBuilder( "[ " );
        for (int i = 0; i < reindexed.Length; ++i)
        {
            output.Append( this[i] );
            if (i == reindexed.Length - 1)
            {
                output.Append( " ]" );
            }
            else
            {
                output.Append( ", " );
            }
        }

        return output.ToString();
    }
}

Обертывая и контролируя доступ к массиву таким образом, мы теперь можем продемонстрировать, как проблема была решена с помощью вызов метода O (1) ...

ArrayReindexer original = new ArrayReindexer( SourceArray );
Console.WriteLine( "   Base array: {0}", original.ToString() );
ArrayReindexer reindexed = new ArrayReindexer( SourceArray );
reindexed.Reindex( 1, 1 );
Console.WriteLine( "Shifted array: {0}", reindexed.ToString() );

выдаст результат:

Базовый массив: [0, 1, 2, 3, 4, 5, 6]
Сдвинутый массив: [0, 2, 3, 4, 5, 6, null]

Я готов поспорить, что будет причина, по которой такое решение не сработает для вас, но я считаю, что это соответствует вашему первоначальному заявлению требования. 8)

Часто бывает полезно подумать обо всех видах решений проблемы, прежде чем реализовывать конкретную, и, возможно, это может быть самым важным, что может продемонстрировать этот пример.

Надеюсь, это поможет!

Вы можете использовать один и тот же массив в качестве источника и назначения для быстрого копирования на месте:

static void Main(string[] args)
        {
            int[] array = {0, 1, 2, 3, 4, 5, 6, 7};
            Array.ConstrainedCopy(array, 1, array, 0, array.Length - 1);
            array[array.Length - 1] = 0;
        }

Вы не можете

• выделить массив с дополнительными 1000 элементов

• иметь целочисленную переменную int base = 0

• вместо доступа к a [i] access a [base + i]

• для выполнения смены просто скажите base ++

Затем, после того как вы проделаете это 1000 раз, скопируйте его и начните заново.
Таким образом, вы будете копировать только один раз за 1000 смен.

Старая шутка:
В: Сколько нужно IBM 360, чтобы сдвинуть регистр на 1 бит?
A: 33. 32, чтобы удерживать биты на месте , и 1, чтобы переместить регистр. (или что-то в этом роде ...)

Используйте метод Array.Copy () , как в

int?[] myArray = new int?[]{0,1,2,3,4};
Array.Copy(myArray, 1, myArray, 0, myArray.Length - 1);
myArray[myArray.Length - 1] = null

Вероятно, Array.Copy - это способ, Microsoft хотела, чтобы мы скопировали элементы массива ...

Вот мое решение, похожее на Task в том, что это простая оболочка Array, и сдвиг массива влево занимает O (1) времени .

public class ShiftyArray<T>
{
    private readonly T[] array;
    private int front;

    public ShiftyArray(T[] array)
    {
        this.array = array;
        front = 0;
    }

    public void ShiftLeft()
    {
        array[front++] = default(T);
        if(front > array.Length - 1)
        {
            front = 0;
        }
    }

    public void ShiftLeft(int count)
    {
        for(int i = 0; i < count; i++)
        {
            ShiftLeft();
        }
    }

    public T this[int index]
    {
        get
        {
            if(index > array.Length - 1)
            {
                throw new IndexOutOfRangeException();
            }

            return array[(front + index) % array.Length];
        }
    }

    public int Length { get { return array.Length; } }
}

Запуск его через тестовый код Джейсона Пуньона ...

int?[] intData = Enumerable.Range(1, 100).Cast<int?>().ToArray();
ShiftyArray<int?> array = new ShiftyArray<int?>(intData);

Stopwatch watch = new Stopwatch();
watch.Start();

for(int i = 0; i < 1000000; i++)
{
    array.ShiftLeft();
}

watch.Stop();

Console.WriteLine(watch.ElapsedMilliseconds);

Занимает ~ 29 мсек, независимо от размера массива.

Вы можете сделать это так:

var items = new int?[] { 0, 1, 2, 3, 4, 5, 6 };  // Your array
var itemList = new List<int?>(items);  // Put the items in a List<>
itemList.RemoveAt(1); // Remove the item at index 1
itemList.Add(null); // Add a null to the end of the list
items = itemList.ToArray(); // Turn the list back into an array

Конечно, было бы эффективнее полностью избавиться от массива и просто использовать List <> . Затем вы можете забыть первую и последнюю строки и сделать это так:

var itemList = new List<int?> { 0, 1, 2, 3, 4, 5, 6 };
itemList.RemoveAt(1); // Remove the item at index 1
itemList.Add(null); // Add a null to the end of the list

Неправильный и немного забавный ответ (спасибо, я буду здесь всю ночь!)

int?[] test = new int?[] {0,1,2,3,4,5,6 };

        int?[] t = new int?[test.Length];
        t = test.Skip(1).ToArray();
        t[t.Length - 1] = null; 

В духе использования Skip (не спрашивайте меня, я знаю худшее использование методов расширения LINQ), единственный способ, которым я думал переписать это было бы

        int?[] test = new int?[] { 0, 1, 2, 3, 4, 5, 6 };

        int?[] t = new int?[test.Length];
        Array.Copy(test.Skip(1).ToArray(), t, t.Length - 1);

Но это НИКОГДА не быстрее, чем другие варианты.

Если он абсолютно должен быть в массиве, то я бы рекомендовал использовать наиболее очевидный код.

for (int index = startIndex; index + 1 < values.Length; index++)
     values[index] = values[index + 1];
values[values.Length - 1] = null;

Это даст оптимизатору больше возможностей найти наилучший путь на любой целевой платформе, на которую будет установлена программа.

EDIT:

Я только что позаимствовал тестовый код Джейсона Пуньона, и боюсь, что он прав. Array.Copy побеждает!

    var source = Enumerable.Range(1, 100).Cast<int?>().ToArray();
    int indexToRemove = 4;

    var s = new Stopwatch();
    s.Start();
    for (int i = 0; i < 1000000; i++)
    {
        Array.Copy(source, indexToRemove + 1, source, indexToRemove, source.Length - indexToRemove - 1);
        //for (int index = indexToRemove; index + 1 < source.Length; index++)
        //    source[index] = source[index + 1]; 
    }
    s.Stop();
    Console.WriteLine(s.Elapsed);

Array.Copy занимает от 103 до 150 мс на моей машине.

цикл for занимает от 269 до 338 мс на моей машине.

самый быстрый способ сделать это - использовать Array.Copy , который в окончательной реализации использует операцию массовой передачи памяти (аналогично memcpy):

var oldArray = new int?[] { 1, 2, 3, 4, 5, 6 };
var newArray = new int?[oldArray.Length];
Array.Copy(oldArray, 1, newArray, 0, oldArray.Length - 1);
// newArray is now { 2, 3, 4, 5, 6, null }

Отредактировано: согласно документации :

Если sourceArray и destinationArray перекрываются, этот метод ведет себя так, как если бы исходные значения sourceArray были сохранены во временном месте до destinationArray перезаписывается.

Итак, если вы не хотите выделять новый массив, вы можете передать исходный массив как для источника, так и для пункта назначения - хотя я полагаю, что компромисс будет несколько медленнее, поскольку значения проходят через временную удерживаемую позицию .

Полагаю, как и в любом расследовании подобного рода, вам следует быстро провести сравнительный анализ.