อะไรคือความแตกต่างระหว่าง `(mcons (mcons '() 25) 16)` และ `(mcons 25 (mcons 16 `()))`

ฉันกำลังยุ่งอยู่กับ โครงสร้างและการตีความของ แบบฝึกหัดโปรแกรมคอมพิวเตอร์ 2.18 ที่นี่เราต้องกำหนดขั้นตอนย้อนกลับเพื่อย้อนกลับรายการ ควรทำดังต่อไปนี้:

(reverse (list 1 4 9 16 25))
;; => (25 16 9 4 1)

ฉันได้คำจำกัดความต่อไปนี้:

(define (reverse list)
  (if (null? list) 
      list
      (cons (reverse (cdr list)) (car list))))
;; => (mcons (mcons (mcons (mcons (mcons '() 25) 16) 9) 4) 1).

จากนั้นใน วิธีแก้ปัญหา พบสิ่งที่คล้ายกันดังนี้:

(define (reverse items) 
  (if (null? (cdr items)) 
      items 
      (append (reverse (cdr items)) 
              (cons (car items) nil))))
;; => (mcons 25 (mcons 16 (mcons 9 (mcons 4 (mcons 1 '()))))).

มีความแตกต่างระหว่าง append และ cons ที่นี่ซึ่งฉันไม่สามารถวางนิ้วได้

คำถามของฉัน: อะไรคือความแตกต่างและเหตุใดผลลัพธ์จึงไม่แสดงเป็น (25 16 9 4 1)


scheme sicp racket cdr cons
person Erwin Rooijakkers    schedule 17.01.2015    source แหล่งที่มา

คำตอบ (1)


arrow_upward
5
arrow_downward

คำตอบสั้นๆ: เวอร์ชันแรกของ reverse กำลังสร้างรายการ ไม่เหมาะสม อย่างไม่ถูกต้อง ส่วนเวอร์ชันที่สองกำลังสร้างรายการ เหมาะสม อย่างไม่มีประสิทธิภาพ เราสามารถทำได้ดีขึ้นตราบใดที่เราเข้าใจความแตกต่างระหว่าง append และ cons

append เชื่อมต่อสอง รายการ หากเราใช้มันเพื่อเพิ่มองค์ประกอบที่ส่วนท้ายของหนึ่งรายการ เราจะทำงานมากเกินความจำเป็น: เราจะต้องสำรวจรายการทั้งหมด ในแต่ละครั้ง เพียงเพื่อที่จะใส่ องค์ประกอบสุดท้าย (ดู: อัลกอริทึมของ Schlemiel the Painter) ดังนั้นการใช้งาน reverse ที่ใช้ append อาจแย่เท่ากับ O(n^2) ในความซับซ้อน

ในทางกลับกัน cons จะเพิ่มองค์ประกอบเดียวที่ส่วนหัวของรายการ สำหรับความซับซ้อน O(n) ในการดำเนินการ reverse โดยทั่วไป ใน Scheme คุณควรพยายามหลีกเลี่ยงการใช้ append เพื่อสร้างรายการเอาต์พุตใหม่ โดยเลือกใช้ cons เสมอ ตอนนี้เรามาดูกันว่าอัลกอริทึมของคุณส่งคืนอะไรบ้างโดยใช้ cons:

(reverse '(1 2 3 4 5))
=> '(((((() . 5) . 4) . 3) . 2) . 1)

ทำไมเป็นอย่างนั้น? เนื่องจากในการสร้างรายการที่เหมาะสมด้วย cons อาร์กิวเมนต์ที่สองจะต้องเป็นรายการที่เหมาะสมอีกรายการหนึ่ง แต่คุณส่งผ่านองค์ประกอบเดียว การใช้งานที่ถูกต้องจำเป็นต้องมีพารามิเตอร์ตัวสะสม - และโดยบังเอิญ สิ่งนี้จะมีประสิทธิภาพมากกว่า เนื่องจากใช้ การเรียกซ้ำส่วนท้าย ซึ่งเป็นแนวคิดที่คุณควรทำความคุ้นเคยอยู่แล้ว ตามที่ได้แนะนำไว้ในส่วนที่ 1.2 ของหนังสือ ลองสิ่งนี้:

(define (reverse lst acc)
  (if (null? lst)
      acc
      (reverse (cdr lst) (cons (car lst) acc))))

(reverse '(1 2 3 4 5) '())
=> '(5 4 3 2 1)

สำหรับส่วนสุดท้ายของคำถาม: รายการจะแสดงด้วย mcons (m หมายความว่าเซลล์ cons ไม่แน่นอน) เนื่องจากภาษาที่คุณใช้อยู่ ให้ลองสลับไปที่ #lang racket ซึ่งใช้ < em>ไม่เปลี่ยนรูป cons เซลล์ตามค่าเริ่มต้น และจะถูกพิมพ์ตามที่คุณต้องการ

person Óscar López    schedule 17.01.2015
comment
ขอบคุณมาก! ฉันใช้ #lang planet neil/sicp แต่จะเปลี่ยนกลับเป็น #lang racket - person Erwin Rooijakkers; 18.01.2015
comment
@ user2609980 อย่าสลับเร็วนัก neil/sicp นั้นใช้ได้สำหรับการทำงานผ่านแบบฝึกหัด SICP ในขณะที่ Racket จะมีนิสัยแปลกๆ อยู่บ้าง จะดีกว่าถ้าคุณคุ้นเคยกับรายการที่กำลังพิมพ์โดยมี mcons แสดงทั้งหมด - person Óscar López; 18.01.2015