Re: ArrayList BinarySearch vs Contains

"Dave Sexton" <dave@jwa[remove.this]online.com> wrote in message
news:u%23TvmDdBHHA.3620@xxxxxxxxxxxxxxxxxxxxxxx
Hi Bill,

It seems you are suggesting that the scale of the data can affect
whether a required sorting operation will actually reduce the overall
performance of an algorithm so that it becomes worse than a linear
search. Can this be true even when the data is sorted as it's being
entered into the structure?

Absolutely.
Seach algorithms have two distinct pieces to them
- Comparisons : Is this the right element? It is greater than this?
Less than this?
- What is the next element in the collection that I should compare
against.

A Linear search does a Fast Compare and a fast iteration to the next
element, but it doesn't apply any logic to reduce the number of
comparisons required. Therefore, for small data sets, a linear search
can be the best option. For large sets, you pay the price of having to
compare agains each and every element until you find the correct one.

A Binary search against a sorted dataset has a fairly fast compare with
a slower iteration to the next element, since it needs to calculate
where it should do the next compare. This additional logic in the
algorithm means that each step in the algorithm is slower than the
linear algorithm, but it drastically reduces the number of steps
involved.Therefore the Binary search is faster when the number of
elements becomes the dominant factor.


The original question asked about the best way to find elements in a
sorted ArrayList, but I would like to bring up an alternative. Try
using a Hashtable instead. It has a higher memory footprint, but the
performance is exceptional. For completeness in this discussion I would
like to point out that Hashtable retrival is a constant time operation
O(1). I ran a quick test comparing Hashtable vs Linear search vs
BinarySearch and the results are impressive. Hashtable wins hands down
when more than a handfull of elements are involved


Bill


.

Relevant Pages

  • Re: ArrayList BinarySearch vs Contains
    ... an algorithm so that it becomes worse than a linear search. ... A Linear search does a Fast Compare and a fast iteration to the next ... drastically reduces the number of steps involved.Therefore the Binary search ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Parallel application ran more slowly than the sequential one?
    ... > Could you tell me what are the reasons to make an parallel application ... Your parallel algorithm may be less efficient than your serial algorithm. ... loading/unloading MPI data structures, sharing files over NFS, process ... Compare the runtime of your parallel program to ...
    (comp.parallel)
  • Re: count of each word occurred
    ... > take each word in order and compare it with the rest of the list ... Another version of this algorithm takes advantage of the fact that it does ... loop over all words in the list ... a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Reading and writing a big file in Ada (GNAT) on Windows XP
    ... common cases (no mapping, single character patterns, and so on). ... block move and compare instructions because they fouled up the pipeline and ... So in this case a better algorithm is probably the way to go (and I ... the source length is>M and the pattern length is>N, ...
    (comp.lang.ada)
  • Re: Search algorithm to use
    ... > One comparison suffices if you use a sentinel. ... The linear search needs an increment. ... > binary search which is just about a wash. ... compare was "expensive" relative to other operations. ...
    (comp.lang.c)