using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
using System.Diagnostics;
using NGrid;
//using NGrid.Collections;
using NGrid.Threading;
interface IDistance<T>
{
double Distance(T x,T y);
}
namespace KMeanNGrid{
public class Point
{
private double[] coords;
public double[] Get()
{
return coords;
}
public void Set(double[] c)
{
coords = c;
}
public void Set0(int nb)
{
coords = new double[nb];
for (int i = 0; i < nb; i++)
coords[i] = 0;
}
public Point Add(Point p)
{
Point p2=new Point();
double[] d=p.Get();
double[] d2=new double[d.GetLength(0)];
for (int i = 0; i < d.GetLength(0); i++)
d2[i] = coords[i] + d[i];
p2.Set(d2);
return p2;
}
public Point Sub(Point p)
{
Point p2 = new Point();
double[] d = p.Get();
double[] d2 = new double[d.GetLength(0)];
for (int i = 0; i < d.GetLength(0); i++)
d2[i] = coords[i] - d[i];
p2.Set(d2);
return p2;
}
public Point Divide(double p)
{
Point p2 = new Point();
double[] d2 = new double[coords.GetLength(0)];
for (int i = 0; i < coords.GetLength(0); i++)
d2[i] = coords[i] / p;
p2.Set(d2);
return p2;
}
public Point Multiply(double p)
{
Point p2 = new Point();
double[] d2 = new double[coords.GetLength(0)];
for (int i = 0; i < coords.GetLength(0); i++)
d2[i] = coords[i] * p;
p2.Set(d2);
return p2;
}
public void Print()
{
for (int i=0;i<coords.GetLength(0)-1;i++)
System.Console.Write("{0:F};", coords[i]);
System.Console.Write("{0:F}", coords[coords.GetLength(0)-1]);
}
}
public class DimensionException : Exception
{ }
public class PointDistance : IDistance<Point>
{
private double sqr(double f)
{
return f * f;
}
public double Distance(Point X, Point Y)
{
double[] x=X.Get(),y=Y.Get();
if (x.GetLength(0) == y.GetLength(0))
{
double s=0;
for (int i = 0; i < x.GetLength(0); i++)
s += sqr(x[i] - y[i]);
return Math.Sqrt(s);
}
throw new DimensionException();
}
}
public class Cluster
{
private int nbClusters;
//data to send
public class GCluster : GObject
{
private Point[] array;//liste des points
private bool[] partition;//tableau disantquels points on a
private int elts;//le nombred'lts ds partition
private Queue<int> toAdd;//les lments ajouter
private IDistance<Point> distance;
private GCluster[] clusters;
private int index;
private Point centroid;
private GState state;
public GCluster(Point[] array,PointDistance distance,bool[] partition,int index)
{
this.array=array;
this.distance=distance;
this.partition = partition;
this.toAdd = null;
this.index = index;
centroid = new Point();
centroid.Set0(2);
elts = 0;
for (int i=0; i<partition.GetLength(0); i++)
if (partition[i])
{
elts++;
centroid=centroid.Add(array[i]);
}
centroid=centroid.Divide((double)elts);
}
public void Init(GCluster[] clusters,GState state)
{
this.clusters = clusters;
this.state = state;
toAdd=new Queue<int>();
}
private void AddPoint(int i)
{
//p1+..+pelts/elts -> p1+...+pelts+p(i)/elts+1
centroid = centroid.Multiply((double)elts).Add(array[i]).Divide((double)(++elts));
partition[i] = true;
}
private void RemovePoint(int i)
{
centroid = centroid.Multiply((double)elts).Sub(array[i]).Divide((double)(--elts));
partition[i] = false;
//centroid.Print();
}
//returns true if the point doesn't move
private bool TestPoint(int i)
{
double d=GetDistance(i);
int k=index;
for (int j = 0; j < index; j++)
{
double dt = clusters[j].GetDistance(i);
if (dt < d)
{
d = dt;
k = j;
}
}
for (int j = index+1; j < clusters.GetLength(0); j++)
{
double dt = clusters[j].GetDistance(i);
if (dt < d)
{
d = dt;
k = j;
}
}
if (k == index) return true;
else
{
clusters[k].AddInQueue(i);
RemovePoint(i);
System.Console.WriteLine("{0:D}-{1:D}->{2:D}", index,i, k);
return false;
}
}
public void DoIter()
{
bool dead = false;
bool toDo = true;
while (toDo)
{
toDo=false;
for(int i=0;i<array.GetLength(0);i++)
{
if (partition[i])
{
if (!TestPoint(i))
{
toDo = true;
if (dead)state.TaskUndone(index);
}
}
if (!TestFile()) toDo=true;
}
if (!toDo)
{
state.TaskDone(index);
dead = true;
}
if (!toDo) toDo = state.GetState();//stop now?
}
}
public void AddInQueue(int i)
{
using (new Lock(this))
{
toAdd.Enqueue(i);
}
}
public bool TestFile()
{
if (toAdd.Count==0)
return true;
elts++;
using (new Lock(this))
{
int head=toAdd.Dequeue();
AddPoint(head);
}
return false;
}
public bool[] GetPartition()
{
return partition;
}
public double GetDistance(int i)
{
return distance.Distance(array[i], centroid);
}
}
public class GState:GObject
{
private GCluster[] clusters;
private int[] state;
private bool gstate;
public void TaskDone(int i)
{
using(new Lock(this))
{
state[i]++;
gstate = false;
for (int j = 0; j < state.GetLength(0); j++)
{
if (state[j]<2)
gstate = true;
}
}
}
public void TaskUndone(int i)
{
using(new Lock(this))
{
for (int j=0;j<state.GetLength(0);j++) state[j] = 0;
gstate = true;
}
}
public bool GetState()
{
for (int i=0;i<state.GetLength(0);i++)
System.Console.Write("{0:D},", state[i]);
System.Console.WriteLine("");
return gstate;
}
public GState(GCluster[] clusters)
{
state = new int[clusters.GetLength(0)];
for (int i = 0; i < clusters.GetLength(0); i++)
state[i] = 0;
gstate = true;
this.clusters = clusters;
}
}
public void DoIt(Point[] array, bool[][] partitions, PointDistance distance)
{
nbClusters = partitions.GetLength(0);
GThread[] threads= new GThread[nbClusters];
//Thread[] threads = new Thread[nbClusters];
GCluster[] clusters = new GCluster[nbClusters];
Stopwatch sw=new Stopwatch();
sw.Start();
for (int i = 0; i < nbClusters; i++)
clusters[i] = (GCluster)(new GCluster(array,distance,partitions[i],i)).GetProxy();
GState state = (GState)(new GState(clusters)).GetProxy();
for (int i = 0; i < nbClusters; i++)
clusters[i].Init(clusters, state);
sw.Stop();
System.Console.WriteLine("Create clusters : Ticks : {0:E}",(float)sw.ElapsedTicks/Stopwatch.Frequency);
sw.Reset();
sw.Start();
for(int i=0;i<nbClusters;i++)
{
threads[i]=(new GThread(new ThreadStart(clusters[i].DoIter))).GetProxy();
// threads[i] = new Thread(new ThreadStart(clusters[i].DoIter));
threads[i].Start();
}
sw.Stop();
System.Console.WriteLine("Thread launch : Ticks : {0:E}", (float)sw.ElapsedTicks / Stopwatch.Frequency);
sw.Reset();
for (int j = 0; j < threads.Length; j++)
{
threads[j].Join();
partitions[j]=clusters[j].GetPartition();
}
}
}
class Program
{
static void Main(string[] args)
{
Random t=new Random();
Point[] f=new Point[100];
for (int i = 0; i<100;i++)
{
double[] r=new double[2];
r[0]=(double)t.Next(32768)/32768;
r[1]=(double)t.Next(32768)/32768;
//r[2]=(double)t.Next(32768)/32768;
f[i] = new Point();
f[i].Set(r);
}
bool[][] partition=new bool[5][];
for (int i = 0; i < 5; i++)
{
partition[i] = new bool[100];
for (int j = 0; j < 100; j++)
{
if (j / 20 == i)
partition[i][j] = true;
else
partition[i][j] = false;
}
}
Cluster c = new Cluster();
PointDistance dist=new PointDistance();
System.Console.WriteLine("Points :");
for (int i = 0; i < 100; i++)
{
f[i].Print();
System.Console.WriteLine(";{0:D}",i/20);
}
c.DoIt(f, partition, dist);
System.Console.WriteLine("Points :");
for (int i = 0; i < 100; i++)
{
f[i].Print();
int k = 0;
for (int j = 0; j < 5; j++)
if (partition[j][i])
k = j;
System.Console.WriteLine(";{0:D}", k);
}
System.Console.ReadKey();
}
}
}
|