Типы коллекций F#

  • Статья

Просмотрив этот раздел, вы можете определить, какой тип коллекции F# лучше всего подходит для конкретной потребности. Эти типы коллекций отличаются от типов коллекций в .NET, таких как в System.Collections.Generic пространстве имен, в том, что типы коллекций F# предназначены с точки зрения функционального программирования, а не объектно-ориентированной перспективы. В частности, только коллекция массивов содержит изменяемые элементы. Поэтому при изменении коллекции создается экземпляр измененной коллекции вместо изменения исходной коллекции.

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

Таблица типов коллекций

В следующей таблице показаны типы коллекций F#.

Тип Описание Связанные ссылки
Список Упорядоченный, неизменяемый ряд элементов одного типа. Реализован как связанный список. Списки

Модуль list
Массив Фиксированная, отсчитываемая от нуля коллекция последовательных элементов данных, которые являются одинаковыми типами. Массивы

Модуль массива

Модуль Array2D

Модуль Array3D
Seq Логический ряд элементов, которые являются одним типом. Последовательности особенно полезны, если у вас есть большая упорядоченная коллекция данных, но не обязательно предполагается использовать все элементы. Отдельные элементы последовательности вычисляются только по мере необходимости, поэтому последовательность может работать лучше, чем список, если не все элементы используются. Последовательности представлены типом seq<'T> , который является псевдонимом для IEnumerable<T>. Таким образом, любой тип платформа .NET Framework, реализующий System.Collections.Generic.IEnumerable<'T> его, можно использовать в качестве последовательности. Последовательности

Модуль Seq
Map Неизменяемый словарь элементов. К элементам обращается ключ. Модуль map
Задание записи Неизменяемый набор, основанный на двоичных деревьях, где сравнение — функция структурного System.IComparable сравнения F#, которая потенциально использует реализации интерфейса для значений ключей. Установка модуля

Таблица функций

В этом разделе сравниваются функции, доступные в типах коллекций F#. Вычислительная сложность функции определяется, где N — это размер первой коллекции, а M — это размер второй коллекции, если таковой имеется. Тире (-) указывает, что эта функция недоступна в коллекции. Так как последовательности оцениваются безумно, функция, например O(1), так как Seq.distinct она возвращается немедленно, хотя она по-прежнему влияет на производительность последовательности при перечислении.

