F # Непрерывные структуры данных для высокочастотных потоков данных в реальном времени

Ответ 1

Вы должны рассмотреть FSharpx.Collections.Vector. Vector <T> предоставит вам функции, подобные Array, включая индексированный O (log32 (n)) поиск и обновление, находящееся в пределах расстояния отпечатка O (1), а также добавление новых элементов в конец вашей последовательности, Существует еще одна реализация Vector, которая может использоваться из F # в Solid Vector. Очень хорошо документированы, а некоторые функции выполняют в 4 раза быстрее в больших масштабах (количество элементов > 10K). Обе реализации выполняются очень хорошо и, возможно, за пределами 1M элементов.

Ответ 2

В своем ответе Джек Фокс предлагает использовать либо FSharpx.Collections Vector<'T>, либо Solid Vector<'T> Грегом Розенбаумом (https://github.com/GregRos/Solid). Я думал, что могу отдать немного в сообщество, предоставив инструкции о том, как встать и работать с каждым из них.

Использование FSharpx.Collections.Vector <T>

Процесс довольно прост:

• Загрузите пакет FSharpx.Core nuget с помощью консоли Project Manager или пакета Nuget Manager для решения. Оба они находятся в Visual Studio → tools → Library Manager.
• Если вы используете его в файле F # script, добавьте #r "FSharpx.Core.dll". Возможно, вам понадобится полный путь.

Использование:

open FSharpx.Collections

let ListOfTuples = [(1,true,3.0);(2,false,1.5)] 
let vector = ListOfTuples |> Vector.ofSeq

printfn "Last %A" vector.Last
printfn "Unconj %A" vector.Unconj
printfn "Item(0) %A" (vector.[0])
printfn "Item(1) %A" (vector.[1])
printfn "TryInitial %A" dataAsVector.TryInitial
printfn "TryUnconj %A" dataAsVector.Last

Использование Solid.Vector <T>

Получение настроек для использования Solid Vector<'T> более активно. Но версия Solid имеет гораздо более удобную функциональность и, как отметил Джек, имеет ряд преимуществ в производительности. Он также имеет много полезной документации.

• Вам нужно будет скачать визуальное студийное решение из https://github.com/GregRos/Solid
• После того, как вы скачали его, вам нужно будет его построить, так как нет готовой к использованию встроенной dll.
• Если вы похожи на меня, вы можете столкнуться с несколькими недостающими зависимостями, которые препятствуют построению решения. В моем случае все они были связаны с основами тестирования nuit (я использую другой). Просто выполните загрузку/добавление каждой из зависимостей до тех пор, пока не будут решены решения.
• Как только это будет сделано, и решение будет построено, у вас появится блестящая новая Solid.dll в папке Solid/Solid/bin. Здесь я ошибся. Это основная dll и достаточно для использования С#. Если вы укажете только ссылку на Solid.dll, вы сможете создать вектор < 'T > в f #, но с тех пор начнутся фанки.
• Чтобы использовать эту структуру данных в F #, вам нужно будет ссылаться на Solid.dll и Solid.FSharp.dll, которые находятся в папке \Solid\SolidFS\obj\Debug\. Вам понадобится только один открытый оператор → open Solid

Вот какой код показывает использование в файле F # script:

#r "Solid.dll"
#r "Solid.FSharp.dll" // don't forget this reference

open Solid

let ListOfTuples2 = [(1,true,3.0);(2,false,1.5)] 
let SolidVector = ListOfTuples2 |> Vector.ofSeq

printfn "%A" SolidVector.Last
printfn "%A" SolidVector.First
printfn "%A" (SolidVector.[0])
printfn "%A" (SolidVector.[1])
printfn "Count %A" SolidVector.Count

let test2 = vector { for i in {0 .. 100} -> i }

Ответ 3

Предположим, что ваш dataObj содержит уникальное поле идентификатора, тогда любая заданная структура данных будет подходящей для вашей работы. Неизменяемые структуры данных в основном используются для функционального стиля кода или настойчивости. Если вам не нужны эти два, вы можете использовать HashSet<T> или SortedSet<T> в библиотеке коллекции .Net.

Некоторая оптимизация по потоку может быть полезна, например, сохранение фиксированного размера Queue<T> для самых последних объектов данных в потоке и сохранение более старых объектов в более тяжелом наборе. Я бы предложил провести сравнительный анализ до перехода на такие решения гибридной структуры данных.

Изменить:

После более тщательного прочтения ваших требований я обнаружил, что вам нужна очередь с индексируемым пользователем индексом или обратным счетчиком. В этой структуре данных операции выделения объектов (например, средняя/сумма и т.д.) Стоят O (n). Если вы хотите выполнить некоторые операции в O (log n), вы можете использовать более сложные структуры данных, например. интервальные деревья или списки пропуска. Однако вам придется реализовать эти структуры данных самостоятельно, так как вам нужно хранить метаинформацию в узлах дерева, которые находятся за API коллекции.

Ответ 4

Это событие помещается в структуру данных. Это структура данных, которую мы пытаемся определить. Должен ли он быть Set, Queue или какой-либо другой структурой?

Сложно сказать без дополнительной информации.

Если ваши данные поступают с отметками времени в порядке возрастания (т.е. они никогда не выходят из строя), вы можете просто использовать какую-то очередь или расширяемый массив.

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

до 800 событий в секунду

Это очень ручные требования к производительности для скорости вставки.

Подмножество элементов либо извлекается, либо каким-то образом повторяется для целей генерации признаков. Это будет либо последние n строк/элементов структуры данных (т.е. Последние 1000 событий или 10000 событий), либо все элементы за последние x сек/мин (т.е. Все события за последние 10 минут). В идеале нам нужна структура, которая позволяет нам делать это эффективно. В частности, имеет значение структура данных, которая допускает случайный доступ n-го элемента без итерации через все остальные элементы.

Если вам нужны только элементы рядом с началом, почему вы хотите получить произвольный доступ? Вам действительно нужен случайный доступ по индексу или вы действительно хотите получить произвольный доступ каким-то другим ключом, как время?

Из того, что вы сказали, я бы предложил использовать обычный F # Map с индексом, поддерживаемый MailboxProcessor, который может добавлять новое событие и извлекать объект, который позволяет индексировать все события, то есть обернуть Map в объекте, который предоставляет свое собственное свойство Item и реализацию IEnumerable<_>. На моей машине это простое решение занимает 50 строк кода и может обрабатывать около 500 000 событий в секунду.