Нурлан
Я подумал что хэш таблицы самое то.
Vladislav
Хеш мэппит ключи в какой рейндж чисел?
Vladislav
В общем, накладывается ряд ограничений который даёт отсутсвие коллизий и мутабельность не нужна. Предполагается, что будет порядка 10^10 элементов. И обращаться надо не по индексу а по ключу.
10^10 объектов у тебя в память не влезут, если у тебя не сервак с 256Gb
Нурлан
Сервака нет :(
Vladislav
И с такими объемами уже лучше в сторону сишки смотреть, имхо
Vladislav
Потому что тупо 10^10 указателей - уже 80Gb
Donat
В хетцнере сервер с такой памятью вполне affordable
Cheese
Внутри таблицы хеш берётся по модулю количества бакетов, поэтому он все равно перестанет быть биективным
это не обязательная деталь реализации
Vladislav
это не обязательная деталь реализации
Мэппинг из значений хеша в индексы корзин - обязателен
Cheese
хэш, гарантированно не дающий коллизий, называется идеальным
Cheese
если нет коллизий, не нужны корзины
Vladislav
простой пример: у тебя два ключа A и B, с хешами 1 и 10^100500. Как будет выглядеть таблица с ними?
Cheese
ладно, ещё одно условие: если идеальный хэш довольно плотно укладывается в [0..n], то можно его использовать как индекс в массиве
Alexander
ну для известных ключей есть алгоритмы
Alexander
вон сишная генерилка хешмап же есть
Vladislav
https://en.wikipedia.org/wiki/Perfect_hash_function#Construction
Cheese
Kit, множество значений твоей хэш-функции похоже на [0..n]?
Нурлан
Значения именно [0..n]
Нурлан
А ключи такие же, но переупорядочение
Нурлан
Почти такие же
Cheese
вот и будет твоя идеальная хэш-таблица
Cheese
ещё одна XY решена!
Нурлан
Мне надо обращаться не по упорядоченным индексам.
Нурлан
Вектор не подойдёт
Нурлан
Это значения
Нурлан
Индексы другие.
Нурлан
Ключи точнее
Cheese
если взять хэш от ключа, получится [0..n]?
Vladislav
в любом случае, haskell для твоей задачи не очень подходит, учитывая объемы данных
Зигохистоморфный
А как же пакет от клапауция?
Alexander
он сделан до конца?
Alexander
ну и там только unboxed, хотя они возможно и нужны
Alexander
ну смотря насколько тебе важна скорость
Alexander
vs удобство писания кода
Нурлан
Расскажи, что именно такое ты решаешь, если не секрет?)
Алгоритм Шэнкса дискретного логарифмирования
Нурлан
https://ru.wikipedia.org/wiki/Алгоритм_Гельфонда_—_Шенкса
Alexander
память через unboxed хорошо ужимается в принципе
Vladislav
Для модуля порядка 10^20?
Нурлан
там задача еще более специфическая, но ужимается по Шэнксу до 10^10
Vladislav
Хм, тогда почему 10^10 записей?
Vladislav
Должно быть порядка корня
Vladislav
Возьми ро метод Полларда, он тоже порядка корня по времени, но с константной памятью, если я правильно помню
Vladislav
https://en.m.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms
Нурлан
Ух ты, не знал про него. Я посмотрю! спасибо
Vladislav
совсем уже охуели (извините)
Vladislav
Спамер?
Alexander
уменьшение кол-ва констрейнтов у функции это повод для minor или major bump?
a66ath
Собирается старый код с ней?
Aleksei (astynax)
Уменьшение констрейнтов, по идее, тянет на minor
Aleksei (astynax)
Но может получиться "слишком полиморфно" и у кого-то не выведется тип без дополнительной аннотации
Alexander
врятли, там что-то типа MonadThrow m было
Alexander
оно не дает доп инфы для выбора
Aleksei (astynax)
Ну это то не должно ничего сломать, да
Aleksei (astynax)
(/me хочет автобампалку semver как в Elm)
Alexander
/me хочет автобампалку PVP
Vladislav
на haskell?
Alex
на go наверное
Vladislav
мало ли, я бы совершенно не удивился
Danila Matveev
это только что прилетело в jvm чат, так что на чем угодно
Vladislav
вот
Vladislav
вангую что там пэхэпэ
Alex
в один конец ага
Danila Matveev
это детали
Alex
для начала неплохо бы написать под идрис массивы :)
Alex
и какую нибудь сетевую либу
Евгений
В каком смысле массивы? Зачем? В идрисе нету векторов?
Alex
вектора это ж просто орнаментированные списки
Alex
с линейным временем индекса, аппенда и прочего