Author: Robert Hyatt
Date: 06:40:24 06/25/00
Go up one level in this thread
On June 25, 2000 at 03:27:07, blass uri wrote: >Can somebody post a C program that translates arrays to 32 bits integers when >usually different arrays get different numbers and also translates it in a way >that it is easy to find if the 32 bits integer is new? arrays to a single int is possible, but it depends on what is in the array as to how the elements might get 'hashed' together. the last requirement is very difficult to do (make it easy to find that the new hash signature has not been computed before.) > >I think that this is the idea behind hash tables > >I need it for my program that I use to solve equations and inequalities. > >I have an array possolution[256][100000] and >I need to check if the possolution[256][i] is not identical to >possolution[256][j] >for all j<i(I do i++ only if it is not identical). this is not a hashing application. When you hash, you have the possibility of a collision (two different source strings producing the same hash signature). IE hashing isn't a pattern-matching algorithm... it is almost the opposite. It compresses a large set of data into one value, although you have to then handle the case where different sets of data produce the same hash signature. > >If I can calculate the hash entry of possolution[256][i] and discover in a short >time that the hash entry of possolution[256][i] is different than the hash entry >of possolution[256][j] for j<i it will save my program a lot of time > >I need to know also how to do it in C with O(log[i]) steps and not in O(i) steps >and I know only how to do it theoretically in O(log[i]) steps but I do not know >how to do it in C because I do not know how to push an array forward(if I have >an array hash[100000] I do not know how to do for (i=35000;i<90000;i++) >hash[i]=hash[i+1] in a short time) > >Uri About the only O(logn) approach to anything is a binary algorithm. IE if your 'solutions' are sorted, then a binary search would search for a specific match in O(logn) time. If they are unsorted, and you can't stand the false matches of hashing, then you are pretty well stuck with O(n).
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.