- android - RelativeLayout 背景可绘制重叠内容
- android - 如何链接 cpufeatures lib 以获取 native android 库?
- java - OnItemClickListener 不起作用,但 OnLongItemClickListener 在自定义 ListView 中起作用
- java - Android 文件转字符串
最近(从一个 SO 评论)我了解到 std::remove
和 std:remove_if
是稳定的。我认为这是一个糟糕的设计选择,因为它阻止了某些优化,我错了吗?
想象一下删除 1M std::vector
的第一个和第五个元素。因为稳定性,我们不能用swap来实现remove
。相反,我们必须移动每个剩余的元素。 :(
如果我们不受稳定性的限制,我们可以(对于 RA 和 BD 迭代器)实际上有 2 个迭代器,一个在前面,第二个在后面,然后使用交换来结束要删除的项目。我相信聪明的人可能会做得更好。我的问题是一般性的,而不是我正在谈论的特定优化。
编辑: 请注意,C++ 宣传零开销原则,并且还有 std::sort
和 std::stable_sort
排序算法。
EDIT2:
优化将类似于以下内容:
对于 remove_if
:
good_iter <= bad_iter
。
remove_if
的最坏情况 - 注意谓词很少为真),我得到了这个:
#include <vector>
#include <string>
#include <iostream>
#include <map>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <memory>
using namespace std;
int main()
{
vector<string> vsp;
int n;
cin >> n;
for (int i =0; i < n; ++i)
{ string s = "123456";
s.push_back('a' + (rand() %26));
vsp.push_back(s);
}
auto vsp2 = vsp;
auto remove_start = std::chrono::high_resolution_clock::now();
auto it=remove_if(begin(vsp),end(vsp), [](const string& s){ return s < "123456b";});
vsp.erase(it,vsp.end());
cout << vsp.size() << endl;
auto remove_end = std::chrono::high_resolution_clock::now();
cout << "erase-remove: " << chrono::duration_cast<std::chrono::milliseconds>(remove_end-remove_start).count() << " milliseconds\n";
auto partition_start = std::chrono::high_resolution_clock::now();
auto it2=partition(begin(vsp2),end(vsp2), [](const string& s){ return s >= "123456b";});
vsp2.erase(it2,vsp2.end());
cout << vsp2.size() << endl;
auto partition_end = std::chrono::high_resolution_clock::now();
cout << "partition-remove: " << chrono::duration_cast<std::chrono::milliseconds>(partition_end-partition_start).count() << " milliseconds\n";
}
C:\STL\MinGW>g++ test_int.cpp -O2 && a.exe
12345678
11870995
erase-remove: 1426 milliseconds
11870995
partition-remove: 658 milliseconds
最佳答案
我假设您是在询问 stable_remove
的假设定义是什么remove
目前是,和 remove
然而实现者认为最好以任何顺序给出正确的值。希望实现者能够在与 stable_remove
完全相同的情况下进行改进。 .
在实践中,库不能轻易地进行这种优化。这取决于数据,但在决定如何删除每个元素之前,您不想花太长时间计算将删除多少元素。例如,您可以执行额外的传递来计算它们,但在很多情况下,额外传递是低效的。仅仅因为在某些情况下不稳定的移除比稳定的更快并不一定意味着在两者之间进行选择的自适应算法是一个不错的选择。
我认为 remove
之间的区别和 sort
众所周知,排序是一个复杂的问题,有很多不同的解决方案以及权衡和调整。所有“简单”排序算法的平均速度都很慢。大多数标准算法都非常简单,remove
是其中之一,但 sort
不是。我认为定义 stable_remove
没有多大意义。和 remove
作为单独的标准功能。
编辑:您对我的调整进行的编辑(类似于 std::partition
但不需要将值保留在右侧)对我来说似乎很合理。它需要一个双向迭代器,但标准中有先例用于在不同迭代器类别上表现不同的算法,例如 std::distance
.因此,标准可以定义 unstable_remove
这只需要一个前向迭代器,但如果它得到一个双向迭代器,就可以了。标准可能不会列出算法,但它可能有这样的短语“如果迭代器是双向的,最多 min(k, n-k)
移动,其中 k
是删除的元素数”,这实际上会强制它.但请注意,该标准目前并未说明移动了多少 remove_if
确实如此,所以我认为将其固定下来根本不是优先事项。
当然没有什么可以阻止您实现自己的 unstable_remove
.
如果我们接受标准不需要指定不稳定删除,那么问题就归结为它定义的函数是否应该被称为 stable_remove
,期待 future remove
这对于 bidi 迭代器的行为不同,如果一些用于执行不稳定删除的巧妙启发式方法变得众所周知值得一个标准函数,则对于前向迭代器的行为可能会有所不同。我会说不是:如果标准函数的名称不完全规则,这不是灾难。从 STL 的 remove_if
中删除稳定性保证可能会非常具有破坏性。 .那么问题就变成了“为什么 STL 不叫它 stable_remove_if
”,对此我只能回答,除了所有答案中的所有要点外,STL 设计过程比标准化过程更快.stable_remove
还会打开一堆关于其他标准功能的蠕虫,这些功能理论上可能具有不稳定的版本。对于一个特别愚蠢的例子应该 copy
被称为 stable_copy
,以防万一存在某些实现,在复制时反转元素的顺序明显更快?应copy
被称为 copy_forward
,以便实现可以选择 copy_backward
中的哪一个和 copy_forward
由 copy
调用根据哪个更快?委员会的部分工作是在某处划清界限。
我认为实际上当前的标准是明智的,单独定义一个 stable_remove
是明智的。和一个 remove_with_some_other_constraints
,但是 remove_in_some_unspecified_way
只是没有提供与 sort_in_some_unspecified_way
相同的优化机会做。 Introsort 是在 1997 年发明的,就像 C++ 被标准化一样,但我不认为 remove
周围的研究工作和过去完全一样,现在就在 sort
附近.我可能错了,优化remove
可能是下一件大事,如果是这样,那么委员会就错过了一个技巧。
关于c++ - std::remove 和 std::remove_if 设计的稳定性是否失败?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13818369/
我正在使用 .remove() 方法删除一个 html 元素,同时对于这个元素,我有一个事件处理程序,但它没有被触发。为什么会这样呢?这是jsFiddle和代码:HTML Delete I'm goi
所以我尝试从另一篇文章中编写此代码: while(fscanf(orderFile," %49[^;];%d; %49[^\n]",fileName,&seconds,timeValue) == 3)
我正在阅读 Nicolai M.Josuttis 撰写的“The C++ STL. A Tutorial and References”一书,在专门介绍 STL 算法的一章中,作者陈述如下:如果你调用
是否有一种简单的机制来确定 DownloadManager remove() 何时完成,因为它看起来是部分异步的。该函数几乎立即返回下载表中已删除的条目计数,但实际的文件系统管理似乎被插入了某个后台线
我愿意: getActionBarToolbar().removeView(logoImage); getActionBarToolbar().addView(logoImage, lp); 我得到:
我有类(class)评论一对多关系。在类(class)表中有 id 和 title 列。在 Review 表中,有 id、comment 和 course_id,其中“course_id”作为指向类(
我在 stackoverflow 上阅读了不同的答案,了解如何销毁 wigdet/jQueryObject 并取消绑定(bind)其上的所有事件。 这就是我的想法。 $('选择器').remove()
我有一个由一个线程填充的 byte[] 列表,然后我有另一个线程正在从该列表中读取并通过网络发送项目。 每次我读取线程 2 中的项目时,我都想将其从内存中清除。但是因为我正在使用线程,如果我使用 .r
就算法而言,从连续数组中删除一组元素可以分两部分有效地完成。 将所有不删除的元素移到数组的前面。 将数组标记得更小。 这可以在 C++ 中使用 erase-remove 习惯用法来完成。 vector
我尝试删除包含在 map 中渲染的制造商的 View 。当我单击按钮时,事件 click .ver 被激活,但没有任何反应,并且我收到以下错误:Uncaught TypeError: undefine
场景: 使用 jQuery 2.0.1 构建的应用程序。 您的团队更喜欢原生 JavaScript。 选项有jQuery .remove()和 ChildNode.remove() . 您需要删除节点
最初我有一个像这样的删除功能: function ViewWorkflowDetail(btn, workflowId) { $("#workflowDetailPanel").remov
我正在编写 C++ 代码来解决 Leetcode 中的这个问题:https://leetcode.com/problems/remove-element/ Given an array nums an
根据太阳, "Iterator.remove is the only safe way to modify a collection during iteration; the behavior is
众所周知,从 std::vector 中完全删除所需项的一种好方法是 erase-remove idiom . 如以上链接中所述(截至本文发布日期),在代码中,erase-remove 习惯用法如下所
我在 HashSet 上调用 Iterator.remove() 时遇到问题。 我有一组带有时间戳的对象。在将新项目添加到集合之前,我会遍历集合,识别该数据对象的旧版本并将其删除(在添加新对象之前)。
这段代码: Collection col = new ArrayList(); col.add("a"); col.add("b"); col.add("c");
我试图通过在下面输入来卸载 conda 环境基础, conda env remove -n base 正如我所建议的那样,我尝试通过使用来停用基地 conda deactivate base 我再次尝
我已经对我的 IOS 应用程序进行了质量扫描分析。我收到以下警告: The binary has Runpath Search Path (@rpath) set. In certain cases
这个问题已经有答案了: Properly removing an Integer from a List (8 个回答) 已关闭 4 年前。 我是java新手。看起来很简单,但我不明白为什么会发生这种
我是一名优秀的程序员,十分优秀!