I have a lot of short arrays(10-20 elements). What is best way(i mean speed) to found one element in each array? Binary search, tries, hashtable etc?
Asked
Active
Viewed 118 times
0
-
@Benj i can represent data in any way. – Neir0 May 10 '12 at 10:32
-
Best method would be to store it so you always put the one you're looking for at the front of the array. Problem solved. – Flexo May 10 '12 at 10:35
-
If your arrays are short, then definitely not hashtable. – Subodh May 10 '12 at 10:36
-
@awoodland I need to search different data many times. – Neir0 May 10 '12 at 10:38
-
The answer to this question - http://stackoverflow.com/questions/10524032/binary-search-efficiency-vs-linear-search-efficiency-in-fortran - may be instructive. – High Performance Mark May 10 '12 at 10:51
1 Answers
1
Measure at least three approaches:
- Linear search
- Binary search
- Hashtable
Measure them for different input sizes and choose the best method at runtime depending on the size of the array.
You could also investigate perfect hashing which trades a big upfront calculation that only needs to be done once for very fast lookup.
usr
- 168,620
- 35
- 240
- 369