2

Suppose you want to combine some arrays of objects that have similar properties:

var people = [{name: 'Jack', age: 10}, {name: 'Jill', age: 12}]
var items = [{owner: 'Jack', name: 'pail'}, {owner: 'Jill', name: 'water'}]

var output = process(people, items)
//  [{name: 'Jack', age: 10, items: ['pail']},
//   {name: 'Jack', age: 12, items: ['water']}]

It could easily be done with a nested loop:

var process = people => people.map(p => ({
  ...p,
  items: p.items.concat(items.find(i => i.owner === p.name))}))

This has complexity O(people * items) which is fine for such a trivial example but might not scale.

You may want to filter one array by another:

var items = [{id: 5, name: 'John'}, {id: 8, name: 'Jordan'}, {id: 16, name: 'Josephine'}]
var ids = [5, 16]

var output = process(items, ids)
//  [{id: 5, name: 'John'}, {id: 16, name: 'Josephine'}]

Which could be done with a similar approach, and would take a similar ammount of time.

The complexity for these kind of problems can be improved from O(a0 * a1 * a2...) to O((a0 + a1 + a2...) * log(a0 + a1 + a2...)) by sorting all the arrays, padding missing values, zipping and then iterating once through the result:

var items = [{id: 5, name: 'John'}, {id: 8, name: 'Jordan'}, {id: 16, name: 'Josephine'}]
var ids = [5, 16]

var result = preProcess(items, ids, v => v.id || v)
//  [[{id: 5, name: 'John'}, {id: 8, name: 'Jordan'}, {id: 16, name: 'Josephine'}],
//   [5, undefined, 16]]

result = zip(result)
//  [[{id: 5, name: 'John'}, 5],
//   [{id: 8, name: 'Jordan'}, undefined],
//   [{id: 16, name: 'Josephine'}, 16]]

result = result.filter(([item, id]) => id).map(([item]) => item)
//  [{id: 5, name: 'John'}, {id: 16, name: 'Josephine'}]

This works great for me and fixed some performance issues in a game. But I've never seen this approach in the wild, is there a better way? If not, does this way have a name? There's plenty of places it could be used.

You could alternatively (not necessarily w/ many arrays) sort one array and use bisection search for the inner loop. Is this what programmers normally do instead?

This is my implementation of preProcess for the curious:

import _ from 'lodash'
import _f from 'lodash/fp'

const _preProcess = (arrs, f) => {
  const result = []
  const indexes = arrs.map(() => 0) // resultIndex, currentIndex
  const sorted = arrs.map(_.flow(_f.map(v => [f(v), v]), _f.sortBy('0')))
  while (indexes.find((v, i) => sorted[i].length - 1 >= v) !== undefined) {
    let values = sorted.map((a, i) => a[indexes[i]])
    const min = _.minBy(values, '0')[0]
    values = values.map(([fv, v], i) => fv === min ? (indexes[i] += 1, v) : undefined)
    result.push(values)
  }
  return _.zip(...result)
}

const preProcess = (...args) =>
  _preProcess(
    args.length === 2 ? args[0] : args.slice(0, -1),
    _.chain(args).last().iteratee().value())
  • 2
    In the context of JavaScript, I'd imagine most people would simply do, in pseudo-code, dict = {}; foreach(item in items){dict[item.id] = item;}; result = ids.map(id => dict[id]); What you are doing (and my version as well) is akin to indexing in a database. – Derek Elkins Apr 24 '16 at 1:10
4

I think the operations you're doing are variations of SQL joins, because in most cases you're taking tuples of data, picking a kind of value from each one to associate, and returning the combination(s) that could be linked.

I'd suggest you look into the jargon, algorithms, and research-papers of RDBMs systems as your first place to mine for more information. I mean, consider what an SQL query-planner has to do: It takes a high-level description of what the user wants to achieve, estimates the sizes of the data-sets involved, checks if useful indexes exist, and chooses a series of many algorithmic steps to chain together in order to get fast and accurate result.

You may want to filter one array by another:

var items = [{id: 5, name: 'John'}, {id: 8, name: 'Jordan'}, {id: 16, name: 'Josephine'}]
var ids = [5, 16]

var output = process(items)
//  [{id: 5, name: 'John'}, {id: 16, name: 'Josephine'}]

... Join on ID?

var people = [{name: 'Jack', age: 10}, {name: 'Jill', age: 12}]
var items = [{owner: 'Jack', name: 'pail'}, {owner: 'Jill', name: 'water'}]

var output = process(people, items)
//  [{name: 'Jack', age: 10, items: ['pail']},
//   {name: 'Jack', age: 12, items: ['water']}]

... Join on owner, with grouping by owner and aggregation of (item-)name?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.