matching problem

            Multiple Producers and Consumers

A. First Edition
This is a small simulation of one particular algorithm in my project.
Actually this is the second version after I fixed a few bugs. 
Regarding the simulation experiment, I fixed a few mistakes and now the result is bit of frustrating.
The most intuitive, straight-forward, greedy algorithm gives only less than 5% as good result as the heuristic, greedy algorithms I described in my previous report. (See below) Therefore the conclusion is that for such kind of NP-complete problem, the best strategy is the simplest, straight-forward, greedy algorithm without any preprocessing at all. This seems I was working for several days for nothing. But it is better for me to implement this in cluster and then find out it is good for nothing.
 
 
 
heuristic result:
the average extra ratio=0.010008, average original ratio=0.727222
non-heuristic, straight-forward, greedy result:
the average extra ratio=0.056072, average original ratio=0.725108
 


B.The problem
		No Strategy is the Best Strategy (see above)

First let¡¯s describe the problem.

Given m number of testers and n number of tiles, for each tile we must choose one tester to compute the ¡°visible pixel information¡± data and sends out to renders and displayer.

 

This is a typical ¡°matching¡± problem which is a NP-complete problem. In order to easily understand the question, let me use a simple example of everyday life for metaphor when number of testers and tiles are equal.

 

Suppose there are N boys(testers) and N girls(tiles) and each boy knows some subset of those N girls. If we want each boy to marry exactly one girl such that he already knows, then it is exactly our problem of testers and tiles.

Please note that such solution may not exist. i.e. You can find N matching of boy and girls such that the boy already knows the girl. In this case, we have to make some matching such that the boy doesn¡¯t know the girl. Now it comes our second optional goal. If we have to make such matching pairs, we prefer to the boy who know less girls because he already has too few choices of girls. The rational in our case is that for each tile(girl), there are some associated testers and if we need to add an extra tester we want to add it to those tiles with less testers so that the exchange processes take roughly similar time compared with tiles involved more testers.

 

As mentioned above, there may not exist a solution such that we don¡¯t have to introduce extra ¡°tester¡±. So, it is not worthwhile to do a ¡°brute-force¡± ¡°depth-first-search¡± etc. A greedy algorithm is good enough for an approximate solution. The question is what strategy do we take to find heuristic solution?

 

  1. Which tile to start?

a)      Starting from tiles with least testers? Usually this gives you better chances to find the solution if it exists because there is less chances to make wrong choices. But is it good for our ¡°optional goal¡± such that when solution doesn¡¯t exist we want to add ¡°extra¡± tester to those tiles with less testers? Obviously not!

b)      Therefore we should start with tiles of most testers.

  1. Within the tile which tester do we choose?

a)      Starting from tester tile with least occurrences in other tiles? Like argument in 1, it has a better chance to find you a solution if it exists. However, does it also give a good chance to satisfy our ¡°optional goal¡± when solution doesn¡¯t exist? I think yes because we have a better chance that tiles with more testers will guarantee no extra tester needs to be introduced. Just imagine the ¡°matching¡± example above, suppose we always ask the girl to pick up her boy friend who has the least popularity with other girls, we will reserve the most popular boy for the girl who knows less boys.

b)      What if we simply pick up the tester which is produced by our current algorithm? Our current algorithm calculates a tester with so-called ¡°smallest¡± range of depth in its depth buffer. Is it convenient for us to stick to our old algorithm as much as possible? I think it won¡¯t make much difference because the above heuristic strategy gives no guarantee of finding solutions or satisfy our optional goals. And the algorithm itself introduce some preprocess overhead like sorting the tiles by its size of testers, sorting testers by its occurrence among tiles. So, if we are doomed to find only an approximate solution, then why not just use a simple strategy?

 

