Определение, имеет ли неупорядоченный вектор <T>все уникальные элементы

Question

Профилирование моего кода, связанного с процессором, заставило меня потратить много времени на проверку того, содержит ли контейнер совершенно уникальные элементы. Предполагая, что у меня есть большой контейнер несортированных элементов (с определением < и =), у меня есть две идеи о том, как это можно сделать:

Первое использование набора:

template <class T>
bool is_unique(vector<T> X) {
  set<T> Y(X.begin(), X.end());
  return X.size() == Y.size();
}

Второй цикл по элементам:

template <class T>
bool is_unique2(vector<T> X) {
  typename vector<T>::iterator i,j;
  for(i=X.begin();i!=X.end();++i) {
    for(j=i+1;j!=X.end();++j) {
      if(*i == *j) return 0;
    }
  }
  return 1;
}

Я протестировал их как можно лучше, и из того, что я могу почерпнуть из прочтения документации по STL, ответ (как обычно) зависит. Я думаю, что в первом случае, если все элементы уникальны, это очень быстро, но при большом вырождении операция, похоже, займет O (N ^ 2) времени. Для подхода с вложенными итераторами, похоже, верно обратное: он светится быстро, если X[0]==X[1], но занимает (понятно) O (N ^ 2) время, если все элементы уникальны.

Есть ли лучший способ сделать это, возможно, алгоритм STL, созданный для этой цели? Если нет, то есть ли какие-нибудь предложения по повышению эффективности?

Answer 1

Ваш первый пример должен быть O (N log N), так как set занимает log N времени для каждой вставки. Я не думаю, что более быстрый O возможен.

Второй пример, очевидно, O (N ^ 2). Коэффициент и использование памяти невелики, поэтому в некоторых случаях он может быть быстрее (или даже самым быстрым).

Это зависит от T, но для общей производительности я бы рекомендовал сортировать вектор указателей на объекты.

template< class T >
bool dereference_less( T const *l, T const *r )
 { return *l < *r; } 

template <class T>
bool is_unique(vector<T> const &x) {
    vector< T const * > vp;
    vp.reserve( x.size() );
    for ( size_t i = 0; i < x.size(); ++ i ) vp.push_back( &x[i] );
    sort( vp.begin(), vp.end(), ptr_fun( &dereference_less<T> ) ); // O(N log N)
    return adjacent_find( vp.begin(), vp.end(),
           not2( ptr_fun( &dereference_less<T> ) ) ) // "opposite functor"
        == vp.end(); // if no adjacent pair (vp_n,vp_n+1) has *vp_n < *vp_n+1
}

или в стиле STL,

template <class I>
bool is_unique(I first, I last) {
    typedef typename iterator_traits<I>::value_type T;
    …

---

И если вы можете изменить порядок исходного вектора, конечно,

template <class T>
bool is_unique(vector<T> &x) {
    sort( x.begin(), x.end() ); // O(N log N)
    return adjacent_find( x.begin(), x.end() ) == x.end();
}

Answer 2

Вы должны отсортировать вектор, если хотите быстро определить, имеет ли он только уникальные элементы. В противном случае лучшее, что вы можете сделать, это O (n ^ 2) время выполнения или O (n log n) время выполнения с O (n) пробелом. Я думаю, что лучше написать функцию, которая предполагает, что вход отсортирован.

template<class Fwd>
bool is_unique(In first, In last)
{
    return adjacent_find(first, last) == last;
}

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

Answer 3

Во-первых, вы можете объединить преимущества обоих: прекратить сборку, если вы уже обнаружили дубликат:

template <class T>
bool is_unique(const std::vector<T>& vec)
{
    std::set<T> test;
    for (typename std::vector<T>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
        if (!test.insert(*it).second) {
            return false;
        }
    }
    return true;
}

Кстати, Potatoswatter хорошо показывает, что в общем случае вы можете избежать копирования T, и в этом случае вы можете использовать std::set<const T*, dereference_less>.

---

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

Answer 4

Разве невозможно просто использовать контейнер, который предоставляет эту «гарантию» с самого начала? Было бы полезно пометить дубликат во время вставки, а не в какой-то момент в будущем? Когда я хотел сделать что-то подобное, я пошел в этом направлении; просто используя набор в качестве «основного» контейнера и, возможно, создавая параллельный вектор, если мне нужно было поддерживать исходный порядок, но, конечно, это делает некоторые предположения о доступности памяти и ЦП ...

Answer 5

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

template <typename T>
bool is_unique(std::vector<T> vec)
{
    std::sort(vec.begin(), vec.end());
    return std::unique(vec.begin(), vec.end()) == vec.end();
}

Будет ли это быстрее, чем использование std::set, как вы знаете, будет зависеть от: -).

Answer 6

Если я могу добавить свои 2 цента.

