Структура данных для поиска

@Shamil1 · Регистрация: 26.03.2015

Студворк — интернет-сервис помощи студентам

Нужно:
1. добавлять элементы
2. определять, сколько элементов больше заданного числа (length $ filter (\x -> x > a))
Обе операции нужно делать за logn (ну, или быстрее)

Есть что-нибудь подходящее среди среди стандартных типов данных или нужно самому писать (сбалансированное дерево)?

@Catstail · 01.04.2016, 06:58

Может быть, поможет это: http://hackage.haskell.org/package/hashtables

XRuZzz · 01.04.2016, 11:49

Если интересуют деревья вроде красно-чёрного и АВЛ, то я залил исходники(не знаю где я их взял):
АВЛ Дерево
Красно-чёрное дерево
Естественно, в hoogle, hackage и stackage есть полноценные реализации.
Но можете посмотреть и мой репозиторий, я готов подправить исходники если нужно.
Можно совместно подумать над проблемой, тема актуальная.

@Shamil1 · 01.04.2016, 16:32 **[ТС]**

Catstail,
Позже посмотрю внимательней, но, судя по названию, это не подходит. Хэши позволяют доставать элементы по ключу, но мне это не нужно.

XRuZzz,
Проблема в том, что "обычное" дерево умеет искать конкретное значение. Можно ли его приспособить для получения ответа на вопрос: "сколько в дереве элементов больше вот этого?".
Проблема актуальная, но чисто академическая (цель - обучение).

Новые блоги и статьи Все статьи Все блоги /
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,887

	Структура данных для поиска 31.03.2016, 23:52. Показов 1188. Ответов 3 Метки нет (Все метки) Нужно: 1. добавлять элементы 2. определять, сколько элементов больше заданного числа (length $ filter (\x -> x > a)) Обе операции нужно делать за logn (ну, или быстрее) Есть что-нибудь подходящее среди среди стандартных типов данных или нужно самому писать (сбалансированное дерево)? 1

@Catstail Супер-модератор 38200 / 21132 / 4310 Регистрация: 12.02.2012 Сообщений: 34,738 Записей в блоге: 14
	01.04.2016, 06:58
	Может быть, поможет это: http://hackage.haskell.org/package/hashtables 1

XRuZzz Антикодер 1888 / 870 / 48 Регистрация: 15.09.2012 Сообщений: 3,088
	01.04.2016, 11:49
	Если интересуют деревья вроде красно-чёрного и АВЛ, то я залил исходники(не знаю где я их взял): АВЛ Дерево Красно-чёрное дерево Естественно, в hoogle, hackage и stackage есть полноценные реализации. Но можете посмотреть и мой репозиторий, я готов подправить исходники если нужно. Можно совместно подумать над проблемой, тема актуальная. 3

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,887
	01.04.2016, 16:32 [ТС]
	Catstail, Позже посмотрю внимательней, но, судя по названию, это не подходит. Хэши позволяют доставать элементы по ключу, но мне это не нужно. XRuZzz, Проблема в том, что "обычное" дерево умеет искать конкретное значение. Можно ли его приспособить для получения ответа на вопрос: "сколько в дереве элементов больше вот этого?". Проблема актуальная, но чисто академическая (цель - обучение). 1