Mic*_*oek 4 c++ algorithm unique c++11
我有一个未分类的双精度矢量(实际上是带有双成员的对象,在这种情况下使用).从这个向量我需要删除最小的非唯一值.但是,不保证存在非唯一值.允许对范围进行排序.
一如既往,我开始寻找std :: algorithm并找到std :: unique.在我的第一个想法中,我将结合使用std :: sort将所有非唯一值移动到向量的末尾,然后在非唯一值上使用min_element.但是,std :: unique会将非唯一值保留在未指定状态的末尾.事实上,我失去了所有非POD成员.
有没有人有建议如何有效地做到这一点？由于代码在程序的瓶颈中使用(已经有点太慢),因此有效地执行它非常重要.
那么,如果你可以对范围进行排序,那么这很容易.按升序对其进行排序,然后迭代直到遇到两个等效的相邻元素.完成.
像这样的东西:
T findSmallestNonunique(std::vector<T> v)
{
std::sort(std::begin(v), std::end(v));
auto it = std::adjacent_find(std::begin(v), std::end(v));
if (it == std::end(v))
throw std::runtime_error("No such element found");
return *it;
}
这是一个演示:
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <iostream>
template <typename Container>
typename Container::value_type findSmallestNonunique(Container c)
{
std::sort(std::begin(c), std::end(c));
auto it = std::adjacent_find(std::begin(c), std::end(c));
if (it == std::end(c))
throw std::runtime_error("No such element found");
return *it;
}
int main(int argc, char** argv)
{
std::vector<int> v;
for (int i = 1; i < argc; i++)
v.push_back(std::stoi(argv[i]));
std::cout << findSmallestNonunique(v) << std::endl;
}
// g++ -std=c++14 -O2 -Wall -pedantic -pthread main.cpp \
// && ./a.out 1 2 2 3 4 5 5 6 7 \
// && ./a.out 5 2 8 3 9 3 0 1 4 \
// && ./a.out 5 8 9 2 0 1 3 4 7
//
// 2
// 3
// terminate called after throwing an instance of 'std::runtime_error'
// what(): No such element found
请注意,这里我没有就地执行搜索,但我可以通过引用获取容器.(这取决于您是否可以对原始输入进行排序.)
由于排序操作,这可能与O(N×log(N))一样"差" ,但它简单易维护,不需要任何分配/副本(整个数据集的单个副本除外)如上所述,你可以完全避免).如果您的输入很大,或者您希望在大多数情况下匹配失败,则可能需要使用其他内容.一如既往:简介!
您可以在(预期)线性时间内执行此操作.
用a unordered_map来计算元素.这是(预期)值的数量的线性.
使用朴素循环查找非唯一中的最小项目.
这是一个可能的实现:
#include <unordered_map>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
const vector<double> elems{1, 3.2, 3.2, 2};
unordered_map<double, size_t> c;
for(const double &d: elems)
++c[d];
bool has = false;
double min_;
for(const auto &e: c)
if(e.second > 1)
{
min_ = has? min(e.first, min_): e.first;
has = true;
}
cout << boolalpha << has << " " << min_ << endl;
return 0;
}
编辑为霍华德Hinnant&Lightness Races In Orbit指出,这包含分配和哈希.因此它将是线性的但具有相对大的因子.其他基于排序的解决方案可能对小尺寸更好.当/如果分析时,使用好的分配器很重要,例如谷歌tcmalloc.
好吧,这是一个算法,实际上删除了最小的非唯一项目(而不是只打印它).
template <typename Container>
void
removeSmallestNonunique(Container& c)
{
using value_type = typename Container::value_type;
if (c.size() > 1)
{
std::make_heap(c.begin(), c.end(), std::greater<value_type>{});
std::pop_heap(c.begin(), c.end(), std::greater<value_type>{});
for (auto e = std::prev(c.end()); e != c.begin(); --e)
{
std::pop_heap(c.begin(), e, std::greater<value_type>{});
if (*e == e[-1])
{
c.erase(e);
break;
}
}
}
}
我选择这个算法主要是因为Orbit中的Lightness Races没有.我不知道这是否会更快sort/adjacent_find.答案几乎肯定取决于输入.
例如,如果没有重复,那么这个算法肯定比慢sort/adjacent_find.如果输入非常非常大,并且最小唯一可能在排序范围的早期,则此算法可能比此更快sort/adjacent_find.
我上面所说的一切都只是在猜测.我在对实际问题的统计可能输入执行所需测量之前放弃了.
也许奥米德可以在他的测试中包括这个,并提供一个总结答案.:-)
7个小时后......时间
我接受了奥米德的代码,纠正了其中的一个小错误,纠正了其他两个算法以实际擦除元素,并更改了测试工具以更广泛地改变大小和重复数量.
这是我在-O3使用clang/libc ++测试的代码:
#include <unordered_map>
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <cassert>
template <typename Container>
void
erase_using_hashTable(Container& vec)
{
using T = typename Container::value_type;
std::unordered_map<T, int> c;
for (const auto& elem : vec){
++c[elem];
}
bool has = false;
T min_;
for (const auto& e : c)
{
if (e.second > 1)
{
min_ = has ? std::min(e.first, min_) : e.first;
has = true;
}
}
if (has)
vec.erase(std::find(vec.begin(), vec.end(), min_));
}
template <typename Container>
void
eraseSmallestNonunique(Container& c)
{
std::sort(std::begin(c), std::end(c));
auto it = std::adjacent_find(std::begin(c), std::end(c));
if (it != std::end(c))
c.erase(it);
}
template <typename Container>
void
removeSmallestNonunique(Container& c)
{
using value_type = typename Container::value_type;
if (c.size() > 1)
{
std::make_heap(c.begin(), c.end(), std::greater<value_type>{});
std::pop_heap(c.begin(), c.end(), std::greater<value_type>{});
for (auto e = std::prev(c.end()); e != c.begin(); --e)
{
std::pop_heap(c.begin(), e, std::greater<value_type>{});
if (*e == e[-1])
{
c.erase(e);
break;
}
}
}
}
template<typename iterator>
iterator partition_and_find_smallest_duplicate(iterator begin, iterator end)
{
using std::swap;
if (begin == end)
return end; // empty sequence
// The range begin,end is split in four partitions:
// 1. equal to the pivot
// 2. smaller than the pivot
// 3. unclassified
// 4. greater than the pivot
// pick pivot (TODO: randomize pivot?)
iterator pivot = begin;
iterator first = next(begin);
iterator last = end;
while (first != last) {
if (*first > *pivot) {
--last;
swap(*first, *last);
} else if (*first < *pivot) {
++first;
} else {
++pivot;
swap(*pivot, *first);
++first;
}
}
// look for duplicates in the elements smaller than the pivot
auto res = partition_and_find_smallest_duplicate(next(pivot), first);
if (res != first)
return res;
// if we have more than just one equal to the pivot, it is the smallest duplicate
if (pivot != begin)
return pivot;
// neither, look for duplicates in the elements greater than the pivot
return partition_and_find_smallest_duplicate(last, end);
}
template<typename container>
void remove_smallest_duplicate(container& c)
{
using std::swap;
auto it = partition_and_find_smallest_duplicate(c.begin(), c.end());
if (it != c.end())
{
swap(*it, c.back());
c.pop_back();
}
}
int main()
{
const int MaxArraySize = 5000000;
const int minArraySize = 5;
const int numberOfTests = 3;
//std::ofstream file;
//file.open("test.txt");
std::mt19937 generator;
for (int t = minArraySize; t <= MaxArraySize; t *= 10)
{
const int range = 3*t/2;
std::uniform_int_distribution<int> distribution(0,range);
std::cout << "Array size = " << t << " range = " << range << '\n';
std::chrono::duration<double> avg{},avg2{}, avg3{}, avg4{};
for (int n = 0; n < numberOfTests; n++)
{
std::vector<int> save_vec;
save_vec.reserve(t);
for (int i = 0; i < t; i++){//por kardan array ba anasor random
save_vec.push_back(distribution(generator));
}
//method1
auto vec = save_vec;
auto start = std::chrono::steady_clock::now();
erase_using_hashTable(vec);
auto end = std::chrono::steady_clock::now();
avg += end - start;
auto answer1 = vec;
std::sort(answer1.begin(), answer1.end());
//method2
vec = save_vec;
start = std::chrono::steady_clock::now();
eraseSmallestNonunique(vec);
end = std::chrono::steady_clock::now();
avg2 += end - start;
auto answer2 = vec;
std::sort(answer2.begin(), answer2.end());
assert(answer2 == answer1);
//method3
vec = save_vec;
start = std::chrono::steady_clock::now();
removeSmallestNonunique(vec);
end = std::chrono::steady_clock::now();
avg3 += end - start;
auto answer3 = vec;
std::sort(answer3.begin(), answer3.end());
assert(answer3 == answer2);
//method4
vec = save_vec;
start = std::chrono::steady_clock::now();
remove_smallest_duplicate(vec);
end = std::chrono::steady_clock::now();
avg4 += end - start;
auto answer4 = vec;
std::sort(answer4.begin(), answer4.end());
assert(answer4 == answer3);
}
//file << avg/numberOfTests <<" "<<avg2/numberOfTests<<'\n';
//file << "__\n";
std::cout << "Method1 : " << (avg / numberOfTests).count() << 's'
<< "\nMethod2 : " << (avg2 / numberOfTests).count() << 's'
<< "\nMethod3 : " << (avg3 / numberOfTests).count() << 's'
<< "\nMethod4 : " << (avg4 / numberOfTests).count() << 's'
<< "\n\n";
}
}
这是我的结果:
Array size = 5 range = 7
Method1 : 8.61967e-06s
Method2 : 1.49667e-07s
Method3 : 2.69e-07s
Method4 : 2.47667e-07s
Array size = 50 range = 75
Method1 : 2.0749e-05s
Method2 : 1.404e-06s
Method3 : 9.23e-07s
Method4 : 8.37e-07s
Array size = 500 range = 750
Method1 : 0.000163868s
Method2 : 1.6899e-05s
Method3 : 4.39767e-06s
Method4 : 3.78733e-06s
Array size = 5000 range = 7500
Method1 : 0.00124788s
Method2 : 0.000258637s
Method3 : 3.32683e-05s
Method4 : 4.70797e-05s
Array size = 50000 range = 75000
Method1 : 0.0131954s
Method2 : 0.00344415s
Method3 : 0.000346838s
Method4 : 0.000183092s
Array size = 500000 range = 750000
Method1 : 0.25375s
Method2 : 0.0400779s
Method3 : 0.00331022s
Method4 : 0.00343761s
Array size = 5000000 range = 7500000
Method1 : 3.82532s
Method2 : 0.466848s
Method3 : 0.0426554s
Method4 : 0.0278986s
更新
我已经用Ulrich Eckhardt的算法更新了上面的结果.他的算法很有竞争力.好工作Ulrich!
我应该向读者警告这个答案,Ulrich的算法容易受到"快速排序O(N ^ 2)问题"的影响,其中对于特定输入,算法可能会严重退化.一般算法是可修复的,Ulrich显然已经意识到这个漏洞,这个评论证明了这一点:
// pick pivot (TODO: randomize pivot?)
这是对O(N ^ 2)问题的一种防御,还有其他问题,例如检测不合理的递归/迭代以及切换到中间流的另一算法(例如方法3或方法2).如上所述,当给定有序序列时,方法4受到严重影响,并且当给出逆序序列时,方法4是灾难性的.在我的平台上,对于这些情况,方法3对于方法2也是次优的,尽管不如方法4差.
寻找用于快速排序算法来解决O(N ^ 2)问题的理想技术在某种程度上是黑色的,但非常值得花时间.我肯定会认为方法4是工具箱中的一个有价值的工具.
首先,关于删除元素的任务,最难的是找到它,但实际上删除它很容易(与最后一个元素交换然后pop_back()).因此,我只会解决这个问题.此外,你提到排序序列是可以接受的,但我从中得出的不仅仅是排序,而且任何类型的重新排序都是可以接受的.
看一下quicksort算法.它选择一个随机元素,然后将序列分为左右两侧.如果您编写分区以便区分"less"和"not less",则可以对序列进行部分排序并在运行中找到最小的副本.
以下步骤应该做的工作:
与常规排序相比,如果您在较低的数字中找到重复项,则不会对整个序列进行排序.在一系列唯一数字上,您将完全对它们进行排序.与使用散列映射建议的元素计数相比,这确实具有更高的渐近复杂度.它是否表现更好取决于您的实现和输入数据.
请注意,这要求可以对元素进行排序和比较.你提到你使用了double值,当你在那里有NaN时,这些值很难排序.我可以想象标准容器中的哈希算法可以使用NaNs,因此使用哈希映射计算还有一点.
以下代码实现了上述算法.它使用一个递归函数来分区输入并查找重复项,从第二个函数调用,然后最终删除副本:
#include <vector>
#include <algorithm>
#include <iostream>
template<typename iterator>
iterator partition_and_find_smallest_duplicate(iterator begin, iterator end)
{
using std::swap;
std::cout << "find_duplicate(";
for (iterator it=begin; it!=end; ++it)
std::cout << *it << ", ";
std::cout << ")\n";
if (begin == end)
return end; // empty sequence
// The range begin,end is split in four partitions:
// 1. equal to the pivot
// 2. smaller than the pivot
// 3. unclassified
// 4. greater than the pivot
// pick pivot (TODO: randomize pivot?)
iterator pivot = begin;
std::cout << "picking pivot: " << *pivot << '\n';
iterator first = next(begin);
iterator last = end;
while (first != last) {
if (*first > *pivot) {
--last;
swap(*first, *last);
} else if (*first < *pivot) {
++first;
} else {
++pivot;
swap(*pivot, *first);
++first;
std::cout << "found duplicate of pivot\n";
}
}
// look for duplicates in the elements smaller than the pivot
auto res = partition_and_find_smallest_duplicate(next(pivot), first);
if (res != first)
return res;
// if we have more than just one equal to the pivot, it is the smallest duplicate
if (pivot != begin)
return pivot;
// neither, look for duplicates in the elements greater than the pivot
return partition_and_find_smallest_duplicate(last, end);
}
template<typename container>
void remove_smallest_duplicate(container& c)
{
using std::swap;
auto it = partition_and_find_smallest_duplicate(c.begin(), c.end());
if (it != c.end())
{
std::cout << "removing duplicate: " << *it << std::endl;
// swap with the last last element before popping
// to avoid copying the elements in between
swap(*it, c.back());
c.pop_back();
}
}
int main()
{
std::vector<int> data = {66, 3, 11, 7, 75, 62, 62, 52, 9, 24, 58, 72, 37, 2, 9, 28, 15, 58, 3, 60, 2, 14};
remove_smallest_duplicate(data);
}