Come dovrei chiamare questa funzione di utilità? È qualcosa di simile comunemente usato?

Question

Come dovrei chiamare questa funzione di utilità? È qualcosa di simile comunemente usato?

#1 da (4 voti)

2

Supponiamo di voler combinare alcune matrici di oggetti con proprietà simili:

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']}]

Potrebbe facilmente essere fatto con un ciclo annidato:

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

Questo ha complessità O(people * items) che va bene per un esempio così banale ma che potrebbe non essere scalabile.

Potresti voler filtrare un array con un altro:

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'}]

Che potrebbe essere fatto con un approccio simile, e richiederebbe un simile ammontare di tempo.

La complessità di questo tipo di problemi può essere migliorata da O(a0 * a1 * a2...) a O((a0 + a1 + a2...) * log(a0 + a1 + a2...)) ordinando tutti gli array, aggiungendo valori mancanti, facendo zip e quindi iterando una volta attraverso il risultato:

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'}]

Questo funziona perfettamente per me e ha risolto alcuni problemi di prestazioni in un gioco. Ma non ho mai visto questo approccio in natura, c'è un modo migliore? In caso contrario, ha un nome in questo modo? Ci sono molti posti in cui può essere usato.

Potresti alternativamente (non necessariamente con molti array) ordinare un array e usare la ricerca di bisezione per il ciclo interno. È ciò che normalmente fanno i programmatori?

Questa è la mia implementazione di preProcess per i curiosi:

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())

javascript algorithms

posta Ashton War 24.04.2016 - 02:52

fonte

1 risposta

Leggi altre domande sui tag javascript algorithms

Test dell'unità per modulo in ZF2 Quali dovrebbero essere le linee guida primarie nella definizione di un contesto limitato?

score 4 · Accepted Answer

Penso che le operazioni che stai facendo siano variazioni di join SQL , perché nella maggior parte dei casi stai prendendo tuple di dati, scegliendo un tipo di valore da associare e restituendo le combinazioni che potrebbero essere collegate.

Suggerirei di esaminare il gergo, gli algoritmi e i documenti di ricerca dei sistemi RDBM come il primo posto per i miei dati per ulteriori informazioni. Voglio dire, considera cosa deve fare un pianificatore di query SQL: richiede una descrizione di alto livello di ciò che l'utente desidera per raggiungere, stima le dimensioni dei set di dati coinvolti, controlla se esistono indici utili e sceglie una serie di molti passaggi algoritmici per concatenare insieme per ottenere risultati rapidi e accurati.

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']}]

... Partecipa al proprietario, con il raggruppamento per proprietario e l'aggregazione del nome (elemento)?