Почему обработка массивов в F # быстрее, чем списки

Я проверял производительность списков F # и массивов. С учетом кода:

let list = [ 1.. 100000 ]
for i in 1 .. 100 do ignore ( list|>List.map(fun n -> n))

let array = [| 1.. 100000 |]
for i in 1 .. 100 do ignore ( array|>Array.map(fun n -> n))

Я бы заподозрил, что оба они будут работать в очень похожее время. На самом деле оказалось, что массивы более чем в 10 раз быстрее: массив занимает 28 мс, а список занимает 346 мс! Почему это? Я понимаю концепцию списка в F # и тот факт, что, например, добавление значений в список или получение подпоследовательности занимает много времени, но в этом коде он просто выполняет итерации по всем элементам, поэтому я думал, что время будет очень сопоставимым.

Тесты в режиме выпуска в Visual Studio 2012 (в режиме Debug в массиве примерно в 5 раз быстрее).

Ответ 1

Основное отличие состоит в том, что массивы выделяются как непрерывный блок памяти - функция Array.map знает размер входного массива и может выполнять только одно выделение, чтобы получить всю память для результирующего массива. С другой стороны, функция List.map должна отдельно выделять одну "cons cell" для каждого элемента входного массива.

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

for i in 1 .. 100 do ignore ( list|>List.filter(fun n -> n%5=1))
for i in 1 .. 100 do ignore ( array|>Array.map(fun n -> n%5=1))

Использование списков имеет другие преимущества - поскольку они неизменяемы, вы можете безопасно обмениваться ссылками на списки. Кроме того, клонирование списка и добавление элемента в начало суперэффективно (выделение одной ячейки), при этом аналогичная операция с массивом будет очень медленной (скопируйте весь массив).