Прежде всего, как заметил @Potatoswatter, если ваши элементы не являются дешевыми для копирования (встроенные / маленькие POD), вы захотите использовать указатели на оригинальные элементы, а не копировать их.

Во-вторых, доступно 2 стратегии.

1. Просто убедитесь, что дубликат не вставлен в первую очередь. Это, конечно, означает управление вставкой, что обычно достигается созданием выделенного класса (с вектором в качестве атрибута).
2. Когда свойство необходимо, проверьте наличие дубликатов

Я должен признать, что склонялся бы к первому. Инкапсуляция, четкое разделение обязанностей и все такое.

Во всяком случае, есть несколько способов в зависимости от требований. Первый вопрос:

• мы должны позволить элементам в vector в определенном порядке или мы можем "связываться" с ними?

Если мы сможем с ними связываться, я бы предложил отсортировать vector: Loki::AssocVector должно помочь вам начать. Если нет, то нам нужно сохранить индекс структуры, чтобы обеспечить это свойство ... подождите минуту: Boost.MultiIndex на помощь?

В-третьих: когда вы отметили, что простой линейный поиск удвоил, вы получите среднюю сложность O (N ² ), которая не годится.

Если < уже определено, то сортировка очевидна с ее сложностью O (N log N). Может также стоить сделать T Hashable, потому что std::tr1::hash_set может дать лучшее время (я знаю, вам нужен RandomAccessIterator, но если T является Hashable, то легко иметь T* Hashable to; ))

Но, в конце концов, реальная проблема заключается в том, что наши советы являются необходимыми, потому что нам не хватает данных.

• Что такое T, вы хотите, чтобы алгоритм был универсальным?
• Какое количество элементов? 10, 100, 10.000, 1.000.000? Потому что асимптотическая сложность является своего рода спорным, когда имеешь дело с несколькими сотнями ....
• И, конечно: можете ли вы обеспечить уникальность во время вставки? Можете ли вы изменить сам вектор?

Answer 7

Вы можете использовать std::unique, но для этого требуется сначала отсортировать диапазон:

template <class T>
bool is_unique(vector<T> X) {
  std::sort(X.begin(), X.end());
  return std::unique(X.begin(), X.end()) == X.end();
}

std::unique изменяет последовательность и возвращает итератор в конец уникального набора, поэтому, если это еще конец вектора, он должен быть уникальным.

Это работает в nlog (n); так же, как ваш пример. Я не думаю, что теоретически вы можете гарантировать, что сделаете это быстрее, хотя использование C ++ 0x std::unordered_set вместо std::set сделало бы это в ожидаемое линейное время - но это требует, чтобы ваши элементы были хэшируемыми, а также имели operator == определено, что может быть не так просто.

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

Answer 8

В (очень) особом случае сортировки дискретных значений с известным, не слишком большим, максимальным значением N.
Вы должны иметь возможность запустить сортировку сегментов и просто проверить, что число значений в каждом сегменте меньше 2.

bool is_unique(const vector<int>& X, int N)
{
  vector<int> buckets(N,0);
  typename vector<int>::const_iterator i;
  for(i = X.begin(); i != X.end(); ++i)
    if(++buckets[*i] > 1)
      return false;
  return true;
}

Сложность этого будет O (n).

Answer 9

Если тип T, который Вы храните в своем векторе, имеет большой размер и его копирование обходится дорого, рассмотрите возможность создания вектора указателей или итераторов для ваших векторных элементов. Отсортируйте его по указанному элементу, а затем проверьте его на уникальность.

Вы также можете использовать для этого std :: set. Шаблон выглядит так

template <class Key,class Traits=less<Key>,class Allocator=allocator<Key> > class set

Я думаю, что вы можете предоставить соответствующий параметр Traits и вставить необработанные указатели для скорости или реализовать простой класс-оболочку для указателей с помощью оператора <. </p>

Не используйте конструктор для вставки в набор. Используйте метод вставки. Метод (одна из перегрузок) имеет сигнатуру

pair <iterator, bool> insert(const value_type& _Val);

Проверяя результат (второй член), вы часто можете обнаружить дубликат гораздо быстрее, чем если бы вы вставили все элементы.

Answer 10

Ну, ваш первый должен взять только N log(N), так что это явно худший вариант развития событий для этого приложения.

Тем не менее, вы должны быть в состоянии получить лучший вариант, если проверяете, как выдобавьте вещи в набор:

template <class T>
bool is_unique3(vector<T> X) {
  set<T> Y;
  typename vector<T>::const_iterator i;
  for(i=X.begin(); i!=X.end(); ++i) {
    if (Y.find(*i) != Y.end()) {
      return false;
    }
    Y.insert(*i);
  }
  return true;
}

Это должно иметь O(1) лучший случай, O(N log(N)) худший случай, а средний случай зависит от распределения входов.