Enclosed please find a simulate program to test the strategy above, it doesn¡¯t shows comparison with other strategy. Instead it only shows it always gives a approximate solution and how good is the solution. The definition of ¡°good¡± here means how many ¡°extra¡± testers are introduced if we simply pick up our original tester choice from our current algorithm.

 

I run my testing program for about 1000 runs and the average ¡°original¡± choice percentage is more than 70% and the average ¡°extra¡± percentage is less than 3%. The ¡°original¡± raitio means my algorithm produces a solution which contains 70% of ¡°original¡± testers which is chosen by our current ¡°smallest¡± tester. The ¡°extra¡± ratio means that my algorithm has to introduce a new tester for the tile.

 

¡¡

C.The idea of program

D.The major functions
E.Further improvement
F.File listing
1. binaryExchange.cpp
2. matching.h
3. matching.cpp
¡¡
¡¡
file name: binaryExchange.cpp
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "matching.h"



struct BinaryDesc
{
	int total;
	int *array;
	int myIndex;
};

int roundCount;


void recvFrom(int me, int from)
{
	printf("me%d will receive from %d\n", me, from);
}

void sendTo(int me, int to)
{
	printf("me%d will send to %d\n", me, to);
}


void doBinary(const BinaryDesc* desc)
{
	int i;
	BinaryDesc myDesc;
	if (desc->total==1)
	{
		printf("finished and last one is %d\n", desc->array[0]);
		return;
	}
	else
	{
		printf("after %d round\n", ++roundCount);
	}
	if (desc->myIndex%2==0)
	{
		//i may have to receive
		
		if (desc->myIndex+1<desc->total)
		{
			recvFrom(desc->array[desc->myIndex], desc->array[desc->myIndex+1]);
		}
		else
		{
			printf("me%d is idle in this round\n", desc->array[desc->myIndex]);
		}
		//in any case I will do this
		myDesc.total=(desc->total+1)/2;
		myDesc.array=new int[myDesc.total];
		for (i=0; i<myDesc.total; i++)
		{
			myDesc.array[i]=desc->array[2*i];
		}
		myDesc.myIndex=desc->myIndex/2;
		doBinary(&myDesc);
		delete[]myDesc.array;
	}
	else
	{
		//i always have to send
		sendTo(desc->array[desc->myIndex], desc->array[desc->myIndex-1]);
		//then I quit;
	}
}


void binaryTest()
{
	BinaryDesc desc;
	int i, last=0;
	desc.total=12;
	desc.array=new int[desc.total];
	printf("the array is:\n");
	for (i=0; i<desc.total; i++)
	{
		desc.array[i]=last+rand()%3+1;
		last=desc.array[i];
		printf("[%d]", desc.array[i]);
	}
	printf("\nand now let's do one by one\n");
	for (i=0; i<desc.total; i++)
	{
		printf("\n******************\nfor index =%d\n", i);
		roundCount=0;
		desc.myIndex=i;
		doBinary(&desc);
	}
	delete[]desc.array;
}

const int TotalTestNumber=1000;
float totalExtraRatio=0;
float totalOriginalRatio=0;

extern float extraCountRatio;
extern float originalCountRatio;

void testMatching()
{
	try
	{
		initTesterDistribution();
	}
	catch (...)
	{
		printf("init problem\n");
		exit(5);
	}
	try
	{		
		//showTesterDistribution();		
	}
	catch (...)
	{
		printf("before process and inside show\n");
		exit(2);
	}
	prepTesterDistribution();
	try
	{
		procTesterDistribution2();
	}
	catch (...)
	{
		printf("process\n");
		exit(4);
	}
	showTesterDistribution();
	uninitTesterDistribution();
	totalExtraRatio+=extraCountRatio;
    totalOriginalRatio+=originalCountRatio;
}


