Re: searching through a set of values

Jens.Toerring_at_physik.fu-berlin.de
Date: 05/06/04 

Date: 6 May 2004 15:31:03 GMT

In comp.programming Mabden <mabden@sbcglobal.net> wrote:
> "Mike" <mikesta@hotmail.com> wrote in message
> news:80214b41.0405060704.2fd456c@posting.google.com...
>> I am kinda new to this so I was looking for some thoughts searching.
>> Just say I have a thousand values in some file. And just say I need to
>> search through that file to see if a given value is inside. I guess
>> there are many ways to do this but I wanted to look at simple
>> efficient ways.
>>
>> One way, is to loop through all values in the file one by one until I
>> find the value. Another way is to sort the values into some sought of
>> alphanumeric order and do a search where you look at the half way
>> point, and depending on the comparison, narrow the search to half the
>> file, and keep using this method to find the value more quickly.
>>
>> What other ways are there? Does it make sense to place these values in
>> a keyed file like a Berkeley DB file and use the tools native to this
>> application to so the search? I am looking for simple but effective
>> ways for getting the search done. Ideas are welcome.
>>
>> PS: I am looking to code the method in C

> Try asking over in comp.lang.c. They love answering homework questions.

No, don't do that. clc isn't for questions about algorithms, so I
removed it from the followup list.

But the question is: do you have to look for a single value in that
file or do you have to do several lookups? In the first case sorting
the values in that array won't help you at all because in order to
sort the data you already have to look at each value at least once
while when you simply scan through all values as they are in the
file you have on average only to look at halve of them. The situation
becomes different when you have to find values repeatedly, then, at
some threshold, sorting the data first will be less expensive. And
for putting the data in a hash the same holds - to create the hash
you also need to look at all the values in the file. And if using a
hash instead of a sorted array is faster for lots of lookups will
also depend on the type of data and the cost of calculating the hash
function versus the cost of doing comparisons.

                                     Regards, Jens 

-- 
  \   Jens Thoms Toerring  ___  Jens.Toerring@physik.fu-berlin.de
   \__________________________  http://www.toerring.de

Relevant Pages

  • Re: Need quick lookup like Hashtable, but dont need to store value
    ... The cost of the individual operations. ... that container will require touching all 100 characters of the target string ... in order to compute its hash. ... For a sorted array, finding a string using a binary search will take at most ...
    (microsoft.public.dotnet.framework)
  • Re: Sorting a Hash of Arrays by an Element in the Array
    ... > but since you can always sort a hash who really cares? ... ascending sort). ... as meaningful as asking for sorting a mathematical set. ... I have no idea what "sorting a HoA on an array element" is supposed to mean. ...
    (comp.lang.perl.misc)
  • Re: Sorting a text file
    ... That is certainly the constraint of using hash for sorting. ... not know how to sort hash by value, then IMHO, he ought to be ... encouraged to stick with the core of Perl for the time being. ...
    (perl.beginners)
  • Re: FAQ 4.41 How can I remove duplicate elements from a list or array?
    ... It's a hash. ... You seem to be under the very bizarre impression that "bubble sort" is ... than to introduce students to the concept of sorting. ... the problem then is in the lookup. ...
    (comp.lang.perl.misc)
  • Re: FAQ 4.41 How can I remove duplicate elements from a list or array?
    ... It's a hash. ... You seem to be under the very bizarre impression that "bubble sort" is ... than to introduce students to the concept of sorting. ... the problem then is in the lookup. ...
    (comp.lang.perl.misc)
Loading