Author: Simon Finn
Date: 07:46:30 06/26/00
Go up one level in this thread
On June 26, 2000 at 08:15:16, blass uri wrote:
>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).
At the end of this code, the first solution_count positions of solution_array
contain distinct solutions. The rest of the array contains junk.
>
>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.
The call to qsort prevents this situation from happening
after the sort, all copies of a single solution
will be adjacent to each other in the array.
Simon
>
>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.