分享一行 Python 代码 `reduce(add, zip(nums[:n], nums[n:]))` - 来自解决 Leetcode #1470. Shuffle the Array 一题

[oahebky]

本来是不会想要分享发出来的。

但是因为在 comment 区发了解法，然后有人问解释一下这行代码，所以就解释了一下。

本着解释都解释了，敲了那么多行字，所以不如分享出来给更多的人看到。

---

(the)Problem

[问题] ：Leetcode#1470. Shuffle the Array

[描述] ：

给你一个数组 nums，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。

请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。

示例 1：

输入：nums = [2,5,1,3,4,7], n = 3
输出：[2,3,5,4,1,7] 
解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7，所以答案为 [2,3,5,4,1,7]

示例 2：N/A

示例 3：

输入：nums = [1,1,2,2], n = 2
输出：[1,2,1,2]

[提示] ：

• 1 <= n <= 500
• nums.length == 2n
• 1 <= nums[i] <= 10^3

来源：力扣（ LeetCode ） 链接： https://leetcode-cn.com/problems/shuffle-the-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

Solution

我的一行解法：

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

解释

对这一行代码的 explain：

https://leetcode.com/problems/shuffle-the-array/discuss/751957/Python-one-line-(Memory-Usage-less-then-100.00):-the-more-pythonic-way/629230

---

[marquina]

@msg7086 #20 对于熟悉函数式编程的人来说，这种写法的可读性当然不差，但并不是所有人都熟悉函数式编程。

[marquina]

@oahebky #12 槽点过多…建议还是先打好基础，至少先明白自己说的东西到底是什么，也建议对代码质量抱有一份敬畏之心。

[Shazoo]

@gwy15

请教下，为何 “一行” 写法的时间复杂度是 O(N^2) ?

看 benchmark 的结果，应该是 O(N^2)的样子；但是看代码，reduce 应该是累加 zip 迭代结果而已。时间复杂度应该是 O(2N)=O(N)啊。

[gwy15]

@Shazoo
list slice -> O(N)
zip -> O(N)
reduce -> N * O(tuple.add)
tuple.add -> N

[mind3x]

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

[mind3x]

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

[gwy15]

@mind3x 随口一说？
这个 reduce 展开就是
it = zip()
v: Tuple = next(it)
for pair in it:
....v = v + pair
return v

您来分析下这个是您说的 O(N) 吗？您觉得 python 还会把 v = v+pair 优化成 v.extend(pair) 吗？

[fakepoet]

po 主 append 的新解法不是“空间没有多余”，因为可以原地处理，不需要新开列表。

[ruanimal]

说实话，po 但凡对时间和空间复杂度比较敏感，就不会觉得这样写好。

[Shazoo]

@gwy15
多谢解释。你的拆解和我理解的一致。但是这个不涉及嵌套，似乎就是 O(KN)=O(N)的复杂度……

@mind3x
看 benchmark 的结果，不太像线性的。（我意思是，不太像你提及的“比较大的系数”。）不过你提及了耗时瓶颈在内存分配，这个能解释下？我咋觉得内存分配貌似不该如此耗时。

[gwy15]

@Shazoo
你仔细再想想？

这个 reduce 如果写成（其他语言的）
it = zip()
reduce((a, b) => {a.extend(b); return a;}, it, [])
那确实是 O(n) 的。

但是这个写的是 reduce(operator.add, it)，那执行的就是 a = a + b，a 和 b 都是 tuple，这不是 N^2 是什么？

[mind3x]

@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% :)

[mind3x]

所以回复里不能写 markdown?

[mind3x]

@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:]), [])
```

[oahebky]

@fakepoet

“原地处理” 的写法是这样的：

```
def solution(nums, n):
____ans = [0] * len(nums)
____for i in range(n):
________ans[2*i] = nums[i]
________ans[2*i+1] = nums[n+i]
____return ans
```

这就是我说的 “上面这样确实时间更快（甚至可以更快），空间也没有多余。” 中的 “可以更快” 的写法。

我 ”append“ 的解法并不是完全是”原地处理“ -- 不多解释。

====

我只是觉得这种（“原地处理”）写法不是太显而易见了吗，有几个人写不出这样的代码？
非我一行写法背后的运行逻辑 -- 涉及到 build-in function 、python 标准库及函数式编程的思维方式，（上面通用的解法）值得拿到这个 python 分区下分享吗？

[binux]

easy 题做起来有啥意思。。。

[Liyiw]

如#21 所说，了解函数式就觉得好懂
我觉得值得分享

[linthieda]

没有人说 reduce 的语义不保证执行顺序吗，楼主根本不懂 reduce

[mind3x]

@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 。

[linthieda]

@mind3x 我不知道，我玩惯了 cudnn 的 reduce，python 这种奇葩实现我不想说什么,