Author: blass uri
Date: 05:15:16 06/26/00
Go up one level in this thread
On June 26, 2000 at 05:41:10, Simon Finn 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?
>>
>>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;
>}
Is the last code supposed only to count the number of solutions?(if all the
solutions are the same it removes nothiong).
If this is the case it is wrong when solution_array[0]=solution_array[2] and
solution_array[0]!=solution_array[1]
and solution_count=3.
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.