void testMatching2()
{
	try
	{
		initTesterDistribution();
	}
	catch (...)
	{
		printf("init problem\n");
		exit(5);
	}
	try
	{		
		//showTesterDistribution();		
	}
	catch (...)
	{
		printf("before process and inside show\n");
		exit(2);
	}
	//prepTesterDistribution();
	try
	{
		procTesterDistribution3();
	}
	catch (...)
	{
		printf("process\n");
		exit(4);
	}
	showTesterDistribution();
	uninitTesterDistribution();
	totalExtraRatio+=extraCountRatio;
    totalOriginalRatio+=originalCountRatio;
}

int main()
{
	srand(time(0));
	//srand(118);
	for (int i=0; i<TotalTestNumber; i++)
	{
		testMatching2();
	}
	printf("the average extra ratio=%f, average original ratio=%f\n", 
		totalExtraRatio/(float)TotalTestNumber,
		totalOriginalRatio/(float)TotalTestNumber);
	return 0;
}



file name: matching.h


//const int TesterCount=10;
//const int TileCount=64;


const int MaxTesterCount=30;
const int MaxTileCount=40;




struct TesterDesc
{
	int index;
	int occurCount;
	int chosenCount;
	int originalCount;
	int tileCount;
	//int tiles[TileCount];//the index of tile chosen to
	int* tiles;//the index of tile chosen to
	//static int priority[TesterCount];
	static int* priority;

};

struct TileDesc
{
	bool internal;
	int original;
	int index;
	int chosenIndex;
	int testerCount;	
	//int testers[TesterCount];
	int* testers;
	//static int priority[TileCount];
	static int* priority;
	static int AverageTesterCountPerTile;
	static int totalChosen;
};


void initTesterDistribution();
void uninitTesterDistribution();
void prepTesterDistribution();
void procTesterDistribution();
void procTesterDistribution2();
void procTesterDistribution3();

void showTesterDistribution();
file name: matching.cpp


#include "matching.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define USING_ORIGINAL 1

//int TesterDesc::priority[TesterCount];
//int TileDesc::priority[TileCount];
int TesterCount=10;
int TileCount=64;


int* TesterDesc::priority;
int* TileDesc::priority;

//the ceiling
int TileDesc::AverageTesterCountPerTile=(TileCount/TesterCount==0)?1:TileCount/TesterCount;
int TileDesc::totalChosen=0;
//(TileCount+TesterCount-1)/TesterCount;

/*
int testerDistribution[TesterCount][TileCount];
int testerDistriCount[TileCount];
int tilePriority[TileCount];//the index of tile sorted by number of tester

int testerOccurCount[TesterCount];//
int testerPriority[TesterCount];//the index of tester sorted by occurrance number
*/

//TesterDesc testerDescArray[TesterCount];
//TileDesc tileDescArray[TileCount];

TesterDesc* testerDescArray;
TileDesc* tileDescArray;

//the result 


