std::string::find vs std::find

Hi All:

I have a large number of elements to be stored into vector or basic string(delimited by \n). I need to search for an element and I would like to know what is faster:

A:

Code:

---

std::string str = "\nElement1\nElement2...element1000\n"
str.find("\nElement3\n");

---

B:

Code:

---

std::vector<string> v;
v.push_back("Element1"); v.push_back("Element2");  ....
std::find(v.begin(), v.end(), "Element3") != v.end() )

---

I'm only interested in search time, I don't need to access any of the elements for reading, modifying or removing.

Thanks a lot,
Petry

The second is likely to be faster.

If we start with \nElement1\nElement2...element1000\n and we search for Element3... For each position in the string we have to start comparing whether the string is equal to to the one we're searching for. That is, we have the number of characters time an equals-test (operator==).

In the second case, we only have to compare at the start of each element. So in stead of one per character of the string we only have to the equals-test (operator==) the same amount of times as the number of elements, which is obviously a lot less.

With the first method, A, all you are doing is writing a new line and then a string of characters, which would be pretty tedious to find a certain character. The second however, is much more powerful. You are adding another string to the vector, which makes it a lot easier to manipulate.

I have just tested the difference.

Filesize: 8mb
Lines: 700.000
Average line length: 15 characters

Time to fill:
vector: 3843ms
string: 3891ms

The search time for the last unique element is:
vector: 218
string: 172

Wow, I wasn't expecting that.

Use a map.

If you need to store items and then access them later via some criteria (IE: a key) a map would be better suited for this. If you want something quicker than a map then you could use the non-standard hash_map in MS STL or you could program your own hash container.

I only to search through the elements, no need to access by key.

Then use std::set.

Quote:

---

Originally Posted by laserlight

Then use std::set.

---

Seconded.
Just make sure you use the member version of find, not std::find and you're performance will be far better instead of a tad worse.

Code:

---

std::set<std::string> s;
s.insert("Element1"); s.insert("Element2");  ....
if ( s.find("Element3") != s.end() )

---

However, a set has a few points of interests:
You cannot store the same element twice. If you need do this use a multiset
It will sort your contents. If you need to keep the ordering use unordered_map (it's in tr1 so if your compiler doesn't support it, use boost::tr1)

>> If you need to keep the ordering use unordered_map
unordered_map, or unordered_set will not keep the ordering. If you need to keep the ordering of how the items were added then vector is the best choice.

The unordered containers are unordered. They aren't sorted but they don't retain the ordering of how you inserted the values (AFAIK). They might be the best option for this as they can have the fastest lookup times compared to the other choices, but you have to make sure you set up the hash properly.

If you don't need to keep the elements in the order you added them, and don't want to use the unordered containers (or don't have access to them), there is another option that might be even better than std::set. That option is to use the vector, but before you search you sort the vector. Then use the binary_search algorithm instead of find. This duplicates the benefits of the binary tree that is how std::set is normally implemented, but adds less overhead because the items are stored in an array instead of linked in a tree.

The suggestion to use a std::set is a good one, but it is not the most efficient data structure for this problem. It is probable that many of the strings in your set are prefixes of each other. If this is the case, you should consider using a data structure which takes advantage of that fact.

The naive implementation with std::set is inefficient if there are many similar strings with long, identical prefixes. The string comparison operation used during the set.find() operation will spend a lot of time comparing these prefixes. A tree data structure is still the right idea, but you should look at something like a ternary tree or a prefix tree.

The lookup/insertion time is still O(log n), but with a far smaller constant factor. The memory usage is vastly improved as well.

Quote:

---

Originally Posted by Daved

>>That option is to use the vector, but before you search you sort the vector. Then use the binary_search algorithm instead of find. This duplicates the benefits of the binary tree that is how std::set is normally implemented, but adds less overhead because the items are stored in an array instead of linked in a tree.

---

I only need to check if an element exists no need to keep the order. I made a new test including set and Daved's suggestion, the results are below:

Filesize: 14mb
Lines: 1.050.000
Average line length: 20 characters

Time to fill:
vector: 7610ms
string: 8906ms
set: 19719ms

The search time for the last unique element is:
vector-find: 297ms
vector-sort-binary_search: 41344ms
vector-binary_search: 0ms
string: 234ms
set: 0ms

It seems that vector & binary_search is the best couple: the fastest way to fill-in the array and 0ms search time. Sorting slows things a lot. All in all - GREAT SOLUTION!

I decided too quickly. I looked for more info on binary_search and it works only in sorted array. It worked in my case while the array was not sorted, but it's not stable solution.

Since sorting takes a lot of time on large array, I think that std::set is the winner..

I'm a little surprised the sort takes that long. I would think it would be closer to the set's load time. Perhaps it is because your data is already mostly sorted?

My guess is that unordered_set will be the fastest of all the generic solutions, since lookup time and load time are all constant assuming your hash and capacity are good. Depending on your actual input you might be able to get a solution that is notably faster if you create your own structure/algorithm as brewbuck suggests, but I assumed that "Element1","Element2", etc, was just an example and your input isn't necessarily so specific.

Quote:

---

Originally Posted by Daved

I'm a little surprised the sort takes that long. I would think it would be closer to the set's load time. Perhaps it is because your data is already mostly sorted?

---

I think that for it to take that long he would have to be sorting it after every push_back.

If you only sort it once, after the data is all loaded in, then perform many binary_searches, then the overhead of the sorting becomes less and less significant to the point that the binary_search will be faster. Still wont beat hashing, but it should be good enough.

Hashing would definitely be faster and it's fairly trivial to write a templated hash container. If I need to 'find' items in a collection I rarely, if ever, use vector or list. For very small containers you probably will not notice any issues but you will as the container grows in size. Sorting can also be slow if you don't use it wisely. This is what iMalc is referring to. A brute force approach would be to sort after every change to the collection and that would also be the slowest approach. The less operations you perform on the container the faster it is going to be. If you only sort when you need to or can break the sort down into segments so less items are sorted at any one time then you should get improvements.

However the only way to know for sure is to try several approaches and see which one works best for your particular application.

Some time ago I discovered a performance bug in MingW's implementation of iter_swap (which is used to swap items by the sorting routine among others). If you happen to have this compiler and change the implementation to:

Code:

---

  //fixed implementation (must be moved after swap in stl_algobase.h)
  template<typename _ForwardIterator1, typename _ForwardIterator2>
    inline void
    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
    {
        //concept requirements...
        swap(*__a, *__b);
    }

---

this might speed up sorting strings in particular (might become comparable to the set).

The problem is that the existing implementation failed to take advantage of overloaded swap functions and creates lots of temporaries, just to swap two strings:

Code:

---

  template<typename _ForwardIterator1, typename _ForwardIterator2>
    inline void
    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
    {
        typedef typename iterator_traits<_ForwardIterator1>::value_type
            _ValueType1;
        //concept requirements...
        const _ValueType1 __tmp = *__a;
        *__a = *__b;
        *__b = __tmp;
    }

---