Array.Copy против Пропустить и взять в С#

Я просматривал этот вопрос и некоторые подобные:

Получение подмассива из существующего массива

Во многих местах я читал такие ответы:

Получение подмассива из существующего массив

Мне интересно, почему Skip и Take не являются операциями с постоянным временем для массивов?

В свою очередь, если бы они были операциями с постоянным временем, не будет ли метод Skip и Take (без вызова ToArray() в конце) иметь такое же время выполнения без накладных расходов, связанных с выполнением Array.Copy, но при этом более эффективное использование пространства?


arrays c# copy skip take
person Rob Hinchliff    schedule 09.09.2011    source источник
comment
Учитывая, что вы исследуете этот материал, вот полезный лакомый кусочек: Buffer.BlockCopy (DMA) действительно быстрее по сравнению с Array.Copy (O(n)) — хотя он работает только для примитивов (int, float и т. д.) .   -  person Jonathan Dickinson    schedule 09.09.2011
comment
Это не поможет мне именно в том, на что я смотрю, поскольку я использую массивы объектов, но это определенно полезно знать, спасибо.   -  person Rob Hinchliff    schedule 09.09.2011

Ответы (1)


arrow_upward
5
arrow_downward

Вы должны различать работу, которую выполняют методы Skip и Take, и работу по потреблению данных, которые возвращают методы.

Сами методы Skip и Take являются операциями O(1), поскольку выполняемая ими работа не зависит от размера входных данных. Они просто настроили перечислитель, способный возвращать элементы из массива.

Работа выполнена, когда вы используете перечислитель. Это операция O(n), где n — количество элементов, которые производит перечислитель. Поскольку перечислители считывают данные из массива, они не содержат копии данных, и вы должны сохранять данные в массиве нетронутыми, пока используете перечислитель.

(Если вы используете Skip для коллекции, которая недоступна по индексу, такой как массив, получение первого элемента — это операция O (n), где n — количество пропущенных элементов.)

person Guffa    schedule 09.09.2011
comment
Однако перечисление массива с помощью Skip and Take не менее эффективно, чем перечисление копии массива, верно? Оценка Skip и Take - постоянное время. Просто к вашему сведению, в моем случае использования ссылочный массив остается неизменным. - person Rob Hinchliff; 09.09.2011
comment
@Rob Hinchliff: в обоих методах есть накладные расходы. Если вы копируете массив, у вас есть накладные расходы на копирование, но тогда вы получаете полное преимущество зацикливания массива, т. е. проверки диапазона при доступе к массиву можно оптимизировать. Когда вы используете перечислитель, накладные расходы находятся в коде перечислителя, т. е. для доступа к каждому элементу требуется немного больше времени. Реальное преимущество перечислителя заключается в том, что вам не нужно хранить копию массива в памяти, что в основном является проблемой только для больших массивов. - person Guffa; 09.09.2011
comment
В чем заключаются дополнительные затраты на перечисление коллекции, возвращаемой Take()? Это что-то вроде того, что на каждой итерации нужно проверять, превышает ли текущий индекс число, переданное в качестве параметра Take()? Если да, то почему это не оптимизировано так же, как скопированный массив, поскольку здесь также можно было бы выполнить проверку диапазона? - person Rob Hinchliff; 09.09.2011
comment
@Rob Hinchliff: накладные расходы в основном связаны с тем, что возвращается не коллекция, а перечислитель. Код вызывает метод MoveNext и свойство Current перечислителя, и это нельзя оптимизировать так же, как доступ к массиву в цикле. Таким образом, доступ к массиву соответствует вызову двух методов, и хотя это не так уж и сложно, это гораздо больше, чем просто прямой доступ к массиву. - person Guffa; 09.09.2011
comment
Это потому, что компилятор не может видеть, что базовая коллекция на самом деле является массивом позади интерфейса IEnumerable, возвращаемого Take()? Думаю, я надеялся, что объект, возвращаемый Take(), возможно, будет иметь немного метаданных или что-то, что убедит среду выполнения использовать цикл массива. - person Rob Hinchliff; 09.09.2011
comment
@Rob Hinchliff: Да, компилятору становится слишком сложно оптимизировать. Можно было бы сделать компилятор посложнее, чтобы он ловил подобные вещи, но маловероятно, что он будет развиваться в этом направлении. Это достаточно хорошо для большинства применений, и если вам действительно нужна дополнительная производительность, вы можете самостоятельно зациклить массив вместо использования методов расширения. - person Guffa; 09.09.2011
comment
И кажется, что с текущими JITters не имеет значения, доступна ли коллекция... по индексу. - person Mark Hurd; 08.01.2015