Схема Сложность Понимание вывода моей функции 'concat lists' output - PullRequest
Новая
       15

Схема Сложность Понимание вывода моей функции 'concat lists' output

0 голосов
/ 13 мая 2018

Я написал функцию my-append, которая берет два списка L1, L2 и добавляет каждый элемент L2 в конец L1.(другими словами, он объединяет L1 с L2)

функция, кажется, работает правильно, однако я получаю странный вывод. 

(my-append '(a b '(1 2 3)) (list '(4 5 6) 7 8 9)) ==>

(list 'a 'b (list 'quote (list 1 2 3)) (list 4 5 6) 7 8 9)

Я новичок в схеме и не могу сказать,если это правильно или сейчас.Пожалуйста, обратите внимание, что я использую продвинутый язык студента внутри доктора ракетки.Вот код для функции.(он использует две вспомогательные функции) 

;my-append
;takes two lists L1,L2 and returns concat of L2 to L1
;it first checks if either list is empty if so it returns the non empty one
;if both are empty returns empty
;if both are non empty determine which list has smaller length
;calls my-append-helper with first arg as smaller second larger
;append-element
;takes a list L and element x and adds x
; to the end of L
; I am super limited on which operations i can use
; so i must resort to this O(n) algorithm

;my-append-helper
;takes either two non empty lists L1 L2 then
;builds the concatenation of L1 L2
;by stripping of first element of L2
;and adding it to L1

(define (append-element L x)
  (cond ((equal? L '())    
         (list x) )          
        (else           
         (cons (first L)    
                (append-element (rest L) x)))))

(define my-append-helper
  (lambda (L1 L2)
    (cond ( (equal? '() L2)
            L1)
          (else (my-append-helper (append-element L1 (first L2)) (rest L2))))))

(define my-append
  (lambda (L1 L2)
    (cond ( (and (equal? L1 '()) (equal? L2 '()))
            '() )
          ( (equal? L1 '() )
            L2 )
          ( (equal? L2 '() )
            L1)
          ( else
            (my-append-helper L1 L2)))))

Ответы [ 2 ]

0 голосов
/ 13 мая 2018

Да, вывод правильный.

> (my-append '(a b '(1 2 3)) (list '(4 5 6) 7 8 9))
(list 'a 'b (list 'quote (list 1 2 3)) (list 4 5 6) 7 8 9)

Он напечатан в стиле, так что при вставке обратно в приглашении результат будет таким же: 

> (list 'a 'b (list 'quote (list 1 2 3)) (list 4 5 6) 7 8 9)
(list 'a 'b (list 'quote (list 1 2 3)) (list 4 5 6) 7 8 9)  ; compare below     vvvvv

Как мы можем быть уверены, что все в порядке?Делая то же самое с двумя частями: 

> '(a b '(1 2 3))
(list 'a 'b (list 'quote (list 1 2 3)))
;     --------------------------------
>  (list '(4 5 6) 7 8 9)
                                 (list (list 4 5 6) 7 8 9)  ; aligned vertically  ^^^
;                                      ------------------

Приложение просто объединяет две части в один список, превращая 

      (list a b c ... n) (list o p q ... z)

в 

      (list a b c ... n        o p q ... z)

или, символически ("в псевдокод "), 

           [a b c ... n]      [o p q ... z]   ; is turned into:
           [a b c ... n        o p q ... z]

О вашем алгоритме.Он добавляет два списка, повторяя шаги 

           [a b c ... n]      [o p q ... z]  
           [a b c ... n]    o   [p q ... z]   
           [a b c ... n o]        [q ... z]

, пока второй список не будет исчерпан.Повторное добавление элемента в конец списка хорошо подходит для языков с таким примитивом, как Clojure conj, который дешев в использовании.Но в Схеме это алгоритмически невыгодно, поскольку повторный обход первого списка для добавления элемента к нему приводит к поведению квадратичного относительно сложности времени (время выполнения вырастет в четыре раза в два разаувеличение размера входных данных).

Еще один способ сделать это - 

           [a b ... m n]      [o p q ... z]  
           [a b ... m]    n   [o p q ... z]   
           [a b ... m]      [n o p q ... z]

, пока не будет использован первый список: 

(define my-append-helper
  (lambda (L1 L2)
    (cond ( (equal? '() L1)
            L2)
          (else (my-append-helper (but-last L1) (cons (last L1) L2))))))
                                           ;     ^^^^ !

consдешево в Схеме, так что это хорошо.Но многократное удаление элемента из конца списка (с еще не реализованным but-last) является алгоритмически невыгодным, поскольку повторный обход первого списка для удаления его последнего элемента приводит к квадратичному поведению в отношениисложность времени (время выполнения вырастет в четыре раза при увеличении размера входных данных в два раза).

Мы на правильном пути с cons, хотя, когда мы замечаем, что добавлениеможет прогрессировать по шагам 

           [a b ... m n]          [o p q ... z] 
         ( [a]   [b ... m n] )    [o p q ... z]  
           [a] ( [b ... m n]      [o p q ... z] )
                ................................
           [a]   [b ... m n        o p q ... z] 
           [a     b ... m n        o p q ... z]

, если мы выделим элемент first из списка first , добавим то, что осталось, а затем все, что осталось для насчтобы сделать это cons этот первый элемент на результат!

0 голосов
/ 13 мая 2018

Это считается? 

(define (myappend lst1 lst2)
  (cond
    ((null? lst2) lst1)
    (else (myappend (cons lst1 (cons (car lst2) '())) (cdr lst2)))))

Это итеративная процедура (а не рекурсивная).

Обратите внимание, что если

  1. Список 2 пуст, вы можете просто вернуть list1.
  2. Поскольку ваш базовый случай требует, чтобы вы возвращали свой список1, просто используйте инвариантное доказательство, в котором вы определили список1 как инвариант.

Если это не сработает, дайте мне знать, и я постараюсь помочь вам отладить ваш код.

...