Подход, используемый старым хэшманом MSVC, заключался в том, чтобы делать выборку реже.
Это означает, что изолированные изменения не будут отображаться в вашем хеше, но то, что вы пытаетесь избежать, - это чтение и обработка всего 80 мб данных для хэширования вашего вектора. Не чтение некоторых персонажей довольно неизбежно.
Второе, что вы должны сделать, это не специализируются std::hash на всех vector с, это может сделать вашу программу плохо формируется (как это было предложено в разрешении дефекта, состояние которого я не помню), и по крайней мере является плохой план (поскольку std обязательно позволит себе добавить хеш-комбинацию и хэширование векторов).
Когда я пишу пользовательский хэш, я обычно использую ADL (Koenig Lookup), чтобы упростить его расширение.
namespace my_utils {
namespace hash_impl {
namespace details {
namespace adl {
template<class T>
std::size_t hash(T const& t) {
return std::hash<T>{}(t);
}
}
template<class T>
std::size_t hasher(T const& t) {
using adl::hash;
return hash(t);
}
}
struct hash_tag {};
template<class T>
std::size_t hash(hash_tag, T const& t) {
return details::hasher(t);
}
template<class T>
std::size_t hash_combine(hash_tag, std::size_t seed, T const& t) {
seed ^= hash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template<class Container>
std::size_t fash_hash_random_container(hash_tag, Container const& c) {
std::size_t size = c.size();
std::size_t stride = 1 + size/10;
std::size_t r = hash(hash_tag{}, size);
for(std::size_t i = 0; i < size; i += stride) {
r = hash_combine(hash_tag{}, r, c.data()[i])
}
return r;
}
// std specializations go here:
template<class T, class A>
std::size_t hash(hash_tag, std::vector<T,A> const& v) {
return fash_hash_random_container(hash_tag{}, v);
}
template<class T, std::size_t N>
std::size_t hash(hash_tag, std::array<T,N> const& a) {
return fash_hash_random_container(hash_tag{}, a);
}
// etc
}
struct my_hasher {
template<class T>
std::size_t operator()(T const& t)const {
return hash_impl::hash(hash_impl::hash_tag{}, t);
}
};
}
my_hasher - универсальный хешер. Он использует либо хеши, объявленные в my_utils::hash_impl (для std типов), либо бесплатные функции, называемые hash, которые будут хешировать данный тип, чтобы хэш-вещи. В противном случае он пытается использовать std::hash<T>. Если это не удается, вы получаете ошибку времени компиляции.
Дать бесплатное hash функции в пространстве имен типа вы хотите хэш имеет тенденцию быть менее раздражающим, чем того, чтобы уйти и открытый std и специализируется std::hash в моем опыте.
Он понимает векторы и массивы, рекурсивно. Выполнение кортежей и пар требует немного больше работы.
Он проецирует указанные векторы и массивы примерно в 10 раз.
(Примечание:. hash_tag является как-то вроде шутки, и способ, чтобы заставить ADL и предотвратить того, чтобы пересылать-объявить hash специализации в hash_impl пространстве имен, потому что это требование отстой)
Стоимость выборка состоит в том, что вы можете получить больше столкновений.
Другой подход, если у вас есть огромное количество данных для хеширования их раз и следить, когда они изменяются. Чтобы сделать этот подход, используйте интерфейс monad для копирования на запись для вашего типа, который отслеживает, обновляется ли хэш. Теперь вектор получает хэширование один раз; если вы измените его, хэш будет отброшен.
Можно пойти дальше и иметь хаос произвольного доступа (где легко предсказать, что происходит, когда вы редактируете заданное значение хэш-мудрый) и опосредуете весь доступ к вектору. Это сложно.
Вы также можете многопоточно перебирать хеширование, но я бы предположил, что ваш код, вероятно, связан с пропускной способностью, а многопоточность там не поможет. Стоит попробовать.
Вы можете использовать более привлекательную структуру, чем плоский вектор (что-то вроде дерева), где изменения в значениях пузырьков в хэш-подобном способе имеют значение хэша корня. Это добавило бы lg (n) накладные расходы ко всему доступу к элементу. Опять же, вам придется обернуть необработанные данные в элементах управления, которые сохраняют хеширование до даты (или отслеживать, какие диапазоны грязны и их необходимо обновить).
Наконец, поскольку вы работаете с 10 миллионами элементов за раз, подумайте о переходе на сильное крупномасштабное решение для хранения данных, например базы данных или что у вас есть. Использование 80-мегабайтных ключей на карте мне кажется странным.
Действительно ли вы используете векторы 'double' с 10 миллионами элементов в качестве ключей? Я как-то сомневаюсь в этом. – milleniumbug
Если это так, то, возможно, попробуйте предварительно вычислить хеш-значения, а не перепрограммировать их при каждом доступе ключей. – milleniumbug
@milleniumbug это вполне возможно в сценарии с высокой нагрузкой с большим количеством ОЗУ. Возможно, он использует неправильный контейнер или должен смотреть в не-STL-решения. – strangeqargo