Самый быстрый способ нарезать массив на две части

Question

У меня есть массив, скажем:

var arr1 = new [] { 1, 2, 3, 4, 5, 6 };

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

arr1 = new [] { 1, 2, 3 };
newArr = new [] { 4, 5, 6 };

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

---

Дополнительная информация:

• Массивы должны быть в состоянии увеличиваться без больших потерь производительности
• Массивы будут содержать только Int32
• Назначение массива - сгруппировать числа в исходном массиве без сортировки всего списка

Вкратце: я хочу разделить следующий входной массив:

int[] arr = new int[] { 1, 3, 4, 29, 31, 33, 35, 36, 37 };

в

arr1 =  1, 3, 4
arr2 =  29, 31, 33, 35, 36, 37

но поскольку идеальная скорость достигается при размере массива 3, arr2 следует разделить на 2 массива равномерного размера.

Примечание

Я знаю, что реализация массива в памяти довольно наивна (ну, по крайней мере, это в C, где вы можете манипулировать количеством элементов в массиве, чтобы размер массива изменялся). Также, что где-то в Win32 API есть функция memory move. Поэтому я думаю, что это будет самый быстрый:

1. Изменить arr1, чтобы оно содержало только 3 элемента
2. Создать новый массив arr2 с размером 3
3. Переместить байты, которые больше не находятся в arr1 в arr2

Answer 1

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

int[] firstChunk = new int[3];
int[] secondChunk = new int[3];
Array.Copy(arr1, 0, firstChunk, 0, 3);
Array.Copy(arr1, 3, secondChunk, 0, 3);

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

Вы могли бы также рассмотреть , а не на самом деле разбиение массива, но вместо этого использовать ArraySegment, чтобы иметь отдельные "куски" массива. Или, возможно, используйте List<T>, чтобы начать с ... трудно понять, не имея больше контекста.

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

Answer 2

Вы ищете что-то подобное?

static unsafe void DoIt(int* ptr)
{
    Console.WriteLine(ptr[0]);
    Console.WriteLine(ptr[1]);
    Console.WriteLine(ptr[2]);
}

static unsafe void Main()
{
    var bytes = new byte[1024];
    new Random().NextBytes(bytes);

    fixed (byte* p = bytes)
    {
        for (int i = 0; i < bytes.Length; i += sizeof(int))
        {
            DoIt((int*)(p + i));
        }
    }

    Console.ReadKey();
}

Это позволяет избежать создания новых массивов (размер которых не может быть изменен, даже с небезопасным кодом!) Полностью и просто передается указательв массив некоторому методу, который читает первые три целых числа.

Answer 3

Если ваш массив всегда будет содержать 6 элементов, как о:

var newarr1 = new []{oldarr[0], oldarr[1],oldarr[2]};
var newarr2 = new []{oldarr[3], oldarr[4],oldarr[5]};

Чтение из памяти происходит быстро.

Answer 4

Поскольку размеры массивов в C # не изменяются динамически, это означает, что ваш первый массив должен иметь минимальную длину 5 или максимальную длину 6, в зависимости от вашей реализации. Затем вам нужно будет динамически создавать новые статические массивы из 3 каждый раз, когда вам нужно разделить. Только после каждого разбиения элементы вашего массива будут в их естественном порядке, если вы не сделаете каждый новый массив длиной 5 или 6 и добавите только самые последние. Этот подход означает, что каждый новый массив будет иметь 2-3 дополнительных указателя.

Если у вас нет известного количества элементов для добавления в ваш массив ДО компиляции приложения, вам также понадобится некоторая форма держателя для ваших динамически создаваемых массивов, то есть вам понадобится массив массивов (зубчатый массив). Поскольку ваш зубчатый массив также имеет статический размер, вам необходимо иметь возможность динамически воссоздавать и изменять его размер по мере создания каждого нового динамически создаваемого массива.

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

---

ОБНОВЛЕНИЕ: Итак, если бы это было абсолютно необходимо от меня ...

public class MyArrayClass
{
    private int[][] _master = new int[10][];
    private int[] _current = new int[3];
    private int _currentCount, _masterCount;

    public void Add(int number)
    {
        _current[_currentCount] = number;
        _currentCount += 1;
        if (_currentCount == _current.Length)
        {
            Array.Copy(_current,0,_master[_masterCount],0,3);
            _currentCount = 0;
            _current = new int[3];
            _masterCount += 1;
            if (_masterCount == _master.Length)
            {
                int[][] newMaster = new int[_master.Length + 10][];
                Array.Copy(_master, 0, newMaster, 0, _master.Length);
                _master = newMaster;
            }
        }
    }

    public int[][] GetMyArray()
    {
        return _master;
    }

    public int[] GetMinorArray(int index)
    {
        return _master[index];
    }

    public int GetItem(int MasterIndex, int MinorIndex)
    {
        return _master[MasterIndex][MinorIndex];
    }
}

Примечание: это, вероятно, не идеальный код, это ужасный способ реализации вещей, и я НИКОГДА не буду делать это в рабочем коде.

Answer 5

Обязательное решение LINQ:

if(arr1.Length > 5)
{
   var newArr = arr1.Skip(arr1.Length / 2).ToArray();
   arr1 = arr1.Take(arr1.Length / 2).ToArray();
}

LINQ быстрее, чем вы думаете; это в основном будет ограничено способностью Framework проходить через IEnumerable (который в массиве чертовски быстр). Это должно выполняться примерно за линейное время и может принимать любой начальный размер arr1.