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

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

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

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

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

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

Модуль List
массив. Изменяемая коллекция последовательных элементов данных с фиксированным размером, начинающимся с нуля, которые имеют одинаковый тип. Массивы

Модуль Array

Модуль Array2D

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

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

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

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

Функция Array Список Последовательность Схема Присвойте параметру Описание
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) - - Возвращает среднее значение для результатов предоставленной функции, примененной к каждому элементу.
блит O (N) - - - - Копирует раздел массива.
cache - - O (N) - - Выполняет вычисление и сохраняет элементы последовательности.
Приведение - - O (N) - - Преобразует элементы в указанный тип.
choose O (N) O (N) O (N) - - Применяет заданную функцию f к каждому элементу x списка. Возвращает список, содержащий результаты для каждого элемента, в котором функция возвращает значение Some(f(x)) .
collect O (N) O (N) O (N) - - Применяет заданную функцию к каждому элементу коллекции, сцепляет все результаты и возвращает объединенный список.
компаревис - - O (N) - - Сравнивает две последовательности, используя заданную функцию сравнения, элемент по элементу.
concat O (N) O (N) O (N) - - Объединяет заданное перечисление перечисления в виде одного объединенного перечисления.
contains - - - - O (log (N)) Возвращает значение true, если набор содержит указанный элемент.
containsKey - - - O (log (N)) - Проверяет, находится ли элемент в домене схемы.
count - - - - O (N) Возвращает количество элементов в наборе.
каунтби - - O (N) - - Применяет функцию создания ключа к каждому элементу последовательности и возвращает последовательность, которая получает уникальные ключи и их количество в исходной последовательности.
copy O (N) - O (N) - - Копирует коллекцию.
create O (N) - - - - Создает массив целых элементов, которые изначально имеют заданное значение.
delay - - O(1) - - Возвращает последовательность, построенную из заданной отложенной спецификации последовательности.
различие - - - - O ( * Журнал M (N)) Возвращает новый набор с элементами второго набора, удаленных из первого набора.
distinct O(1)* Возвращает последовательность, которая не содержит повторяющихся записей в соответствии с универсальным хэшем и сравнениями на равенство для записей. Если элемент встречается в последовательности несколько раз, последующие вхождения отбрасываются.
дистинктби O(1)* Возвращает последовательность, которая не содержит повторяющихся записей в соответствии с универсальным хэшем и сравнениями на равенство по ключам, возвращаемым данной функцией формирования ключа. Если элемент встречается в последовательности несколько раз, последующие вхождения отбрасываются.
empty O(1) O(1) O(1) O(1) O(1) Создает пустую коллекцию.
exists (существует) O (N) O (N) O (N) O (log (N)) O (log (N)) Проверяет, удовлетворяет ли какой либо элемент последовательности заданному предикату.
exists2- O (минимум (N, M)) - O (минимум (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 , если ни один элемент не удовлетворяет предикату.
финдкэй - - - O (log (N)) - Вычисляет функцию для каждого сопоставления в коллекции и возвращает ключ для первого сопоставления, в котором функция возвращает значение true . Если такого элемента не существует, эта функция вызывает System.Collections.Generic.KeyNotFoundException .
папка O (N) O (N) O (N) O (N) O (N) Применяет функцию к каждому элементу коллекции, перечисляя аргумент накапливаемое в потоке с помощью вычисления. Если входная функция — f, а элементы — i0... в эта функция выполняет вычисление f (... (f s I0)...) окне.
fold2 O (N) O (N) - - - Применяет функцию к соответствующим элементам двух коллекций, перечисляя аргумент накапливаемое в потоке с помощью вычисления. Коллекции должны иметь одинаковые размеры. Если входная функция — f, а элементы — i0... в и j0... ЖН, эта функция вычислит f (... (f s, i0 j0)...) в ЖН.
foldBack O (N) O (N) - O (N) O (N) Применяет функцию к каждому элементу коллекции, перечисляя аргумент накапливаемое в потоке с помощью вычисления. Если входная функция — f, а элементы — i0... в эта функция выполняет вычисление f i0 (... (f в s)).
foldBack2 O (N) O (N) - - - Применяет функцию к соответствующим элементам двух коллекций, перечисляя аргумент накапливаемое в потоке с помощью вычисления. Коллекции должны иметь одинаковые размеры. Если входная функция — f, а элементы — i0... в и j0... ЖН, эта функция вычислит f i0 j0 (... (f в ЖН s)).
ForAll O (N) O (N) O (N) O (N) O (N) Проверяет, соответствуют ли все элементы коллекции заданному предикату.
forall2 O (N) O (N) O (N) - - Проверяет, соответствуют ли все соответствующие элементы коллекции заданному попарному предикату.
Get/n O(1) O (N) O (N) - - Возвращает элемент из коллекции по заданному индексу.
head - O(1) O(1) - - Возвращает первый элемент коллекции.
init O (N) O (N) O(1) - - Создает коллекцию, заданную измерением, и функцию генератора для вычислений элементов.
инитинфините - - O(1) - - Формирует последовательность, которая при переборе возвращает последовательные элементы путем вызова заданной функции.
intersect - - - - O (журнал (N) * Журнал (M)) Вычисление пересечения двух наборов.
интерсектмани - - - - O (N1 * N2...) Вычисление пересечения последовательности наборов. Последовательность не должна быть пустой.
isEmpty O(1) O(1) O(1) O(1) - Возвращает значение true , если коллекция пуста.
испроперсубсет - - - - O ( * Журнал M (N)) Возвращает true , если все элементы первого набора находятся во втором наборе, и хотя бы один элемент второго набора не находится в первом наборе.
испроперсуперсет - - - - O ( * Журнал M (N)) Возвращает значение true , если все элементы второго набора находятся в первом наборе, и хотя бы один элемент первого набора не входит во второй набор.
подмножество - - - - O ( * Журнал M (N)) Возвращает значение true , если все элементы первого набора находятся во втором наборе.
Супермножество - - - - O ( * Журнал M (N)) Возвращает, true Если все элементы второго набора находятся в первом наборе.
iter O (N) O (N) O (N) O (N) O (N) Применяет заданную функцию к каждому элементу коллекции.
iteri O (N) O (N) O (N) - - Применяет заданную функцию к каждому элементу коллекции. Целое число, передаваемое в функцию, указывает индекс элемента.
iteri2 O (N) O (N) - - - Применяет заданную функцию к паре элементов, созданных из совпадающих индексов в двух массивах. Целое число, передаваемое в функцию, указывает индекс элементов. Длина двух массивов должна быть одинаковой.
iter2 O (N) O (N) O (N) - - Применяет заданную функцию к паре элементов, созданных из совпадающих индексов в двух массивах. Длина двух массивов должна быть одинаковой.
last O(1) O (N) O (N) - - Возвращает последний элемент в применимой коллекции.
length O(1) O (N) O (N) - - Возвращает количество элементов в коллекции.
карта O (N) O (N) O(1) - - Создает коллекцию, элементы которой являются результатами применения заданной функции к каждому элементу массива.
map2 O (N) O (N) O(1) - - Создает коллекцию, элементы которой являются результатами применения заданной функции к соответствующим элементам двух коллекций попарно. Длина двух входных массивов должна быть одинаковой.
map3 - O (N) - - - Создает коллекцию, элементы которой являются результатами применения заданной функции к соответствующим элементам трех коллекций одновременно.
действует O (N) O (N) O (N) - - Создает массив, элементы которого являются результатами применения заданной функции к каждому элементу массива. Целочисленный индекс, передаваемый функции, указывает индекс преобразуемого элемента.
mapi2 O (N) O (N) - - - Выполняет сборку коллекции, элементы которой являются результатами применения заданной функции к соответствующим элементам двух коллекций попарно, также передавая индекс элементов. Длина двух входных массивов должна быть одинаковой.
max O (N) O (N) O (N) - - Возвращает наибольший элемент в коллекции по сравнению с использованием оператора Max .
максби O (N) O (N) O (N) - - Возвращает наибольший элемент в коллекции, по сравнению с использованием параметра Max в результатах функции.
макселемент - - - - O (log (N)) Возвращает наибольший элемент в наборе согласно упорядочению, используемому для набора.
мин O (N) O (N) O (N) - - Возвращает элемент наименьшего уровня в коллекции по сравнению с использованием оператора min .
минби O (N) O (N) O (N) - - Возвращает элемент наименьшего уровня в коллекции по сравнению с использованием оператора min в результатах функции.
минелемент - - - - O (log (N)) Возвращает нижний элемент в наборе согласно упорядочению, используемому для набора.
офаррай - O (N) O(1) O (N) O (N) Создает коллекцию, содержащую те же элементы, что и заданный массив.
офлист O (N) - O(1) O (N) O (N) Создает коллекцию, содержащую те же элементы, что и заданный список.
ofSeq O (N) O (N) - O (N) O (N) Создает коллекцию, содержащую те же элементы, что и заданная последовательность.
кэширован - - O (N) - - Возвращает последовательность каждого элемента во входной последовательности и его предшественника, за исключением первого элемента, который возвращается только в качестве предшественника второго элемента.
partition O (N) O (N) - O (N) O (N) Разделяет коллекцию на две коллекции. Первая коллекция содержит элементы, для которых заданный предикат возвращает true , а вторая коллекция содержит элементы, для которых заданный предикат возвращает false .
permute O (N) O (N) - - - Возвращает массив со всеми элементами переставляются в соответствии с заданной перестановкой.
брать O (N) O (N) O (N) O (log (N)) - Применяет заданную функцию к последовательным элементам, возвращая первый результат, в котором функция возвращает часть. Если функция никогда не возвращает некоторые, System.Collections.Generic.KeyNotFoundException вызывается.
readonly - - O (N) - - Создает объект последовательности, который делегирует заданному объекту последовательности. Эта операция гарантирует, что приведение типа не сможет повторно обнаружить и изменить исходную последовательность. Например, если задан массив, возвращаемая последовательность будет возвращать элементы массива, но возвращаемый объект последовательности нельзя привести к массиву.
reduce O (N) O (N) O (N) - - Применяет функцию к каждому элементу коллекции, перечисляя аргумент накапливаемое в потоке с помощью вычисления. Эта функция начинается с применения функции к первым двум элементам, передает этот результат в функцию вместе с третьим элементом и т. д. Функция возвращает окончательный результат.
редуцебакк O (N) O (N) - - - Применяет функцию к каждому элементу коллекции, перечисляя аргумент накапливаемое в потоке с помощью вычисления. Если входная функция — f, а элементы — i0... в эта функция выполняет вычисление f i0 (... (f в-1 в)).
remove - - - O (log (N)) O (log (N)) Удаляет элемент из домена на карте. Если элемент отсутствует, исключение не возникает.
водил - O (N) - - - Создает список указанной длины с каждым набором элементов на заданное значение.
расширения O (N) O (N) - - - Возвращает новый список с элементами в обратном порядке.
наличия O (N) O (N) O (N) - - Применяет функцию к каждому элементу коллекции, перечисляя аргумент накапливаемое в потоке с помощью вычисления. Эта операция применяет функцию ко второму аргументу и первому элементу списка. Затем операция передает этот результат в функцию вместе со вторым элементом и т. д. Наконец, операция возвращает список промежуточных результатов и окончательный результат.
scanBack O (N) O (N) - - - Напоминает операцию foldBack, но возвращает и промежуточные, и окончательные результаты.
singleton - - O(1) - O(1) Возвращает последовательность, которая получает только один элемент.
set O(1) - - - - Задает для элемента массива указанное значение.
skip - - O (N) - - Возвращает последовательность, которая пропускает N элементов базовой последовательности, а затем возвращает оставшиеся элементы последовательности.
skipWhile - - O (N) - - Возвращает последовательность, которая при переборе пропускает элементы базовой последовательности, пока заданный предикат возвращает, true а затем выдает оставшиеся элементы последовательности.
sort O (n * журнала (n)) среднее значение

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

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

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

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

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

O (N ^ 2) наихудший случай
O (n * log (n)) - - - Сортирует элементы коллекции, используя заданную функцию сравнения в качестве порядка и возвращая новую коллекцию.
sub O (N) - - - - Создает массив, содержащий заданный поддиапазон, заданный начальным индексом и длиной.
Sum O (N) O (N) O (N) - - Возвращает сумму элементов в коллекции.
sumBy O (N) O (N) O (N) - - Возвращает сумму результатов, созданных путем применения функции к каждому элементу коллекции.
tail - O(1) - - - Возвращает список без первого элемента.
take - - O (N) - - Возвращает элементы последовательности вплоть до указанного числа.
takeWhile - - 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 Если такого элемента не существует.
трифиндкэй - - - O (log (N)) - Возвращает ключ первого сопоставления в коллекции, удовлетворяющего заданному предикату, или возвращает, None Если такого элемента не существует.
tryPick O (N) O (N) O (N) O (log (N)) - Применяет заданную функцию к последовательным элементам, возвращая первый результат, в котором функция возвращает Some для некоторого значения. Если такого элемента не существует, операция возвращает None .
Unfold - - O (N) - - Возвращает последовательность, содержащую элементы, создаваемые данным вычислением.
union - - - - O ( * Журнал M (N)) Вычисление объединения двух наборов.
унионмани - - - - O (N1 * N2...) Выполняет вычисление объединения последовательности наборов.
unzip O (N) O (N) O (N) - - Разделяет список пар на два списка.
unzip3 O (N) O (N) O (N) - - Разделяет список триад на три списка.
оконные - - O (N) - - Возвращает последовательность, которая дает скользящие окна элементов, которые были выведены из входной последовательности. Каждое окно возвращается в виде нового массива.
zip O (N) O (N) O (N) - - Объединяет две коллекции в список пар. Два списка должны иметь одинаковую длину.
zip3 O (N) O (N) O (N) - - Объединяет три коллекции в список Тройн. Списки должны иметь одинаковую длину.

См. также