union в C можно использовать для динамичесого предстваления типа данных?

т.е. связка из метки типа + union всех возможных типов

но это очень оптимизированное взятие бита

не очень, там % 2 вместо & 1

т.е. связка из метки типа + union всех возможных типов

Да, так многие делают. В С++ std::variant релизован приблизительно так же

а есть альтернативы?

если говорить только об Си

можно держать tag + pointer

и маллокать нужный тип

не очень, там % 2 вместо & 1

Дада, еще сдвиги вместо делений умножений

всякое барахло до sizeof(pointer) можно сувать прямо туда как values

а есть альтернативы?

например в исходниках Python 2.7 можно посмотреть реализацию PyObject и всех остальных типов

например в исходниках Python 2.7 можно посмотреть реализацию PyObject и всех остальных типов

именно 2.7?

я сейчас просто 3ую ветку ковыряю

я просто не знакю как в ветке 3+ они сделали

понял, спасибо

Дада, еще сдвиги вместо делений умножений

Это всё компилятор соптимизирует. Можно не заморачиваться, если делите/умножаете на константу

не очень, там % 2 вместо & 1

компилятор разберется

да я знаю что разберется

с -O0 правда затупит

впрочем в данном случае &1 просто логичнее

Всё верно, идея в том, чтобы оставить самый минимум и позволить инлайниться. Меня 10% прироста производительности завораживают, ничего не могу с собой поделать...

А все компиляторы поддерживают static inline функции в хедерах?

в теории - да :)

вот такие магии с числами не есть хорошо

Приходится ее и юзать

GitHub - rkapsi/patricia-trie: Practical Algorithm to Retrieve... github.com PATRICIA Trie. Practical Algorithm to Retrieve Information Coded in Alphanumeric. The PATRICIA Trie is also known under the names Radix and Crit Bit Tree.

Radix tree - Wikipedia en.wikipedia.org Donald R. Morrison first described what he called "Patricia trees" in 1968;[4] the name comes from the acronym PATRICIA, which stands for "Practical Algorithm To Retrieve Information Coded In...

GitHub - rkapsi/patricia-trie: Practical Algorithm to Retrieve... github.com PATRICIA Trie. Practical Algorithm to Retrieve Information Coded in Alphanumeric. The PATRICIA Trie is also known under the names Radix and Crit Bit Tree.

Ой там вообще жопа

если index - это бит, то почему не byteNum = index / 8 (или >> 3, если хочется)?

лоло, похоже на магию которую я не помню, надо будет пересмотреть кодес и литературу перечитать

И тогда вопрос, как оно работало корректно

Надо будет затестить лоло

ну это похоже просто неверная имплементация )

перезаписывала память где-то далекооо

(ну или читала)

?

я на достаточно нормальных тестах тестировал

Короче буду разбиратьчя

пример теста есть?

просто запросы на удаление и поиск

И вставку

С разной длины строками

Короче, пока не затещу ничаво не скажу!

да тут вопрос про тест функции теста этого бита )

ну малоль, там отображение памяти закольцовано

всяко бывает :)

я исходил их того, что раз работает интерфейс, то и внутренние функции работают

Ну и в такой функции трудно ошибиться(но можно ;-))

simon the shame ?

Кстати, а никто не исследовал, почему std::mutex и std::timed_mutex не реализованы вот так: https://patchwork.freedesktop.org/patch/41241/ Вроде бы ничего не мешает, а автор обещает 10% прирост производительности?

Это linux-specific, на винде еще интереснее.

Кто -нибудь работал с boost.property tree? Как и чем вы сравнивали два дерева?

Если быть чуть точнее, то как и чем сравнивать два дерева, в которых порядок нодов не совпадает

Но уровень вложенности и содержимое совпадают

Встоонный sort и стандартный operator == не помогают

Самописный компаратор тоже

Руками, рекурсивно.

И довольно неоптимально выйдет, если чо.

Если нужно именно сравнение, предлагаю написать хешер.

Как вариант, но что бы не напороться на несовпадающий порядок придется элементы первого дерева искать по тем же путям во втором. Что не избавляет от проблемы, когда первое только подмножество второго

Кто -нибудь работал с boost.property tree? Как и чем вы сравнивали два дерева?

ручками рекурсивно, д

И сравнивать хеши.

Если нужно именно сравнение, предлагаю написать хешер.

а коллизии?

Пренебречь.

тогда уже сравнивать руками))

при коллизии сравнивать ручками рекурсивно лоль

Хэш - уже лучше

ERROR: S client not available

хэш имеет смысл, если сравнивать часто и много, а также много false'ов

Нет, просто забить на сравнение руками и использовать только хеши. Взять просто подлиннее. И хешировать правильно.

Спасибо всем за обсуждения и Андрею в особенности за идею с хэшом

а вдруг спутник с орбиты уйдёт?

Но если нужны гаранртии, то да, хеш, потом руками.

Спасибо всем за обсуждения и Андрею в особенности за идею с хэшом

Не за что :D

Особо сильные гарантии не нужны, компаратор нужен только для тестов

тогда пофиг

Вот и я так же думаю)

но лучше где-то записать, что при ошибке смотреть в сторону хэшей

Хорошее замечание, спасибо)

Но если нужны гаранртии, то да, хеш, потом руками.

нубовопрос. А если тот же unordered_map находит совпадение по хешу, он потом руками делает сравнение? serachItem == resultItem?

Да.

конечно

тем более, там коллизии очень вероятны

окей

тем более, там коллизии очень вероятны

А в цифрах можно? :) Для своих объектов можно довольно неплохой хешер написать.

Там по умолчанию должны быть неплохие

А в цифрах можно? :) Для своих объектов можно довольно неплохой хешер написать.

зависит от размера объекта. для int16_t при размере баскета (или как там это называется) 65536 коллизий не будет если объект хранит в себе данных на байт 10-20, то уже без коллизий не обойтись

конкретные цифры - если N объектов на M корзин -> в среднем по N/M с одинаковым хешом

Только ты не знаешь сколько сейчас бит используется

если объект размера значащих K бит, то есть 2^K его различных копий

нубовопрос. А если тот же unordered_map находит совпадение по хешу, он потом руками делает сравнение? serachItem == resultItem?

На случай колизий хеша. Если хеши разные - тогда значения точно нет, если хеши одинаковые - тогда либо значение есть, либо колизия => чтобы точно убедиться, надо сравнить еще и значения

сам хэш может быть довольно уникальным, но unordered берут же от него % basket_num. может от реализации еще зависеть

Я о том же

сам хэш может быть довольно уникальным, но unordered берут же от него % basket_num. может от реализации еще зависеть

Там, кстати, в последнем GCC круто сделали: избавились от дорогих операций % и / за счет того что basket_num всегда степень двойки => компилятор заменяет их на операции сдвига и бинарного &

Вроде это изначально так должно быть нет?

Там, кстати, в последнем GCC круто сделали: избавились от дорогих операций % и / за счет того что basket_num всегда степень двойки => компилятор заменяет их на операции сдвига и бинарного &

так вроде есть две реализации - на простых числах и на степенях двойки. там у простых чисел тоже есть какой-то плюс

Ну яб сразу так написал еслиб мне сказали писать хэштаблицу

это вопрос похожий на "а как перевыделять память в динамических контейнерах - в 1.5 раза или по простым числам? или в 2?"

В 2