Кэширование значений с плавающей запятой в 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 были около 100000 записей.)

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 хэш-карта будет быстрее.

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