Author: Simon Finn
Date: 02:41:10 06/26/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?
>
>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).
>
>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)
As Bob Hyatt mentioned, you don't need to hash to get a O(n log(n)) solution.
If you don't care about the order of the solutions in your array, all
you have to do is (approximately) the following:
#define SOLUTION_SIZE 256
typedef int[SOLUTION_SIZE] solution;
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;
}
return 0;
}
#define MAX_SOLUTIONS 100000
static solution[MAX_SOLUTIONS] solution_array;
static int solution_count;
/* Uri's code to generate solutions goes here. */
/* It should initialize solution_count to the number of */
/* solutions (<= MAX_SOLUTIONS) contained in solution_array. */
/* Sort the solutions, so that duplicates are adjacent */
qsort(solution_array, sizeof(solution), solution_count, compare);
/* Remove duplicates */
{
int i = 0, j;
for (j = 1; j < solution_count; j++)
{
if (solution_array[j] != solution_array[i])
{
i++;
if (i != j)
{
solution_array[i] = solution_array[j];
}
}
}
solution_count = i+1;
}
If you do care about the order of the solutions, add an extra field
that records the initial position of the solution in solution_array,
and add a final sort that restores the solutions to these positions.
Simon
>
>Uri
This page took 0.02 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.