Function Массив List Sequence Карта Set Description
append O(N) O(N) O(N) - - Возвращает новую коллекцию, содержащую элементы первой коллекции, за которой следуют элементы второй коллекции.
add - - - O(log(N)) O(log(N)) Возвращает новую коллекцию с добавленным элементом.
average O(N) O(N) O(N) - - Возвращает среднее значение элементов в коллекции.
averageBy O(N) O(N) O(N) - - Возвращает среднее значение результатов предоставленной функции, примененной к каждому элементу.
blit O(N) - - - - Копирует раздел массива.
cache - - O(N) - - Вычисляет и сохраняет элементы последовательности.
cast - - O(N) - - Преобразует элементы в указанный тип.
choose O(N) O(N) O(N) - - Применяет данную функцию f к каждому элементу x списка. Возвращает список, содержащий результаты для каждого элемента, в котором функция возвращается Some(f(x)).
collect O(N) O(N) O(N) - - Применяет данную функцию к каждому элементу коллекции, объединяет все результаты и возвращает объединенный список.
compareWith - - O(N) - - Сравнивает две последовательности с помощью данной функции сравнения, элемента по элементу.
concat O(N) O(N) O(N) - - Объединяет указанные перечисления в виде единого объединения перечисления.
содержит - - - - O(log(N)) Возвращает значение true, если набор содержит указанный элемент.
containsKey - - - O(log(N)) - Проверяет, находится ли элемент в домене карты.
count - - - - O(N) Возвращает количество элементов в наборе.
countBy - - O(N) - - Применяет функцию создания ключей к каждому элементу последовательности и возвращает последовательность, которая дает уникальные ключи и их количество вхождения в исходной последовательности.
copy O(N) - O(N) - - Копирует коллекцию.
create O(N) - - - - Создает массив целых элементов, которые изначально являются заданным значением.
delay - - O(1) - - Возвращает последовательность, созданную из заданной отложенной спецификации последовательности.
различие - - - - O(M*log(N)) Возвращает новый набор с элементами второго набора, удаленным из первого набора.
distinct O(1)* Возвращает последовательность, которая не содержит повторяющихся записей в соответствии с универсальными хэшами и сравнениями равенства для записей. Если элемент возникает несколько раз в последовательности, последующие вхождения будут отключены карта.
distinctBy O(1)* Возвращает последовательность, содержащую повторяющиеся записи в соответствии с универсальными хэш-сравнениями и сравнениями равенства ключей, возвращаемых заданной функцией создания ключей. Если элемент возникает несколько раз в последовательности, последующие вхождения будут отключены карта.
empty O(1) O(1) O(1) O(1) O(1) Создает пустую коллекцию.
существует O(N) O(N) O(N) O(log(N)) O(log(N)) Проверяет, соответствует ли любой элемент последовательности заданному предикату.
существует2 O(min(N,M)) - O(min(N,M)) Проверяет, соответствует ли любая пара соответствующих элементов входных последовательностей заданному предикату.
fill O(N) Задает диапазон элементов массива заданному значению.
Фильтр O(N) O(N) O(N) O(N) O(N) Возвращает новую коллекцию, содержащую только элементы коллекции, для которой возвращается trueзаданный предикат.
поиск O(N) O(N) O(N) O(log(N)) - Возвращает первый элемент, для которого возвращается trueданная функция. Возвращает, System.Collections.Generic.KeyNotFoundException если такой элемент не существует.
findIndex O(N) O(N) O(N) - - Возвращает индекс первого элемента в массиве, который удовлетворяет заданному предикату. Вызывает, System.Collections.Generic.KeyNotFoundException если элемент не удовлетворяет предикату.
findKey - - - O(log(N)) - Вычисляет функцию для каждого сопоставления в коллекции и возвращает ключ для первого сопоставления, где функция возвращается true. Если такой элемент не существует, эта функция вызывается System.Collections.Generic.KeyNotFoundException.
Сложить O(N) O(N) O(N) O(N) O(N) Применяет функцию к каждому элементу коллекции, потокуя аргумент аккумулятора через вычисления. Если входная функция имеет значение f, а элементы — i0... IN, эта функция вычисляет f (... (f s i0)...) В.
свертка2 O(N) O(N) - - - Применяет функцию к соответствующим элементам двух коллекций, потокуя аргумент аккумулятора через вычисления. Коллекции должны иметь одинаковые размеры. Если входная функция имеет значение f, а элементы — i0... iN и j0... jN, эта функция вычисляет f (... (f s i0 j0)...) iN jN.
foldBack O(N) O(N) - O(N) O(N) Применяет функцию к каждому элементу коллекции, потокуя аргумент аккумулятора через вычисления. Если входная функция имеет значение f, а элементы — i0... IN, эта функция вычисляет f i0 (... (f iN s)).
foldBack2 O(N) O(N) - - - Применяет функцию к соответствующим элементам двух коллекций, потокуя аргумент аккумулятора через вычисления. Коллекции должны иметь одинаковые размеры. Если входная функция имеет значение f, а элементы — i0... iN и j0... jN, эта функция вычисляет f i0 j0 (... (fN jN s)).
forall O(N) O(N) O(N) O(N) O(N) Проверяет, соответствуют ли все элементы коллекции заданному предикату.
forall2 O(N) O(N) O(N) - - Проверяет, соответствуют ли все соответствующие элементы коллекции по парным предикатам.
get /nth O(1) O(N) O(N) - - Возвращает элемент из коллекции, заданный его индексом.
заголовок - O(1) O(1) - - Возвращает первый элемент коллекции.
init O(N) O(N) O(1) - - Создает коллекцию с учетом измерения и функции генератора для вычисления элементов.
initInfinite - - O(1) - - Создает последовательность, которая при итерации возвращает последовательные элементы путем вызова данной функции.
пересечение - - - - O(log(N)*log(M)) Вычисляет пересечение двух наборов.
intersectMany - - - - O(N1*N2...) Вычисляет пересечение последовательности наборов. Последовательность не должна быть пустой.
isEmpty O(1) O(1) O(1) O(1) - Возвращает значение true , если коллекция пуста.
isProperSubset - - - - O(M*log(N)) Возвращает, true если все элементы первого набора находятся во втором наборе, а хотя бы один элемент второго набора не входит в первый набор.
isProperSuperset - - - - O(M*log(N)) Возвращает, true если все элементы второго набора находятся в первом наборе, а хотя бы один элемент первого набора не входит во второй набор.
isSubset - - - - O(M*log(N)) Возвращает, true если все элементы первого набора находятся во втором наборе.
isSuperset - - - - O(M*log(N)) Возвращает, true если все элементы второго набора находятся в первом наборе.
Iter O(N) O(N) O(N) O(N) O(N) Применяет данную функцию к каждому элементу коллекции.
итери O(N) O(N) O(N) - - Применяет данную функцию к каждому элементу коллекции. Целое число, передаваемое функции, указывает индекс элемента.
iteri2 O(N) O(N) - - - Применяет данную функцию к паре элементов, которые извлекаются из сопоставленных индексов в двух массивах. Целое число, передаваемое функции, указывает индекс элементов. Два массива должны иметь одинаковую длину.
итер2 O(N) O(N) O(N) - - Применяет данную функцию к паре элементов, которые извлекаются из сопоставленных индексов в двух массивах. Два массива должны иметь одинаковую длину.
последняя O(1) O(N) O(N) - - Возвращает последний элемент в применимой коллекции.
length O(1) O(N) O(N) - - Возвращает количество элементов в коллекции.
map O(N) O(N) O(1) - - Создает коллекцию, элементы которой являются результатами применения данной функции к каждому элементу массива.
map2 O(N) O(N) O(1) - - Создает коллекцию, элементы которой являются результатами применения данной функции к соответствующим элементам двух коллекций по паре. Два входных массива должны иметь одинаковую длину.
map3 - O(N) - - - Создает коллекцию, элементы которой являются результатами применения данной функции к соответствующим элементам трех коллекций одновременно.
Mapi O(N) O(N) O(N) - - Создает массив, элементы которого являются результатами применения данной функции к каждому элементу массива. Целочисленный индекс, передаваемый функции, указывает индекс преобразуемого элемента.
mapi2 O(N) O(N) - - - Создает коллекцию, элементы которой являются результатами применения данной функции к соответствующим элементам двух коллекций по паре, а также передает индекс элементов. Два входных массива должны иметь одинаковую длину.
макс. O(N) O(N) O(N) - - Возвращает наибольший элемент коллекции, сравниваемый с помощью оператора max .
maxBy O(N) O(N) O(N) - - Возвращает наибольший элемент в коллекции, сравниваемый с использованием максимального значения результата функции.
maxElement - - - - O(log(N)) Возвращает величайший элемент в наборе в соответствии с порядком, используемым для набора.
мин O(N) O(N) O(N) - - Возвращает наименьший элемент коллекции, сравниваемый с помощью оператора min .
minBy O(N) O(N) O(N) - - Возвращает наименьший элемент коллекции, сравниваемый с помощью оператора min в результатах функции.
minElement - - - - O(log(N)) Возвращает самый низкий элемент набора в соответствии с порядком, используемым для набора.
ofArray - O(N) O(1) O(N) O(N) Создает коллекцию, содержащую те же элементы, что и заданный массив.
ofList O(N) - O(1) O(N) O(N) Создает коллекцию, содержащую те же элементы, что и указанный список.
ofSeq O(N) O(N) - O(N) O(N) Создает коллекцию, содержащую те же элементы, что и заданная последовательность.
Pairwise - - O(N) - - Возвращает последовательность каждого элемента во входной последовательности и его предшественнике, за исключением первого элемента, который возвращается только в качестве предшественника второго элемента.
секцию O(N) O(N) - O(N) O(N) Разделяет коллекцию на две коллекции. Первая коллекция содержит элементы, для которых возвращается заданный предикат, а вторая коллекция содержит элементы, для которых возвращается truefalseзаданный предикат.
пермут O(N) O(N) - - - Возвращает массив со всеми элементами в соответствии с указанной перемутацией.
Выбрать O(N) O(N) O(N) O(log(N)) - Применяет данную функцию к последовательным элементам, возвращая первый результат, в котором функция возвращает Some. Если функция никогда не возвращает некоторые, System.Collections.Generic.KeyNotFoundException вызывается.
readonly - - O(N) - - Создает объект последовательности, который делегирует заданному объекту последовательности. Эта операция гарантирует, что приведение типов не может повторно обнаружить и изменить исходную последовательность. Например, если задан массив, возвращаемая последовательность вернет элементы массива, но вы не можете привести возвращаемый объект последовательности к массиву.
reduce O(N) O(N) O(N) - - Применяет функцию к каждому элементу коллекции, потокуя аргумент аккумулятора через вычисления. Эта функция начинается с применения функции к первым двум элементам, передает этот результат в функцию вместе с третьим элементом и т. д. Функция возвращает окончательный результат.
reduceBack O(N) O(N) - - - Применяет функцию к каждому элементу коллекции, потокуя аргумент аккумулятора через вычисления. Если входная функция имеет значение f, а элементы — i0... IN, эта функция вычисляет f i0 (... (f iN-1 iN)).
remove - - - O(log(N)) O(log(N)) Удаляет элемент из домена карты. Исключение не возникает, если элемент отсутствует.
реплика te - O(N) - - - Создает список указанной длины с каждым элементом, заданным заданным значением.
rev O(N) O(N) - - - Возвращает новый список с элементами в обратном порядке.
scan O(N) O(N) O(N) - - Применяет функцию к каждому элементу коллекции, потокуя аргумент аккумулятора через вычисления. Эта операция применяет функцию ко второму аргументу и первому элементу списка. Затем операция передает этот результат в функцию вместе со вторым элементом и т. д. Наконец, операция возвращает список промежуточных результатов и окончательный результат.
scanBack O(N) O(N) - - - Напоминает операцию свертывания, но возвращает как промежуточные, так и конечные результаты.
singleton - - O(1) - O(1) Возвращает последовательность, которая дает только один элемент.
set O(1) - - - - Задает элемент массива указанному значению.
skip - - O(N) - - Возвращает последовательность, которая пропускает N-элементы базовой последовательности, а затем возвращает остальные элементы последовательности.
skipTime - - O(N) - - Возвращает последовательность, которая при итерации пропускает элементы базовой последовательности во время возврата true заданного предиката, а затем возвращает оставшиеся элементы последовательности.
sort Среднее значение O(N*log(N))

