Remove the smallest non-unique value from the vector

Question

I have an unsorted doubles vector (actually double-member objects, which is used in this case). From this vector I need to remove the smallest non-single value. However, it is not guaranteed that there is a non-unique meaning. Sort range is allowed.

As always, I started by looking for std :: algorithm and found std :: unique. In my first idea, I would use this in combination with std :: sort to move all non-unique values ​​to the end of the vector, and then use min_element over non-historical values. However, std :: unique will leave unique values ​​at the end in an unspecified state. And indeed, I lost all non POD members.

Does anyone have a suggestion on how to do this effectively? It is important to do this efficiently, because the code is used in the bottleneck of the program (which is already too slow).

Answer 1

(I add an additional answer, since 1) the focus of the first answer was to use the ready-made STL components, and 2) Howard Hinnant has raised some interesting points since then.)

Thanks to Howard Hinnant on the principle of comparing different approaches (as well as a very unique solution)! This led to what I personally find interesting (and do not quite understand).

However, the test was somewhat problematic, IMHO.

The question is what the problem was

... , ... ,

, :

• int s, ; double , int s ', - Theta (n log (n)), - O (n).

• main ( ) . , , , , + .

• , vector, ( ). , vector of double , OP , .

---

, - gcc libstd++ pb_ds extension. № 1 №2 (sort + adjacent_find), - , №3 (make_heap).

, "-", .

template<typename T, class Hash=std::hash<T>>
class smallest_dup_remover
{
public:
    explicit smallest_dup_remover(std::size_t max_size) 
    {
        while(m_mask < max_size)
            m_mask *= 2;

        m_status.resize(m_mask);
        m_vals.resize(m_mask);

        --m_mask;
    }

    void operator()(std::vector<T> &vals)
    {
        std::fill(std::begin(m_status), std::end(m_status), 0);
        bool has = false;
        T min_;
        std::vector<T> spillover;
        spillover.reserve(vals.size());
        for(auto v: vals)
        {
            const std::size_t pos = m_hash(v) & m_mask;
            char &status = m_status[pos];
            switch(status)
            {
            case 0:
                status = 1;
                m_vals[pos] = v;
                break;
            case 1:
                if(m_vals[pos] == v)
                {
                    status = 2;
                    min_ = has? std::min(min_, v): v;
                    has = true;
                }
                else
                    spillover.push_back(v);
                break;
            case 2:
               if(m_vals[pos] != v)
                    spillover.push_back(v);
            }
        }
        std::sort(std::begin(spillover), std::end(spillover));
        auto it = std::adjacent_find(std::begin(spillover), std::end(spillover));
        if(has && it == std::end(spillover))
            remove_min(vals, min_);
        else if(has && it != std::end(spillover))
            remove_min(vals, std::min(min_, *it));
        else if(!has && it != std::end(spillover))
            remove_min(vals, *it);
    }

private:
    void remove_min(std::vector<T> &vals, T t)
    {
        vals.erase(std::find(vals.begin(), vals.end(), t)); 
    }

private:
    size_t m_mask = 1;
    std::vector<char> m_status;
    std::vector<T> m_vals;
    Hash m_hash;
};

vector s:

• a "status" vector, 0, 1 "many"

• a "values" vector, " "

• " ",

"many" " " . (.. , ) "" vector. vector , # 2. "" .

---

- , , - , .

( # 1 -, # 2 - quicksort, # 3 - ).

, ( 1,5 ), :

, , , , -, . , , , , .

, . :

, .

, .

+ ( ):

, , , 100 ( ):

. . MakeHeap , , ( ). , , . , heapsort. , .

, . , , , .

---

:

• , -, : n n log (n), # 2?

• Hinnant , + ? 1.5 X , Bootstrap Resampling, 37%, .

• , . .

• :

  • OP, , + .

  • , , . (, , ) - Howard Hinnant , . , , , .

Answer 2

() .

• unordered_map . () .

• -uniques, .

:

#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;
}

---

. , , . , . . / , , Google tcmalloc.

Answer 3

, , . , , . .

- :

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 & times; log (N)), - / ( , , , ). , - , . : !

Answer 4

, , ( ).

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;
            }
        }
    }
}

, . , , sort/adjacent_find . .

, , , sort/adjacent_find. , , , , , , , sort/adjacent_find.

, , . .

, Omid .: -)

7 ...

Omid's, , , , .

, , clang/lib++ -O3:

#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

. . !

, " O (N ^ 2)", . , , , , :

// pick pivot (TODO: randomize pivot?)

O (N ^ 2), , / (, 3 2). 4 , . 3 2 , , 4.

O (N ^ 2) - , . 4 .

Answer 5

-, , - , ( , pop_back()). . , , , , , .

. , . , "" " ", .

:

• . , . : , (!) , , .
• .
• , .
• , .
• , , .

, , . . -, . , .

, , . , double, , , , NaN. , NaN, , -.

The following code implements the algorithm above. It uses one recursive function to split the input and find duplicates called from the second function, which then removes the duplicate:

#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);
}