在低延迟的应用程序中，unordered_map是比vector更好的解决方案吗？
在开发低延迟应用程序时，使用unordered_map代替vector是否可取？
我最近参加了一家金融公司的面试，该公司致力于开发低延迟交易应用程序。我被问到一个问题，我用一个unordered_map回答了这个问题，与使用向量(O(n*n))相比，这个问题在效率方面(0(n))似乎相当好。但是，我知道为了利用缓存一致性的好处，建议尽可能多地使用向量并避免使用unordered_map。我只是想看看对于这个问题是否有更好的解决方案，我被问到的问题是检查两个字符串是否是彼此的排列。
bool isPermutation(const std::string& first, const std::string& second) {
std::unordered_map<char, int> charDict;
if(first.length() != second.length())
return false;
for(auto it: first) {
charDict[it]++;
}
for(auto it: second) {
if(charDict.count(it) > 0) {
--charDict[it];
} else {
return false;
}
return true;
}您可以假设两个字符串的长度相等，并且仅当第二个字符串中每个字符的出现次数与第一个字符串中的每个字符的出现次数相同时，才假定函数返回true。
回答 2
Stack Overflow用户
发布于 2019-01-23 23:58:55
当然可以，但这真的取决于你想要解决的问题。如果您的键空间的域是未知的，那么就很难提出一个比unordered_map更快的通用解决方案。
在这种情况下，密钥空间的域是已知的:它被限制为ASCII字符。这很方便，因为您可以立即将项(char)转换为向量索引(std::size_t)。因此，您可以只使用每个字符的值作为vector的索引，而不是在每次查找时都对其进行散列。
但总的来说，不会过早优化。如果unordered_map是最自然的解决方案，我会从那里开始，然后分析，如果您发现性能不能满足您的需求，请查看重新设计您的解决方案。(这并不总是最好的建议；如果您知道您正在处理一段非常关键的代码，那么从一开始就需要考虑某些设计决策。如果您从不兼容的设计开始，那么以后再回来重构可能会困难得多。)
Stack Overflow用户
发布于 2019-01-24 12:38:24
因为只有256个可能的键，所以您可以使用256个计数的堆栈分配数组，这将比向量或unordered_map更快。如果为first.size()+second.size() < 128，则仅将实际发生的关键点的计数初始化为0。否则，memset整个数组。
https://stackoverflow.com/questions/54330963
复制相似问题
腾讯云开发者
