"In function"

[Disruptive]

I need some advice on the quickest method of checking whether a number is contained in an array. I have an single dimension array of variable length. I need to perform a check to see if a number is contained within the array. Currently one can look through the array. However this is very time consuming. Is there a quicker way to do this? I am performing this operation many many times so speed really is important.

Any ideas?

Thanks

 

[sedj]

Binary Trees.
A POSIX standard tree API :

http://www.opengroup.org/onlinepubs/007908799/xsh/search.h.html

--------------------------------------------------
Free Java/J2EE Database Connection Pooling Software

http://www.primrose.org.uk

 

[Disruptive]

I should add the the size of this array is not always going to be very large. Around 4/5 elements most of the time.

 

[sedj]

How can you describe looping 5 elements in an array as time-consuming ? For such a piddling size array, then a binary tree search is overkill - your best bet is a 'for' loop.

--------------------------------------------------
Free Java/J2EE Database Connection Pooling Software

http://www.primrose.org.uk

 

[countdrak]

Is the array sorted? If yes, then you can do some manipulations to make it faster.

But if its not sorted, then don't bother, this is probably the fastest you can get.

Even using some manipulations the change of speed won't be noticeable at all since you have only 4-5 elements.

 

[TrojanWarBlade]

Why don't you profile your code to see if this test is causing the problems you think it is?
Often I find people think that a particular part of their code is time consuming and yet when profiled discover that actually there is another part that is far more painful and important to address.
Don't make assumptions about it, test it.
If you are right then you might need to look at embedding some assembler (if you can get away with the portability problems!)


Trojan.

 

[Disruptive]

Asssembly is what I feared. I looks like it needs to be portable, so assembly is out. I just wondered if there were any tips to speed this up.

Thanks for the suggestions guys.

 

[ArkM]

If you don't know anything about an array contents you MUST scan an array on element by element basis (if you want a platform-independent solution and it's not a char array, of course). No silver bullets for this task...

 

[Disruptive]

Hmmm, I thought as much. I am justing asking the obvious really!

 

[Salem]

> However this is very time consuming. Is there a quicker way to do this?
> I am performing this operation many many times so speed really is important.
I would suggest you just write the obvious thing and worry about performance for when you've actually finished the program (got it working), and have some meaningful real-world data to try on it.

Then (and only then) can you conduct meaningful profiling runs to tell you where the hot spots really are (rather than your guesses). Premature optimisation is a terrible disease.

Linear search - O(n/2)+K (average search time is half the array)
Binary search - O(log2)+K (assumes array is sorted)
Most texts leave off the K because it's insignificant for large n (very large n), but for smaller applications, the K for binary search is a damn sight bigger than the K for a linear search. So whilst bsearch looks good on paper, it could be slower.

--

 

[TrojanWarBlade]

Can you offer any info on the reasons for this searching?
Any sample data?
You may find that there is another way to tackle the whole issue (rather than the detail of one little loop).



Trojan.