0

「numbers」という名前のリスト (3 1 4 5 2) があるとします。インデックス 0 から任意のインデックスまでリストを逆にするコマンド、つまり (逆数 2) を探しています。これは新しいリストを (4 1 3 5 2) として与えます。

私はグーグルを試しましたが、適切な関数を見つけることができず、この段階で関数を自分で書くにはあまりにも初心者です。

ありがとうございました。

4

2 に答える 2

6

ライブラリ関数に基づく単純な CL バージョン:

(defun reverse-first-n (list n)
  (nreconc (subseq list 0 n) (nthcdr n list)))
  1. これはメモリ最適です。つまり、不必要に割り当てません。
    • 末尾をコピーする必要がないため、 subseqの代わりにnthcdr
    • revappendとにかく新鮮なリストである最初の引数をコピーするので、nreconcより経済的です。
  2. listこのバージョンは、n番目の位置に3回 ( で 1 回、subseqで 1 回nthcdr、次にで 1 回)トラバースするため、速度が最適ではありませんnreconc

最適なバージョンは次のとおりです。

(defun reverse-first-n (list n)
  (if (or (= n 0) (= n 1))
      list
      (do* ((tail (list (pop list)))
            (head tail (cons (pop list) head))
            (count (1- n) (1- count)))
           ((zerop count)
            (setf (cdr tail) list)
            head))))

これがコードのパフォーマンスのボトルネックになる可能性はほとんどないことに注意してください。2 番目のバージョンを提供する主な目的は、広範で適切に設計された CL ライブラリーによってどれだけの時間と労力が節約されるかを示すことです。

于 2013-08-04T17:12:24.253 に答える
2

Lisp のどの方言を使用していますか? これがSchemeソリューションです(SRFI 1を使用):

(require srfi/1)    ; assuming you're using Racket
(define (reverse-first-n lst n)
  (call-with-values (lambda ()
                      (split-at lst n))
                    append-reverse!))

タイトルが言うように、質問の説明とは異なり、関数を実際に「最初のn要素を逆にする」ようにしました。たとえば、次のようになります。

> (reverse-first-n '(3 1 4 5 2) 2)
'(1 3 4 5 2)
> (reverse-first-n '(3 1 4 5 2) 3)
'(4 1 3 5 2)

OP の要求に応じて、Common Lisp バージョンを次に示します。sds はすでにかなりまともなバージョンを投稿しているので、私が書いているバージョンは、Scheme ソリューションのより直接的な移植です ( append-reverse!nreconc; call-with-valuesmultiple-value-call; そして、SRFI 1split-atを CL に移植しています):

(defun split-at (list n)
  (if (zerop n)
      (values '() list)
      (multiple-value-bind (prefix suffix)
                           (split-at (cdr list) (1- n))
        (values (cons (car list) prefix) suffix))))

(defun reverse-first-n (list n)
  (multiple-value-call #'nreconc (split-at list n)))

(なぜsplit-at? その目的は、take( subseq) とdrop( nthcdr) の両方に、入力リストの 1 回の走査のみを提供することです。)

于 2013-08-04T15:32:13.807 に答える