3 ответов:
Вероятно, существует много различных (и хороших) ответов, но, по моему скромному мнению, общая характеристика вероятностных структур данных заключается в том, что они дают вам приблизительный, а не точный ответ.
Сколько здесь предметов? Около 1523425 с вероятностью 99%
Обновление: Быстрый поиск произвел ссылку на достойную статью по данному вопросу:
Https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/
Вероятностные структуры данных не могут дать вам определенного ответа, вместо этого они предоставляют вам разумную аппроксимацию ответа и способ аппроксимации этой оценки. Они чрезвычайно полезны для больших данных и потоковых приложений, поскольку позволяют значительно уменьшить объем необходимой памяти (по сравнению со структурами данных, которые дают вам точные ответы).
В большинстве случаев эти структуры данных используют хэш-функции для рандомизации элементов. Потому что они игнорируйте столкновения они сохраняют размер постоянным, но это также причина, по которой они не могут дать вам точные значения. Преимущества, которые они приносят:
- они используют небольшой объем памяти (вы можете контролировать, сколько)
- их можно легко распараллелить (хэши независимы)
- у них есть постоянное время запроса (даже не амортизированная константа, как в словаре)
Часто используемые вероятностные структуры данных:
В Википедии есть список вероятностных структур данных для вашей справки: https://en.wikipedia.org/wiki/Category:Probabilistic_data_structures
Существуют различные определения того, что такое" вероятностная структура данных". ИМХО, вероятностная структура данных означает, что структура данных использует некоторый рандомизированный алгоритм или использует некоторые вероятностные характеристики внутренне, но они не должны вести себя вероятностно или недетерминированно от перспектива пользователя структуры данных.
Существует множество "вероятностных структур данных" с вероятностно - поведение, такое какфильтр Блума иГиперлог упомянутый по другим ответам.
В то же время существуют и другие " вероятностные структуры данных" с определенным поведением (с точки зрения пользователя), таким как пропустить список . Для списка пропусков пользователи могут использовать его аналогично сбалансированному двоичному дереву поиска, но это реализована с некоторой вероятностью связанная идея внутренне. И согласно автору скип-листа Уильяму пью:
Списки пропусков представляют собой вероятностную структуру данных , которая, по-видимому, вытеснение сбалансированных деревьев как метод реализации выбора для многие приложения. Алгоритмы списка пропусков имеют одинаковую асимптотику ожидаемые временные границы как сбалансированные деревья и проще, быстрее и использовать меньшее пространство.
Comments