NodeJS 用于扁平化多个输入数组的Javascript函数

qco9c6ql  于 2023-02-03  发布在  Node.js
关注(0)|答案(6)|浏览(126)

我正在处理一些对象数组,这些对象数组将使用React呈现到UI中。下面是我正在做的事情的上下文。我从不同的API获得不同的数据集。这些数据集是对象数组的数组。例如

[
 [{age: 23, name: john}],
 [{age: 24, name: jane}],
 [{age: 25, name: sam}],
 [{age: 26, name: smith}],
]

使用这种格式,很难在UI中呈现结果。因此,一个简单的修复方法是将数组扁平化,返回一个对象数组,然后我可以Map并在UI上显示数据。现在,我对从API返回的每个数据集都进行了这种操作。

  • 首先,我使用array.flat()扁平化数组的每个数组
  • 其次,我使用array.filter()过滤重复项
  • 第三,我使用array.sort()对这些项进行排序
  • 第四步,使用array.concat()将数组合并在一起
  • 第五步,Map前面4步生成的最终数组。

遵循我上面列出的这种风格对我来说似乎是势在必行的,我想使用一种更函数化的方法,我可以将pipe函数放在一起,这将使它更具声明性而不是命令性。目前,我被困在编写一个将接受数组作为输入的函数上,然后将数组扁平化为一个最终数组。现在我知道我可以使用reduce()方法和扁平化数组。我在StackOverflow上遇到了一个解决方案,它看起来像这样,可以从这个链接Flatten Array看到

const flatten = (arr) => {
    return arr.reduce((flat, toFlatten) => {
        return flat.concat(
            Array.isArray(toFlatten) ? flatten(toFlatten) : toFlatten
        )
    }, [])
}

我在想,也许我可以扩展输入arr参数,但这似乎会引发此错误

RangeError: Maximum call stack size exceeded

如果能以正确的方式指导我,并向我展示实现我列出的所有这些操作的有效方法,我将不胜感激。谢谢

pvabu6sv

pvabu6sv1#

这个解决方案应该能满足你的需求,如果有几个不同的返回数据的样本可以合并在一起,那会很有帮助,但是我试着重现了你在下面的解决方案中所解释的内容。
首先,我将所有不同的源数组组合成一个数组,然后将其扁平化为任何源数组具有的任何深度。如果此深度可变,我使用flat(Infinity),但您也可以使用有限深度(flat(2)flat(3))。一旦我将数组扁平化,我就将其简单地转换为Set以删除任何重复项,然后将其转换回数组。

const source1 = [
  [{age: 23, name: 'john'}],
  [{age: 24, name: 'jane'}],
  [{age: 25, name: 'sam'}],
  [{age: 26, name: 'smith'}]
];

const source2 = [
  [{age: 27, name: 'mike'}],
  [{age: 28, name: 'joanne'}],
  [{age: 29, name: 'lois'}],
  [{age: 30, name: 'paul'}]
];

const allSources = [...new Set([source1,source2].flat(Infinity))];

console.log(allSources);

**此处的重要说明:因为数组和对象都是引用类型,所以即使两个源数组有相同的键值对对象,也不会被视为重复。为了真正过滤掉重复的对象,需要遍历两个对象的键,比较它们的关联值,如下所示:

const source1 = [
  [{age: 23, name: 'john'}],
  [{age: 24, name: 'jane'}],
  [{age: 25, name: 'sam'}],
  [{age: 26, name: 'smith'}]
];

const source2 = [
  [{age: 23, name: 'john'}],
  [{age: 24, name: 'jane'}],
  [{age: 25, name: 'sam'}],
  [{age: 26, name: 'smith'}],
  [{age: 27, name: 'mike'}],
  [{age: 28, name: 'joanne'}],
  [{age: 29, name: 'lois'}],
  [{age: 30, name: 'paul'}]
];

const allSources = [source1,source2].flat(Infinity).filter((obj,_,a) => a.find(o => Object.keys(obj).length === Object.keys(o).length && Object.keys(obj).every(objKey => Object.keys(o).includes(objKey) && obj[objKey] === o[objKey])) === obj);