void initTesterDistribution()
{
	int originalIndex;
	int i, j, k, number;
	bool isOK;
	try
	{	
		TileCount=rand()%MaxTileCount+1;
		//TileCount=1;
		TesterCount=rand()%MaxTesterCount+1;
		//TesterCount=20;
		TileDesc::AverageTesterCountPerTile=(TileCount/TesterCount==0)?1:TileCount/TesterCount;

		testerDescArray=new TesterDesc[TesterCount];
		tileDescArray=new TileDesc[TileCount];
		TileDesc::priority=new int[TileCount];
		TesterDesc::priority=new int[TesterCount];
		assert(testerDescArray);
		assert(tileDescArray);
		assert(TileDesc::priority);
		assert(TesterDesc::priority);
		TileDesc::totalChosen=0;

		//init tester desc
		for (i=0; i<TesterCount; i++)
		{
			testerDescArray[i].index=i;
			TesterDesc::priority[i]=i;
			testerDescArray[i].tiles=new int[TileCount];
			assert(testerDescArray[i].tiles);
			testerDescArray[i].tileCount=0;
			testerDescArray[i].originalCount=0;
			testerDescArray[i].occurCount=testerDescArray[i].chosenCount=0;
		}
	}
	catch (...)
	{
		printf("tester init\n");
		exit(6);
	}


	try
	{
		//init tile desc
		for (i=0; i<TileCount; i++)
		{
			tileDescArray[i].index=i;
			TileDesc::priority[i]=i;
			tileDescArray[i].chosenIndex=-1;
			tileDescArray[i].internal=false;
			tileDescArray[i].testers=new int[TesterCount];
			assert(tileDescArray[i].testers);

			tileDescArray[i].testerCount=rand()%TesterCount+1;
			try
			{
				for (j=0; j<tileDescArray[i].testerCount; j++)
				{		
					//we need to random allocate tester index for testerCount times
					do
					{
						isOK=true;
						number=rand()%TesterCount;

						//check if it is used
						for (k=0; k<j; k++)
						{
							if (number==tileDescArray[i].testers[k])
							{
								isOK=false;
								break;
							}
						}
					}
					while (!isOK);
					tileDescArray[i].testers[j]=number;
					testerDescArray[number].tiles[testerDescArray[number].tileCount]=i;
					testerDescArray[number].tileCount++;
					testerDescArray[number].occurCount++;
				}
			}
			catch(...)
			{
				printf("loop\n");
			}
			try
			{
				originalIndex=rand()%tileDescArray[i].testerCount;
				tileDescArray[i].original=tileDescArray[i].testers[originalIndex];
				testerDescArray[tileDescArray[i].original].originalCount++;
			}
			catch(...)
			{
				printf("what?\n");
			}
		}
	}
	catch(...)
	{
		printf("tile init\n");
		exit(7);
	}
}

//tester sorted by its occurrance
int sortTester(const void* first, const void* second)
{
	return testerDescArray[*((int*)first)].tileCount-testerDescArray[*((int*)second)].tileCount;
}


int sortTile(const void* first, const void* second)
{
	return tileDescArray[*((int*)first)].testerCount-tileDescArray[*((int*)second)].testerCount;
}


void prepTesterDistribution()
{
	try
	{
		if (TileCount>1)
		{
			qsort(TesterDesc::priority, TesterCount, sizeof(int), sortTester);
		}
		if (TesterCount>1)
		{
			qsort(TileDesc::priority, TileCount, sizeof(int), sortTile);
		}
	}
	catch(...)
	{
		printf("prep\n");
		exit(1);
	}
}


