Есть ли способ добавления хвоста в массив, который более эффективен, чем добавление в F#?
В настоящее время я пытаюсь создать программу, в которой у меня есть рекурсивная функция, которая для каждого цикла добавляет один новый элемент в массив, который она создает. Я не хотел использовать функцию добавления много раз, потому что моя функция должна выполнять большое количество циклов, и из предыдущего опыта я узнал, что функция добавления в общем случае занимает много времени. Я пытался везде искать функцию, которая просто добавляет один элемент в конец массива, но я не нашел ничего подобного. Так что я думал, что я хотел бы спросить здесь.
Поэтому мой вопрос в основном таков: "Есть ли более эффективный способ добавления одного элемента в конец массива, чем добавление?"
Обновлено с новым вопросом относительно предыдущего
Поэтому вместо этого я использовал список, вставляя каждый новый элемент в качестве заголовка, и возвращал список по завершении функции. Это сделало функцию примерно в 70 раз быстрее. Но проблема остается, так как у меня есть другая функция, которая делает почти то же самое, которая стала примерно в 4 раза медленнее, увеличив общее время выполнения моей основной функции. Функции очень похожи. Первая функция (которая стала намного быстрее) генерирует целочисленные значения, добавляя каждый новый int в список. Вторая функция (та, которая стала намного медленнее) создает объект, добавляя каждый новый объект в список. У кого-нибудь есть идея, почему одна функция стала намного быстрее, а другая стала намного медленнее?
3 ответа
ResizeArray - более эффективная структура данных для этой задачи, например:
let filterRange predicate (i, j) =
let results = ResizeArray(j-i+1)
for k = i to j do
if predicate k then results.Add(k)
results.ToArray()
Модуль ResizeArray из F# PowerPack предоставляет функции высокого порядка для управления ResizeArray функционально. Однако следует помнить, что эти функции создают новые ResizeArray экземпляры, которые делают их менее эффективными, чем методы.NET.
Чисто функциональной альтернативой является использование списка в качестве аккумулятора, добавление элементов к аккумулятору, обращение его (если порядок имеет значение) и преобразование в массив в конце:
let filterRange predicate (i, j) =
let rec loop k acc =
if k = j+1 then acc
elif predicate k then loop (k+1) (k::acc)
else loop (k+1) acc
loop i [] |> List.rev |> Array.ofList
Я бы предложил использовать список вместо массива. Если вам действительно нужен окончательный результат в массиве, вы можете преобразовать список в массив в конце процесса - он все равно будет быстрее.