AT
есть что-нибудь более быстрое, чем counting trie для подсчёта количества слов в тексте?
Пробовал open addressing hash table с сохранением части хеша (hash / tableSize) в ключ, но это уже на стадии копирования строк в массив стухает.
Size: a a a
2020 September 21
ВВ
как сделать инкремент числа биты которого хранятся задом на перёд? чтоб побыстрее, естественно
В «Алгоритмических трюках для программиста» разобрано увеличение обращённого целого числа и есть код.
ВВ
почему экзотика, разве это не просто разные эндианности?
endianness — это про порядок байтов. Биты в байте идут как положено.
А
Подскажите unordered_map в С++ уже реализован в виде хеша? То есть поиск по ключу занимает O(1)?
DK
Complexity
Constant on average, worst case linear in the size of the container.
https://en.cppreference.com/w/cpp/container/unordered_map/find
Constant on average, worst case linear in the size of the container.
https://en.cppreference.com/w/cpp/container/unordered_map/find
d
В fft где-то надобится
Про fft в яблочко
d
В «Алгоритмических трюках для программиста» разобрано увеличение обращённого целого числа и есть код.
Это книга?
A
Алексей
Подскажите unordered_map в С++ уже реализован в виде хеша? То есть поиск по ключу занимает O(1)?
Да, но на самом деле он довольно медленный
А
Да, но на самом деле он довольно медленный
Но так или иначе замены то ему нет?
A
Обычный map разве что)
A
Понятно, что асимптотика другая, но вроде иногда с ним даже лучше, насколько я помню
ВВ
Это книга?
Да, Hacker's Delight в оригинале.
d
Да, Hacker's Delight в оригинале.
Понял
d
Вообще я уже не уверен что нужен именно инкремент, возможно простое обращение индекса попрёт, алгоритмы для этого вчера нагуглить удалось
ВВ
Обращение в той книжке тоже есть.
d
Обращение в той книжке тоже есть.
Зависит от того что будет эффективнее
ВВ
Зависит от того что будет эффективнее
Что быстрее инкрементирует обращённое число? Прямой алгоритм эффективнее.
ВВ
В общем, моё дело посоветовать, а там уже сами выберете. :)
d
Что быстрее инкрементирует обращённое число? Прямой алгоритм эффективнее.
У меня на каждой итерации будет индекс инкрементируемый как обычно, возможно, обращение окажется эффективнее инкремента обращённого представления
AT
есть что-нибудь более быстрое, чем counting trie для подсчёта количества слов в тексте?
в общем, по-видимому нереально сделать что-то на x86-64 быстрее, чем это (для текстов на английском)