void procTesterDistribution()
{
	int i, j, tileIndex, smallest, testerIndex;//, chosenIndex;
	int total;
	try
	{
		for (i=0; i<TileCount; i++)
		{
			//by sequence of priority, that is, the length is from short to long
			tileIndex=TileDesc::priority[i];
			smallest=-1;
			testerIndex=-1;
			//find the tester with smallest length
			for (j=0; j<tileDescArray[tileIndex].testerCount; j++)
			{
				testerIndex=tileDescArray[tileIndex].testers[j];
				if (smallest<testerDescArray[testerIndex].occurCount&&
					testerDescArray[testerIndex].chosenCount<TileDesc::AverageTesterCountPerTile)
				{
					smallest=testerDescArray[testerIndex].occurCount;
					tileDescArray[tileIndex].chosenIndex=testerIndex;
				}
				testerDescArray[testerIndex].occurCount--;
			}
			//check if it is smaller than average, if yes it is chosen
			if (smallest!=-1&&smallest<TileDesc::AverageTesterCountPerTile)
			{
				testerDescArray[tileDescArray[tileIndex].chosenIndex].chosenCount++;
				//tileDescArray[tileIndex].testerIndex=chosenIndex;
			}
			else
			{
				//now we need to pickup one tester with highest priority			
				tileDescArray[tileIndex].chosenIndex=-1;
				total=0;
				for (j=0; j<TesterCount; j++)
				{
					testerIndex=TesterDesc::priority[j];
					if (testerDescArray[testerIndex].chosenCount<TileDesc::AverageTesterCountPerTile)
					{
						//find it
						tileDescArray[tileIndex].chosenIndex=testerIndex;
						testerDescArray[testerIndex].chosenCount++;
						break;
					}
					total+=testerDescArray[testerIndex].chosenCount;
				}
				//this means all tester reaches average, but we need to take care the "remainder"
				//we simply choose among tester who just reaches average
				if (tileDescArray[tileIndex].chosenIndex==-1)
				{
					for (j=0; j<tileDescArray[tileIndex].testerCount; j++)
					{
						testerIndex=tileDescArray[tileIndex].testers[j];
						if (testerDescArray[testerIndex].chosenCount==TileDesc::AverageTesterCountPerTile)
						{
							tileDescArray[tileIndex].chosenIndex=testerIndex;
							testerDescArray[testerIndex].chosenCount++;
							
							break;
						}
					}
				}
				//this means all tester in this particular tile reaches just "above" average
				//then we just pick any one who is just reach average
				if (tileDescArray[tileIndex].chosenIndex==-1)
				{
					for (j=0; j<TesterCount; j++)
					{
						testerIndex=TesterDesc::priority[j];
						if (testerDescArray[testerIndex].chosenCount==TileDesc::AverageTesterCountPerTile)
						{
							tileDescArray[tileIndex].chosenIndex=testerIndex;
							testerDescArray[testerIndex].chosenCount++;
							break;
						}
					}
				}
				if (tileDescArray[tileIndex].chosenIndex==-1)
				{
					printf("error\n");
					exit(1);
				}
			}
			for (j=0; j<tileDescArray[tileIndex].testerCount; j++)
			{
				if (tileDescArray[tileIndex].chosenIndex==tileDescArray[tileIndex].testers[j])
				{
					tileDescArray[tileIndex].internal=true;
				}
			}
		}
	}
	catch(...)
	{
		printf("process here\n");
	}
}