О(N^2) худший случай		 O(N*log(N)) O(N*log(N)) - - Сортирует коллекцию по значению элемента. Элементы сравниваются с помощью сравнения.
sortBy Среднее значение O(N*log(N))

О(N^2) худший случай		 O(N*log(N)) O(N*log(N)) - - Сортирует указанный список с помощью ключей, предоставляемых данной проекцией. Ключи сравниваются с помощью сравнения.
sortInPlace Среднее значение O(N*log(N))

О(N^2) худший случай		 - - - - Сортирует элементы массива, изменяя его и используя заданную функцию сравнения. Элементы сравниваются с помощью сравнения.
sortInPlaceBy Среднее значение O(N*log(N))

О(N^2) худший случай		 - - - - Сортирует элементы массива, изменяя его и используя заданную проекцию для ключей. Элементы сравниваются с помощью сравнения.
sortInPlaceWith Среднее значение O(N*log(N))

О(N^2) худший случай		 - - - - Сортирует элементы массива, изменяя его и используя заданную функцию сравнения в качестве порядка.
sortWith Среднее значение O(N*log(N))

О(N^2) худший случай		 O(N*log(N)) - - - Сортирует элементы коллекции, используя заданную функцию сравнения в качестве порядка и возвращая новую коллекцию.
дочерний объект O(N) - - - - Создает массив, содержащий заданный подранг, заданный путем запуска индекса и длины.
sum O(N) O(N) O(N) - - Возвращает сумму элементов в коллекции.
sumBy O(N) O(N) O(N) - - Возвращает сумму результатов, создаваемых путем применения функции к каждому элементу коллекции.
tail - O(1) - - - Возвращает список без первого элемента.
take - - O(N) - - Возвращает элементы последовательности до указанного количества.
takeTime - - O(1) - - Возвращает последовательность, которая при итерации дает элементы базовой последовательности, а заданный предикат возвращается true , а затем не возвращает никаких элементов.
Toarray - O(N) O(N) O(N) O(N) Создает массив из данной коллекции.
Tolist O(N) - O(N) O(N) O(N) Создает список из данной коллекции.
toSeq O(1) O(1) - O(1) O(1) Создает последовательность из данной коллекции.
truncate - - O(1) - - Возвращает последовательность, которая при перечислении возвращает не более N элементов.
tryFind O(N) O(N) O(N) O(log(N)) - Выполняет поиск элемента, удовлетворяющего заданному предикату.
tryFindIndex O(N) O(N) O(N) - - Выполняет поиск первого элемента, удовлетворяющего заданному предикату, и возвращает индекс соответствующего элемента или None если такой элемент отсутствует.
tryFindKey - - - O(log(N)) - Возвращает ключ первого сопоставления в коллекции, удовлетворяющий заданному предикату, или возвращается None , если такой элемент отсутствует.
tryPick O(N) O(N) O(N) O(log(N)) - Применяет данную функцию к последовательным элементам, возвращая первый результат, в котором функция возвращает Some некоторое значение. Если такой элемент отсутствует, операция возвращается None.
unfold - - O(N) - - Возвращает последовательность, содержащую элементы, создаваемые заданным вычислением.
union - - - - O(M*log(N)) Вычисляет объединение двух наборов.
unionMany - - - - O(N1*N2...) Вычисляет объединение последовательности наборов.
unzip O(N) O(N) O(N) - - Разделяет список пар на два списка.
распакуть 3 O(N) O(N) O(N) - - Разбивает список тройных на три списка.
оконный - - O(N) - - Возвращает последовательность, которая дает скользящие окна, содержащие элементы, которые извлекаются из входной последовательности. Каждое окно возвращается в виде нового массива.
zip O(N) O(N) O(N) - - Объединяет две коллекции в список пар. Два списка должны иметь одинаковую длину.
ZIP3 O(N) O(N) O(N) - - Объединяет три коллекции в список тройных значений. Списки должны иметь равную длину.

См. также