Sets and Vectors. Are sets fast in C++?

Question

Please read the question here - http://www.spoj.com/problems/MRECAMAN/

The question was to compute the recaman's sequence where, a(0) = 0 and, a(i) = a(i-1)-i if, a(i-1)-i > 0 and does not come into the sequence before else, a(i) = a(i-1) + i.

Now when I use vectors to store the sequence, and use the find function, the program times out. But when I use an array and a set to see if the element exists, it gets accepted (very fast). IS using set faster?

Here are the codes:

Vector implementation

vector <int> sequence;
sequence.push_back(0);
for (int i = 1; i <= 500000; i++)
{
    a = sequence[i - 1] - i;
    b = sequence[i - 1] + i;
    if (a > 0 && find(sequence.begin(), sequence.end(), a) == sequence.end())
        sequence.push_back(a);
    else
        sequence.push_back(b);
}

Set Implementation

int a[500001]
set <int> exists;
a[0] = 0;
for (int i = 1; i <= MAXN; ++i)
{
    if (a[i - 1] - i > 0 && exists.find(a[i - 1] - i) == exists.end()) a[i] = a[i - 1] - i;
    else a[i] = a[i - 1] + i;
    exists.insert(a[i]);
}

Answer 1

Lookup in an std::vector:

find(sequence.begin(), sequence.end(), a)==sequence.end()

is an O(n) operation (n being the number of elements in the vector).

Lookup in an std::set (which is a balanced binary search tree):

exists.find(a[i-1] - i) == exists.end()

is an O(log n) operation.

So yes, lookup in a set is (asymptotically) faster than a linear lookup in vector.

Answer 2

There is only one valid answer to most "Is XY faster than UV in C++" questions:

Use a profiler.

While most algorithms (including container insertions, searches etc.) have a guaranteed complexity, these complexities can only tell you about the approximate behavior for large amounts of data. The performance for any given smaller set of data can not be easily compared, and the optimizations that a compiler can apply can not be reasonably guessed by humans. So use a profiler and see what is faster. If it matters at all. To see if performance matters in that special part of your program, use a profiler.

However, in your case it might be a safe bet that searching a set of ~250k elements can be faster than searching an unsorted vector of tat size. However, if you use the vector only for storing the inserted values and leave the sequence[i-1] out in a separate variable, you can keep the vector sorted and use an algorithm for sorted ranges like binary_search, which can be way faster than the set.

A sample implementation with a sorted vector:

const static size_t NMAX = 500000;
vector<int> values = {0};
values.reserve(NMAX );
int lastInserted = 0;

for (int i = 1; i <= NMAX) {
  auto a = lastInserted - i;
  auto b = lastInserted + i;

  auto iter = lower_bound(begin(values), end(values), a);
  //a is always less than the last inserted value, so iter can't be end(values)

  if (a > 0 && a < *iter) {
    lastInserted = a;
  }
  else {
    //b > a => lower_bound(b) >= lower_bound(a)
    iter = lower_bound(iter, end(values), b);
    lastInserted = b;
  }
  values.insert(iter, lastInserted);
}

I hope I did not introduce any bugs...