您现在还未登录!

登录/注册后可体验更多内容。如未找到验证邮件,请查看垃圾箱或"点击右上角头像"-->"编辑资料"重新发送。

QQ手机/电脑邮箱无法在移动端注册/验证,使用网页版即可。请使用非国产浏览器(建议Chrome/Firefox)登录。

PS:密码找回重做中,请点击此处来找回。点击边栏前往其余页面。

1,1,4,5,1,4按顺序进行四则运算可以得到的所有结果


  • 木毛认可

    相信我不是第一个写类似程序的homo,但我用了homo最喜欢的语言(Lisp(因为括号很多(无力)))

    (不会用Markdown,排版混乱请谅解)


    1. 首先介绍一下前缀表达式(波兰式)

    • 使用前缀表达式来表示四则运算可以忽略运算符优先级带来的问题,因此在计算的时候比较方便。我的结果全是用前缀表达式来表示的(因为我比较懒),要是想变成常见的中缀表达式的话,也很简单,举个🌰,比如从附件里面找到一行结果等于19的:

    ((* 1 (* 1 (* 4 (- 5 (/ 1 4))))) res= 19)

    • 先把每一层嵌套中的运算符和第一个操作数换位置:

    ((1 * (1 * (4 * (5 - (1 / 4))))) res= 19)

    • 再根据优先级去括号:

    (1 * 1 * 4 * (5 - 1 / 4) = 19)

    完成

    (racket默认自带分数表达,所以完全不用担心野蛮浮点运算造成的误差)

    (注意即便换成中缀表达式114514的顺序也没变)

    2. 再说一下思路

    • 算出 (1 1 4 5 1 4)这个列表所能构成的所有“先左再右遍历为114514”的二叉树(只在叶子上有数字,以列表的列表表示)

    (1 1 4 5 1 4) ==>
    '((1 (1 (4 (5 (1 4)))))
    (1 (1 (4 ((5 1) 4))))
    (1 (1 ((4 5) (1 4))))
    (1 (1 ((4 (5 1)) 4)))…(后略)

    • 加上运算符号

    ===>
    '((+ 1 (+ 1 (+ 4 (+ 5 (+ 1 4)))))
    (- 1 (+ 1 (+ 4 (+ 5 (+ 1 4)))))
    (* 1 (+ 1 (+ 4 (+ 5 (+ 1 4)))))
    (/ 1 (+ 1 (+ 4 (+ 5 (+ 1 4)))))
    (+ 1 (- 1 (+ 4 (+ 5 (+ 1 4)))))
    (- 1 (- 1 (+ 4 (+ 5 (+ 1 4)))))…(后略)

    • 进行运算(顺便排了序)

    ===>
    '(((- 1 (* (* (+ 1 4) 5) (+ 1 4))) res= -124)
    ((- 1 (* (+ 1 4) (* 5 (+ 1 4)))) res= -124)
    ((* (* (* (+ 1 1) 4) 5) (- 1 4)) res= -120)
    ((* (* (+ 1 1) (* 4 5)) (- 1 4)) res= -120)
    ((* (- 1 (* (+ 1 4) 5)) (+ 1 4)) res= -120)
    ((* (* (+ 1 1) 4) (* 5 (- 1 4))) res= -120)…(后略)

    (结果不一定对,如果有错误或疏漏请博识兄贵指出,谢谢茄子)


    下面是代码

    #lang racket
    (define ls (list 1 9 1 9))
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;helper
    (define flatmap
      (lambda (f ls)
        (if (eq? ls '())
            '()
             (append (f (car ls))
                     (flatmap f (cdr ls))))))
    (define Qsort
      (lambda (comp ls)
        (if (eq? ls '())
            '()
            (let ((fst (car ls))
                  (res (cdr ls)))
              (let ((l (filter (lambda (num) (comp num fst)) res))
                    (r (filter (lambda (num) (not (comp num fst))) res)))
                (append (Qsort comp l) (append (list fst) (Qsort comp r))))))))
    
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;(1 2 3) -> [(1 (2 3))  ((1 2) 3)]
    (define divide
      (lambda (ls)
        (define split
          (lambda (ls)
            (define inner
              (lambda (fst snd)
                (if (eq? snd '())
                    '()
                    (cons (list fst snd)
                          (inner (append fst (list (car snd)))
                                 (cdr snd))))))
            (inner (list (car ls))
                   (cdr ls))))
        (cond ((eq? (cdr ls) '()) ls)
              (else (let ((lst-of-splited-lsts (split ls)))
                      (flatmap (lambda (splited-lst)
                                 (let ((fst-lsts (divide (car splited-lst)))
                                       (snd-lsts (divide (cadr splited-lst))))
                                   (flatmap (lambda (sm-ls-frm-snd)
                                              (map (lambda (sm-ls-frm-fst)
                                                     (list sm-ls-frm-fst  sm-ls-frm-snd))
                                                   fst-lsts))
                                            snd-lsts)))
                               lst-of-splited-lsts))))))
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;[(1 2)] -> [(+ 1 2) (- 1 2) (* 1 2) (/ 1 2)]                          
    (define add-oprtor
      (lambda (lst-of-lsts)
        (define inner
          (lambda (ls)
            (if (number? ls)
                (list ls)
                (let ((fst-ele-lst (add-oprtor (list (car ls))))
                      (snd-ele-lst (add-oprtor (list (cadr ls)))))
                  (let ((glued-lst (flatmap (lambda (sm-ls-frm-snd)
                                              (flatmap (lambda (sm-ls-frm-fst)
                                                     (list   (list '+ sm-ls-frm-fst sm-ls-frm-snd)
                                                             (list '- sm-ls-frm-fst sm-ls-frm-snd)
                                                             (list '* sm-ls-frm-fst sm-ls-frm-snd)
                                                             (list '/ sm-ls-frm-fst sm-ls-frm-snd)))
                                                   fst-ele-lst))
                                            snd-ele-lst)))
                    glued-lst)))))
        (flatmap (lambda (ls) (inner ls))
                 lst-of-lsts)))
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;(+ 1(- 2 3)) -> 0
    (define calc
      (lambda (exp)
        (if (number? exp)
            exp
            (let ((oprtor (car exp))
                  (fst-ele (calc (cadr exp)))
                  (snd-ele (calc (caddr exp))))
              (cond ((eq? fst-ele 'failed) 'failed)
                    ((eq? snd-ele 'failed) 'failed)
                    (else (cond ((eq? oprtor '+) (+ fst-ele snd-ele))
                                ((eq? oprtor '-) (- fst-ele snd-ele))
                                ((eq? oprtor '*) (* fst-ele snd-ele))
                                (else (if (= snd-ele 0)
                                          'failed
                                          (/ fst-ele snd-ele))))))))))
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;,,,
    (define solve
      (lambda ()
        (Qsort (lambda (x y) (let ((xnum (caddr x))
                                   (ynum (caddr y)))
                               (cond ((eq? xnum 'failed) #f)
                                     ((eq? ynum 'failed) #t)
                                     (else (<= xnum ynum)))))
               (map (lambda (ele) (list ele 'res= (calc ele)))
                    (add-oprtor (divide ls))))))
    (solve)
    

    另外由于完全没有优化,本程序运行缓慢,只可以运行六个或六个以下的数字(比如114514可以,1919810不行)


         恢复函数
    即可编程为了我
    巨大多废料递归
    的确副作用欠缺
    老爷爷无药可救(指运行效率低下)


    这里是结果:0_1535984377678_114514.txt


  • 圈内名人 木毛认可 捐赠者 猫猫 SCP基金会 女装人研究会 管理员

    我帮你按照markdown大致改了改,你可以翻编辑历史对比一下,就大概知道markdown一些符号的运作方式了:

    ### 相信我不是第一个写类似程序的homo,但我用了homo最喜欢的语言(Lisp(因为括号很多(无力)))
    #### (不会用Markdown,排版混乱请谅解)
    
    ---
    ### 1. 首先介绍一下前缀表达式(波兰式)
    - 使用前缀表达式来表示四则运算可以忽略运算符优先级带来的问题,因此在计算的时候比较方便。我的结果全是用前缀表达式来表示的(因为我比较懒),要是想变成常见的中缀表达式的话,也很简单,举个🌰,比如从附件里面找到一行结果等于19的:
    >  ((* 1 (* 1 (* 4 (- 5 (/ 1 4)))))  res= 19)
    - 先把**每一层嵌套中**的运算符和第一个操作数换位置:
    > ((1 * (1 * (4 * (5 - (1 / 4)))))  res= 19)
    - 再根据优先级去括号:
    > (1 * 1 * 4 * (5 - 1 / 4)  = 19)
    ### **完成**
    #### (racket默认自带分数表达,所以完全不用担心野蛮浮点运算造成的误差)
    ##### (注意即便换成**中缀表达式**114514的顺序也没变)
    
    ---
    ### 2. 再说一下思路
    - **算出 (1 1 4 5 1 4)这个列表所能构成的所有“先序遍历为114514”的二叉树(以列表的列表表示)**
    > (1 1 4 5 1 4)   ==>
    '((1 (1 (4 (5 (1 4)))))
    (1 (1 (4 ((5 1) 4))))
    (1 (1 ((4 5) (1 4))))
    (1 (1 ((4 (5 1)) 4)))......(后略)
    - **加上运算符号**
    > ===>
    '((+ 1 (+ 1 (+ 4 (+ 5 (+ 1 4)))))
      (- 1 (+ 1 (+ 4 (+ 5 (+ 1 4)))))
      (* 1 (+ 1 (+ 4 (+ 5 (+ 1 4)))))
      (/ 1 (+ 1 (+ 4 (+ 5 (+ 1 4)))))
      (+ 1 (- 1 (+ 4 (+ 5 (+ 1 4)))))
      (- 1 (- 1 (+ 4 (+ 5 (+ 1 4)))))......(后略)
    - **进行运算(顺便排了序)**
    > ===>
    >'(((- 1 (* (* (+ 1 4) 5) (+ 1 4))) res= -124)
    >  ((- 1 (* (+ 1 4) (* 5 (+ 1 4)))) res= -124)
    >  ((* (* (* (+ 1 1) 4) 5) (- 1 4)) res= -120)
    >  ((* (* (+ 1 1) (* 4 5)) (- 1 4)) res= -120)
    >  ((* (- 1 (* (+ 1 4) 5)) (+ 1 4)) res= -120)
    >  ((* (* (+ 1 1) 4) (* 5 (- 1 4))) res= -120)......(后略)
    #### **(结果不一定对,如果有错误或疏漏请博识兄贵指出,谢谢茄子)**
    
    ---
    ## **下面是代码**:
     // 因为不能有两组“```”,这行就去掉了
    lisp
    #lang racket
    (define ls (list 1 9 1 9))
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;helper
    (define flatmap
      (lambda (f ls)
        (if (eq? ls '())
            '()
             (append (f (car ls))
                     (flatmap f (cdr ls))))))
    (define Qsort
      (lambda (comp ls)
        (if (eq? ls '())
            '()
            (let ((fst (car ls))
                  (res (cdr ls)))
              (let ((l (filter (lambda (num) (comp num fst)) res))
                    (r (filter (lambda (num) (not (comp num fst))) res)))
                (append (Qsort comp l) (append (list fst) (Qsort comp r))))))))
    
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;(1 2 3) -> [(1 (2 3))  ((1 2) 3)]
    (define divide
      (lambda (ls)
        (define split
          (lambda (ls)
            (define inner
              (lambda (fst snd)
                (if (eq? snd '())
                    '()
                    (cons (list fst snd)
                          (inner (append fst (list (car snd)))
                                 (cdr snd))))))
            (inner (list (car ls))
                   (cdr ls))))
        (cond ((eq? (cdr ls) '()) ls)
              (else (let ((lst-of-splited-lsts (split ls)))
                      (flatmap (lambda (splited-lst)
                                 (let ((fst-lsts (divide (car splited-lst)))
                                       (snd-lsts (divide (cadr splited-lst))))
                                   (flatmap (lambda (sm-ls-frm-snd)
                                              (map (lambda (sm-ls-frm-fst)
                                                     (list sm-ls-frm-fst  sm-ls-frm-snd))
                                                   fst-lsts))
                                            snd-lsts)))
                               lst-of-splited-lsts))))))
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;[(1 2)] -> [(+ 1 2) (- 1 2) (* 1 2) (/ 1 2)]                          
    (define add-oprtor
      (lambda (lst-of-lsts)
        (define inner
          (lambda (ls)
            (if (number? ls)
                (list ls)
                (let ((fst-ele-lst (add-oprtor (list (car ls))))
                      (snd-ele-lst (add-oprtor (list (cadr ls)))))
                  (let ((glued-lst (flatmap (lambda (sm-ls-frm-snd)
                                              (flatmap (lambda (sm-ls-frm-fst)
                                                     (list   (list '+ sm-ls-frm-fst sm-ls-frm-snd)
                                                             (list '- sm-ls-frm-fst sm-ls-frm-snd)
                                                             (list '* sm-ls-frm-fst sm-ls-frm-snd)
                                                             (list '/ sm-ls-frm-fst sm-ls-frm-snd)))
                                                   fst-ele-lst))
                                            snd-ele-lst)))
                    glued-lst)))))
        (flatmap (lambda (ls) (inner ls))
                 lst-of-lsts)))
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;(+ 1(- 2 3)) -> 0
    (define calc
      (lambda (exp)
        (if (number? exp)
            exp
            (let ((oprtor (car exp))
                  (fst-ele (calc (cadr exp)))
                  (snd-ele (calc (caddr exp))))
              (cond ((eq? fst-ele 'failed) 'failed)
                    ((eq? snd-ele 'failed) 'failed)
                    (else (cond ((eq? oprtor '+) (+ fst-ele snd-ele))
                                ((eq? oprtor '-) (- fst-ele snd-ele))
                                ((eq? oprtor '*) (* fst-ele snd-ele))
                                (else (if (= snd-ele 0)
                                          'failed
                                          (/ fst-ele snd-ele))))))))))
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;,,,
    (define solve
      (lambda ()
        (Qsort (lambda (x y) (let ((xnum (caddr x))
                                   (ynum (caddr y)))
                               (cond ((eq? xnum 'failed) #f)
                                     ((eq? ynum 'failed) #t)
                                     (else (<= xnum ynum)))))
               (map (lambda (ele) (list ele 'res= (calc ele)))
                    (add-oprtor (divide ls))))))
    (solve)
     // 因为不能有两组“```”,这行就去掉了
    ---
    #### 另外由于完全没有优化,本程序运行缓慢,只可以运行六个或六个以下的数字(比如114514可以,1919810不行)
    
    ---
        恢复函数
    即可编程为了我
    巨大多废料递归
    的确副作用欠缺
    老爷爷无药可救(指运行效率低下)
    
    ---
    #### **这里是结果:**[0_1535984377678_114514.txt](/assets/uploads/files/1535984392283-114514.txt)
    

    我是markdown新咸鱼 随意排版的 欢迎各种提议


  • 木毛认可

    @磁盘酱 嗯,感觉这样有层次感不少。
    另外我把代码框换了一下,默认的代码框给Lisp代码的着色过于弱智。



  • 在成为homo之前就最喜欢lisp,原来是因为命中注定会成为homo


  • 管理员

    Lisp太他妈触了



  • 感觉就这个问题来说,Lisp是最好写的,用别的语言写会更复杂。前缀表达式很适合这种问题。


  • 木毛认可

    突然心血来潮,写了一个转化为中缀表达式同时消括号的函数,这样应该就好看一点了;大致思路就是分情况分析,分支还蛮多的,改了好几次,不保证没错


    代码(只有后面不一样):

    #lang racket
    (define ls (list 1 1 4 5 1 4)) 
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;helper
    (define flatmap
      (lambda (f ls)
        (if (eq? ls '())
            '()
             (append (f (car ls))
                     (flatmap f (cdr ls))))))
    (define Qsort
      (lambda (comp ls)
        (if (eq? ls '())
            '()
            (let ((fst (car ls))
                  (res (cdr ls)))
              (let ((l (filter (lambda (num) (comp num fst)) res))
                    (r (filter (lambda (num) (not (comp num fst))) res)))
                (append (Qsort comp l) (append (list fst) (Qsort comp r))))))))
    
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;(1 2 3) -> [(1 (2 3))  ((1 2) 3)]
    (define divide
      (lambda (ls)
        (define split
          (lambda (ls)
            (define inner
              (lambda (fst snd)
                (if (eq? snd '())
                    '()
                    (cons (list fst snd)
                          (inner (append fst (list (car snd)))
                                 (cdr snd))))))
            (inner (list (car ls))
                   (cdr ls))))
        (cond ((eq? (cdr ls) '()) ls)
              (else (let ((lst-of-splited-lsts (split ls)))
                      (flatmap (lambda (splited-lst)
                                 (let ((fst-lsts (divide (car splited-lst)))
                                       (snd-lsts (divide (cadr splited-lst))))
                                   (flatmap (lambda (sm-ls-frm-snd)
                                              (map (lambda (sm-ls-frm-fst)
                                                     (list sm-ls-frm-fst  sm-ls-frm-snd))
                                                   fst-lsts))
                                            snd-lsts)))
                               lst-of-splited-lsts))))))
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;[(1 2)] -> [(+ 1 2) (- 1 2) (* 1 2) (/ 1 2)]                          
    (define add-oprtor
      (lambda (lst-of-lsts)
        (define inner
          (lambda (ls)
            (if (number? ls)
                (list ls)
                (let ((fst-ele-lst (add-oprtor (list (car ls))))
                      (snd-ele-lst (add-oprtor (list (cadr ls)))))
                  (let ((glued-lst (flatmap (lambda (sm-ls-frm-snd)
                                              (flatmap (lambda (sm-ls-frm-fst)
                                                     (list   (list '+ sm-ls-frm-fst sm-ls-frm-snd)
                                                             (list '- sm-ls-frm-fst sm-ls-frm-snd)
                                                             (list '* sm-ls-frm-fst sm-ls-frm-snd)
                                                             (list '/ sm-ls-frm-fst sm-ls-frm-snd)))
                                                   fst-ele-lst))
                                            snd-ele-lst)))
                    glued-lst)))))
        (flatmap (lambda (ls) (inner ls))
                 lst-of-lsts)))
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;(+ 1(- 2 3)) -> 0
    (define calc
      (lambda (exp)
        (if (number? exp)
            exp
            (let ((oprtor (car exp))
                  (fst-ele (calc (cadr exp)))
                  (snd-ele (calc (caddr exp))))
              (cond ((eq? fst-ele 'failed) 'failed)
                    ((eq? snd-ele 'failed) 'failed)
                    (else (cond ((eq? oprtor '+) (+ fst-ele snd-ele))
                                ((eq? oprtor '-) (- fst-ele snd-ele))
                                ((eq? oprtor '*) (* fst-ele snd-ele))
                                (else (if (= snd-ele 0)
                                          'failed
                                          (/ fst-ele snd-ele))))))))))
    
    
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;-> infix
    (define translt-to-infix
      (lambda (ls)
        (define get-oprtor
          (lambda (x)
            (if (pair? x)
                (car x)
                'none)))
        (if (pair? ls)
            (let ((oprtor (car ls))
                  (l1 (cadr ls))
                  (l2 (caddr ls)))
              (let ((op-l1 (get-oprtor l1))
                    (op-l2 (get-oprtor l2)))
                (let ((t-l1 (translt-to-infix l1))
                      (t-l2 (translt-to-infix l2)))
                  (if (or (eq? oprtor '*) (eq? oprtor '/))
                      (if (or (eq? op-l1 '+) (eq? op-l1 '-))
                          (if (or (eq? op-l2 '+) (eq? op-l2 '-))
                              (list t-l1
                                    oprtor
                                    t-l2)
                              (if (and (eq? oprtor '/) (or (eq? op-l2 '*) (eq? op-l2 '/)))
                                  (append t-l1
                                          (list oprtor
                                                t-l2))
                                  (append (list t-l1)
                                          (cons oprtor t-l2))))
                          (if (or (eq? op-l2 '+) (eq? op-l2 '-))
                              (append (append t-l1 (list oprtor))
                                      (list t-l2))
                              (if (and (eq? oprtor '/) (or (eq? op-l2 '*) (eq? op-l2 '/)))
                                  (append t-l1
                                          (list oprtor
                                                t-l2))
                                  (append t-l1
                                          (cons oprtor t-l2)))))
                      (if (and (eq? oprtor '-) (or (eq? op-l2 '+) (eq? op-l2 '-)))
                          (append t-l1
                                  (list oprtor
                                        t-l2))
                          (append t-l1
                                  (cons oprtor
                                        t-l2)))))))
              (list ls)))) 
    
    
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;,,,
    (define solve
      (lambda ()
        (map (lambda (ele) (append (car ele) (list '= (cadr ele))))
             (Qsort (lambda (x y) (let ((xnum (cadr x))
                                        (ynum (cadr y)))
                                    (cond ((eq? xnum 'failed) #f)
                                          ((eq? ynum 'failed) #t)
                                          (else (<= xnum ynum)))))
                    (map (lambda (ele) (list (translt-to-infix ele) (calc ele)))
                         (add-oprtor (divide ls)))))))
    
    (solve)
    
    

    结果0_1537069772894_114514-infix.txt



  • 木毛都是程序员兼数学家可能性微存


  • 圈内名人 木毛认可 捐赠者 猫猫 SCP基金会 女装人研究会 管理员

    @kxy09 因特有的数字论证造而造就的可能性微存



  • 收了一藏,等本废物把链表搞完再研究


  • 管理员

    想起了当初算阪神算的工具
    我记得racket应该有pattern matching的,不知道用了以后会不会比手写car cdr要好


  • 管理员

    如果是保留顺序的话复杂度是O(2^n) 不保留顺序的话复杂度是O(n!2^n)
    所以没什么可优化的(暴言)


  • 木毛认可

    @arsdragonfly racket应该是有模式匹配的,但是我对scheme的了解仅限于SICP里讲到了的,因此我没有用



  • 兄啊你这内存这么大可怎么用啊,快去看三章罢(指SICP


  • 木毛认可

    @sataycc fa!?,我记得三章讲的是状态吧,我感觉没有什么能用来降低内存使用量的办法;再加上GO是屑,所以赋值也是屑(暴论)



  • @田所浩治容疑者
    迫真list, call-by-need的里技
    Friedman, Daniel P. (1976). “Cons should not evaluate its arguments”. ICALP.

    印象中三章提到这个了


  • 木毛认可

    @sataycc 这里用惰性列表应该也省不了什么资源吧(困惑),不过Friedman这篇论文我也没看过,我只知道惰性列表有很强的表达能力



  • @田所浩治容疑者 兄啊你display一下这个(add-oprtor (divide ls)),想想也知道会指数爆炸吧,这么大的东西直接在内存里铺开map


  • 木毛认可

    @sataycc 但是在这个列表中的确是每一个元素都会被用到,因此无论列表是不是惰性的,使用的内存都是一个数量级的(反而应该说因为thunk的使用,惰性列表会消耗更多内存)。另外这道题答案本身就是指数级的,我也没办法啊(



  • @田所浩治容疑者 除了这个Qsort实在是太屑了无法lazy,剩下的操作都可以写成循环,所以可以在O(1)的空间复杂度完成。那么lazy就只是一个语法糖了。


  • 木毛认可

    @sataycc O(n)空间复杂度是immutable pair的原罪,因为每一次map都会导致创建一个新的列表,无论这个列表是否是惰性的(不过惰性列表求值map f (map g l) 类似的这种表达式有优势 ,但是空间依旧是O(n)的)。我觉得你对惰性求值的理解有点偏差



  • @田所浩治容疑者
    我们当场表示一个所有自然数:
    (define (n x) (cons x (lambda () (n (add1 x)))))
    (define ns (n 1))
    然后把所有自然数加1:
    (define (mymap f s) (cons (f (car s)) (lambda () (mymap f ((cdr s))))))
    (define nsplus1 (mymap add1 ns))
    占用的空间只有两个元素而已。
    不难理解吧?


  • 木毛认可

    @sataycc 但是这里知道的信息也只是表头是2而已,要想知道其他元素,还得继续求值。一个被求值了1个元素的流是一个元素,一个被求值了1000个元素的流也是一个元素,但是两者占用空间是不同的(后者多了999个用于记录的thunk)。



  • @田所浩治容疑者
    当然要继续求值,但是每求下一个元素只是一个元素的计算量;稍微做一个代换就知道这样实现的lazy list是不会保存什么thunk的。
    现在我们用O(1)的空间输出s中从m到n的所有数:(当然屏幕缓冲区是不算数的)
    (define (output m n s)
    (define (output-acc m n s acc)
    (if (< acc m) (output-acc m n ((cdr s)) (add1 acc))
    (if (>= m n) (display “finished”) (begin (display (car s)) (output-acc m (sub1 n) ((cdr s)) acc)))))
    (output-acc m n s 0))
    你可以在DrRacket里试着运行一下(output 100000000 100000001 ns),如果你的说法成立,右下角的内存占用应该有至少400M的增长。


  • 木毛认可

    @sataycc 因为ns不是真正的流,用lambda把参数包起来之后再求值的确可以得到正确的惰性求值的结果(其实更像是只有文本替换的正则序展开),但是无法保存已被求值的元素(你这样计算得到了正确的输出结果,但是把表里面所有在过程中被求值出来的元素都给扔掉了);所以在真正的惰性求值实现中,每一个被延时的对象都会有一个thunk(可以看SICP四章或者EOPL 4.5)。


    证据的话你可以用lazy racket(drracket左下角就可以选)或者Haskell写一段逻辑相同的代码,看一看内存的使用情况。

    (define (n x) (cons x (n (add1 x))))
    (define ns (n 1))
    
    (define (output m n s)
      (define (output-acc m n s acc)
        (if (< acc m) (output-acc m n (cdr s) (add1 acc))
            (if (>= m n) (display "finished") (begin (display (car s)) (output-acc m (sub1 n) (cdr s) acc)))))
    (output-acc m n s 0))
    
    (output 100000000 100000001 ns)
    
    
    

    我的思路(指上面的114514计算器)的确不少都可以写成循环,但是要想要O(1)的空间复杂度的话只能用mutable pair加上imperative programming。

    另外在“最后一步”用这样丢掉所有表头元素来用display实现尾递归进行输出的方法是可以节省内存的(因为之后这个列表就再也不会被用到了),但是前面是不行的(因为这个表还要被被用到)。

    如果足够神触的话,说不定就可以将所有前面的过程都包到这个“最后一步”里,但这个是非常困难的,不够declarative(无知)。



  • @田所浩治容疑者
    你的最后一段应该就是我想说的。
    我从来没有把这个东西叫做流,正是因为它不是一个真正的流; 但是我觉得在这种每一步计算量不大的且需要枚举输出全部结果的场景下不保存中间结果这个tradeoff是赚的。



  • @田所浩治容疑者 顺便给你一个第零手资料: friedman作为call-by-need的发明者不太爱用lazy这个词,而他的学生说无论是否memoize都算lazy。所以我觉得在scheme的语境中大概这个词没那么重要。当然我也只上了他半个学期的课……
    欢迎来IU,这破学校我连个inm民都没找到(


  • 木毛认可

    @sataycc fa!?,那不就是王垠大学吗?(迫真)。能亲自去上Friedman老爷子的课我也是挺羡慕的,我是国内土鳖211低端自学人(


登录后回复
 

更多本版内容

  • 2
  • 5
  • 6
  • 14
  • 18
  • 6
  • 12
  • 5

友情链接

中文InmWiki 中文饼Wiki InmTieba 例区Discord afdian “bilibili” TIS v2mm | 自由职业者社区