Телеграмм чат группы Fsharp

Чтобы найти 10 наибольших, не надо сортировать всё.

00:14пожаловаться #1

Prunkles Dreemurr in F# Chat

Разве сортировка не требует в любом случае полного прохождения по коллекции?

Допустим у нас список

[ 5; 4; 3; …; 1 ]

Если не доходить до последнего элемента (1, точно попадёт в начало списка), то как ты поймёшь о его существовании?

00:14пожаловаться #2

прохождения требует, но сортировка же ещё и про переупорядочивание

00:15пожаловаться #3

Сергей in F# Chat

Ну за m*n можно вытащить m элементов конечно

00:15пожаловаться #4

если использовать какой-нибудь selection sort, то на 10 элементах из 50к будет довольно неплохо

00:15пожаловаться #5

вообще можно отсортировать за O(n+m*log(m))

00:16пожаловаться #6

достаточно иметь priority queue ограниченного размера, в которую совать элемента исходной коллекции один за другим

00:17пожаловаться #7

ДБ

мне кажется пузырьком можно пройтись?

00:20пожаловаться #8

Очередь - это что-то странное. Просто массив и отдельно хранить максимальное и минимальное из этого массива.

00:20пожаловаться #9

ДБ

я пройду 10 раз и готово?

00:20пожаловаться #10

Хотя может я не туда воюю.

00:20пожаловаться #11

зачем что-то придумывать, если уже есть структура "очередь с приоритетом", которая как раз предоставит всё в сортированном виде?

00:20пожаловаться #12

Я не понимаю, в чём смысл очереди. Есть SortedList, например.

00:21пожаловаться #13

Vladislav Khapin in F# Chat

Не проще сразу отсортированное хранить?

00:21пожаловаться #14

ДБ

для каждого запроса своя сортировка

00:22пожаловаться #15

ДБ

там score совпадений от строки

00:22пожаловаться #16

ДБ

у одного в топе динамо, у другого в топе милан

00:22пожаловаться #17

какие у него O?

00:22пожаловаться #18

SortedList<TKey,TValue> Class (System.Collections.Generic)

logn получение, n - вставка. Возможно, словарь лучше. У него вставка logn.
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.sortedlist-2?view=net-5.0#remarks

Docs

Represents a collection of key/value pairs that are sorted by key based on the associated IComparer<T> implementation.

00:24пожаловаться #19

да, в сортированном словаре вставка и удаление логарифмические, годится