Кэширование значений с плавающей точкой в ​​C ++

Question

Я хотел бы назначить уникальный объект для набора значений с плавающей запятой.При этом я изучаю два различных варианта:

Первый вариант - поддерживать статическую хэш-карту (std::unordered_map<double,Foo*>) в классе и избегать создания дубликатов.Это означает, что вместо вызова конструктора я проверю, есть ли значение в хэше, и если это так, используйте его повторно.Мне также необходимо удалить значение из хэш-карты в деструкторе.

Второй вариант - разрешить дублирование значений во время создания, только чтобы попытаться отсортировать их все сразу и обнаружить дубликаты после того, как все значения былисоздано.Я думаю, мне понадобятся хэш-карты для этой сортировки.Или тогда упорядоченная карта ('std :: map) будет работать так же хорошо?

Есть ли основания ожидать, что первый вариант (который мне нравится больше) будет значительно медленнее в любой ситуации?То есть, будет ли поиск дублирующих записей намного быстрее, если я выполню все записи сразу, а не по одной записи за раз?числа и бесконечности, которые будут добавлены на карту.Некоторые повторяющиеся записи для одной и той же константы также не являются проблемой, если это произойдет для нескольких записей - это приведет к очень небольшому снижению скорости.

Answer 1

В зависимости от источника и возможных значений чисел с плавающей запятой, более серьезной проблемой может быть определение хеш-функции, которая соблюдает равенство.(0, Inf и NaN - значения проблемы - большинство форматов с плавающей запятой имеют два представления для 0, +0.0 и -0.0, которые сравниваются равными; я думаю, что то же самое верно для Inf. И два NaN всегда сравнивают неравные, дажекогда они имеют одинаковую битовую комбинацию.)

Кроме этого, во всех вопросах производительности вы должны измерять.Вы не указываете, насколько большим может стать набор.Если это не так уж сложно, если все значения вставляются заранее, наиболее быстрым решением часто является использование push_back для std::vector, затем std::sort и, при желании, std::unique после заполнения вектора.Во многих случаях использование std::vector и его сортировка выполняются быстрее, даже если частые добавления и удаления.(Когда вы получаете новый запрос, используйте std::lower_bound, чтобы найти точку входа; если значение в найденном местоположении не равно, вставьте новую запись в этой точке.) Улучшенная локальность std::vector в значительной степени компенсирует любые дополнительные расходыиз-за перемещения объектов во время вставки и удаления, и часто даже из-за того, что доступ - это O (lg n), а не O (1).(В одном конкретном случае я обнаружил, что точка безубыточности между хеш-таблицей и отсортированной std::vector составляла около 100 000 записей.)

Answer 2

Рассматривали ли вы на самом деле его измерение?

Никто из нас не может сказать вам, как код, который вы рассматриваете, будет на самом деле работать. Напишите код, скомпилируйте его, запустите и измерьте, насколько быстро он работает.

Потратить время на то, чтобы предсказать, какое решение будет быстрее, (1) пустая трата времени и (2) вероятность получения неверных результатов.

Но если вам нужен абстрактный ответ, то это зависит от вашего варианта использования.

Если вы можете собрать все значения и отсортировать их один раз, это можно сделать за O(n lg n) время.

Если вы вставляете элементы по одному в структуру данных с характеристиками производительности std::map, то каждая вставка будет занимать O(lg n) время, поэтому выполнение n вставок также займет O(n lg n) время. .

Вставка в хэш-карту (std::unordered_map) занимает постоянное время, поэтому n вставки можно выполнить в O(n). Таким образом, теоретически для достаточно больших значений n карта хеша будет быстрее.

На практике, в вашем случае никто не знает. Вот почему вы должны измерить его, если вы на самом деле беспокоитесь о производительности.