Поделиться через

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

  • Статья

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

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

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

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

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

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

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

Модуль Array2D

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

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

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

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

Функция Массив Список Последовательность Карта Набор Описание
добавить O(N) O(N) O(N) - - Возвращает новую коллекцию, содержащую элементы первой коллекции, за которой следуют элементы второй коллекции.
добавлять - - - O(log(N)) O(log(N)) Возвращает новую коллекцию с добавленным элементом.
средний O(N) O(N) O(N) - - Возвращает среднее значение элементов в коллекции.
усреднениеПо O(N) O(N) O(N) - - Возвращает среднее значение результатов предоставленной функции, примененной к каждому элементу.
blit O(N) - - - - Копирует раздел массива.
тайник - - O(N) - - Вычисляет и сохраняет элементы последовательности.
актёрский состав - - O(N) - - Преобразует элементы в указанный тип.
выбирать O(N) O(N) O(N) - - Применяет данную функцию f к каждому элементу x списка. Возвращает список, содержащий результаты для каждого элемента, где функция возвращает Some(f(x)).
собирать O(N) O(N) O(N) - - Применяет данную функцию к каждому элементу коллекции, объединяет все результаты и возвращает объединенный список.
compareWith - - O(N) - - Сравнивает две последовательности с помощью данной функции сравнения, элемента по элементу.
concat O(N) O(N) O(N) - - Объединяет данное перечисление перечислений как одно объединённое перечисление.
Содержит - - - - O(log(N)) Возвращает значение true, если набор содержит указанный элемент.
содержитКлюч - - - O(log(N)) - Проверяет, находится ли элемент в домене карты.
считать - - - - O(N) Возвращает количество элементов в наборе.
countBy - - O(N) - - Применяет функцию создания ключей к каждому элементу последовательности и возвращает последовательность, которая дает уникальные ключи и их количество вхождения в исходной последовательности.
копировать O(N) - O(N) - - Копирует коллекцию.
создавать O(N) - - - - Создает массив целых элементов, которые изначально являются заданным значением.
задержка - - O(1) - - Возвращает последовательность, созданную из заданной отложенной спецификации последовательности.
разница - - - - O(M*log(N)) Возвращает новый набор с элементами второго набора, удаленным из первого набора.
отчетливый O(1)* Возвращает последовательность, не содержащую дубликатов, согласно обобщённым хэшам и сравнению на равенство для элементов. Если элемент возникает несколько раз в последовательности, последующие вхождения удаляются.
различатьПо O(1)* Возвращает последовательность, не содержащую повторяющихся записей, в соответствии с универсальными хэш-сравнениями и сравнениями на равенство ключей, которые возвращает заданная функция создания ключей. Если элемент встречается несколько раз в последовательности, последующие вхождения удаляются.
пустой 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)) Проверяет, соответствует ли любая пара соответствующих элементов входных последовательностей заданному предикату.
заполнять 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, если такой элемент отсутствует.
найтиИндекс 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)...) iN.
свертка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)).
для всех 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) - - Возвращает первый элемент коллекции.
инициализация O(N) O(N) O(1) - - Создает коллекцию с учетом измерения и функции генератора для вычисления элементов.
initInfinite - - O(1) - - Создает последовательность, которая при итерации возвращает последовательные элементы путем вызова данной функции.
пересекаться - - - - O(log(N)*log(M)) Вычисляет пересечение двух множеств.
intersectMany - - - - O(N1*N2...) Вычисляет пересечение последовательности наборов. Последовательность не должна быть пустой.
пусто 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, если все элементы второго набора находятся в первом наборе.
повторение 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) - - Возвращает последний элемент в применимой коллекции.
длина O(1) O(N) O(N) - - Возвращает количество элементов в коллекции.
карта O(N) O(N) O(1) - - Создает коллекцию, элементы которой являются результатами применения данной функции к каждому элементу массива.
map2 O(N) O(N) O(1) - - Создает коллекцию, элементы которой являются результатами применения данной функции к соответствующим элементам двух коллекций по паре. Два входных массива должны иметь одинаковую длину.
карта3 - O(N) - - - Создает коллекцию, элементы которой являются результатами применения данной функции к соответствующим элементам трех коллекций одновременно.
мапи 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) - - Возвращает наибольший элемент в коллекции, определяемый с помощью max результата функции.
maxElement (максимальный элемент) - - - - O(log(N)) Возвращает величайший элемент в наборе в соответствии с порядком, используемым для набора.
минута O(N) O(N) O(N) - - Возвращает наименьший элемент коллекции, сравниваемый с помощью оператора min.
minBy O(N) O(N) O(N) - - Возвращает наименьший элемент коллекции, сравниваемый с помощью оператора min в результатах функции.
минимальныйЭлемент - - - - O(log(N)) Возвращает самый низкий элемент набора в соответствии с порядком, используемым для набора.
ofArray - 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) - - Возвращает последовательность каждого элемента во входной последовательности и его предшественнике, за исключением первого элемента, который возвращается только в качестве предшественника второго элемента.
раздел O(N) O(N) - O(N) O(N) Разделяет коллекцию на две коллекции. Первая коллекция содержит элементы, для которых заданный предикат возвращает true, а вторая коллекция содержит элементы, для которых заданный предикат возвращает false.
переставлять O(N) O(N) - - - Возвращает массив, в котором все элементы переставлены в соответствии с указанной перестановкой.
выбирать O(N) O(N) O(N) O(log(N)) - Применяет данную функцию к последовательным элементам, возвращая первый результат, в котором функция возвращает Some. Если функция никогда не возвращает Some, вызывается System.Collections.Generic.KeyNotFoundException.
случайный выбор O(1) O(1) O(1) - - Возвращает случайный элемент из данной коллекции.
randomChoiceBy O(1) O(1) O(1) - - Возвращает случайный элемент из данной коллекции с указанной функцией randomizer.
randomChoiceWith O(1) O(1) O(1) - - Возвращает случайный элемент из данной коллекции с указанным экземпляром Random.
случайныйВыбор O(count) O(count) O(счет) - - Возвращает коллекцию случайных элементов из данной коллекции, каждый элемент можно выбрать несколько раз.
randomChoicesBy O(счёт) O(количество) O(количество) - - Возвращает коллекцию случайных элементов из данной коллекции с указанной функцией randomizer, каждый элемент можно выбрать несколько раз.
случайныеВыборыС O(количество) O(количество) O(count) - - Возвращает коллекцию случайных элементов из данной коллекции с указанным экземпляром Random, при этом каждый элемент может быть выбран несколько раз.
случайная выборка O(счёт) О(количество) O(счет) - - Возвращает случайный выборку элементов из данной коллекции, каждый элемент можно выбрать только один раз.
случайнаяВыборкаПо O(count) O(количество) O(count) - - Возвращает случайную выборку элементов из заданной коллекции с указанной функцией randomizer, каждый элемент может быть выбран только один раз.
randomSampleWith О(количество) O(счёт) O(количество) - - Возвращает случайный образец элементов из данной коллекции с указанным экземпляром Random, каждый элемент можно выбрать только один раз.
randomShuffle O(N) O(N) O(N) - - Возвращает новую коллекцию, перемешаемую в случайном порядке.
randomShuffleBy O(N) O(N) O(N) - - Возвращает новую коллекцию, перемешанную в случайном порядке, используя указанную функцию randomizer.
randomShuffleWith O(N) O(N) O(N) - - Возвращает новую коллекцию, перемешаемую в случайном порядке с указанным экземпляром Random.
случайноеПеремешиваниеНаМесте O(N) - - - - Сортирует входной массив в случайном порядке, изменив массив на месте.
randomShuffleInPlaceBy O(N) - - - - Сортировка входного массива в случайном порядке с помощью указанной функции randomizer путем мутации массива на месте.
randomShuffleInPlaceWith O(N) - - - - Сортирует входной массив в случайном порядке с использованием указанного экземпляра Random, изменяя массив на месте.
readonly - - O(N) - - Создает объект последовательности, который делегирует заданному объекту последовательности. Эта операция гарантирует, что приведение типов не может повторно обнаружить и изменить исходную последовательность. Например, если задан массив, возвращаемая последовательность вернет элементы массива, но вы не можете привести возвращаемый объект последовательности к массиву.
уменьшать O(N) O(N) O(N) - - Применяет функцию к каждому элементу коллекции, передавая аргумент аккумулятора через весь процесс вычисления. Эта функция начинается с применения функции к первым двум элементам, передает этот результат в функцию вместе с третьим элементом и т. д. Функция возвращает окончательный результат.
reduceBack O(N) O(N) - - - Применяет функцию к каждому элементу коллекции, передавая аргумент аккумулятора через последовательность вычислений. Если входная функция имеет значение f, а элементы — i0... IN, эта функция вычисляет f i0 (... (f iN-1 iN)).
убирать - - - O(log(N)) O(log(N)) Удаляет элемент из домена карты. Исключение не возникает, если элемент отсутствует.
воспроизводить - O(N) - - - Создает список указанной длины, где каждый элемент имеет заданное значение.
обороты O(N) O(N) - - - Возвращает новый список с элементами в обратном порядке.
сканировать O(N) O(N) O(N) - - Применяет функцию к каждому элементу коллекции, передавая аргумент аккумулятора через вычисления. Эта операция применяет функцию ко второму аргументу и первому элементу списка. Затем операция передает этот результат в функцию вместе со вторым элементом и т. д. Наконец, операция возвращает список промежуточных результатов и окончательный результат.
scanBack O(N) O(N) - - - Напоминает операцию "foldBack", но возвращает как промежуточные, так и конечные результаты.
синглтон - - O(1) - O(1) Возвращает последовательность, которая дает только один элемент.
набор O(1) - - - - Задает элемент массива указанному значению.
пропустить - - O(N) - - Возвращает последовательность, которая пропускает N-элементы базовой последовательности, а затем возвращает остальные элементы последовательности.
пропуститьПока - - O(N) - - Возвращает последовательность, которая при итерации пропускает элементы базовой последовательности, а заданный предикат возвращает true, а затем возвращает остальные элементы последовательности.
сортировать Среднее значение O(N*log(N))

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

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