void procTesterDistribution2()
{
	int i, j, tileIndex, smallest, testerIndex;//, chosenIndex;
	try
	{
		for (i=0; i<TileCount; i++)
		{
			//by sequence of priority, that is, the length is from short to long
			tileIndex=TileDesc::priority[i];
			smallest=-1;
			testerIndex=-1;
			//find the tester with smallest length
			tileDescArray[tileIndex].chosenIndex=-1;
#ifndef USING_ORIGINAL
			for (j=0; j<tileDescArray[tileIndex].testerCount; j++)
			{
				testerIndex=tileDescArray[tileIndex].testers[j];
				if (smallest<testerDescArray[testerIndex].occurCount&&
					testerDescArray[testerIndex].chosenCount<TileDesc::AverageTesterCountPerTile)
				{
					smallest=testerDescArray[testerIndex].occurCount;
					tileDescArray[tileIndex].chosenIndex=testerIndex;
				}
				testerDescArray[testerIndex].occurCount--;
			}
#else
			testerIndex=tileDescArray[tileIndex].original;
			if (testerDescArray[testerIndex].chosenCount<TileDesc::AverageTesterCountPerTile)
			{
				tileDescArray[tileIndex].chosenIndex=testerIndex;
				//testerDescArray[testerIndex].chosenCount++;
			}
#endif
			//check if it is smaller than average, if yes it is chosen
			if (tileDescArray[tileIndex].chosenIndex!=-1)
			{
				testerDescArray[tileDescArray[tileIndex].chosenIndex].chosenCount++;
				
				//tileDescArray[tileIndex].testerIndex=chosenIndex;
			}
			else
			{
				//now we need to pickup one tester with highest priority			
				if (TileDesc::totalChosen>=TileDesc::AverageTesterCountPerTile*TesterCount)
				{
					testerIndex=tileDescArray[tileIndex].original;
					if (testerDescArray[testerIndex].chosenCount==TileDesc::AverageTesterCountPerTile)
					{
						tileDescArray[tileIndex].chosenIndex=testerIndex;
						testerDescArray[testerIndex].chosenCount++;		
					}
					if (tileDescArray[tileIndex].chosenIndex==-1)
					{
						for (j=0; j<tileDescArray[tileIndex].testerCount; j++)
						{
							testerIndex=tileDescArray[tileIndex].testers[j];
							if (testerDescArray[testerIndex].chosenCount==TileDesc::AverageTesterCountPerTile)
							{
								tileDescArray[tileIndex].chosenIndex=testerIndex;
								testerDescArray[testerIndex].chosenCount++;						
								break;
							}
						}
					}
					if (tileDescArray[tileIndex].chosenIndex==-1)
					{
						for (j=0; j<TesterCount; j++)
						{
							testerIndex=TesterDesc::priority[j];
							if (testerDescArray[testerIndex].chosenCount==TileDesc::AverageTesterCountPerTile)
							{
								tileDescArray[tileIndex].chosenIndex=testerIndex;
								testerDescArray[testerIndex].chosenCount++;							
								break;
							}
						}
					}
				}
				else
				{
					for (j=0; j<tileDescArray[tileIndex].testerCount; j++)
					{
						testerIndex=tileDescArray[tileIndex].testers[j];
						if (testerDescArray[testerIndex].chosenCount<TileDesc::AverageTesterCountPerTile)
						{
							tileDescArray[tileIndex].chosenIndex=testerIndex;
							testerDescArray[testerIndex].chosenCount++;						
							break;
						}
					}
				
					if (tileDescArray[tileIndex].chosenIndex==-1)
					{
						for (j=0; j<TesterCount; j++)
						{
							testerIndex=TesterDesc::priority[j];
							if (testerDescArray[testerIndex].chosenCount<
								TileDesc::AverageTesterCountPerTile)
							{
								//find it
								tileDescArray[tileIndex].chosenIndex=testerIndex;
								testerDescArray[testerIndex].chosenCount++;
								break;
							}
						}
						
					}
				}

				if (tileDescArray[tileIndex].chosenIndex==-1)
				{
					printf("error\n");
					exit(1);
				}
			}
			for (j=0; j<tileDescArray[tileIndex].testerCount; j++)
			{
				if (tileDescArray[tileIndex].chosenIndex==tileDescArray[tileIndex].testers[j])
				{
					tileDescArray[tileIndex].internal=true;
				}
			}
			
			TileDesc::totalChosen++;
		}
	}
	catch(...)
	{
		printf("process\n");
	}

}


