Подтвердить что ты не робот

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

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

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

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, построенный для этой цели? Если нет, есть ли какие-либо предложения eek из более высокой эффективности?

4b9b3361

ОТВЕТЫ

Ответ 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();
}

Ответ 2

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

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

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

Ответ 3

Стандартная библиотека имеет 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, как вы знаете, зависит: -).

Ответ 4

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

Ответ 5

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

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

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

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

Ответ 6

Вы можете использовать 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); так же, как ваш пример. Я не думаю, что теоретически вы можете сделать это быстрее, хотя использование С++ 0x std::unordered_set вместо std::set будет делать это в ожидаемое линейное время, но это требует, чтобы ваши элементы были хешируемыми, а также иметь operator ==, что может быть не так просто.

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

Ответ 7

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 8

Ну, ваш первый должен взять только 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)) худший случай, а средний случай зависит от распределения входов.

Ответ 9

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

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

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

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

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

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

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

Ответ 10

В (очень) специальном случае сортировки дискретных значений с известным, не слишком большим максимальным значением 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).

Ответ 11

Используя текущие стандартные контейнеры С++, у вас есть хорошее решение в первом примере. Но если вы можете использовать хэш-контейнер, вы можете сделать лучше, так как хэш-набор будет nO (1) вместо nO (log n) для стандартного набора. Конечно, все будет зависеть от размера n и конкретной реализации библиотеки.