Author: blass uri
Date: 07:15:53 06/25/00
Go up one level in this thread
On June 25, 2000 at 09:40:24, Robert Hyatt wrote: > 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). I think that I did not explain myself clearly I need to check if possolution[0][i]....possolution[255][i] is identical to possolution[0][j]...possolution[255][j] for j=0,1...i-1 hasing can help me because I know if the hash of the first sequence is a new number that that solution i is not identical to a previous solution without a lot of work. 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. The problem is not that I do not know to search in o(log n) time but how to add the new number in the right place not in O(n) time. I do not know how to do it in less than n steps and I believe that it must be possible because when chess programs add a new position to the hash tables they must put it in the right place in the hash tables(otherwise I see no way for them to search fast if the position is a new position or probably an old position) Uri
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.