Сомневаюсь

Только в ограниченных частных случаях - типа элементы числа из ограниченного неширокого диапазона

не очень понимаю, что в данном контексте подразумевается под in-place модификацией, но можно попробовать извернуться блум филтром.

Ассимптотически будет O(n), но с большой константой, плюс будет вероятность, что итоговый ответ получится неверным, но зато O(n) (:

> не очень понимаю, что в данном контексте подразумевается под in-place модификацией
без использования мутабельности
пример, который не катит:
https://github.com/clojure/clojure/blob/clojure-1.9.0/src/clj/clojure/core.clj#L4976
мутабельное множество

этот пример тривиально переделать на иммутабельное множество, но это никак не изменит О(н лог(н))

можешь написать иммутабельный блум фильтр, в оценку добавится ещё константа из кложурячих векторов.

Ага. Правда они пишут что основание логарифма настолько большое, что для большинства практических применений оно будет как O(n)

Поправил

Но это не повод вводить в заблуждение, необоснованно требуя О(н)

да я просто спрашиваю возможно ли это в принципе =)
действительно кажется что нет, но как это доказать пока хз

Это возможно в принципе. Если у тебя в списке значения только целые числа от 1 до 5, ты бежишь по нему за О(н) и проверяешь в нагребенном векторе встретившихся за О(1)

bucketsort ftw

Вопрос вопросов: воспользоваться ли омерзительно императивной хэш-таблицей или поискать что-нибудь ортодоксальное в книжке Окасаки? %)

поискать, а потом воспользоваться

Зависит от того, нужна ли вам персистентность.
Если нет, то и нафиг надо, императивная реализация быстрее и проще.

Про хеш-таблицы у Окасаки ничего нет.
Потому что персистентную чисто функциональную хеш таблицу, операции с которой за "O(1)" были бы непонятно как делать. Нужен чисто функциональный массивчик, доступ на к произвольному элементу которого был бы за O(1). Окасаки (да и весь мир) умеет только за O(log n).
Если перстистентность все-таки нужна, используйте map, с ключами на тех же хешах, например. Логарифм на операцию вряд ли вам чем-то помешает, если вы не свой гугл пишите.

Совершенно согласен. Это я позволил себе поиронизировать над задачей выше :)

Упс, я выше вашего сообщения не читал c:

Всем привет! Есть одно свободное место для докладчика 25го апреля, также с большим удовольствием примем мини-доклад :)

Уже нет :)