我正在处理一些对象数组,这些对象数组将使用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
如果能以正确的方式指导我,并向我展示实现我列出的所有这些操作的有效方法,我将不胜感激。谢谢
6条答案
按热度按时间pvabu6sv1#
这个解决方案应该能满足你的需求,如果有几个不同的返回数据的样本可以合并在一起,那会很有帮助,但是我试着重现了你在下面的解决方案中所解释的内容。
首先,我将所有不同的源数组组合成一个数组,然后将其扁平化为任何源数组具有的任何深度。如果此深度可变,我使用
flat(Infinity)
,但您也可以使用有限深度(flat(2)
或flat(3)
)。一旦我将数组扁平化,我就将其简单地转换为Set
以删除任何重复项,然后将其转换回数组。**此处的重要说明:因为数组和对象都是引用类型,所以即使两个源数组有相同的键值对对象,也不会被视为重复。为了真正过滤掉重复的对象,需要遍历两个对象的键,比较它们的关联值,如下所示:
ljsrvy3e2#
可以使用
Array.flat()
来展开多级数组。默认值为1,但是可以使用Array.flat(Infinity)
来展开多级数组。要删除重复项,现在可以将展平的数组缩减为Map,然后使用
Map.values()
迭代器和Array.from()
将其转换回数组:0sgqnhkj3#
这是一个不平凡的问题,也是一个学习设计数据结构的机会。这是一个长格式的答案,希望能给你自己做这些分析的工具。这篇文章使用布兰登善意的答案作为对比的基础。首先,我们需要检查一些JavaScript内置结构的属性。
我们从数组开始,如果我们有一个数组
input
,和一个已知的索引i
,我们可以在常数时间内取出元素。input[i]
。这意味着input
和i
的大小都不会影响获得答案所需的时间。这在Big O notation中表示为 * O(1)*。这是真的,因为数组实际上是指向内存中某个位置的指针,而i
是偏移量。找到元素是position + i
的一个 * 常量 * 计算,它总是一个简单的加法。然而,如果索引是未知的,而我们希望通过元素的值来找到它,我们必须一次扫描一个元素,这被称为线性复杂度,用 * O表示因为时间/空间的量相对于输入的大小
n
线性缩放。对于n = 3
元素的阵列,我们最多只需要检查3个元素就可以找到匹配项。对于n = 1000
数组,我们最多需要检查1,000个元素!几乎所有的数组运算都随输入数组的大小而缩放。这些线性运算包括
entries
、every
、fill
、filter
、find
、findIndex
、flat
、flatMap
、for..of
、forEach
、from
、includes
、indexOf
、join
、keys
、lastIndexOf
、map
、reduce
、reduceRight
、reverse
、slice
、some
、toString
和values
。线性运算的一个重要特性是,当它们嵌套时,它们变为二次,或 * O(n2)。一个简单的方法是两个嵌套的
for
循环, O(n)* O(n)= O(n * n)*。如果n = 1000
,这可能需要1,000,000次计算。这也适用于其他线性运算,如嵌套在filter
中的includes
-接下来我们来看看JavaScript的对象,和数组一样,如果我们有一个对象
input
和一个已知的键query
,我们可以在常数时间内获取一个值,* O(1)*-现在假设我们有两个对象,
foo
和bar
,并希望确定它们是否相等,我们的函数isEqual
将Object.keys
,* O(n),其中every
, O(n),并且嵌套includes
, O(n),使用属性查找, O(1)。这是 * O(n + n (n +1)),它简化为 * O(n2)。这里的includes
检查是不必要的,但我们按照Brandon的例子进行比较-对于最后一个示例,我们使用一个对象数组
input
和一个query
对象,并尝试查找查询的索引。(n2)*。当我们将这个运算嵌套在线性findIndex
中时,我们得到 * O(n)**O(n2)= O(n3)。如果n = 1000
,这将需要1,000,000,000次计算!正如您所看到的,线性运算的计算复杂度可以非常快速地扩展-现在让我们分析一下Brandon的回答。我不想让任何人认为我在挑他的毛病。他的程序是有效的,并且返回正确的结果。然而,随着输入大小的增加,它的进程 * 可以 * 让你的cpu停止。如果这个程序被循环使用,或者每次UI刷新都发生,它 * 可能 * 是个问题。
| 复杂性|操作|
| - ------|- ------|
| * 第(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)-除了
get
之外,Map还提供了has
,它可以回答我们的特定Mapm
* 是否具有 * 特定键k
-我们可以使用Map的高性能属性来编写我们自己的递归Map类型
recmap
。在我们深入研究它的实现之前,下面是我们希望它如何工作--我们可以将上面的
t
可视化为嵌套Map的递归序列-用户不需要理解Array、Object或Map就可以有效地使用它。这被称为数据抽象,它是编写有效数据结构的一个重要属性。我们将构建数据类型,以便嵌套结构由模块的操作自动管理-
我们的
recmap
是extremely fast,能够在不到一秒的时间内过滤一百万个值,这很棒,但是有一个小问题:这个问题的目的是将对象彼此比较。我的第二个数据结构
坚持住,我们几乎完成了。我们围绕Map设计了
recmap
,这样用户就不必担心管理嵌套结构。我们将围绕recmap
构建unique
,这样用户就不必担心嵌套的Map或键序列。相反,我们可以简单地创建一个empty
集合,并自由地使用add
来获取我们想要的任意多个值-输入对象的键的顺序并不重要。我们总是会得到正确的答案-
如果我们尝试用不同的键顺序来
add
相同的对象也没关系。它只会被添加一次-唯一
由于我们现有的
recmap
,这个模块更容易编写。它是recmap.set
和recmap.has
的一个简单 Package 器,添加了一个toKey
函数,负责输入对象的排序。这种从简单数据结构构建复杂数据结构的技术是每个函数式程序员都必须掌握的-上面注意我们没有导出
toKey
,这是一个private函数,仅供我们的模块使用;用户无需担心的实现细节。还要注意的是,我们调用了recmap.values
,现在我们将实现它-基准
我们已经取得了沿着进展,现在是时候来衡量一下我们的
unique
数据结构和布兰登答案中提出的线性filter
算法之间的差异了,为了比较这两种算法,我们将使用randCoord
来生成随机{ x, y }
对象--unique
算法迭代input
和add
的每个元素到我们的集合-如上所述,
filter
算法是filter
-〉find
-〉every
-〉includes
的多元链。大小为
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
|一百二十四块九十九|千分之一|上面我们比较了只有两个字段的对象。在最后一个基准测试中,让我们看看两种算法在处理具有七个字段
first
、last
、age
、phone
、gender
和email
的对象时的比较结果。这等于 * 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分|
编写我们自己的数据结构的一大优势是我们可以根据需要改变它们的行为和调整它们的性能。如果我们添加一个对象,并尝试使用该对象的子集查找,我们将得到
true
答案-如果
t
的底层表示为-这意味着
has(t, {a: 1})
将找到下面的嵌套Map,并返回true
-你可能认为这是
unique
的问题,但这个问题也存在于recmap
中。这是一个bug,我们可以通过引入一个简单的checksum
-不需要对
unique
进行任何更改。我们可以继续工作了-我们的
recmap
模块使用Map
作为底层表示,但用户不知道(不应该知道)这一点。如果用户尝试将自己的Map
插入到混合中,会发生什么情况?引入wrap
实用程序,我们可以允许用户插入 * any * 值类型,并防止泄漏任何实现细节-我们围绕原生Map设计了
recmap
,它提供了一些其他有用的方法。我们可以添加entries
和keys
来提供更完整的实现-没有功能演示的答案是不完整的,imo。我已经内联了
recmap
和unique
模块,因为我们仅限于一个"文件"进行演示。我们将从Brandon的帖子中借用输入示例-所有重复的都被删除了-
fumotvh34#
这个差不多有个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)是关于平坦函数的,第三个是关于约化函数的,谢谢大家。
vyu0f0g15#
只要你所有的数据都是相同的基本形状,我会尽快把它连接起来。你可以在reduce参数中使用数组重构(
[item]
代替item
)来有效地扁平化它,用reduce删除重复项,最后排序。exdqitrt6#
我认为你的算法的复杂性在于"如何理解唯一性",因为你的数据似乎没有主键(例如
id
s)。在我的示例中,元素是唯一的
age
和name
。也许你需要一种不同的方法。
排序和Map就足够简单了:)