std::remove_if 的渐近复杂度
Asymptotic complexity of std::remove_if
我正在为具有硬编码最大元素数 N 的数据结构开发一种擦除方法,该方法依赖于 std::array
来避免堆内存。虽然 std::array
只包含 N 个元素,但只有 M 个元素,其中 M 是 "relevant" 个元素,其中 M 小于或等于 N。例如,如果 N 为 10,则数组如下所示:
std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 };
...如果 M 为 7,则只有前 7 个元素是 "relevant",而其他元素被认为是垃圾(结尾的 { -1, -1, -9 }
是垃圾)。我在这里使用 int
作为 SO 示例,但实际程序存储实现 operator==
的对象。下面是一个删除所有 -1
并更新 M:
的工作示例
#include <algorithm>
#include <array>
#include <iostream>
constexpr unsigned N = 10;
unsigned M = 7;
std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 };
int main() {
for (unsigned i = 0; i < M; ++i)
std::cout << elements[i] << ' ';
std::cout << '\n';
auto newEnd = std::remove_if(
std::begin(elements), std::begin(elements) + M,
[](const auto& element) {
return -1 == element;
}
);
unsigned numDeleted = M - std::distance(std::begin(elements), newEnd);
M -= numDeleted;
std::cout << "Num deleted: " << numDeleted << '\n';
for (unsigned i = 0; i < M; ++i)
std::cout << elements[i] << ' ';
std::cout << '\n';
return 0;
}
我的问题是 std::remove_if
的渐近复杂度是多少?我想在 std::remove_if
和 std::distance
之间它是 O(2M) 或 O(M),其中 std::remove_if
是一个更昂贵的操作。但是我不确定 std::remove_if
是否是 O(N * M) 由于每次删除都会移动元素
编辑:为清楚起见,我知道这应该应用谓词 M 次,但我想知道每次谓词为真时是否应用 N 次转换
来自 cppreference:
Complexity:
Exactly std::distance(first, last)
applications of the predicate.
没有对移除的元素进行移位操作,因为它们在调用 std::remove_if
后可能具有未指定的值
编辑
回想起来,这个答案解决了一个比提出的问题更复杂的问题——"push back to end" 函数如何在线性时间内实现。关于提出的具体问题 - 关于 remove_if
- @millenimumbug 的回答更好地解决了这个问题。
我明白为什么你会认为复杂度是 Θ(m n),因为每个 m 删除的项目可能需要移动 Θ(n) 距离。
实际上可以及时做到这一点 Θ(n) 和额外的 O(1) space (只是一些额外的迭代器)。
考虑下图,显示算法可能实现的迭代。
红色的项目是一组连续的已识别项目,将被删除到最后,此时(你只需要两点来记录)。绿色项目是现在正在考虑的项目(另一个指针)。
如果要删除绿色项目,则红色组只需将其包含即可变大。这在下图中显示,其中红色组展开。在下一次迭代中,绿色项目将是它右边的项目。
如果不是,则需要将所有红色组移过它。有些想法可以说服你,这可以在红色组中以线性时间完成(即使迭代器保证只是前向迭代器)。
为什么复杂度是线性的?因为你可以想象这等同于绿色元素相对于左侧组向左移动。基本原理与摊销分析类似。
下图为第二种情况。在下一次迭代中,绿色元素(正在考虑中)将再次位于红色组的右侧。
我正在为具有硬编码最大元素数 N 的数据结构开发一种擦除方法,该方法依赖于 std::array
来避免堆内存。虽然 std::array
只包含 N 个元素,但只有 M 个元素,其中 M 是 "relevant" 个元素,其中 M 小于或等于 N。例如,如果 N 为 10,则数组如下所示:
std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 };
...如果 M 为 7,则只有前 7 个元素是 "relevant",而其他元素被认为是垃圾(结尾的 { -1, -1, -9 }
是垃圾)。我在这里使用 int
作为 SO 示例,但实际程序存储实现 operator==
的对象。下面是一个删除所有 -1
并更新 M:
#include <algorithm>
#include <array>
#include <iostream>
constexpr unsigned N = 10;
unsigned M = 7;
std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 };
int main() {
for (unsigned i = 0; i < M; ++i)
std::cout << elements[i] << ' ';
std::cout << '\n';
auto newEnd = std::remove_if(
std::begin(elements), std::begin(elements) + M,
[](const auto& element) {
return -1 == element;
}
);
unsigned numDeleted = M - std::distance(std::begin(elements), newEnd);
M -= numDeleted;
std::cout << "Num deleted: " << numDeleted << '\n';
for (unsigned i = 0; i < M; ++i)
std::cout << elements[i] << ' ';
std::cout << '\n';
return 0;
}
我的问题是 std::remove_if
的渐近复杂度是多少?我想在 std::remove_if
和 std::distance
之间它是 O(2M) 或 O(M),其中 std::remove_if
是一个更昂贵的操作。但是我不确定 std::remove_if
是否是 O(N * M) 由于每次删除都会移动元素
编辑:为清楚起见,我知道这应该应用谓词 M 次,但我想知道每次谓词为真时是否应用 N 次转换
来自 cppreference:
Complexity: Exactly
std::distance(first, last)
applications of the predicate.
没有对移除的元素进行移位操作,因为它们在调用 std::remove_if
编辑
回想起来,这个答案解决了一个比提出的问题更复杂的问题——"push back to end" 函数如何在线性时间内实现。关于提出的具体问题 - 关于 remove_if
- @millenimumbug 的回答更好地解决了这个问题。
我明白为什么你会认为复杂度是 Θ(m n),因为每个 m 删除的项目可能需要移动 Θ(n) 距离。
实际上可以及时做到这一点 Θ(n) 和额外的 O(1) space (只是一些额外的迭代器)。
考虑下图,显示算法可能实现的迭代。
红色的项目是一组连续的已识别项目,将被删除到最后,此时(你只需要两点来记录)。绿色项目是现在正在考虑的项目(另一个指针)。
如果要删除绿色项目,则红色组只需将其包含即可变大。这在下图中显示,其中红色组展开。在下一次迭代中,绿色项目将是它右边的项目。
如果不是,则需要将所有红色组移过它。有些想法可以说服你,这可以在红色组中以线性时间完成(即使迭代器保证只是前向迭代器)。
为什么复杂度是线性的?因为你可以想象这等同于绿色元素相对于左侧组向左移动。基本原理与摊销分析类似。
下图为第二种情况。在下一次迭代中,绿色元素(正在考虑中)将再次位于红色组的右侧。