3

私は Common Lisp でマージソートの一般的な実装を持っています: 私は分割関数とマージ関数の異なる実装を持っており、分割関数とマージ関数の組み合わせごとにマージソート関数を構築したいと考えています。

  • どの分割関数も文字列のリストを入力として取り、2 つのリスト (元のリストの 2 つの半分) のリストを返します。
  • どのマージ関数も、2 つの並べ替えられたリストを入力として取り、並べ替えられたマージされたリストを返します。

各マージ ソート関数は、次の関数を呼び出すことによって作成されます。

(defun make-merge-sort-function (split-function merge-function)

  (defun merge-sort (lst)
    (if (or (null lst) (null (cdr lst)))
        lst
        (let ((s (funcall split-function lst)))
          (funcall merge-function (merge-sort (car s)) (merge-sort (cadr s))))))

  (lambda (lst)
    (merge-sort lst)))

名前をプライベートに保ち、名前空間を台無しにしないように、merge-sort内部で定義しました。make-merge-sort-function

私のコードは、いくつかの Common Lisp 実装 (Steel Bank Common Lisp など) で動作します。

  • すべてのテスト実行の出力が適切にソートされ、
  • 結果のマージソート関数ごとに実行時間が異なり、異なる分割/マージの組み合わせが使用されたことを示しています。

したがって、私のコードは正しいと思います。

ただし、Allegro Common Lisp でプログラムを実行すると、次の警告が表示されます。

Warning: MERGE-SORT is defined more than once as `operator' in file foo.lisp.

whereは呼び出されるfoo.lispファイルです。したがって、プログラムは正常に動作しますが、最初の呼び出しの後にmake-merge-sort-function呼び出しごとにこの警告が出力されます。関数をグローバルmake-merge-sort-functionにすると (2 つの引数とが追加されます)、警告は消えます。merge-sortsplit-functionmerge-function

Allegro Common Lisp では、この警告の意味に関する兆候は見つかりませんでした。私が試した他の実装 (ABCL、CMUCL、CCL、CLISP、SBCL) では、警告は表示されません。内部関数 (クロージャー) の新しいインスタンスが複数回定義されても問題ないと思いますが、これが問題になる理由がわかりません。何か案は？

4

2 に答える 2

4

Common Lisp で入れ子になることはありません。defun

letinside defunの代わりに 使用するのと同じように、nested の代わりにdefvar使用します 。labelsdefun

(defun make-merge-sort-function (split-function merge-function)
  (labels ((merge-sort (lst)
             (if (or (null lst) (null (cdr lst)))
                 lst
                 (let ((s (funcall split-function lst)))
                   (funcall merge-function (merge-sort (car s)) 
                                           (merge-sort (cadr s)))))))
    #'merge-sort))
于 2014-04-18T21:06:39.190 に答える
1

テスト コードは表示されないため、次の CLISP セッション トランスクリプトを検討してください。

[3]> (defun make-merge-sort-function (split-function merge-function)
  (defun merge-sort (lst)
    (if (or (null lst) (null (cdr lst)))
        lst
        (let ((s (funcall split-function lst)))
          (funcall merge-function (merge-sort (car s))
                                  (merge-sort (cadr s))))))
  (lambda (lst)
    (merge-sort lst)))
MAKE-MERGE-SORT-FUNCTION
[4]> (fboundp 'merge-sort)
NIL                         <<---------------------------- NB
[5]> (defun sp1(x)(princ" IN SPL1 ") x)
SP1
[6]> (defun sp2(x)(princ" IN SPL2 ") x)
SP2
[7]> (defun mg1(x y)(princ" IN MRG1 ") x)
MG1
[9]> (setq f1 (make-merge-sort-function #'sp1 #'mg1))
#<FUNCTION :LAMBDA (LST) (MERGE-SORT LST)>
[10]> (fboundp 'merge-sort)
T                           <<---------------------------- NB !!
[12]> (funcall f1 '(1 2 3))
 IN SPL1                    <<---------------------------- NB
*** - CDR: 1 is not a list
[14]> (setq f2 (make-merge-sort-function #'sp2 #'mg1))
#<FUNCTION :LAMBDA (LST) (MERGE-SORT LST)>
[15]> (funcall f1 '(1 2 3))
 IN SPL2                    <<---------------------------- NB !!!
*** - CDR: 1 is not a list

これで、コードが思っていたのとは違うことを行っていることがわかります。おそらく、テスト コードはその問題を洗い流していませんでした。

どうやら、ネストされたdefunはグローバルにアクセス可能な functionを定義しmerge-sort、 の 2 番目の呼び出しはそれをmake-merge-sort-function再定義します。

于 2014-05-01T07:13:14.710 に答える