amarao (amarao_san) wrote,
amarao
amarao_san

Алгоритм поиска "топа"

В ходе разбора бытовой админской задачи выросла интересная алгоритмическая задачка:

На вход программы поступает N значений. Читать их можно только последовательно и только один раз (разумеется, можно пропускать, но пропущенное не вернуть).

Программа располагает фиксированным объёмом памяти. Нужно сформировать top (M) повторяющихся значений (то есть выписать самые повторяющиеся). M << N. Памяти есть O(M).

Есть какие-то алгоритмы вокруг этого?

Если строгих алгоритмов нет, есть ли вероятностные? Типа "в большинстве случаев довольно точно угадывает top"?
Subscribe

  • Rust soundness

    Каждый раз, когда я сталкиваюсь с маленькими "но" в Rust'е, это ощущение тщательной продуманности. Например, простейшие fold-функции для итераторов:…

  • still_ntp

    В ходе локального мозгового штурма у меня родилась суперидея. Надо написать ntp сервер, который может отдавать указанную дату. Т.е. сказали при…

  • arping'а не достаточно

    Я обнаружил, что arping не умеет делать целый запрос полностью (т.е. source mac, dest mac, source ip, dest ip). Dest либо IP, либо mac, и это немного…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 5 comments