search

mourner / kdbush

A fast static index for 2D points
ISC License
637 stars 69 forks source link

Use an appropriate type for indices regardless of data type #20

Closed flekschas closed 6 years ago

flekschas commented 6 years ago

First of all, thanks for providing this awesome lib! This is more a question rather than a bug report.

I notice that one can specify the dtype using the 4th parameter of the constructor, which is used for the index and coords array: https://github.com/mourner/kdbush/blob/master/src/index.js#L18-L19

Would it make sense to store the indices in anything other than a typed int array? I am asking myself this because storing the points as floats would automatically set this.ids to floats as well.

As an idea, we could fix this.ids to its most efficient dtype using something like this

  const bits = Math.log2(points.length);
  let IdxArrayType = Uint8Array;
  if (bits > 8) IdxArrayType = Uint16Array;
  if (bits > 16) IdxArrayType = Uint32Array;

  this.ids = new IdxArrayType(points.length);
  this.coords = new ArrayType(points.length * 2);
mourner commented 6 years ago

You're right — this would be a nice improvement. Flatbush already does this: https://github.com/mourner/flatbush/blob/master/index.js#L47 — let's do the same in KDBush. Want to do a PR?

flekschas commented 6 years ago

Sounds good! I am happy to piece together PR.

derhuerst commented 6 years ago

Just found kdbush and want to add an export/import functionality, similar to Flatbush.from. Will wait for this PR.

flekschas commented 6 years ago

PR is out. I tried to keep things as minimal as possible.

Just out of curiosity, I noticed that the runtime goes down quite a bit when changing the coordinate dtype from Int32Array to Float32Array. Do you know why?