Author: Simon Finn
Date: 07:52:52 06/26/00
Go up one level in this thread
On June 26, 2000 at 08:36:35, blass uri wrote:
>On June 26, 2000 at 08:07:02, blass uri wrote:
>
>>On June 26, 2000 at 05:47:28, Simon Finn wrote:
>>
>>>>static int compare(solution* a, solution* b)
>>>>{
>>>> int i;
>>>> for (i = 0; i < SOLUTION_SIZE; i++)
>>>> {
>>>> if (a[i] < b[i]) return -1;
>>>> if (a[i] > b[i]) return 1;
>>>
>>>Sorry - that should be:
>>> if ((*a)[i] < (*b)[i]) return -1;
>>>
>>>etc.
>>>
>>>> }
>>>> return 0;
>>
>>
>>This compare is slow because it can take SOLUTION_SIZE steps and it often takes
>>more than 1 step.
There's a trade-off.
Computing a hash-key will take SOLUTION_SIZE steps,
but you only do it once per solution.
Comparing two solutions often takes many fewer steps
(often only 1), but you do it log(n) times per solution.
If log(n) is about 20, and SOLUTION_SIZE is 256, hashing
loses unless the *average* number of steps in the comparision
is more than 10. This depends on your data, of course.
Are your solutions really that similar?
Actually, the real cost is the O(n log(n)) copy operations
in the sort, but this can be eliminated by indirection -
sorting an array of indices into the original data-structure.
>>
>>I am not interested in the question if solution a is bigger or smaller than
>>solution b but only in the question if it is different and in order to do it
>>usually quickly I need to find hash number for every solution.
Agreed. The only purpose of the sort is to bring identical solutions
together so that we can elimiate them quickly.
Simon
>
>I can add that I thought to put the hash numbers in the right array but I
>understand that I do not need to do it because I can use an array of pointers
>lasthash[1048576] that gives me for every last 20 less significant digits of the
>hash number the list of the numbers of solutions with the hash numbers that end
>with these digits and in most of the cases the pointer will give me only 0 or 1
>hash number if the number of solution is not bigger than 1000000 and I have not
>enough memory for more than 1000000 solutions if I do not compress my solutions.
>
>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.