V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
oahebky
V2EX  ›  Python

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

  •  
  •   oahebky · 2020-07-25 14:07:02 +08:00 · 4088 次点击
    这是一个创建于 1586 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    但是因为在 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


    第 1 条附言  ·  2020-07-25 17:50:15 +08:00

    如果网友点击来是想看这行代码背后运行的逻辑的话,建议先看我“详情”里面给的链接,里面有对这行代码是怎么运行的解释。

    然后可以看看评论区,里面有部分没有情绪化的评论有说明这行代码缺陷在哪里。

    ====

    如果网友点进来觉得这行代码写得不好的原因是它不是最优的,那么我同意你的看法,

    def solution(nums, n):
        ans = []
        for i in range(n):
            ans.append(nums[i])
            ans.append(nums[n+i])
        return ans
    

    上面这样确实时间更快(甚至可以更快),空间也没有多余。

    如果觉得这道题这么解近似最优了,很开心。 我也没话可说,因为我发这个帖子不是来分享这道题的最优解的

    如果预设立场要来贬这行代码,然后又把哪里不好的地方说错了,那么我认为这位网友就是杠精。

    第 2 条附言  ·  2020-07-27 11:38:32 +08:00

    关于本帖初衷

    “一行”在程序员圈子,对于使用不同语言的 promgrammer 来说确实相对来说属于较敏感词。 不过也确实没想到有部分人反应会这么强烈,为了喷而喷,喷不到点上。

    在我看来像函数式编程的语言和支持部分函数式编程的语言,能够合理使用一行的写法就该使用一行的写法。 人家弄一个函数出来,就是为了把定义变量、循环语句、等等重复的工作省掉。

    我分享这行代码的出发点是因为几个高阶函数在解决这个问题的应用场景很典型

    -- 个人认为是个很好的学习或了解 zip, reduce 的场景,以及涉及到的 functools、和 operator 标准库等。

    ===

    关于算法性能问题

    我在做这道题的时候,确实没有考虑 time complexity 和 space complexity;因为一般写法的最优解真的太显而易见。 所以我是从 know higher order function,practice higher order function 的考虑来实现这道题的。

    讨论区正如上一个附言所说,有部分人指出这行的代码缺陷,确实有指到真正的点上。 从结论来说,谢谢 @mind3x 的写法更新,time complexity 为 O(n) 的写法可以更新成这样:

    def list_extend(l, tuple):
        l.extend(tuple)
        return l
    
    class Solution:
        def shuffle(self, nums: List[int], n: int) -> List[int]:
            return reduce(list_extend, zip(nums[:n], nums[n:]), [])
    

    如果要写成一行,其实也没有 “强扭”:

    def solution(nums, n):
        return reduce(lambda l, t: (l.append(t), l)[-1], zip(nums[:n], nums[n:], [])
    

    不过这么写,由于 reduce 多了 initial 参数,理解起来要多花点力气,脱离原本发 functools.reduce(operator.add, zip(nums[:n], nums[n:])) 这一行的初衷。

    关于性能分析,为什么是 $O(n^2)$ @gwy15 在评论区已经解释清楚了。

    注意一下我在评论区说的

    l = [1, 2]
    l.append(1)
    

    l = [1, 2]
    l = l + [1]
    

    的区别。

    关于 python 内置类型等方面的使用在算法性能上的分析,这一点有兴趣的朋友可以从 《python 算法教程》一书中了解。其中有说道 list、set、dict 需要注意的地方。

    $O(tuple.__add__)$ => $O(n)$ 会造成

    reduce(tuple.__add__, <tuple iter>) => $O(reduce) * O(tuple.__add__)$ => $O(n^2)$

    的性能问题确实是我在使用这个解法的时候没有去严格分析的。

    我了解 tuple + tuple 的问题,不过看了题目 1<=n<=500,我确实没有细想去分析出 $O(n^2)$ 的缺陷。 审题会看一下 n 范围,我想刷过上百道 leetcode 题的朋友应该会懂,这是个刷出来的习惯。因此我个人潜意识里面知道 tuple + tuple 会拖慢速度,但是由于取值范围小,没有去分析是 $O(n)$ 的慢还是 $O(n^2)$ 的慢。

    $O(n)$ 写成 $O(n^2)$ 肯定是不好的,正如评论区某个人说的面试这么写是要被挂掉的。

    第 3 条附言  ·  2020-07-27 11:45:15 +08:00

    总结

    “append”是希望还在学 python 的朋友不要被部分人的节奏带偏了。

    本帖初衷是分享一个 python 的 build-in function,functools、operator 标准库,函数式编程方面的东西,因为在 leetcode 的 comment 区解释了一下这一行代码的运行过程,对于对 python 这方面写法还不甚了解的朋友我认为是值得分享的。

    本帖原话也没有说这行代码性能 OK,本帖潜意思也没有说这行代码性能 OK,因为敲下键盘之前就知道这么写速度是较慢的;

    (再强调一下,针对这道题来说,(各种语言)通用的一般写法写成最优不是很显而易见的吗?这道题就那么写完,有增加什么知识吗?)做到这道题刚好拿来练手 python 的高阶函数和了解函数式编程;是用来 know 和 practice to master 的。

    但是另一方面, time complexity 是比 higher order function 更重要的;所以评论区跑代码,改代码指出原贴的一行代码的性能问题是十分有价值的,所以这一行代码也可以作为"在产品中滥用" one-liner 的反例

    附:

    虽然说该行代码在产品中是反例。 不过在产品中,遇到这么简单的问题,个人认为应该这么写:

    def solution(nums, n):
        for i in range(n):
            yield nums[i]
            yield nums[n+i]
    

    使用:

    for i in solution(the_nums, the_n): ...

    or

    reformat_nums = list(solution(the_nums, the_n))

    如果是按原题意,可能的实际问题是成对取结果,可以直接这么写:

    return zip(nums[:n], nums[n:])

    python 还有 itertools 库可以提供类似这样问题的实用 function。

    leetcode 本来就是用来做练习、掌握知识点用的;总不能说所有 leetcode 题上的“最优解”用在生产环境也是“最优的”吧?

    不要被情绪化的、主观偏见的评论带偏了。

    总结这么多,是想说,这个贴初衷是分享 python 语言支持部分函数式编程范式的一种类型的写法,以及还有很多实用的 python 标准库。但是有杠精乱喷,所以我强调下不要被杠精带偏节奏,本帖没有说这行解法最好,本帖的初衷也不是杠精口中的那类。

    然后有人在评论区指出本帖这行代码的性能问题,这一点我知道会慢,但是确实没有仔细分析;所以对于性能方面讲到重点的地方确实没有错。

    你应该看到 reduce(add, zip(nums[:n], nums[n:])) 这样写法的“好懂”之处在哪里;

    同时经过本帖的讨论,知道 reduce(add, <tuple iter>) 的性能问题在哪里(reduce(add, <int iter>) 即没有这个性能问题)。另一方面我后面也说了,这个问题本质上不是“一行”的问题,不是代码写成一行性能就会变差,在产品代码中,遇到本帖这类问题,有更好的实现方法(上面“附”以及写出来了)。

    而不是因为你(预设立场)反对“python 语言可以一行解决一些问题”觉得不爽,然后过来贬低“一行”代码的写法。

    指明代码缺陷在哪里没有问题,我认同这个问题,可以往细节分析。但是预设立场为喷而喷,这种杠精我或不客气回复,或懒得回复。

    ======

    结束语

    引用牛人的话作为进一步阐明这个分享帖的出发点,和结束语

    “要不这样吧, 如果编程语言里有个地方你弄不明白, 而正好又有个人用了这个功能, 那就开枪把他打死。 这比学习新特性要容易些,然后过不了多久, 那些活下来的程序员就会开始用 0.9.6 版的 Python, 而且他们只需要使用这个版本中易于理解的那一小部分就好了(眨眼) 。”[^1] —— Tim Peters

    [^1]: 给 comp.lang.python Usenet 小组的留言,2002 年 12 月 23 日, “Acrimony in c.l.p”( https://mail.python.org/pipermail/python-list/2002-December/147293.html ) 。

    53 条回复    2020-07-27 10:38:43 +08:00
    msg7086
        1
    msg7086  
       2020-07-25 14:14:46 +08:00   ❤️ 2
    顺便 Ruby 里可以用:
    nums.each_slice(n).to_a.transpose.flatten

    当然也可以用很朴素的:
    nums[0..n-1].zip(nums[n..-1]).flatten
    jmc891205
        2
    jmc891205  
       2020-07-25 14:36:47 +08:00 via iPhone   ❤️ 9
    本来遍历一遍就可以解决的问题,用了 reduce 和 zip 等于遍历了两遍。
    本来开一个数组就可以解决的问题,用了 zip 和 slice 就需要额外内存去保存他们的返回值。

    时间和内存都浪费了,还降低了代码可读性。
    oahebky
        3
    oahebky  
    OP
       2020-07-25 15:03:06 +08:00
    @jmc891205

    “额外内存去保存他们的返回值”???
    “降低了代码可读性”???

    你就是传说中的杠精?

    这个是发在 Python 主题下的帖子,我写的是 python3 的代码,不懂 python3 的特性还有不了解高阶函数就不要出来秀智商了。
    carlclone
        4
    carlclone  
       2020-07-25 15:05:06 +08:00 via Android
    这是算法题不是接口调用题
    oahebky
        5
    oahebky  
    OP
       2020-07-25 15:12:13 +08:00
    @carlclone

    那么你是觉得有多少人写不出这道题的与编程语言无关的通用解法?

    别一上来就杠。看懂这一行代码背后的执行过程了吗?

    看懂的人也就不会说出你这样的话了。
    jmc891205
        6
    jmc891205  
       2020-07-25 15:25:08 +08:00
    @oahebky
    那请教一下,python3 有什么高级特性,可以在求 zip(nums[:n], nums[n:])时不使用额外的 O(n)内存保存两个 slice 产生的新 list,而直接求出 zip 的结果?

    代码可读性见仁见智,没有一个评价标准。不过对于一个 trival solution,应该没有人会读不懂还要请你解释一下。
    marquina
        7
    marquina  
       2020-07-25 15:34:44 +08:00   ❤️ 9
    楼上说得没错。当执行 nums[:n]和 nums[n:]的时候,就相当于复制了一遍原数组,这就是额外内存消耗。
    zip 确实是迭代器,不需要额外内存,但 zip 返回的是 tuple,对 tuple 做 add 需要生成新 tuple+销毁旧 tuple (因为是不可变对象),这又是额外的内存+性能消耗。
    最要命的是,最后该函数返回的是 tuple,但题目要求的是 list,如果判题器加个 ret type checker,或需要对返回值进行 append 操作,那就完蛋了。
    总之,一行代码看起来很 nb,但很多时候也只是看起来 nb 罢了。
    gjquoiai
        8
    gjquoiai  
       2020-07-25 15:47:13 +08:00
    没有指针的语言就是蛋疼。。把一个数组分成两半遍历都麻烦的不行
    leeshuai
        9
    leeshuai  
       2020-07-25 15:57:03 +08:00
    他扣帽子一直可以的
    ChanKc
        10
    ChanKc  
       2020-07-25 16:11:47 +08:00
    其实第一时间能想到这个写法的话,在周赛里面还是很有用的
    fishCatcher
        11
    fishCatcher  
       2020-07-25 16:15:08 +08:00 via iPhone   ❤️ 1
    任何反对 lz 的声音都被归类为一上来就杠
    oahebky
        12
    oahebky  
    OP
       2020-07-25 16:32:45 +08:00
    @marquina

    复制一遍数组没错。
    不过如果是 C/C++ 之类的静态语言,也是第一部要创建一个同样长度的数组用来放值返回吧?

    另外一定要这么扣细节的话,写成 `(nums[i] for i in range(n))` 够不够再省内存?
    (实际上这个 solution 在 python3 的所有提交中已经是 less 100.00% 的 memory usage 了。)

    各位看官觉得是 zip(nums[:n], nums[n:]) 好呢?
    还是 zip((nums[i] for i in range(n)), (nums[j] for j in range(n, len(nums)))) 好呢?

    ----

    返回 tuple 和 题目要求 list 确实值得注意,不过 python 中写代码,类型本质是“鸭子类型”和“蟒蛇类型”区别,不然也就不是动态类型了。

    ----

    我从头到尾都没有说这个解法性能好。
    我的目的也不在于性能,就原题 `1<=n<=500` 的题目,遍历一遍和遍历两遍关系很大吗?


    ----

    “一行代码看起来了很 nb”?

    `functools.reduce(operator.add, zip(nums[:n], nums[n:]))` 这一行代码是为了 nb 吗?
    如果你是这么觉得的话,那么就没有讨论代码的意义了,因为从一开始就预设立场,把我分享这行代码的意图曲解成为了 nb 。
    YuTengjing
        13
    YuTengjing  
       2020-07-25 16:41:39 +08:00
    感叹一下,刷了将近 300 道题的我,现在看到很多文章的原题大都可以很快想出最优解。以前没过刷题的时候特别怕面试被问算法题,觉得自己很虚,觉得自己很容易被替代~
    oahebky
        14
    oahebky  
    OP
       2020-07-25 16:49:52 +08:00
    @gjquoiai

    不知道
    for i in range(n)
    for j in range(n, len(nums))

    这样分两半哪里麻烦?


    可以说几个 python 没有指针很麻烦的实例,个人比较感兴趣,可以学习下。
    gwy15
        15
    gwy15  
       2020-07-25 16:59:31 +08:00   ❤️ 10
    正常的写法:空间(额外) O(1),时间 O(n)
    你的“一行”写法:空间(额外) O(n),时间 O(n^2),伴随大量 GC

    我写了个 benchmark,你的“一行解法”仅仅 n=100k 的规模,就要 30s 一次,对比正常写法 24ms,慢了一千倍以上。

    https://imgchr.com/i/UzxYLQ

    https://gist.github.com/gwy15/22616306f560f65d77b6ca23954e91a3

    你当然可以说“题目就是 n~500,这么写也能过”。能过是一回事,明明有性能更好也更好理解的代码不用,非要这么写,那以后系统瓶颈的时候你是打算拿着 cProfile 慢慢找瓶颈吗?

    至于拿 leetcode 的排行说性能,leetcode 的运行时间打底就是 40ms,能说明啥?你加个 time.sleep(0.03) 都可能是 40ms 。

    拿高阶函数写又不是什么很有优越感的事情,楼主上来就“杠精”、“不懂 python3”、“不了解高阶函数”、“不要出来秀智商”,这个行为让人觉得很莫名其妙。
    monkeymonkey
        16
    monkeymonkey  
       2020-07-25 17:13:09 +08:00 via iPhone   ❤️ 5
    lz 典型的学了一点小技巧出来 showoff 被打脸,一瓶子不满半瓶子晃荡。所谓的 python“高级”特性也不过是程序员基本功而已,楼上各位提到时间复杂度空间复杂度,GC,profiling,这些才是真正的“高级”内容。
    lysS
        17
    lysS  
       2020-07-25 17:23:32 +08:00
    楼主学习到了一个小技巧,感觉自己的知识又提升了;你们居然不迎合楼主,可恶🐶
    oahebky
        18
    oahebky  
    OP
       2020-07-25 17:29:43 +08:00
    @gwy15

    实际生产环境,能有 n = 100k 的规模我会这么写:

    def func(nums, n):
    ____for i in range(n):
    ________yield nums[i]
    ________yield nums[n+i]

    我发这行没有说是最优解,也没有它是最优解的潜意思。

    各位急着贬的网友这么想我也没有办法,只能说我只想给其它 python programmer 多了解一些使用 Python 特性的不同的 solution 。

    另外,不是算法的时间是 O(n^2)。
    调用函数就要了解函数,如果不了解确实不适合这么干。

    上面网友说的对,这个解法确实有大量 GC 。时间是在 tuple 的 `+` 运算上。
    换句话说,

    ```python
    def sum1(iterable):
    ____ans = 0
    ____for i in iterable:
    ________ans += i
    ____return ans
    ```

    的“通用”写法和

    ```python
    def sum2(iterable):
    ____functools.reduce(operator.add, iterable)
    ```

    都是 O(n) 的解法,而不是用了 reduce 或者 add 就变成 O(n^2) 的解法。

    ----

    而是 operator.add((1, 2), (1, 2)) 与:
    ```
    l = [1, 2]
    l.append(1)
    l.append(2)
    ```
    的区别。


    类似是
    ```
    l = [1, 2]
    l.append(1)
    ```

    ```
    l = [1, 2]
    l = l + [1]
    ```
    的区别。

    所以你要是说“不懂不要乱用”,那确实如此。
    但是你要说因为“多行写成一行代码”复杂度会 O(n) 变 O(n^2)

    那我建议你再仔细了解一下背后的原因。
    huskar
        19
    huskar  
       2020-07-25 17:30:27 +08:00 via Android
    说实在的,这解法真不怎么样…性能和可读性一样也不占
    msg7086
        20
    msg7086  
       2020-07-25 17:43:45 +08:00
    说性能问题也就算了,这题还能怎么写得比 zip()更可读?
    虽然我起手写了 transpose 但是我觉得 zip 比 transpose 要更可读一些。
    marquina
        21
    marquina  
       2020-07-25 18:30:00 +08:00 via Android
    @msg7086 #20 对于熟悉函数式编程的人来说,这种写法的可读性当然不差,但并不是所有人都熟悉函数式编程。
    marquina
        22
    marquina  
       2020-07-25 18:34:00 +08:00 via Android
    @oahebky #12 槽点过多…建议还是先打好基础,至少先明白自己说的东西到底是什么,也建议对代码质量抱有一份敬畏之心。
    Shazoo
        23
    Shazoo  
       2020-07-25 19:10:16 +08:00
    @gwy15

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

    看 benchmark 的结果,应该是 O(N^2)的样子;但是看代码,reduce 应该是累加 zip 迭代结果而已。时间复杂度应该是 O(2N)=O(N)啊。
    gwy15
        24
    gwy15  
       2020-07-25 19:15:36 +08:00   ❤️ 3
    @Shazoo
    list slice -> O(N)
    zip -> O(N)
    reduce -> N * O(tuple.add)
    tuple.add -> N
    mind3x
        25
    mind3x  
       2020-07-25 19:16:50 +08:00   ❤️ 1
    @Shazoo 他那也是随口一说,慢是慢在额外的内存分配,O(N)乘了个比较大的系数 k 而已,他一看这么慢那就是 O(N^2)了
    mind3x
        26
    mind3x  
       2020-07-25 19:20:31 +08:00
    @gwy15 tuple.add -> N 是什么意思? O(N)吗?
    gwy15
        27
    gwy15  
       2020-07-25 19:45:28 +08:00
    @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
        28
    fakepoet  
       2020-07-25 20:58:21 +08:00
    po 主 append 的新解法不是“空间没有多余”,因为可以原地处理,不需要新开列表。
    ruanimal
        29
    ruanimal  
       2020-07-25 21:11:48 +08:00
    说实话,po 但凡对时间和空间复杂度比较敏感,就不会觉得这样写好。
    Shazoo
        30
    Shazoo  
       2020-07-25 21:23:24 +08:00
    @gwy15
    多谢解释。你的拆解和我理解的一致。但是这个不涉及嵌套,似乎就是 O(KN)=O(N)的复杂度……

    @mind3x
    看 benchmark 的结果,不太像线性的。(我意思是,不太像你提及的“比较大的系数”。)不过你提及了耗时瓶颈在内存分配,这个能解释下?我咋觉得内存分配貌似不该如此耗时。
    gwy15
        31
    gwy15  
       2020-07-25 21:42:25 +08:00   ❤️ 2
    @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
        32
    mind3x  
       2020-07-25 22:31:22 +08:00   ❤️ 2
    @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
        33
    mind3x  
       2020-07-25 22:32:13 +08:00
    所以回复里不能写 markdown?
    mind3x
        34
    mind3x  
       2020-07-25 22:35:48 +08:00   ❤️ 1
    @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
        35
    oahebky  
    OP
       2020-07-26 00:42:07 +08:00
    @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
        36
    binux  
       2020-07-26 00:59:51 +08:00
    easy 题做起来有啥意思。。。
    Liyiw
        37
    Liyiw  
       2020-07-26 01:05:21 +08:00
    如#21 所说,了解函数式就觉得好懂
    我觉得值得分享
    linthieda
        38
    linthieda  
       2020-07-26 01:59:49 +08:00 via iPad
    没有人说 reduce 的语义不保证执行顺序吗,楼主根本不懂 reduce
    mind3x
        39
    mind3x  
       2020-07-26 02:06:03 +08:00
    @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
        40
    linthieda  
       2020-07-26 02:10:21 +08:00 via iPad
    @mind3x 我不知道,我玩惯了 cudnn 的 reduce,python 这种奇葩实现我不想说什么,
    mind3x
        41
    mind3x  
       2020-07-26 02:19:07 +08:00
    @linthieda 哦,那 Java, C++, Scala, Javascript, Swift, Rust 的 reduce 实现大概都很奇葩了 :)

    Reduce 的并行版本对 combine 函数是有额外要求的:必须遵循结合律。你玩惯的只是刚好是并行的版本。
    linthieda
        42
    linthieda  
       2020-07-26 02:19:13 +08:00 via iPad
    @mind3x 但是我还是想说,我面的人如果这样用 reduce 我肯定给 N, 我不 care 一个具体语言里它怎么玩他的 API, 但你解题必须要体现出你的 cs 基本功, 非对易算符用了 reduce 结果是 inconsistent 的.
    linthieda
        43
    linthieda  
       2020-07-26 02:23:19 +08:00 via iPad
    @mind3x 大概是把实现造成的特性写在文档里让人 exploit 让我觉得奇葩.
    mind3x
        44
    mind3x  
       2020-07-26 03:00:57 +08:00   ❤️ 1
    @linthieda 所以 Java, C++, Scala, Javascript, Swift, Rust 的 reduce 都是刚好实现成了一个特性?各家的 API 基本都是 reduce(combiner, iterator) 这一个类似的定义,既然数据流的定义是一个 iterator,自然行为就是从前到后,从左到右。这也能被扳成“把实现造成的特性写在文档里让人 exploit”,佩服。

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

    再说一遍,并行实现的 reduce 才是更特例化的版本:combiner 要 associative,数据集也从简单的流式输入变成要完全放进内存的能随机访问的数组。
    msg7086
        45
    msg7086  
       2020-07-26 04:36:54 +08:00
    @linthieda Reduce 本来就只是操作而非具体的实现。
    就像 Hash 哈希表一样,有些实现里哈希表是按 Key 排序的,有些实现里哈希表是保持顺序的,有些实现里哈希表是乱序的。不能因为你用的 Hash 正好是乱序的,就把其他语言里有序的哈希表给批判一通吧?
    同样 Reduce 本来指的也就是「归纳」操作,把多个输入处理成单个输出,至于是 Ordered reduce 还是 Unordered reduce,完全是看你语言的实现而已。没用过 CuDNN,但是很多语言里的 Reduce 都是 Ordered 处理的,所以你不 care 具体语言的这种想法本身就是错的。
    Actrace
        46
    Actrace  
       2020-07-26 09:38:01 +08:00
    做程序员久了就是这样。以为自己写的代码别人看不懂就能突显优越感。这也是为什么这些算法网站能火的原因。
    不过在老板眼里,业务能力差不能赚钱的话,立马就会被换掉~😂
    在队友眼里,挖了一堆坑,谁都无法接手,恨不得爆锤~😂
    capbone
        47
    capbone  
       2020-07-26 11:11:41 +08:00   ❤️ 1
    reshape 一下不是更符合直觉么?

    print(np.reshape(x, (2, -1)).T.flatten().tolist())
    zzth370
        48
    zzth370  
       2020-07-26 11:21:20 +08:00
    看到各位大佬发言,学习到了,哈哈
    lxilu
        49
    lxilu  
       2020-07-27 00:29:58 +08:00 via iPhone
    「一行」向来敏感,要是没有这个词肯定少很多争吵,我想楼主应该知道
    oahebky
        50
    oahebky  
    OP
       2020-07-27 09:23:08 +08:00
    @lxilu
    ======
    回复:

    “一行”确实相对来说属于较敏感词。不过没想到有部分人反应会这么强烈,为了喷而喷,喷不到点上。

    在我看来像函数式编程的语言和支持部分函数式编程的语言,能够合理使用一行的写法就该使用一行的写法。
    人家弄一个函数出来,就是为了把定义变量、循环语句、等等重复的工作省掉。

    我分享这行代码的出发点是因为几个高阶函数在解决这个问题的应用场景很典型 - 个人认为是个很好的学习 zip, reduce 的场景。
    (如果更新成
    `return reduce(lambda l, t: (l.append(t), l)[-1], zip(nums[:n], nums[n:])`
    则没有 $O(tuple.\_\_add\_\_)$ => $O(n)$ 会造成
    reduce(tuple.\_\_add\_\_, <tuple iter>) 的 $O(n^2)$ 性能问题)

    ======

    “要不这样吧, 如果编程语言里有个地方你弄不明白, 而正好又有个人用了这个功能, 那就开枪把他打死。 这比学习新特性要容易些,然后过不了多久, 那些活下来的程序员就会开始用 0.9.6 版的 Python, 而且他们只需要使用这个版本中易于理解的那一小部分就好了(眨眼) 。”[^1] —— Tim Peters

    [^1]: 给 comp.lang.python Usenet 小组的留言,2002 年 12 月 23 日, “Acrimony in c.l.p”( https://mail.python.org/pipermail/python-list/2002-December/147293.html ) 。
    Shazoo
        51
    Shazoo  
       2020-07-27 09:26:41 +08:00
    @gwy15
    @mind3x

    多谢二位解释~ tuple.add 的确是 O(N) 的操作。之前没多想过这个,直觉认为是 extend 类的操作…… immutable list 点醒梦中人。
    necomancer
        52
    necomancer  
       2020-07-27 09:49:59 +08:00   ❤️ 1
    @capbone np.reshape(x, (2,-1)).ravel('F').tolist(),少个转置^^
    shunia
        53
    shunia  
       2020-07-27 10:38:43 +08:00
    虽然我不懂 python,但是我不影响我看 44 楼打脸打的好爽。最关键打脸就算了,还用英文打回去,痛快。
    44 楼上面的兄弟让我想起三十而已里面的售货员,演着演着突然开始飙英文,这也就算了还自己骗自己(明知不婚是坑)。
    PS: 我对剧和演员和演员所代表的人群都没有任何偏见,纯粹联想到而已
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4594 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 10:10 · PVG 18:10 · LAX 02:10 · JFK 05:10
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.