是否有更好的实现来保持唯一整数对的计数？
这是用C ++编写的。 我需要为每一对数字保留一个计数。 这两个数字的类型是“int”。 我排序这两个数字，所以（n1 n2）对与（n2 n1）对相同。 我使用std :: unordered_map作为容器。
我一直在使用Matthew Szudzik，Wolfram Research，Inc.的优雅配对功能。在我的实现中，该函数为我提供了一个类型为“long”（我的机器上是64位）的唯一数字， INT”。 我用这个long作为unordered_map（std :: unordered_map）的关键字。 有没有更好的方法来保持这些对的计数？ 我的意思是，更快，如果可能的话使用更少的内存。
另外，我并不需要很长时间。 即使您可以假设这两个数字的范围可以达到32位的最大值，但我预计配对函数的最大可能值最多需要36位。 如果没有别的，至少有没有办法将36位作为unordered_map的关键字？ （一些其他数据类型）
我想过使用bitset，但我不确定std :: hash是否会为任何给定的36位bitset生成一个唯一的密钥，这可以用作unordered_map的密钥。
我将不胜感激任何想法，建议等。
首先，我认为你是错误的假设。 对于std::unordered_map和std::unordered_set哈希不必是唯一的（对于像std::string这样的数据类型，原则上不可能是这样），2个不同的键会产生相同的哈希值。 但是如果发生碰撞，它不会是世界末日，只是访问速度会变慢。 我会从2个数字生成32位散列，如果你有一个典型值的想法，只是测试散列冲突的概率，并相应地选择散列函数。
为了这个工作，你应该使用一对32位数字作为std::unordered_map一个键，并提供一个合适的散列函数。 计算唯一的64位密钥并将其与哈希映射一起使用是有争议的，因为hash_map会计算该密钥的另一个哈希值，所以有可能让它变慢。
大约36位密钥，这是不是一个好主意，除非你有一个特殊的CPU来处理36位数据。 您的数据将在64位边界上对齐，并且您不会有任何保存内存的好处，否则您将受到未对齐数据访问的惩罚。 在第一种情况下，您只需要额外的代码就可以从64位数据中获得36位（如果处理器支持它的话）。 在第二种情况下，即使存在一些冲突，代码也会比32位散列更慢。
如果这个hash_map是一个瓶颈，你可能会考虑不同的哈希映射实现，像goog-sparsehash.sourceforge.net
就我的两分钱而言，你在文章中的配对功能比你实际需要的复杂得多。 将2个32位UNISIGNED值唯一地映射到64是很容易的。 下面是这样做的，甚至可以处理非对数状态，而不会严重影响数学外设（如果有的话）。
uint64_t map(uint32_t a, uint32_t b)
{
uint64_t x = a+b;
uint64_t y = abs((int32_t)(a-b));
uint64_t ans = (x<<32)|(y);
return ans;
}
void unwind(uint64_t map, uint32_t* a, uint32_t* b)
{
uint64_t x = map>>32;
uint64_t y = map&0xFFFFFFFFL;
*a = (x+y)>>1;
*b = (x-*a);
}
另一种选择：
uint64_t map(uint32_t a, uint32_t b)
{
bool bb = a>b;
uint64_t x = ((uint64_t)a)<<(32*(bb));
uint64_t y = ((uint64_t)b)<<(32*!(bb));
uint64_t ans = x|y;
return ans;
}
void unwind(uint64_t map, uint32_t* a, uint32_t* b)
{
*a = map>>32;
*b = map&0xFFFFFFFF;
}
这是一个独特的关键。 你可以很容易地将其修改为无序映射的散列函数提供者，不管它是否会比std :: map更快取决于你得到的值的数量。
注意：如果值a + b> 32位，这将失败。
链接地址: http://www.djcxy.com/p/72537.html上一篇: Is there a better implementation for keeping a count for unique integer pairs?