Код быстрой сортировки сюсюкать


Я был бы очень признателен, если кто-то может пересмотреть свою реализацию быстрой сортировки. Кроме того, я создал мой список динамически и написал пару тестов. Я, конечно, понимаю, что тесты не полные, но я решил остановиться, где я был и увидеть, если я мог бы получить некоторую обратную связь.

(defun categorize_list(pivot thelist less more)
    (let ((comparee (car thelist)) (therest (cdr thelist)))
      (if (null thelist)
            (list less more)
        (if (< comparee pivot)
          (categorize_list pivot therest (append less (list comparee)) more)
          (categorize_list pivot therest less (append more (list comparee)))
        )
        )
      )
  )

(defun quicksort(thelist)
  (if (null thelist)
    ()
      (let (
            (pivot (car thelist))
            (therest (cdr thelist))
        )
        (let ((categorized_list (categorize_list pivot therest () ())))

            (append (quicksort (nth 0 categorized_list)) (list pivot) (quicksort (nth 1 categorized_list)))
        )
        )
      )
  )


(defun make_list(thelist remaininglength)
  (if (eq remaininglength 0)
    thelist
    (make_list (append (list (random 25)) thelist) (- remaininglength 1))
  )
  )

(defun should_be_least_to_greatest(thelist)
  (if (< (length thelist) 2)
       nil 
      (if (<= (nth 0 thelist) (nth 1 thelist))
        (should_be_least_to_greatest (cdr thelist))
        (error "Out of order: ~d !< ~d ~%" (nth 0 thelist) (nth 1 thelist))
        )
      )
  )

(defun test_should_become_in_order(thelist)
  (let ((sortedList (quicksort thelist)))
    (format t "IN: ~a ~% SD: ~a ~% Testing sort.~%" thelist sortedList)
    (should_be_least_to_greatest sortedList)
    )
  )

(defun test_should_maintain_length(thelist)
  (if (not (eql (length thelist) (length (quicksort thelist))))
    (error "The sorted list is a different length than the original list! ~%")
    )
  )

(let ((thelist (make_list () 10)))
    (test_should_become_in_order thelist)
    (test_should_maintain_length thelist)
)


2422
5
задан 3 марта 2011 в 04:03 Источник Поделиться
Комментарии
3 ответа

Я не знаю, что такое политика о том, где/как поставить последующие комментарии код, поскольку система клиент StackExchange, похоже, не очень хорошо подходят для их нитевидные природы. В любом случае, здесь идет.

(let ((pivot (car the-list)) (the-rest (cdr the-list)))
(let ((categorized-list (categorize-list pivot the-rest () ())))

Посмотреть давай*.

(let ((the-list ()))
(loop for l from 1 to length do (setq the-list (append the-list (list (random 25))))) the-list))

Это кажется довольно неуклюжим. Это просто:

(loop for l from 1 to length collect (random 25))

И вот:

(loop for l from 0 to (- (length the-list) 2) do
(unless (<= (nth l the-list) (nth (+ l 1) the-list)) (error "Out of order: ~d < ~d ~%" (nth l the-list) (nth (+ l 1) the-list)))))

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

(loop for p on the-list while (second p)
when (< (second p) (first p))
do (error "Out of order: ~d < ~d~%" (second p) (first p)))

Если вы собираетесь писать общий Лисп код, он платит, чтобы узнать петли МКД (или итерации, ее духовным преемником).

Другие случайные вещи:


  • Ваш код стал намного ... шире. Хотя я ценю меньшее количество линий, есть предел. Я не часто вижу несколько пусть связываний на одну строчку, например.

  • Вы иногда все-таки выходит вне космос, чем парень, как список(пивот, который выглядит смешно.

5
ответ дан 5 марта 2011 в 04:03 Источник Поделиться

Ваше форматирование. Это будет намного проще для других программистов, которые будут читать ваш код, если вы используете более стандартным стилем. Например, у вас есть много строк с ничего, но висит скобки. Ваши функции имеют комментарии. Иногда вы use_underscores и иногда вы используете compoundwords но сюсюкать стиль hypenated-слова. Ваш отступ-это несовместимо: выучить команду в текстовом редакторе отступ ваш исходный код для вас, и используйте его.

Вместо:

(if (not (eql (length thelist) (length (quicksort thelist))))

Через Оку на цифры кажется странным. Я думаю, что = бы предпочтительнее. Если только с одной ветки слишком странно, когда, или если, как правило, предпочитают. Таким образом:

(unless (= (length thelist) (length (quicksort thelist)))

В другом месте, вы сделать сравнение с:

(eq remaininglength 0)

Поведение эквалайзера с целыми числами неопределено. Вы можете использовать = или в этом случае:

(zerop remaininglength)

Вы используете рекурсию много, даже если она не требуется, например, в make_list и should_be_least_to_greatest. Общий Лисп не требует оптимизация хвостовых вызовов, а не вообще общий стиль. Цикла (или цикла), вероятно, будет проще и более эффективно.

Вы входите в список применения <=. Сюсюкать по <= уже принимает любое количество аргументов, так что если вам не нужно знать конкретные элементы, которые вышли из строя, вы можете просто применить его один раз.

8
ответ дан 3 марта 2011 в 07:03 Источник Поделиться

У вас есть несколько негативных условий, что это плохая идея в любом языке.

(if (null thelist)
()

Я бы изменить его на:

(defun quicksort(thelist)
(unless (null thelist)
; Sort list
) ; Pardon the dangling ), but there's a comment on the last line

2
ответ дан 3 марта 2011 в 04:03 Источник Поделиться