ckmeans is not O(kn log(n))?

[breck7]

We are using ckmeans for generating color scales for maps.

ckmeans seems to be giving roughly O(kn^2) performance.

With the code below, I am getting about .25s seconds when N is 10,000 and ~25s when N is 100,000 (so roughly 100x longer instead of 20x).

const ss = require("simple-statistics")
const lodash = require("lodash")
const range = lodash.range
const ckmeans = ss.ckmeans

const rands = (count) => range(0, count).map((i) => Math.floor(1000 * Math.random()))
const kSize = 5
range(1, 6).forEach((power) => {
  const start = Date.now()
  const nSize = Math.pow(10, power)
  const dataset = rands(nSize)
  const result = ckmeans(dataset, kSize)
  const time = Date.now() - start
  console.log([kSize, nSize, time])
})

// Outputs:
[ 5, 10, 2 ]
[ 5, 100, 5 ]
[ 5, 1000, 16 ]
[ 5, 10000, 444 ]
[ 5, 100000, 24337 ]

[breck7]

Here's a slightly updated script for generating more data:

const ss = require("simple-statistics")
const lodash = require("lodash")
const range = lodash.range
const ckmeans = ss.ckmeans

const rands = (count) => range(0, count).map((i) => Math.floor(1000 * Math.random()))
const kSize = 5
const runs = []
range(3, 6).forEach((power) => {
  const start = Date.now()
  range(1, 3).forEach((multiple) => {
    const nSize = multiple * Math.pow(10, power)
    ckmeans(rands(nSize), kSize)
    runs.push([kSize, nSize, Date.now() - start])
  })
})

console.log(`kSize,nSize,time`)
console.log(runs.map((run) => run.join(",")).join("\n"))

kSize,nSize,time
5,1000,36
5,2000,53
5,10000,258
5,20000,1236
5,100000,23122
5,200000,113886