Я смотрел на следующих примерах должностей (среди многих), и ни один не соответствует моим требованиям, к сожалению:Как рассчитать процентиль каждого элемента в отсортированный список ключевых элементов/значение отсортированных путем изменения значения
Вот описание проблемы.
У нас есть список элементов key/value (я хочу, чтобы на данный момент не использовать термин «словарь»), отсортированные по значению, где «значение» любого данного элемента может меняться в любое время и часто изменяется , После изменения какого-либо значения нам нужно снова отсортировать список элементов по значению. После повторного сортировки нам нужно знать индекс каждого элемента в списке BY KEY, чтобы рассчитать каждый элемент PERCENTILE этого элемента.
Другими словами, нам нужно рассчитать PERCENTILE каждого элемента в сортированном (по значению) списке элементов ключа/значения LARGE, где значения быстро меняются.
Очевидно, что существует «наивный» способ сделать это, учитывая количество изменений в значениях, большое количество пар ключ/значение, повторную сортировку и вычисление процентили каждый раз, это не будет функционировать.
У кого-нибудь есть очень быстрый алгоритм (или эвристический), который делает это?
Когда элемент изменяется, вам не нужно сортировать весь список, просто переместите этот элемент на новое место. Процентники изменяются только для элементов между старыми и новыми позициями. – Barmar
Вы изучили структуру данных очереди с приоритетом? –
И процентили все изменяются на фиксированную сумму: '1/N', где N - общее количество элементов. За исключением элементов, которые были связаны либо старым значением, либо новым значением. – Barmar