void procTesterDistribution3()
{
	int i, j, tileIndex, smallest, testerIndex;//, chosenIndex;
	try
	{
		for (i=0; i<TileCount; i++)
		{
			//by sequence of priority, that is, the length is from short to long
			tileIndex=i;
			smallest=-1;
			testerIndex=-1;
			//find the tester with smallest length
			tileDescArray[tileIndex].chosenIndex=-1;

			testerIndex=tileDescArray[tileIndex].original;

			if (testerDescArray[testerIndex].chosenCount<TileDesc::AverageTesterCountPerTile)
			{
				tileDescArray[tileIndex].chosenIndex=testerIndex;
				//testerDescArray[testerIndex].chosenCount++;
			}

			//check if it is smaller than average, if yes it is chosen
			if (tileDescArray[tileIndex].chosenIndex!=-1)
			{
				testerDescArray[tileDescArray[tileIndex].chosenIndex].chosenCount++;
				
				//tileDescArray[tileIndex].testerIndex=chosenIndex;
			}
			else
			{
				
				//now we need to pickup one tester with highest priority			
				if (TileDesc::totalChosen>=TileDesc::AverageTesterCountPerTile*TesterCount)
				{
					//give priority to original
					testerIndex=tileDescArray[tileIndex].original;
					if (testerDescArray[testerIndex].chosenCount==TileDesc::AverageTesterCountPerTile)
					{
						tileDescArray[tileIndex].chosenIndex=testerIndex;
						testerDescArray[testerIndex].chosenCount++;		
					}
					else
					{						
						//now try testers within tile
						//now we just pick up those with chosenCount just reaching average					
						for (j=0; j<tileDescArray[tileIndex].testerCount; j++)
						{
							testerIndex=tileDescArray[tileIndex].testers[j];
							if (testerDescArray[testerIndex].chosenCount==TileDesc::AverageTesterCountPerTile)
							{
								tileDescArray[tileIndex].chosenIndex=testerIndex;
								testerDescArray[testerIndex].chosenCount++;							
								break;
							}
						}
						//now try all testers
						if (tileDescArray[tileIndex].chosenIndex==-1)
						{
							for (j=0; j<TesterCount; j++)
							{
								testerIndex=j;
								if (testerDescArray[testerIndex].chosenCount==
									TileDesc::AverageTesterCountPerTile)
								{
									//find it
									tileDescArray[tileIndex].chosenIndex=testerIndex;
									testerDescArray[testerIndex].chosenCount++;
									break;
								}
							}
						}	
					}
				}
				else
				{
					//first we just pick up any tester in that tile with smaller chosenCount
					for (j=0; j<tileDescArray[tileIndex].testerCount; j++)
					{
						testerIndex=tileDescArray[tileIndex].testers[j];
						if (testerDescArray[testerIndex].chosenCount<TileDesc::AverageTesterCountPerTile)
						{
							tileDescArray[tileIndex].chosenIndex=testerIndex;
							testerDescArray[testerIndex].chosenCount++;						
							break;
						}
					}
					//then we have to pick up from any tester with chosenCount smaller than average
					if (tileDescArray[tileIndex].chosenIndex==-1)
					{
						for (j=0; j<TesterCount; j++)
						{
							testerIndex=j;
							if (testerDescArray[testerIndex].chosenCount<
								TileDesc::AverageTesterCountPerTile)
							{
								//find it
								tileDescArray[tileIndex].chosenIndex=testerIndex;
								testerDescArray[testerIndex].chosenCount++;
								break;
							}
						}
					}
				}			
				
		
				if (tileDescArray[tileIndex].chosenIndex==-1)
				{
					printf("error\n");
					exit(1);
				}
			}
			for (j=0; j<tileDescArray[tileIndex].testerCount; j++)
			{
				if (tileDescArray[tileIndex].chosenIndex==tileDescArray[tileIndex].testers[j])
				{
					tileDescArray[tileIndex].internal=true;
				}
			}
			
			TileDesc::totalChosen++;
		}
	}
	catch(...)
	{
		printf("process\n");
	}

}

int extraCount=0;
int originalCount=0;
float extraCountRatio;
float originalCountRatio;
void showTesterDistribution()
{
	int i, j;
	extraCount=0;
	originalCount=0;
	extraCountRatio=0;
	originalCountRatio=0;
	for (i=0; i<TileCount; i++)
	{
		printf("tile#%d:", i);
		for (j=0; j<tileDescArray[i].testerCount; j++)
		{
			printf("[%d],", tileDescArray[i].testers[j]);
		}
		if (!tileDescArray[i].internal)
		{
			printf("{extra}");
			extraCount++;
		}	
		printf("\nchosen[%d], original[%d]", tileDescArray[i].chosenIndex, 
			tileDescArray[i].original);
		if (tileDescArray[i].original==tileDescArray[i].chosenIndex)
		{
			originalCount++;
		}
	
		printf("\n");
	}

	extraCountRatio=(float)(extraCount)/(float)(TileCount);
	originalCountRatio=(float)originalCount/(float)(TileCount);
	printf("\nextraCount=%d, ratio=%f, originalCount=%d, ratio=%f\n", extraCount, 
		extraCountRatio, originalCount, originalCountRatio);

	printf("\n*********************************\n");
	for (i=0; i<TesterCount; i++)
	{
		printf("\ntester#%d:tileCount=%d, chosenCount=%d, originalCount=%d\n", i, 
			testerDescArray[i].tileCount, testerDescArray[i].chosenCount, 
			testerDescArray[i].originalCount);
	}
}