console.log(allSources);
ljsrvy3e

ljsrvy3e2#

可以使用Array.flat()来展开多级数组。默认值为1,但是可以使用Array.flat(Infinity)来展开多级数组。

const arr = [[{"age":23,"name":"john"}],[{"age":24,"name":"jane"}],[{"age":25,"name":"sam"}],[{"age":26,"name":"smith"}]]

const result = arr.flat()

console.log(result)

要删除重复项,现在可以将展平的数组缩减为Map,然后使用Map.values()迭代器和Array.from()将其转换回数组:

const arr = [[{"age":23,"name":"john"}],[{"age":24,"name":"jane"}],[{"age":25,"name":"sam"}],[{"age":26,"name":"smith"}], [{"age":33,"name":"john"}]]

const result = Array.from(
  arr.flat()
    .reduce((acc, o) => 
      acc.has(o.name)
        ? acc
        : acc.set(o.name, o)
      , new Map())
    .values()
)

console.log(result)
0sgqnhkj

0sgqnhkj3#

这是一个不平凡的问题,也是一个学习设计数据结构的机会。这是一个长格式的答案,希望能给你自己做这些分析的工具。这篇文章使用布兰登善意的答案作为对比的基础。首先,我们需要检查一些JavaScript内置结构的属性。

    • 阵列的性能**

我们从数组开始,如果我们有一个数组input,和一个已知的索引i,我们可以在常数时间内取出元素。input[i]。这意味着inputi的大小都不会影响获得答案所需的时间。这在Big O notation中表示为 * O(1)*。这是真的,因为数组实际上是指向内存中某个位置的指针,而i是偏移量。找到元素是position + i的一个 * 常量 * 计算,它总是一个简单的加法。

const input =
  [ "foo", "bar", "cat", "dog", "hat", "ham" ]

const i =
  4

const result =
  input[i]

console.log(result) // "hat"

然而,如果索引是未知的,而我们希望通过元素的值来找到它,我们必须一次扫描一个元素,这被称为线性复杂度,用 * O表示因为时间/空间的量相对于输入的大小n线性缩放。对于n = 3元素的阵列,我们最多只需要检查3个元素就可以找到匹配项。对于n = 1000数组,我们最多需要检查1,000个元素!

const input =
  [ "foo", "bar", "cat", "dog", "hat", "ham" ]

const query =
  "hat"

const result =
  input.findIndex(v => v == query)

console.log(result) // 4

几乎所有的数组运算都随输入数组的大小而缩放。这些线性运算包括entrieseveryfillfilterfindfindIndexflatflatMapfor..offorEachfromincludesindexOfjoinkeyslastIndexOfmapreducereduceRightreverseslicesometoStringvalues。线性运算的一个重要特性是,当它们嵌套时,它们变为二次,或 * O(n2)
一个简单的方法是两个嵌套的for循环,
O(n)* O(n)= O(n * n)*。如果n = 1000,这可能需要1,000,000次计算。这也适用于其他线性运算,如嵌套在filter中的includes-

const input =
  [ "foo", "bar", "cat", "dog", "hat", "ham" ]

const result =
  input.filter(v => v.includes("a")) // <- nested linear operations

console.log(result)
// [ "bar", "cat", "hat", "ham" ]
    • 对象的性能**

接下来我们来看看JavaScript的对象,和数组一样,如果我们有一个对象input和一个已知的键query,我们可以在常数时间内获取一个值,* O(1)*-

const input =
  { a: 1, b: 2, c: 3 }

const query =
  "b"

const result =
  input[b]

console.log(result) // 2

现在假设我们有两个对象,foobar,并希望确定它们是否相等,我们的函数isEqualObject.keys,* O(n),其中every O(n),并且嵌套includes O(n),使用属性查找, O(1)。这是 * O(n + n (n +1)),它简化为 * O(n2)。这里的includes检查是不必要的,但我们按照Brandon的例子进行比较-

const foo =
  { a: 1, b: 3 }

const bar =
  { b: 3, a: 1 }