О(N^2) худший случай		 - - - - Сортирует элементы массива, изменяя его на месте и используя заданную функцию сравнения. Элементы сравниваются с помощью сравнить.
сортироватьНаМестеПо Среднее значение 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) - - - - Создает массив, содержащий поддиапазон, заданный начальным индексом и длиной.
сумма O(N) O(N) O(N) - - Возвращает сумму элементов в коллекции.
sumBy O(N) O(N) O(N) - - Возвращает сумму результатов, создаваемых путем применения функции к каждому элементу коллекции.
хвост - O(1) - - - Возвращает список без первого элемента.
брать - - O(N) - - Возвращает элементы последовательности до указанного количества.
приниматьПока - - O(1) - - Возвращает последовательность, которая при итерации дает элементы базовой последовательности, а заданный предикат возвращает true, а затем не возвращает больше элементов.
toArray - O(N) O(N) O(N) O(N) Создает массив из данной коллекции.
СформироватьСписок O(N) - O(N) O(N) O(N) Создает список из данной коллекции.
toSeq O(1) O(1) - O(1) O(1) Создает последовательность из данной коллекции.
укорачивать - - O(1) - - Возвращает последовательность, которая при перечислении возвращает не более N элементов.
tryFind O(N) O(N) O(N) O(log(N)) - Выполняет поиск элемента, удовлетворяющего заданному предикату.
попробоватьНайтиИндекс O(N) O(N) O(N) - - Выполняет поиск первого элемента, удовлетворяющего заданному предикату, и возвращает индекс соответствующего элемента или None, если такой элемент отсутствует.
попробоватьНайтиКлюч - - - O(log(N)) - Возвращает ключ первого сопоставления в коллекции, удовлетворяющий заданному предикату, или возвращает None, если такой элемент отсутствует.
tryPick O(N) O(N) O(N) O(log(N)) - Применяет данную функцию к последовательным элементам, возвращая первый результат, в котором функция возвращает Some для некоторого значения. Если такой элемент отсутствует, операция возвращает None.
развертывать - - O(N) - - Возвращает последовательность, содержащую элементы, создаваемые заданным вычислением.
союз - - - - O(M*log(N)) Вычисляет объединение двух наборов.
unionMany - - - - O(N1*N2...) Вычисляет объединение последовательности наборов.
разархивировать 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) - - Объединяет три коллекции в список троек. Списки должны иметь равную длину.

См. также