Re: Which is faster ?
- Posted by DerekParnell (admin) Feb 17, 2009
- 961 views
On a long sequence of items which is faster using the
find() function or searching with a for loop ???
find() should always be faster than a manual loop. In fact, find() is even faster in 4.0 than it was in 3.1. If the list gets too long, however, other methods may be able to beat it, such as a binary search (of which there is an implementation in the 4.0 std library). But of course, you have to make sure that you sort your data first.
Matt
Just a bit more clarification, find() is faster for long sequences. If the sequence is, say less than 10-15 items, then a loop can be faster. Also, the type of data in the sequence can influence the speed too. Generally, comparing integers (using find() or '=') is faster than comparing atoms, which is in turn fast than comparing sequences.
However, following Matt's advice, if you know something about the contents of the sequence before seeking, you can often come up with a smarter way of searching it.
- A sorted sequence would benefit from a binary search.
- Or if there are mostly only a few items that are found much more than other items, arrange to have them at the front of the sequence.
- Or if the sequence is fairly static (doesn't change much), you might consider a hash map instead.
- Maybe you can arrange the sequence to contain a set of sub-sequences based of the length of the item. Such that all 1-element items are in the first sub-sequence, 2-element items in the second sub-sequence etc.... Then when doing a search, you can quick work out which sub-sequence your item is contained it.
