asynchronous - How to remove repeating entries in a massive array (javascript)

Question

I'm trying to graph a huge data set (about 1.6 million points) using Kendo UI. This number is too large, but I have figured out that many of these points are repeating. The data is currently stored in this format: [ [x,y], [x,y], [x,y]...] with each x and y being a number, thus each subarray is a point. The approach I have in mind is to create a second empty array, and then loop through the very long original array, and only push each point to the new one if it isn't already found there.

I tried to use jQuery.inArray(), but it does not seem to work with the 2D array I have here.

I currently try this:

    var datMinified = [];
    for( z = 2; z < dat1.length; z++) //I start at 2 because the first 2 elements are strings, disregard this
     {

       if( !(testContains(datMinified, dat1[z])) )
       {

         datMinified.push(dat1[z])

       }
      }

with the helper functions defined as:

    function testContains(arr, val)
      {
        for(i=0;i<arr.length;i++)
        {
          if( arraysEqual( arr[i], val) )
          {
            return true;
          }
        }
        return false;
      }

and:

    function arraysEqual(arr1, arr2)
    {
      if(! (arr1.length == arr2.length))
      {
        return false;
      }
      for( i = 0; i < arr1.length; i++ )
      {
        if( !(arr1[i] == arr2[i]))
        {
          return false;
        }
      }
      return true;
    }

When I run this script, even with a smaller array of length 6 thousand it still gets stuck up. Maybe jQuery is a good solution?

Edit: I was also thinking that there might be some way to tell the browser to not time out and just sit and work through the data?

Answer 1

You have a non-trivial problem but I'm gonna blast right through so ask questions if I lose you somewhere along the line. This solution does not cast the coordinate into a String or serialise it using other techniques like JSON.stringify -

Start with a way to create coordinates -

const Coord = (x, y) =>
  [ x, y ]

To demonstrate the solution, I need to construct many random coordinates -

const rand = x =>
  Math.floor(Math.random() * x)

const randCoord = x => 
  Coord(rand(x), rand(x))

console.log(randCoord(1e3))
// [ 655, 89 ]

Now we make an array of 1 million random coordinates -

const million =
  Array.from(Array(1e6), _ => randCoord(1e3))

Now we make a function to filter all of the unique values using DeepMap, a tiny module I developed in this answer.

const uniq = (coords = []) =>
{ const m = new Map
  const r = []
  for (const c of coords)
    if (!DeepMap.has(m, c))
      { DeepMap.set(m, c, true)
        r.push(c)
      }
  return r
}

Because for and DeepMap have excellent performance, uniq can identify all of the unique values in less than one second -

console.time("uniq")
const result = uniq(million)
console.timeEnd("uniq")

console.log("uniq length:", result.length)
console.log("sample:", result.slice(0,10))

// uniq: 535 ms
// uniq length: 631970
// sample: 
// [ [ 908, 719 ]
// , [ 532, 967 ]
// , [ 228, 689 ]
// , [ 942, 546 ]
// , [ 716, 180 ]
// , [ 456, 427 ]
// , [ 714, 79 ]
// , [ 315, 480 ]
// , [ 985, 499 ]
// , [ 212, 407 ]
// ]

Expand the snippet below to verify the results in your own browser -

const DeepMap =
  { has: (map, [ k, ...ks ]) =>
      ks.length === 0
        ? map.has(k)
        : map.has(k)
          ? DeepMap.has(map.get(k), ks)
          : false

  , set: (map, [ k, ...ks ], value) =>
      ks.length === 0
        ? map.set(k, value)
        : map.has(k)
            ? (DeepMap.set(map.get(k), ks, value), map)
            : map.set(k, DeepMap.set(new Map, ks, value))
  }

const Coord = (x, y) =>
  [ x, y ]

const rand = x =>
  Math.floor(Math.random() * x)

const randCoord = x => 
  Coord(rand(x), rand(x))

const million =
  Array.from(Array(1e6), _ => randCoord(1e3))

const uniq = (coords = []) =>
{ const m = new Map
  const r = []
  for (const c of coords)
    if (!DeepMap.has(m, c))
      { DeepMap.set(m, c, true)
        r.push(c)
      }
  return r
}

console.time("uniq")
const result = uniq(million)
console.timeEnd("uniq")

console.log("uniq length:", result.length)
console.log("sample:", result.slice(0,10))

// uniq: 535 ms
// uniq length: 631970
// sample: 
// [ [ 908, 719 ]
// , [ 532, 967 ]
// , [ 228, 689 ]
// , [ 942, 546 ]
// , [ 716, 180 ]
// , [ 456, 427 ]
// , [ 714, 79 ]
// , [ 315, 480 ]
// , [ 985, 499 ]
// , [ 212, 407 ]
// ]