使用无序映射与数组进行搜索

Question

我有一个块分配函数，它接受一个数组，然后在其中搜索以找到表示空闲 space 的值 0，然后将块分配给可用的空闲 [=16] =].我正在尝试使用无序映射来提高搜索 0 的速度。在我的函数中，数组中的所有元素都被插入到无序映射中。我想知道与仅使用数组相比，实现如下所示的无序映射是否还能提高搜索速度？

int arr[] = {15, 11, 0, 0, 0, 27, 0, 0}; // example array
int n = sizeof(arr)/sizeof(arr[0]);
unordered_map<int, int> hash;
    for(i=n;i>=0;i--)
    {
        hash[i+1] = arr[i]; 
    }
    for(auto v : hash)
    {
        if(v.second==0) 
        {
            return v.second; 
        }
    }

int arr[] = {15, 11, 0, 0, 0, 27, 0, 0};
int n = sizeof(arr)/sizeof(arr[0]);
    for(i=0;i<n;i++)
    {
        if(arr[i]==0) 
        {
            return arr[i];
        }
    }

Answer 1

首先，请注意，您编写的两个函数始终 return 为零，这不是您想要的。

现在，回答主要问题：不，这种方法没有帮助。在这两种情况下，您只是迭代数组中的值，直到找到一个为零的值。在最坏的情况下，这是一个 O(n) 操作，在这里引入 unordered_map 只会减慢速度。

你可以在这里做的最相似的事情实际上帮助会像

std::unordered_map<int, std::vector<int>> lookup;
for(int i = 0; i < n; i++)
{
  lookup[arr[i]].push_back(i);
}

现在，如果您想找到其中包含零的块，您只需从 lookup[0] 中找到一个元素即可。

但是，鉴于我们只需要跟踪其中包含 0 的块，而不是立即查找其中包含 13 的块，我们可以好吧，就这样吧：

std::vector<int> emptyBlocks;
for(int i = 0; i < n; i++)
{
  if(arr[i] == 0) { emptyBlocks.push_back(i); }
}

然后我们可以根据需要抓取空块。

请注意，您应该从 emptyBlocks 的后面获取块，以便从列表中删除它们不需要我们将所有内容都移过来。如果出于某种原因需要首先采用最小的索引，请在构建空块列表时向后遍历 arr。

也就是说，当您分配块时，您通常会尝试找到一系列连续空块。如果是这种情况，您可能需要一种查找给定大小的块的起点的方法。你可能也希望它被订购，这样你就可以要求“最小的块至少这么大。”

使用无序映射与数组进行搜索

Searching using unordered map vs array

c++

arrays

unordered-map