const isEqual = (x,y) =>
  Object.keys(x).every(k => y.includes(k) && y[k] === x[k])

console.log(isEqual(foo, bar)) // true
    • 复合性能**

对于最后一个示例,我们使用一个对象数组input和一个query对象,并尝试查找查询的索引。(n2)*。当我们将这个运算嵌套在线性findIndex中时,我们得到 * O(n)**O(n2)= O(n3)。如果n = 1000,这将需要1,000,000,000次计算!正如您所看到的,线性运算的计算复杂度可以非常快速地扩展-

const input =
  [ { a: 1, b: 1 }, { a: 1, b: 2 }, { a: 1, b: 3 } ]

const query =
  { b: 2, a: 1 }

function isEqual(x, y) {
  return Object.keys(x).every(k => y.includes(k) && y[k] === x[k])
}

const result =
  input.findIndex(v => isEqual(v, query))

console.log(result) // 1

现在让我们分析一下Brandon的回答。我不想让任何人认为我在挑他的毛病。他的程序是有效的,并且返回正确的结果。然而,随着输入大小的增加,它的进程 * 可以 * 让你的cpu停止。如果这个程序被循环使用,或者每次UI刷新都发生,它 * 可能 * 是个问题。

const allSources =
  [source1,source2]
      .flat(Infinity)
      .filter((obj,_,a) =>
         a.find(o =>
           Object.keys(obj).length === Object.keys(o).length
             && Object.keys(obj).every(objKey =>
               Object.keys(o).includes(objKey)
                 && obj[objKey] === o[objKey])) === obj)

