Быстрое объединение объединения целого числа

Question

Мне нужно сделать много союзов упорядоченного набора целых чисел (я бы хотел избежать дубликатов, но это нормально, если есть).

Это код с наилучшей производительности до сих пор:

// some code added for better understanding 
std::vector< std::pair<std::string, std::vector<unsigned int> > vec_map; 
vec_map.push_back(std::make_pair("hi", std::vector<unsigned int>({1, 12, 1450}); 
vec_map.push_back(std::make_pair("stackoverflow", std::vector<unsigned int>({42, 1200, 14500}); 

std::vector<unsigned int> match(const std::string & token){ 
    auto lower = std::lower_bound(vec_map.begin(), vec_map.end(), token, comp2()); 
    auto upper = std::upper_bound(vec_map.begin(), vec_map.end(), token, comp()); 

    std::vector<unsigned int> result; 

    for(; lower != upper; ++lower){ 
     std::vector<unsigned int> other = lower->second; 
     result.insert(result.end(), other.begin(), other.end()); 
    } 
    std::sort(result.begin(), result.end()); // This function eats 99% of my running time 

    return result; 
} 

Valgrind (с помощью инструмента callgrind) говорит мне, что я провожу 99% времени делает вид.

Это то, что я пытался до сих пор:

• Использование зЬй :: набор (очень плохой производительности)
• Использование зЬй :: set_union (плохая производительность)
• сохраняя кучу с станд :: push_heap (на 50% медленнее)

Есть ли какая-нибудь надежда получить какую-то производительность? Я могу изменить свои контейнеры и использовать boost и, возможно, некоторые другие lib (в зависимости от их лицензии).

EDIT целые числа могут быть как большой 10 000 000 EDIT 2 дал несколько примеров того, как я использую его, из-за какой-то путаницы

Answer 1

Пользовательские слияния сортировки могут дают небольшую помощь.

#include <string> 
#include <vector> 
#include <algorithm> 
#include <map> 
#include <iostream> 
#include <climits> 

typedef std::multimap<std::string, std::vector<unsigned int> > vec_map_type; 
vec_map_type vec_map; 
struct comp { 
    bool operator()(const std::string& lhs, const std::pair<std::string, std::vector<unsigned int> >& rhs) const 
    { return lhs < rhs.first; } 
    bool operator()(const std::pair<std::string, std::vector<unsigned int> >& lhs, const std::string& rhs) const 
    { return lhs.first < rhs; } 
}; 
typedef comp comp2; 

    std::vector<unsigned int> match(const std::string & token){ 
     auto lower = std::lower_bound(vec_map.begin(), vec_map.end(), token, comp2()); 
     auto upper = std::upper_bound(vec_map.begin(), vec_map.end(), token, comp()); 

     unsigned int num_vecs = std::distance(lower, upper); 
     typedef std::vector<unsigned int>::const_iterator iter_type; 
     std::vector<iter_type> curs; 
     curs.reserve(num_vecs); 
     std::vector<iter_type> ends; 
     ends.reserve(num_vecs); 
     std::vector<unsigned int> result; 
     unsigned int result_count = 0; 

     //keep track of current position and ends 
     for(; lower != upper; ++lower){ 
      const std::vector<unsigned int> &other = lower->second; 
      curs.push_back(other.cbegin()); 
      ends.push_back(other.cend()); 
      result_count += other.size(); 
     } 
     result.reserve(result_count); 
     //merge sort 
     unsigned int last = UINT_MAX; 
     if (result_count) { 
      while(true) { 
       //find which current position points to lowest number 
       unsigned int least=0; 
       for(unsigned int i=0; i< num_vecs; ++i){ 
        if (curs[i] != ends[i] && (curs[least]==ends[least] || *curs[i]<*curs[least])) 
         least = i; 
       } 
       if (curs[least] == ends[least]) 
        break; 
       //push back lowest number and increase that vectors current position 
       if(*curs[least] != last || result.size()==0) { 
        last = *curs[least]; 
        result.push_back(last); 
          } 
       ++curs[least]; 
      } 
     } 
     return result; 
    } 

    int main() { 
     vec_map.insert(vec_map_type::value_type("apple", std::vector<unsigned int>(10, 10))); 
     std::vector<unsigned int> t; 
     t.push_back(1); t.push_back(2); t.push_back(11); t.push_back(12); 
     vec_map.insert(vec_map_type::value_type("apple", t)); 
     vec_map.insert(vec_map_type::value_type("apple", std::vector<unsigned int>())); 
     std::vector<unsigned int> res = match("apple"); 
     for(unsigned int i=0; i<res.size(); ++i) 
      std::cout << res[i] << ' '; 
     return 0; 
    } 

http://ideone.com/1rYTi

Answer 2

Это выглядит как экземпляр multi-way merge. В зависимости от ввода (профиля и времени!) Лучшим алгоритмом может быть то, что у вас есть или что-то, что создает результат постепенно, путем выбора наименьшего целого из всех контейнеров или чего-то более сложного.

Answer 3

Если число элементов является относительно большой процент диапазона возможных int с, вы могли бы получить достойную производительность из того, что по сути является упрощенным «хеширования» (использовать DB).

(если имеется относительно небольшое число целых чисел по сравнению с диапазоном возможных значений, это, вероятно, не самый лучший подход.)

По сути, мы делаем гигантский растровый, а затем установить флаги только по индексам соответствующие входные int с и, наконец, восстановить результат на основании этих флагов:

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <time.h> 

template <typename ForwardIterator> 
std::vector<int> IntSetUnion(
    ForwardIterator begin1, 
    ForwardIterator end1, 
    ForwardIterator begin2, 
    ForwardIterator end2 
) { 

    int min = std::numeric_limits<int>::max(); 
    int max = std::numeric_limits<int>::min(); 

    for (auto i = begin1; i != end1; ++i) { 
     min = std::min(*i, min); 
     max = std::max(*i, max); 
    } 

    for (auto i = begin2; i != end2; ++i) { 
     min = std::min(*i, min); 
     max = std::max(*i, max); 
    } 

    if (min < std::numeric_limits<int>::max() && max > std::numeric_limits<int>::min()) { 

     std::vector<int>::size_type result_size = 0; 
     std::vector<bool> bitmap(max - min + 1, false); 

     for (auto i = begin1; i != end1; ++i) { 
      const std::vector<bool>::size_type index = *i - min; 
      if (!bitmap[index]) { 
       ++result_size; 
       bitmap[index] = true; 
      } 
     } 

     for (auto i = begin2; i != end2; ++i) { 
      const std::vector<bool>::size_type index = *i - min; 
      if (!bitmap[index]) { 
       ++result_size; 
       bitmap[index] = true; 
      } 
     } 

     std::vector<int> result; 
     result.reserve(result_size); 
     for (std::vector<bool>::size_type index = 0; index != bitmap.size(); ++index) 
      if (bitmap[index]) 
       result.push_back(index + min); 

     return result; 

    } 

    return std::vector<int>(); 

} 

void main() { 

    // Basic sanity test... 
    { 

     std::vector<int> v1; 
     v1.push_back(2); 
     v1.push_back(2000); 
     v1.push_back(229013); 
     v1.push_back(-2243); 
     v1.push_back(-530); 

     std::vector<int> v2; 
     v1.push_back(2); 
     v2.push_back(243); 
     v2.push_back(90120); 
     v2.push_back(329013); 
     v2.push_back(-530); 

     auto result = IntSetUnion(v1.begin(), v1.end(), v2.begin(), v2.end()); 

     for (auto i = result.begin(); i != result.end(); ++i) 
      std::cout << *i << std::endl; 

    } 

    // Benchmark... 
    { 

     const auto count = 10000000; 

     std::vector<int> v1(count); 
     std::vector<int> v2(count); 

     for (int i = 0; i != count; ++i) { 
      v1[i] = i; 
      v2[i] = i - count/2; 
     } 

     std::random_shuffle(v1.begin(), v1.end()); 
     std::random_shuffle(v2.begin(), v2.end()); 

     auto start_time = clock(); 
     auto result = IntSetUnion(v1.begin(), v1.end(), v2.begin(), v2.end()); 
     auto end_time = clock(); 
     std::cout << "Time: " << (((double)end_time - start_time)/CLOCKS_PER_SEC) << std::endl; 
     std::cout << "Union element count: " << result.size() << std::endl; 

    } 

} 

Это печатает ...

Time: 0.402 

... на моей машине.

Если вы хотите получить свой ввод int s от чего-то другого, кроме std::vector<int>, вы можете реализовать свой собственный итератор и передать его IntSetUnion.

Answer 4

Вы сортируете целые числа с ограниченным диапазоном, это один из тех редких случаев, когда можно было использовать radix sort. К сожалению, единственный способ узнать, превосходит ли это обобщенный вид, - попробовать его.

Answer 5

АЛЬТЕРНАТИВА РЕШЕНИЕ:

Метод станд :: сортировки (если он основан на быстром-то) очень хорошая сортировка не сортируется vectorsO (LogN), еще лучше с отсортированного вектора, но если ваш вектор инвертирован, имеют O (N^2). Может случиться так, что, когда вы выполняете объединение, у вас много операндов, причем первый из них содержит более крупные значения, чем последователи.

Я хотел бы попробовать следующее (я полагаю, элементы из входных векторов уже отсортированы):

• Как было предложено другими людьми здесь вы должны reseve требуемого размера по результатам вектора, прежде чем начать заполнять его.

• В случае std :: distance (lower, upper) == 1 нет причин для объединения, просто скопируйте contento одного операнда.

• Сортируйте операнды вашего объединения, возможно, по размеру (больше первого), или если диапазоны не перекрываются или частично перекрываются только по первому значению), так что вы максимизируете количество элементов, которые уже отсортированы по следующий шаг. Вероятно, лучшим является стратегия, которая учитывает обе вещи SIZE и RANGE каждого операнда вашего союза. Многое зависит от реальных данных.

• Если имеется несколько операндов с большим количеством элементов, добавьте элементы на обратной стороне вектора результата, но после добавления каждого вектора (из второго) вы можете попытаться объединиться (std :: inplace_merge) старый контент с добавлением, это также дедуплицирует элементы для вас.

• Если количество операндов велико (по сравнению с общим количеством элементов), вы должны остаться с прежней стратегией сортировки после этого, но вызовите std :: unique для дедупликации после сортировки. В этом случае вы должны сортировать по диапазону содержащихся элементов.