void uninitTesterDistribution()
{
	int i;
	for (i=0; i<TileCount; i++)
	{
		delete[]tileDescArray[i].testers;	
	}
	delete[]tileDescArray;
	delete[]TileDesc::priority;


	for (i=0; i<TesterCount; i++)
	{
		delete[]testerDescArray[i].tiles;	
	}

	delete[]testerDescArray;
	delete[]TesterDesc::priority;
}




		


The result is like this:
tile#0:[3],{extra}
chosen[0], original[3]
tile#1:[3],[1],[2],[5],[0],
chosen[0], original[0]
tile#2:[4],[5],[1],
chosen[1], original[1]
tile#3:[3],[2],
chosen[3], original[3]
tile#4:[3],{extra}
chosen[4], original[3]
tile#5:[5],[3],
chosen[5], original[5]
tile#6:[4],[2],[3],[0],[5],[1],
chosen[2], original[2]
tile#7:[0],[5],[4],[3],[1],[2],
chosen[4], original[4]
tile#8:[0],[5],[1],[2],
chosen[5], original[5]
tile#9:[2],[3],[1],[4],[5],[0],
chosen[3], original[2]
tile#10:[1],
chosen[1], original[1]

extraCount=2, ratio=0.181818, originalCount=8, ratio=0.727273

*********************************

tester#0:tileCount=5, chosenCount=2, originalCount=1

tester#1:tileCount=7, chosenCount=2, originalCount=2

tester#2:tileCount=6, chosenCount=1, originalCount=2

tester#3:tileCount=8, chosenCount=2, originalCount=3

tester#4:tileCount=4, chosenCount=2, originalCount=1

tester#5:tileCount=7, chosenCount=2, originalCount=2
tile#0:[1],[0],[4],[6],
chosen[4], original[4]
tile#1:[0],[2],[4],[6],[5],[3],
chosen[5], original[5]
tile#2:[4],[2],
chosen[2], original[2]
tile#3:[5],
chosen[5], original[5]
tile#4:[1],[6],[2],
chosen[1], original[1]
tile#5:[1],[0],[5],
chosen[0], original[1]
tile#6:[5],[0],[3],[2],[6],
chosen[5], original[3]
tile#7:[0],
chosen[0], original[0]
tile#8:[5],{extra}
chosen[6], original[5]
tile#9:[3],[2],[0],[4],[5],[1],[6],
chosen[3], original[3]
tile#10:[6],[5],[0],[2],[3],[4],
chosen[3], original[3]
tile#11:[4],[2],[3],[1],[6],
chosen[1], original[1]
tile#12:[4],[2],[3],
chosen[4], original[3]
tile#13:[1],[6],[3],
chosen[6], original[3]
tile#14:[0],[2],[3],[5],[6],
chosen[0], original[3]

extraCount=1, ratio=0.066667, originalCount=9, ratio=0.600000

*********************************

tester#0:tileCount=8, chosenCount=3, originalCount=1

tester#1:tileCount=6, chosenCount=2, originalCount=3

tester#2:tileCount=9, chosenCount=1, originalCount=1

tester#3:tileCount=8, chosenCount=2, originalCount=6

tester#4:tileCount=7, chosenCount=2, originalCount=1

tester#5:tileCount=8, chosenCount=3, originalCount=3

tester#6:tileCount=9, chosenCount=2, originalCount=0


¡¡


¡¡


¡¡












                                                               
                      







                       back.gif (341 bytes)       

up.gif (335 bytes)                                       
next.gif (337 bytes)