| 复杂性|操作|
| - ------|- ------|
| * 第(1)款 *|x1米52英寸1 x英寸、x1米53英寸1 x英寸、x1米54英寸1 x英寸|
| 时间复杂度O(n)|x1米55英寸1 x英寸、x1米56英寸1 x英寸、x1米57英寸1 x英寸、x1米58英寸1 x英寸、x1米59英寸1 x英寸|
| 计算复杂性|
| - ------|
| 时间复杂度O(n + n *(n +1 + 1 + n +1 + n + n (n + n +1 + 1 + 1 + 1)))|
| 时间复杂度O(n + n *(n *(n +1 + 1 + n +1 + n + n (n)))|
| 时间复杂度O(n + n *(n (n +1 + 1 + n +1 + n + n2)))|
| 时间复杂度O(n + n)|
| 时间复杂度O(n)|

    • 第一个数据结构**

filter(...)算法上面有 * O(n4)* 复杂度。对于n = 1000的输入大小,估计为1,000,000,000,000(万亿)次运算!如果我们想要更快的解决方案,就不能依赖Array的线性运算,但是JavaScript并不包含我们所需要的数据类型。也许你以前从来没有设计过自己的数据结构,也许你不知道这是可能的,没关系!
现在我们来看看Map,它和Object有着非常相似的属性。主要的区别是对象的键必须是字符串,而Map可以将任何键类型与任何值相关联。和Array和Object一样,如果需要,我们可以嵌套Map任意数量的层。我们将使用get,顺序为get。在常数**时间内查找嵌套值。这表示为 * O(1)+O(1)= O(2),并简化为 * O(1)-

const key1 =
  { a: "ay" }      // <- any type for key1

const key2 =
  [ "bee" ]        // <- any type for key2

const someValue =
  Symbol("ess")    // <- any value

const m =
  new Map([[ key1, new Map([[ key2, someValue ]]) ]])

const result =
  m.get(key1).get(key2)

console.log(result === someValue) // true

除了get之外,Map还提供了has,它可以回答我们的特定Mapm * 是否具有 * 特定键k-

const key1 =
  { a: "ay" }

const m =
  new Map([[ key1, "foo" ]])

console.log(m.has(key1))  // true
console.log(m.has("bar")) // false
    • 重新Map**

我们可以使用Map的高性能属性来编写我们自己的递归Map类型recmap。在我们深入研究它的实现之前,下面是我们希望它如何工作--

import { empty, get, set } from "./recmap.js"

const t = empty()                 // <- empty recmap

set(t, ["a", 1, "b", 2], "hello") // <- set a deep value

const result =
  get(t, ["a", 1, "b", 2])        // <- retrieve a deep value

console.log(result) // "hello"

我们可以将上面的t可视化为嵌套Map的递归序列-

Map { "a" => Map { 1 => Map { "b" => Map { 2 => "hello" }}}}

用户不需要理解Array、Object或Map就可以有效地使用它。这被称为数据抽象,它是编写有效数据结构的一个重要属性。我们将构建数据类型,以便嵌套结构由模块的操作自动管理-

// recmap.js

const empty = () =>
  new Map                         // <- representation of "empty" recmap

const has = (t, [ k, ...ks ]) =>  // <- recursive wrapper around Map.has
  ks.length == 0
    ? t.has(k)
    : t.has(k)
      ? has(t.get(k), ks)
      : false

const set = (t, [ k, ...ks ], v) => // <- recursive wrapper around Map.set
  ks.length == 0
    ? t.set(k, v)
    : t.has(k)
      ? (set(t.get(k), ks, v), t)
      : t.set(k, set(empty(), ks, v))

const get = (t, [ k, ...ks ]) =>    // <- recursive wrapper around Map.get
  ks.length == 0
    ? t.get(k)
    : t.has(k)
      ? get(t.get(k), ks)
      : undefined

export { empty, has, set, get }     // <- public module interface

我们的recmapextremely fast,能够在不到一秒的时间内过滤一百万个值,这很棒,但是有一个小问题:这个问题的目的是将对象彼此比较。

我的第二个数据结构

坚持住,我们几乎完成了。我们围绕Map设计了recmap,这样用户就不必担心管理嵌套结构。我们将围绕recmap构建unique,这样用户就不必担心嵌套的Map或键序列。相反,我们可以简单地创建一个empty集合,并自由地使用add来获取我们想要的任意多个值-

import { empty, has, add, values } from "./unique.js"

const t = empty()             // <- empty unique

add(t, { a:1, b:2, c:3 })     // <- any object

const result =
  has(t, { a:1, b:2, c:3 })   // <- has any object?

console.log(result) // true

输入对象的键的顺序并不重要。我们总是会得到正确的答案-

console.log(has(t, { b:2, c:3, a:1 })) // true

如果我们尝试用不同的键顺序来add相同的对象也没关系。它只会被添加一次-

add(t, { b:2, c:3, a:1 })
add(t, { b:2, a:1, c:3 })
add(t, { c:3, a:1, b:2 })

console.log(Array.from(values(t)))
[ { c:3, a:1, b:2 } ]   // <- only one distinct object is added

唯一

由于我们现有的recmap,这个模块更容易编写。它是recmap.setrecmap.has的一个简单 Package 器,添加了一个toKey函数,负责输入对象的排序。这种从简单数据结构构建复杂数据结构的技术是每个函数式程序员都必须掌握的-

// unique.js

import * as recmap from "./recmap.js"

const add = (t, v) =>         // <- wrapper around recmap.set
  recmap.set(t, toKey(v), v)

const has = (t, v) =>         // <- wrapper around recmap.has
  recmap.has(t, toKey(v))

const toKey = v =>            // <- private helper, sequences an object
  Object
    .entries(v)
    .sort((a,b) => a[0].localeCompare(b[0]))
    .flat()

const empty =
  recmap.empty   // <- same empty representation as recmap

const values =
  recmap.values  // <- todo

export { add, empty, has, values } // <- public interface

上面注意我们没有导出toKey,这是一个private函数,仅供我们的模块使用;用户无需担心的实现细节。还要注意的是,我们调用了recmap.values,现在我们将实现它-

// recmap.js (continued)

const empty = //...
const has = //...
const set = //...
const get = //...

function* values (t)
{ if (t instanceof Map)
    for (const v of t.values())
      yield *values(v)
  else
    yield t.unwrap
}

export
  { empty, has, set, get, values } // <- update export

基准

我们已经取得了沿着进展,现在是时候来衡量一下我们的unique数据结构和布兰登答案中提出的线性filter算法之间的差异了,为了比较这两种算法,我们将使用randCoord来生成随机{ x, y }对象--

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

const randCoord = size =>
  ({ x: rand(size), y: rand(size) })

const input =
  Array.from(Array(count), _ => randCoord(size))

unique算法迭代inputadd的每个元素到我们的集合-

console.time("unique")
const a = empty()
for (const x of input)
  add(a, x)
console.timeEnd("unique")
console.log(`uniques: ${Array.from(values(a)).length}`)

如上所述,filter算法是filter-〉find-〉every-〉includes的多元链。

console.time("filter")
const b = filter(input)
console.timeEnd("filter")
console.log(`uniques: ${b.length}`)

大小为randCoord(10)时,我们生成从(0,0)(10,10)的坐标,最大可能性为 10 x 10 = 100 个唯一坐标-
| 计数|独特的|演算法|运行时间|各|
| - ------|- ------|- ------|- ------|- ------|
| 一百|六十四|filter|二点二六|0.023|
| 一千|一百|filter|十一时三十分|0.011|
| 一万|一百|1米100英寸1英寸|九十六点七三分|0.010分|
| 十万|一百|filter|八○二点五二|0.008|
在这种情况下,线性filter算法不必检查超过100个元素来确定其中一个元素是否唯一。因此,即使有100,000个元素,重复项也可以很容易地检测出来。但是,unique数据结构检测重复项的速度更快-
| 计数|独特的|演算法|运行时间|各|
| - ------|- ------|- ------|- ------|- ------|
| 一百|六十四|unique|九点六八分|0.097|
| 一千|一百|unique|三点八八|0.004|
| 一万|一百|unique|十二时十六分|千分之一|
| 十万|一百|unique|一○六点三一分|千分之一|
您的真实数据使用{ name, age }对象,唯一组合可能远远大于 10 x 10。接下来,我们将了解随着可能的唯一组合的增加,filter的性能会受到怎样的影响。我们生成从(0,0)(100,100)的坐标,其最大可能性为 *100 × 100 = 10,000 * 唯一坐标。
| 计数|独特的|演算法|运行时间|各|
| - ------|- ------|- ------|- ------|- ------|
| 一百|九十八|filter|二点五二|0.025|
| 一千|九四六|filter|四十八点六三分|0.049|
| 一万|六千三百四十人|filter|3 105英镑|0.310|
| 十万|一万|filter|六万七千四百六十元|0.675|
这里filter开始抬头。在1,000个元素的情况下,运行时间已经增加了 * 4倍 *。在10,000个元素的情况下,我们看到增加了 * 32倍 *。相比之下,unique处理更大的输入空间,而实际上运行时间没有增加-
| 计数|独特的|演算法|运行时间|各|
| - ------|- ------|- ------|- ------|- ------|
| 一百|九十八|unique|九点七六分|0.098|
| 一千|九四六|1米120英寸1英寸|四、十一|0.004|
| 一万|六千三百四十人|unique|十三、十|千分之一|
| 十万|一万|unique|一百二十一点五十五分|千分之一|

大小为randCoord(1000)时,我们生成从(0,0)(1000,1000)的坐标,最大可能性为 * 1,000 x 1,000 = 1,000,000 * 个唯一坐标。这类似于{ first, last }对象,其中可能有1,000个唯一的名字和1,000个唯一的姓氏-
| 计数|独特的|演算法|运行时间|各|
| - ------|- ------|- ------|- ------|- ------|
| 一百|一百|filter|0.39|0.004|
| 一千|九九九|filter|三十八点八六分|0.039|
| 一万|九千九百五十人|filter|3 710英镑|0.371|
| 十万|九万五千一百八十六人|1米130英寸1英寸|三十六万四千五百四十九元|三点六四五|
我们需要指出的一个值得注意的模式是,随着unique数量的增加,filter查找每个结果所需的时间增加了一倍。由于要检查的元素数量很大,达到100,000个,因此需要6分钟以上才能完成。同时,unique计算结果时,运行时间不会随着unique数量的增加而增加-
| 计数|独特的|演算法|运行时间|各|
| - ------|- ------|- ------|- ------|- ------|
| 一百|一百|unique|0.12|千分之一|
| 一千|九九九|unique|0.97|千分之一|
| 一万|九千九百五十人|x1米135英寸1x|十一时零四分|千分之一|
| 十万|九万五千一百八十六人|unique|一百二十四块九十九|千分之一|

    • 真实示例**

上面我们比较了只有两个字段的对象。在最后一个基准测试中,让我们看看两种算法在处理具有七个字段firstlastagephonegenderemail的对象时的比较结果。

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

const randObj = () => ({
    first: rand(1000),
    last: rand(1000),
    age: rand(100),
    phone: rand(1e10),
    gender: rand(2),
    email: rand(1e20)
})

const input =
  Array.from(Array(count), randObj)

这等于 * 1000 x 1000 x 100 x 10,000,000,000 x 2 x 100,000,000,000,000,000 = 200,000,000,000,000,000,000,000,000,000,000,000 *,或 * 2e38 *,可能是唯一的-
| 计数|独特的|演算法|运行时间|各|
| - ------|- ------|- ------|- ------|- ------|
| 一百|一百|filter|一点九五|0.019|
| 一千|一千|filter|五十三点四十七分|0.053|
| 一万|一万|x1米145英寸1x|4,435.00英镑|0.444|
| 十万|十万|filter|四十七万一千六百二十二元|四点七一六|
| 一百万|一百万|x1米147英寸|?|?|
毫不奇怪,即使在100,000个对象中,也没有发现一个重复项。这演示了两种算法的最坏情况。我抛出了一个包含1,000,000个元素的大型基准测试,只是为了对unique算法进行压力测试。虽然filter需要12个多小时才能完成,unique可在 * 不到5秒 * 内确定结果-
| 计数|独特的|演算法|运行时间|各|
| - ------|- ------|- ------|- ------|- ------|
| 一百|一百|unique|十一点四十九分|零点一一五|
| 一千|一千|unique|六点五十五分|0.007分|
| 一万|一万|unique|四十七点七七分|0.005分|
| 十万|十万|unique|小行星404.93|0.004|
| 一百万|一百万|x1米155英寸1x|4,956.00英镑|0.005分|

    • 增强功能1**

编写我们自己的数据结构的一大优势是我们可以根据需要改变它们的行为和调整它们的性能。如果我们添加一个对象,并尝试使用该对象的子集查找,我们将得到true答案-

import { empty, add, has } from "./unique.js"

const t = empty()

add(t, {a: 1, b: 2})

console.log(has(t, {a: 1})) // true ❌

如果t的底层表示为-

Map { "a" => Map { 1 => Map { "b" => Map { 2 => ... }}}}

这意味着has(t, {a: 1})将找到下面的嵌套Map,并返回true-

{ "b" => Map { 2 => ... }}

你可能认为这是unique的问题,但这个问题也存在于recmap中。这是一个bug,我们可以通过引入一个简单的checksum-

// recmap.js (continued)

const checksum = key =>
  [ key.length, ...key ]  // <- prepend sequence with length

const empty = // ...
const _get = // ... originally `get`, now private
const _has = // ... originally `has`, now private
const _set = // ... originally `set`, now private

// new wrappers: checksum the key and call private function
const get = (t, k) => _get(t, checksum(k))
const has = (t, k) => _has(t, checksum(k))
const set = (t, k, v) => _set(t, checksum(k), v)

export // ...

不需要对unique进行任何更改。我们可以继续工作了-

add(t, {a: 1, b: 2})
console.log(has(t, {a: 1})) // false ✅
console.log(has(t, {a: 1, b: 2})) // true ✅
console.log(has(t, {b: 2, a: 1})) // true ✅
    • 增强功能2**

我们的recmap模块使用Map作为底层表示,但用户不知道(不应该知道)这一点。如果用户尝试将自己的Map插入到混合中,会发生什么情况?引入wrap实用程序,我们可以允许用户插入 * any * 值类型,并防止泄漏任何实现细节-

// recmap.js (continued)

const checksum = // ...
const empty = // ...
const _get = // ... 
const _has = // ... 
const _set = // ...

const wrap = v =>       // <- wrap utility
  ({ unwrap: v })

const has = // ...
const get = (t, k) => _get(t, checksum(k)).unwrap  // <- unwrap
const set = (t, k, v) => _set(t, checksum(k), wrap(v)) // <- wrap

export // ...
    • 增强功能3**

我们围绕原生Map设计了recmap,它提供了一些其他有用的方法。我们可以添加entrieskeys来提供更完整的实现-

// recmap.js (continued)

// ...

function* entries (t, path = [])
{ if (t instanceof Map)
    for (const [k, v] of t.entries())
      yield *entries(v, [...path, k])
  else
    yield [path.slice(1), t.unwrap ]
}

function* keys (t, path = [])
{ if (t instanceof Map)
    for (const [k, v] of t.entries())
      yield *keys(v, [...path, k])
  else
    yield path.slice(1)
}

export { ..., entries, keys } // <- update export
    • 演示**

没有功能演示的答案是不完整的,imo。我已经内联了recmapunique模块,因为我们仅限于一个"文件"进行演示。我们将从Brandon的帖子中借用输入示例-

const source1 =
  [ {age: 23, name: 'john'}
  , {age: 24, name: 'jane'}
  , {age: 25, name: 'sam'}
  , {age: 26, name: 'smith'}
  ]

const source2 =
  [ {age: 23, name: 'john'}
  , {age: 24, name: 'jane'}
  , {age: 25, name: 'sam'}
  , {age: 26, name: 'smith'}
  , {age: 27, name: 'mike'}
  , {age: 28, name: 'joanne'}
  , {age: 29, name: 'lois'}
  , {age: 30, name: 'paul'}
  ]
const recmap = (_ => {     // recmap module
  const empty = () => new Map
  const checksum = key => [ key.length, ...key ]
  const wrap = v => ({ unwrap: v })
  const _has = (t, [ k, ...ks ]) =>  ks.length == 0 ? t.has(k) : t.has(k) ? _has(t.get(k), ks) : false
  const _set = (t, [ k, ...ks ], v) => ks.length == 0 ? t.set(k, v) : t.has(k) ? (_set(t.get(k), ks, v), t) : t.set(k, _set(empty(), ks, v))
  const _get = (t, [ k, ...ks ]) => ks.length == 0 ? t.get(k) : t.has(k) ? _get(t.get(k), ks) : undefined
  const has = (t, keys) => _has(t, checksum(keys))
  const set = (t, keys, v) => _set(t, checksum(keys), wrap(v))
  const get = (t, keys) => _get(t, checksum(keys))?.unwrap
  function* values (t) { if (t instanceof Map) for (const v of t.values()) yield *values(v); else yield t.unwrap }
  return { empty, get, has, set, values }
})()

const unique = (_ => {     // unique module
  const toKey = v => Object.entries(v).sort((a,b) => a[0].localeCompare(b[0])).flat()
  const add = (t, v) => recmap.set(t, toKey(v), v)
  const has = (t, v) => recmap.has(t, toKey(v))
  const empty = recmap.empty
  const values = recmap.values
  return { add, empty, has, values }
})()

const source1 = [{age: 23, name: 'john'}, {age: 24, name: 'jane'}, {age: 25, name: 'sam'}, {age: 26, name: 'smith'}]
const source2 = [{age: 23, name: 'john'}, {age: 24, name: 'jane'}, {age: 25, name: 'sam'}, {age: 26, name: 'smith'}, {age: 27, name: 'mike'}, {age: 28, name: 'joanne'}, {age: 29, name: 'lois'}, {age: 30, name: 'paul'}]
const result = unique.empty()

for (const x of [...source1, ...source2])
  unique.add(result, x)

console.log(Array.from(unique.values(result)))

所有重复的都被删除了-

[ { age: 23, name: 'john' }
, { age: 24, name: 'jane' }
, { age: 25, name: 'sam' }
, { age: 26, name: 'smith' }
, { age: 27, name: 'mike' }
, { age: 28, name: 'joanne' }
, { age: 29, name: 'lois' }
, { age: 30, name: 'paul' }
]
fumotvh3

fumotvh34#

const source1 = [
    [{age: 23, name: 'john'}],
    [{age: 24, name: 'jane'}],
    [{age: 25, name: 'sam'}],
    [{age: 26, name: 'smith'}]
  ];
  
  const source2 = [
    [{age: 23, name: 'john'}],
    [{age: 24, name: 'jane'}],
    [{age: 25, name: 'sam'}],
    [{age: 26, name: 'smith'}],
    [{age: 27, name: 'mike'}],
    [{age: 28, name: 'joanne'}],
    [{age: 29, name: 'lois'}],
    [{age: 30, name: 'paul'}]
  ];
  
 
let source  = [...source1,...source2].flat().reduce((initialState,currentObject)=>{
let [newSource,hashMap]=initialState
if( hashMap[currentObject.age] === undefined){
    hashMap[currentObject.age] = currentObject.name
    newSource.push(currentObject)
} 
return initialState
},[[],{}])[0]
  console.log({ source});

这个差不多有个O(n+m),二次扩散算子的复杂度为O(n+m)在将它们添加到数组中之前。function。另外,当尝试检查元素时,使用hashMap或对象总是很好的,这种方法的时间复杂度为O(1)当搜索而不是使用数组.includes时,其最坏情况为O(N).我知道这个解决方案来晚了,但我希望它能让每个人都受益。更少的是我忘记了脚本的时间复杂度是O(N * M)+ O(N * M)+ O(N * M)= 3O(N * M)这仍然是O(N * M),第一个O(N * M)是关于扩展算子的,第二个O(N * M)是关于平坦函数的,第三个是关于约化函数的,谢谢大家。

vyu0f0g1

vyu0f0g15#

只要你所有的数据都是相同的基本形状,我会尽快把它连接起来。你可以在reduce参数中使用数组重构([item]代替item)来有效地扁平化它,用reduce删除重复项,最后排序。

const data1 = [
 [{age: 23, name: "john"}],
 [{age: 24, name: "jane"}],
 [{age: 25, name: "sam"}],
 [{age: 26, name: "smith"}]
];

const data2 = [
 [{age: 23, name: "bob"}],
 [{age: 24, name: "billy"}],
 [{age: 25, name: "sam"}],
 [{age: 26, name: "brenda"}]
];

const result = data1.concat(data2)
  .reduce((acc, [item], i, arr) => {
    if (!acc[item.name]) acc[item.name] = item;
    if (i === arr.length - 1) return Object.values(acc);
    return acc;
  }, {})
  .sort((a, b) => a.name.localeCompare(b.name));
  
console.log(result);
exdqitrt

exdqitrt6#

我认为你的算法的复杂性在于"如何理解唯一性",因为你的数据似乎没有主键(例如id s)。
在我的示例中,元素是唯一的agename
也许你需要一种不同的方法。
排序和Map就足够简单了:)

const toHash = ({ age, name }) => `${age}_${name}`.toUpperCase();

const fn = R.pipe(
  R.concat,
  R.flatten,
  
  // Remove Duplicates
  R.indexBy(toHash),
  R.values,

  // sort
  R.sortBy(R.prop('age')),
);

const a = [
  [{age: 23, name: 'john'}],
  [{age: 24, name: 'jane'}],
  [{age: 25, name: 'sam'}],
  [{age: 26, name: 'smith'}],
  [{age: 30, name: 'paul'}],
];

const b = [
  [{age: 27, name: 'mike'}],
  [{age: 23, name: 'john'}],
  [{age: 28, name: 'joanne'}],
  [{age: 29, name: 'lois'}],
  [{age: 30, name: 'paul'}],
];

console.log(
  fn(a, b),
);
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.27.1/ramda.js" integrity="sha512-3sdB9mAxNh2MIo6YkY05uY1qjkywAlDfCf5u1cSotv6k9CZUSyHVf4BJSpTYgla+YHLaHG8LUpqV7MHctlYzlw==" crossorigin="anonymous"></script>

相关问题