在C++中高效地规范化一个数组

Question

在C++中高效地规范化一个数组

c++arraysalgorithmnormalization

3

我正在寻找一种在C++中高效地对数组进行归一化的方法。归一化是指将所有数组值转换为小于或等于n的值。所以这个数组：

5235 223 1000 40 40

变成了：

4 2 3 1 1 或者 3 1 2 0 0

以下是我的代码：

vector<int> normalize_array(vector<int> arr){
    vector<int> tmp(arr), ret(arr.size());

    sort(tmp.begin(), tmp.end());

    for (int i = 0; i < arr.size(); ++i){
        vector<int>::iterator iter = find(tmp.begin(), tmp.end(), arr[i]);
        ret[i] = std::distance(tmp.begin(), iter);
    }

    return ret;
}

输出结果为4 2 3 0 0，上述代码不能很好地处理重复元素。是否有更好的方法来解决这个问题？

- zangw

这看起来像是幅度指数而不是归一化，所以1.对数组进行索引排序，2.交换值和它们的索引。这个复杂度为O(N.log(N))，其中N是数组中值的数量。不要认为你可以比这更好。 - Spektre

给定的实现似乎是O(n^2)。在值和索引之间建立映射可能将其削减为O(n log n)。 - sp2danny

3

只需将“find”替换为“lower_bound”，就可以做到相同的效果。 - sp2danny

此外，通过值获取 arr 会不必要地产生额外的向量副本。 - oblitum

代码实际上并没有产生期望的输出（它输出了 4 2 3 0 0）。请明确您真正希望进行的转换。 - rici

4个回答

1

我将提议以下解决方案，其时间复杂度为O(n log n)。唯一的问题是，该算法无法处理具有相同归一化值的重复值。

struct IndexComp {
    IndexComp(const std::vector<int>& vec) : m_vec(vec) {}
    bool operator() (int i,int j) { return (m_vec[i] < m_vec[j]);}
    const std::vector<int>& m_vec;
};

std::vector<int> normalize_array(const std::vector<int>& arr){
    std::vector<int> tmp, ret(arr.size());

    IndexComp indexComp(arr);

    for (int i = 0; i < arr.size(); ++i){
        tmp.push_back(i);
    }

    std::sort(tmp.begin(), tmp.end(), indexComp);

    for (int i = 0; i < arr.size(); ++i){
        ret[tmp[i]] = i;
    }

    return ret;
}

- sachse

1

这里有一个主要基于标准库的 O(n log n) 解决方案，可以处理重复值，正如 OP 中的示例所提示的一样（尽管它从 0 开始编号，而不是从 1，因此示例输入会产生3 1 2 0 0）。

template<typename It, typename OutIt>
void normalize_array(It b, It e, OutIt out) {
  using T = typename It::value_type;
  std::map<T, int> tmp;
  std::transform(b, e, std::inserter(tmp, tmp.begin()),
                 [](T v){ return std::make_pair(v, 0); });
  int i = 0; for (auto& ent : tmp) ent.second = i++;
  std::transform(b, e, out,
                 [&](T v){ return tmp[v]; });
}

不直接排序，而是将所有元素放入临时映射中。这将对它们进行排序并消除重复项（O(n log n)）；我本可以使用 set，但我想要下一步中使用映射来按顺序编号值（O(n)）。然后，可以使用此映射查找每个值的索引。（O(n log n)）。

虽然该解决方案在复杂性方面是最佳的，但可能有办法减少常数。

在 coliru 上实时查看。

- rici

将地图添加到问题中会添加非连续内存访问（基于节点的数据结构），这可能不太友好。尽管类似原始基于向量的解决方案包含O个重复项，但它似乎更加缓存友好，这是一个重要问题，因为OP要求实际性能，而不仅仅是理论性能。 - oblitum

1

如果您以这种方式定义归一化（数学家可能会说归一化是完全不同的东西），那么它就成为了排序问题（您正在有效地创建一个升序值索引数组）。因此，我想您应该查看排序算法并将其用于您的情况。只需注意具有相同值的元素具有相同的索引 - 这通常不是排序算法所做的。

- Maciej Baranowski

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- oblitum · Accepted Answer

按照评论中所述的方法应用优化，并使用C++ lambda表达式：

vector<int> normalize_array(const vector<int> &arr /* O(1) */) {
    vector<int> tmp(arr) /* O(N) */, ret(arr.size()) /* O(1) */;

    sort(tmp.begin(), tmp.end()); // O(N lg N)

    transform(arr.cbegin(), arr.cend(), ret.begin(), [&tmp](int x) {
        return distance(tmp.begin(), lower_bound(tmp.begin(), tmp.end(), x));
    }); // O(N lg N)

    return ret; // O(1) by move semantics
} // O(1) + O(N) + O(1) + O(N lg N) + O(N lg N) == O(N lg N)

在以下解决方案中，受@sachse答案启发但使用C++11，修复了您的问题并进行了正确归一化，以产生4 2 3 1 1，我相信这是预期的结果：

实时示例

vector<int> normalize_array(const vector<int> &arr) {
    if (arr.empty())
        return {};

    vector<int> idx(arr.size()), ret(arr.size());

    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(),
         [&arr](int i, int j) { return arr[i] < arr[j]; });

    ret[idx[0]] = 1;
    for (size_t i = 1; i < arr.size(); ++i) {
        ret[idx[i]] = ret[idx[i - 1]] + (arr[idx[i]] != arr[idx[i - 1]]);
    }

    return ret;
}

Live Example