0

私はLispを学んでいます。再帰を使用して、アルファベット順に並べられた2つの文字列をマージするCommonLisp関数を実装しました。これが私のコードですが、何か問題があり、理解できませんでした。

(defun merge (F L)
    (if (null F)
        (if (null L)
            F         ; return f
            ( L ))    ; else return L
        ;else if
        (if (null L)
            F)        ; return F
    ;else if
    (if (string< (substring F 0 1) (substring L 0 1)
        (concat 'string (substring F 0 1) 
                        (merge (substring F 1 (length F)) L)))
    ( 
        (concat 'string (substring L 0 1) 
                        (merge F (substring L 1 (length L)) ))
    ))))

a = adf編集：入力が文字列と文字列b = beg であり、結果または出力がであるなど、2つの文字列をマージしたいだけですabdefg。

前もって感謝します。

4

4 に答える 4

3

Kazが示すように、使用string<はやり過ぎchar<です。代わりに使用する必要があります。各ステップで再length計算すると、このアルゴリズムは2次式になるため、避ける必要があります。「偽造」に使用sortすると、O（n）ではなくO（n log n）になります。常に使用concatenate 'stringすると、不要なトラバーサルの追加コストも発生する可能性があります。

これが自然な再帰的解決策です：

(defun str-merge (F L)
  (labels ((g (a b)
             (cond
               ((null a)  b)
               ((null b)  a)
               ((char<  (car b)  (car a))
                  (cons  (car b)  (g a (cdr b))))
               (t (cons  (car a)  (g (cdr a) b))))))
    (coerce (g  (coerce F 'list) (coerce L 'list))
            'string)))

しかし、Common Lispには末尾呼び出しの最適化保証はなく、末尾再帰のモジュロcons最適化保証は言うまでもありません（後者が1974年に「Lisp1.6rplacaとrplacdフィールド割り当て演算子」を使用して記述されていたとしても）。したがって、これをトップダウンの出力リスト構築ループとして手動でコーディングする必要があります。

(defun str-merge (F L &aux (s (list nil)) )     ; head sentinel
  (do ((p s                (cdr p))
       (a (coerce F 'list) (if q  a  (cdr a)))
       (b (coerce L 'list) (if q (cdr b)  b ))
       (q nil))
      ((or (null a) (null b))
         (if a (rplacd p a) (rplacd p b))
         (coerce (cdr s) 'string))              ;         FTW!
    (setq q  (char<  (car b)  (car a)))   ; the test result
    (if q
      (rplacd p (list (car b)))
      (rplacd p (list (car a))))))
于 2012-04-25T07:50:24.310 に答える
2

コメントから判断すると、一連の条件（他の言語のif一連のsなど）で使用しようとしているようです。else ifそのためには、おそらくcondが必要です。

if私はそれを他のいくつかのエラーに置き換えてcondクリーンアップしました、そしてそれはうまくいきました。

(defun empty (s) (= (length s) 0))

(defun my-merge (F L)
  (cond 
   ((empty F)
    (if (empty L)
      F 
      L)) 
   ((empty L)
    F)
   (t
    (if (string< (subseq F 0 1) (subseq L 0 1))
      (concatenate 'string (subseq F 0 1) (my-merge (subseq F 1 (length F)) L)) 
      (concatenate 'string (subseq L 0 1) (my-merge F (subseq L 1 (length L))))))))

あなたのテストケースはあなたが望むように出てきました：

* (my-merge "adf" "beg")

"abdefg"
于 2012-04-24T21:16:18.637 に答える
2

かなりの数の良い答えがありましたが、なぜ私はもう1つ追加するのですか？さて、以下はおそらくここの他の答えよりも効率的です。

(defun merge-strings (a b)
  (let* ((lena (length a))
         (lenb (length b))
         (len (+ lena lenb))
         (s (make-string len)))
    (labels
        ((safe-char< (x y)
           (if (and x y) (char< x y)
               (not (null x))))
         (choose-next (x y)
           (let ((ax (when (< x lena) (aref a x)))
                 (by (when (< y lenb) (aref b y)))
                 (xy (+ x y)))
             (cond
               ((= xy len) s)
               ((safe-char< ax by)
                (setf (aref s xy) ax)
                (choose-next (1+ x) y))
               (t
                (setf (aref s xy) by)
                (choose-next x (1+ y)))))))
      (choose-next 0 0))))

(merge-strings "adf" "beg")

特にメモリ割り当ての意味でより効率的です-結果の文字列を書き込むのに十分なメモリを割り当てるだけで、何も強制しません（リストから文字列へ、または配列から文字列へなど）。見た目はあまり良くないかもしれませんが、これはすべての計算を1回だけ実行しようとしています。

もちろん、これはこの関数を作成するための最も効率的な方法ではありませんが、効率をまったく考慮せずにプログラミングしても、それほど効果はありません。

于 2012-04-26T18:32:03.853 に答える
-1

それを行う再帰的な方法（コメントに従って修正-他のソリューションもIFフォームを取得できます）。

(defun merge-strings (a b)
  (concatenate 'string
               (merge-strings-under a b)))

(defun merge-strings-under (a b)
  (when (and
       (= (length a)
          (length b))
       (> (length a) 0))
    (append (if (string< (aref a 0) (aref b 0))
                (list (aref a 0) (aref b 0))
                (list (aref b 0) (aref a 0)))
            (merge-strings-under (subseq a 1)
                           (subseq b 1)))))

これを繰り返す方法があります。

(concatenate 'string 
    (loop for i across "adf" for j across "beg" nconc (list i j)))

これらは、文字列を文字のリストに組み込み、それをベクトル化することに依存していることに注意してください（文字列は文字のベクトルです）。

よりC風のアプローチを書くこともできます...

(defun merge-strings-vector (a b)
  (let ((retstr (make-array (list (+
                                   (length a)
                                   (length b)))
                            :element-type 'character)))
    (labels ((merge-str (a b i)
               (when (and
                    (= (length a)
                       (length b))
                    (/= i (length a)))
                 (setf (aref retstr (* 2 i)) (aref a i))
                 (setf (aref retstr (1+ (* 2 i))) (aref b i))
                 (merge-str a b (1+ i)))))

      (merge-str a b 0)
      retstr)))

これは、他の2つとは異なり、関数内に副作用があることに注意してください。それはまた、imo、理解するのがより難しいです。

3つすべてがSBCL56で実行するのにさまざまなサイクル数を要します。私のほとんどのトライアルでは、それぞれが6Kから11Kかかるようです。理由はわかりません。

于 2012-04-24T20:56:19.250 に答える