@linthieda 所以 Java, C++, Scala, Javascript, Swift, Rust 的 reduce 都是刚好实现成了一个特性？各家的 API 基本都是 reduce(combiner, iterator) 这一个类似的定义，既然数据流的定义是一个 iterator，自然行为就是从前到后，从左到右。这也能被扳成“把实现造成的特性写在文档里让人 exploit”，佩服。

为了避免继续抬杠下去，我就再补充一点：reduce 既然是从 iterator 拿输入，顺序自然是由 iterator 决定。给个 reverse iterator，顺序就反过来——但仍然是有序的！

再说一遍，并行实现的 reduce 才是更特例化的版本：combiner 要 associative，数据集也从简单的流式输入变成要完全放进内存的能随机访问的数组。

@linthieda 哦，那 Java, C++, Scala, Javascript, Swift, Rust 的 reduce 实现大概都很奇葩了 :)

Reduce 的并行版本对 combine 函数是有额外要求的：必须遵循结合律。你玩惯的只是刚好是并行的版本。

@linthieda 你可能对 Python 的 reduce 有什么误解。官方文档 https://docs.python.org/3/library/functools.html :

Apply function of two arguments cumulatively to the items of iterable, from left to right, so as to reduce the iterable to a single value.

注意 from left to right 。

@mind3x @Shazoo @gwy15 上面贴错代码了，应该是

```
def list_extend(l, tuple):
l.extend(tuple)
return l

def shuffle(self, nums: List[int], n: int) -> List[int]:
return reduce(list_extend, zip(nums[:n], nums[n:]), [])
```

所以回复里不能写 markdown?

@gwy15 你说得对，我对 python 不熟，对 reduce()的实现想当然了——我以为至少 reduce 内部能做点优化，比如先用 list 存结果，最后再转成输出需要的类型。看了 reduce 的实现，发现就是进来什么 type 出去什么 type 。

@Shazoo 因为 Python 的 tuple 是 immutable list，每次 a+b 会把 a 和 b 的内容都复制一份，所以+是 O(N)而不是 O(1)，整个就是 O(N^2)了。

但这种容器类型的选择带来的副作用其实很容易解决，只要把 @oahebky 的代码稍加修改成：

```
def list_extend(l, tuple):
l.extend(tuple)
return l

def shuffle(self, nums: List[int], n: int) -> List[int]:
return reduce(add, zip(nums[:n], nums[n:]), [])
```

就从 O(N^2)变回正常的 O(N)。100000 次 benchmark 结果：
```
------------------------------------------------------------------------------- benchmark '100000': 2 tests -------------------------------------------------------------------------------
Name (time in ms) Min Max Mean StdDev Median IQR Outliers OPS Rounds Iterations
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_one_line_100_000 9.1088 (1.0) 9.3158 (1.0) 9.2438 (1.0) 0.0803 (1.0) 9.2957 (1.0) 0.1367 (1.14) 2;0 108.1806 (1.0) 10 12
test_iteration_100_000 10.0337 (1.10) 10.2967 (1.11) 10.1028 (1.09) 0.0854 (1.06) 10.0623 (1.08) 0.1199 (1.0) 1;0 98.9827 (0.91) 10 10
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
```
比 iteration 还快 10% :)

@gwy15 tuple.add -> N 是什么意思？ O(N)吗？

@Shazoo 他那也是随口一说，慢是慢在额外的内存分配，O(N)乘了个比较大的系数 k 而已，他一看这么慢那就是 O(N^2)了

@SmaliYu 他说的是错的，insert 不使其他迭代器失效本来前提就是单线程。多线程读写完全不是一回事

前年肉翻了，过了一年买了大 house，继续愉快写代码。

O 记的软件这么多年了还这德性……

老外过圣诞一样

另外 mbp 用的可不是标压的 CPU，都是 48EU+128M eDRAM 的 Iris Pro 集显

继续 14nm…

Lambda 了解一下。

@danmu17 可能我呆的是假欧美公司...

@KentY 他是学生，对收入大概没多少概念的

Pixel 1/2/3(全 XL)在手，每次升级后都比旧版本流畅。
要说卡，只有微信卡。

Leetcode medium 刷下来没什么问题的话，只要英语口语能应付面试，我可以内推荷兰 Uber，在阿姆斯特丹。公司给办签证给搬家费。裸辞没什么必要，不管去哪里都应该先拿到 offer 再说。