索引映射的高效算法

假设您遇到以下问题。您有两个具有一对一映射的索引集。为了简单起见，假设您有一个数组，如int a [] = {21, 30, 45, 78}这个列表将{1,2,3,4}映射到{21,30,45,78}。什么是获得反向映射的最有效方式，即给定索引30，如果想要算法返回2，则需要45，您需要3等等。我可以想到以下内容：索引映射的高效算法

索引的二进制搜索。这是有效的内存，并且具有复杂性O(log n)。
有一个数组有79元素，并有reverseMap[21] = 1, reverseMap[30] = 2, reverseMap[45] = 3, reverseMap[78] = 4。这是O(1)，因此速度更快，但不是有效的内存。

对于我的应用程序来说，内存和速度都很重要。我缺乏记忆，因为这是一个数字处理代码，因此可以使用数亿个点。速度也很重要，因为算法会被调用很多次。

我觉得哈希表在这里很有用，但我不太了解它的评论。我希望对这个问题有所了解。此外，由于编码是在c++完成的，我希望看到使用STL而不是外部库的方法。

来源

2012-02-24 GradGuy

这功课吗？ – 2012-02-24 20:22:39

@LightnessRacesin不是真的 - 只是正在进行的项目中的一部分。我有一个解决方案，但什么要知道别人的想法 – GradGuy 2012-02-24 20:23:49

然后，我相信你正在寻找http://codereview.stackexchange.com – 2012-02-24 20:24:20

一如既往：简介。我们可以猜测，但没有运行你的代码，我们可能是错的。我做了一个rough benchmark on ideone（时间是基于我的电脑）。我做的unsigned int十万查找数组中的十万台（我厌倦等待你的“亿万”），而这些是我的结果：

unsorted vector found 1633382974 in 2140 ticks. 
sorted vector found 1633382974 in 62 ticks. 
unordered_map found 1633382974 in 16 ticks. 
std::map found 1633382974 in 172 ticks. //that's half the time of a blink

但是我必须指出，保持这些在你的程序的内存中将有一些开销超过未排序的向量。如果我们创建时间添加到十万查找的时机，我们得到：

unsorted vector found 1633382974 in 2141 ticks. 
sorted vector found 1633382974 in 1797 ticks. 
unordered_map found 1633382974 in 16218 ticks. 
std::map found 1633382974 in 30749 ticks. //a full thirty seconds

所以，你可以看到，时序依赖完全在你在你的代码做什么。尝试不同的东西，在上优化，然后以最快的速度执行代码。

来源

2012-02-24 22:05:53

我会的。感谢您的有益讨论:) – GradGuy 2012-02-24 22:29:18

什么是获得反向映射

双std::map<value, value>最有效的方式。或std::unordered_map即，任何地图类，双。也就是说第一个映射将来自arrayA的值映射到arrayB，第二个映射将来自arrayB的值映射到arrayA。或者先将地图索引映射到值，然后将第二个映射值映射到索引。

您可以使用std::lower_bound（二分查找）和两个std::vector<std::pair<value, value> >做同样的事情，但您需要确保所有数据都已排序。它将使用比两个std::map更少的内存，但是你很可能会花更多的时间来确保数据被排序。

对于我的应用程序内存和速度是很重要的

你忘了开发时间。如果您的完美解决方案需要3个月的时间才能完成，那可能不值得。
你需要告诉你有多少内存，你使用的是什么类型的数据，以及需要多少数据。
总是有平衡。 “速度”或“记忆”。或者是中间的东西。

数亿点

切换到64位的，购买额外的内存。或者将已排序的数据存储在磁盘上（允许对部分加载的数据进行二进制搜索）并忘记速度，或尝试使用“从标准输入读取，立即写入标准输出”方式进行处理。请注意，硬件比开发时间便宜。在不知道数据类型的情况下，不可能推荐其他任何东西。

来源

2012-02-24 21:38:01 SigTerm

索引映射的高效算法

回答

相关问题