Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Wanna make a program....
Index -> General Programming
Goto page Previous  1, 2
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
codemage




PostPosted: Fri Dec 09, 2005 1:12 pm   Post subject: (No subject)

Binary search is blazingly fast in every language, including turing.

If an extra few cycles mean that much to you, you can use a better method in Turing. The trinary sort isn't much more complex than binary, and will cut down your log2N search time to log3N. Rolling Eyes
Sponsor
Sponsor
Sponsor
sponsor
bugzpodder




PostPosted: Fri Dec 09, 2005 9:31 pm   Post subject: (No subject)

GlobeTrotter wrote:
Why not do a binary search?


lets say you look up word "abracadabra" in the dictionary. Would you flip to the middle of the dictionary, then check if the middle word is 'abracadabra', if not, then look in the first half and repeat the process?

no you wouldnt. you would instead flip to the really beginning of the dictionary, and check! so, no, you shouldnt use binary search in this case.
bugzpodder




PostPosted: Fri Dec 09, 2005 9:34 pm   Post subject: (No subject)

Cornflake wrote:
The problem is that there are more then 100000 words that realisitcally would be in a dictionary. Storing them all in memory would be impossible, as would be a binary search tree (as you'd still need them in memory). The best you coudld do is some sort of hash based lookup table with pointers to the correct location in the database file.


binary search tree can be represented in a tight array. 100000 strings isnt that big of a deal. thats merely a couple of MB of RAM, hardly comparable to machines with GBs of ram. Assuming you are talking about english words, which has average length <10.
bugzpodder




PostPosted: Fri Dec 09, 2005 9:36 pm   Post subject: (No subject)

codemage wrote:
Binary search is blazingly fast in every language, including turing.

If an extra few cycles mean that much to you, you can use a better method in Turing. The trinary sort isn't much more complex than binary, and will cut down your log2N search time to log3N. Rolling Eyes


trinary sort? first of all, sorting takes O(N) time (you need to look at each element once). if you mean "trinary search", i dont think it is possible or that it even exists. but i might be wrong. for starters, why dont u tell me what this "trinary sort" is? i dont see how you can consistently cut down the array by 2/3 each term hence achieving log3N time.
codemage




PostPosted: Mon Dec 12, 2005 10:10 am   Post subject: (No subject)

Freudian slip there.

Referring to the searching algorithm. Trinary search. Trinary search is similar to binary, except it cuts the target group in thirds, instead of in half.

I have the code kicking around somewhere... I'll post it if I can find it.

Re - searching: if you're using a logN type search like binary, if your dictionary is 1 million words long, you're only spending 20 operations to find the word. There's not going to be a humanly noticeable difference between that and a more efficient search algorithm - if everything is stored in a form of quick-access memory.

EDIT: Trinary looks more or less like this:
I won't put the whole test case, 'cuz this isn't the turing source section...

code:
loop
    lowmid := low + ((high - low) div 3)
    highmid := high - ((high - low) div 3)

    counter := counter + 1

    if sortedarray (lowmid) = target then
        put "found it in ", counter, " tries."
        put "@ location ", lowmid
        exit

    elsif sortedarray (highmid) = target then
        put "found it in ", counter, " tries."
        put "@ location ", highmid
        exit

    elsif sortedarray (lowmid) > target then
        high := lowmid - 1

    elsif sortedarray (highmid) < target then
        low := highmid + 1

    else
        high := highmid - 1
        low := lowmid + 1

    end if
end loop
bugzpodder




PostPosted: Mon Dec 12, 2005 6:16 pm   Post subject: (No subject)

However, if you for some reason need to perform a million of these operations every minute, which would be better? 3 million or 20 million? if you could do it faster, why not? As I said, as humans you wouldnt want to start searching for english words in a dictionary from middle, would you? you'd definitely start from beginning. this is because we know the data is uniformly distributed and we can take advantage of this to obtain faster times. so why not let our algorithm do that? this is called interpolation search (TAOCP V2, Knuth, p419). This takes log log N time rather than log N with uniform data.

trinary search maybe be only slightly faster than binary search. You think that its log3N, but clearly we are doing more work per iteration. We are doing up to 5 extra steps per iteration. each binary search does about 3 steps.

so each three iteration of trinary seach corresponds to about five iterations of binary search. thats (1/3)^3=1/27 and (1/2)^5=1/32
can you see which one is better now?
McKenzie




PostPosted: Tue Dec 13, 2005 9:29 pm   Post subject: (No subject)

I'd use VB. VB allows you to access Access databases very simply. All you would need is a simple SQL statement to find the record. If you insist on doing it by hand I'd use a Hash table.
wtd




PostPosted: Tue Dec 13, 2005 9:51 pm   Post subject: (No subject)

McKenzie wrote:
I'd use VB. VB allows you to access Access databases very simply. All you would need is a simple SQL statement to find the record. If you insist on doing it by hand I'd use a Hash table.


Many languages make it easy to deal with databases, and databases other than Access. Smile
Sponsor
Sponsor
Sponsor
sponsor
md




PostPosted: Wed Dec 14, 2005 2:33 pm   Post subject: (No subject)

McKenzie wrote:
I'd use VB. VB allows you to access Access databases very simply. All you would need is a simple SQL statement to find the record. If you insist on doing it by hand I'd use a Hash table.


Or you could use any number of languages and SQLite; as wtd pointed out there are any number of databases for any number of lanuages.
McKenzie




PostPosted: Wed Dec 14, 2005 9:25 pm   Post subject: (No subject)

Of course, but what was being lost in the argument over which search algorithm is the most efficient was the fact that the original poster was not some programming guru. He asked for simple. VB is simple. It's not limited to Access Databases, that was just an example.
Martin




PostPosted: Thu Dec 15, 2005 3:29 am   Post subject: (No subject)

McKenzie wrote:
Of course, but what was being lost in the argument over which search algorithm is the most efficient was the fact that the original poster was not some programming guru. He asked for simple. VB is simple. It's not limited to Access Databases, that was just an example.


Good point. The problem with programmers eh?

Visual Basic Express can be downloaded here: http://msdn.microsoft.com/vstudio/express/vb/default.aspx
rizzix




PostPosted: Thu Dec 15, 2005 10:20 am   Post subject: (No subject)

McKenzie wrote:
Of course, but what was being lost in the argument over which search algorithm is the most efficient was the fact that the original poster was not some programming guru. He asked for simple. VB is simple. It's not limited to Access Databases, that was just an example.
I believe Java is much easier than VB when it comes to database programming -- JDBC
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 2 of 2  [ 27 Posts ]
Goto page Previous  1, 2
Jump to:   


Style:  
Search: