This is much faster:
distMatCompiled = Compile[{{cluster, _Real, 2}},
Outer[Function[diff, diff.diff][#1 - #2] &, cluster, cluster, 1, 1]
, CompilationTarget -> "C"
]
medoidCompiled[cluster_] := Block[{distances, indexOfMin},
distances = Total@distMatCompiled[cluster];
indexOfMin = First[Ordering[distances, 1]];
{cluster[[indexOfMin]], indexOfMin}
]
On my machine:
SeedRandom[0];
cluster = RandomReal[{0, 1}, {5000, 14}];
AbsoluteTiming[m1 = medoidSimple[cluster]]
(* 48.116032 *)
AbsoluteTiming[m2 = medoidCompiled[cluster]]
(* 6.779268 *)
m1 == m2
(* True *)
The reason you couldn't compile efficiently in your example is that SquaredEuclideanDistance is not in the list of compilable functionslist of compilable functions.
UPDATE:
Just for fun I wanted to implement your optimization idea:
medoidCompiled2 = Compile[{{cluster, _Real, 2}},
Block[{len = Length[cluster], bestInd = 1, bestVal, partsum, j},
bestVal =
Total[Table[
Function[x, x.x][cluster[[1]] - cluster[[i]]], {i, len}]];
Do[
partsum = 0.;
j = 1;
While[j <= len && partsum < bestVal,
partsum += Function[x, x.x][cluster[[i]] - cluster[[j]]];
j++
];
If[j == len + 1 && partsum < bestVal, bestVal = partsum;
bestInd = i]
, {i, 2, len}
];
bestInd
]
, CompilationTarget -> "C"
]
It performs a bit better than my first attempt:
AbsoluteTiming[m3 = medoidCompiled2[cluster]]
(* 4.286030 *)
Last[m1] == m3
(* True *)
Of course this cannot beat the insane timings ciao and blochwave have come up with ;)
