Функция для сравнения наборов; помочь улучшить эффективность - PullRequest
Новая
       19

Функция для сравнения наборов; помочь улучшить эффективность

1 голос
/ 08 февраля 2011

Я пытаюсь написать функцию, которая сравнивает два списка, чтобы увидеть, представляют ли они один и тот же набор.То есть '(a b c d d) и '(d c b a d) представляют один и тот же набор.Элементы могут быть в любом порядке.

Это то, что у меня есть, и это работает: 

(defun samesetp (list1 list2)
  (cond
    ((null list1) (null list2))
    ((eq list2 (remove (car list1) list2 :count 1)) nil)
    (t (samesetP (cdr list1) (remove (car list1) list2 :count 1))))))

Причина, по которой мне это не нравится, состоит в том, что (remove (car list1) list2 :count 1)) вычисляется дважды - один разчтобы проверить, действительно ли операция remove что-то удалила, и один раз для рекурсивного тестирования остальных списков без этого элемента.

Кто-нибудь может предложить способ улучшить это без использования другого алгоритма?

Ответы [ 2 ]

10 голосов
/ 08 февраля 2011 
(defun samesetp (list1 list2)
    (cond
        ((null list1) (null list2))
        ((eq list2 (remove (car list1) list2 :count 1)) nil)
        (t (samesetP (cdr list1) (remove (car list1) list2 :count 1))))
    )
)

Сначала давайте отформатируем это правильно: 

(defun samesetp (list1 list2)
  (cond ((null list1) (null list2))
        ((eq list2 (remove (car list1) list2 :count 1)) nil)
        (t (samesetP (cdr list1) (remove (car list1) list2 :count 1)))))

Если вы дважды используете форму и хотите изменить ее, вам нужно сохранить значение. Пусть это конструкция для этого. Если он не помещается в один КОНД, тогда вам нужен второй. 

(defun samesetp (list1 list2)
  (cond ((null list1) (null list2))
        (t (let ((list3 (remove (car list1) list2 :count 1)))
             (cond ((eq list2 list3) nil)
                   (t (samesetP (cdr list1) list3)))))))

Теперь эквалайзер нельзя использовать для сравнения списков. Используйте EQUAL. 

(defun samesetp (list1 list2)
  (cond ((null list1) (null list2))
        (t (let ((list3 (remove (car list1) list2 :count 1)))
             (cond ((equal list2 list3) nil)
                   (t (samesetP (cdr list1) list3)))))))

COND здесь избыточен, используйте IF: 

(defun samesetp (list1 list2)
  (if (null list1)
      (null list2)
    (let ((list3 (remove (car list1) list2 :count 1)))
      (if (equal list2 list3)
          nil
        (samesetP (cdr list1) list3)))))

Теперь вам нужно только заставить функцию делать то, что было задано в домашнем задании. Но это все равно твоя домашняя работа.

1 голос
/ 05 августа 2011

Полагаю, вам не разрешено использовать встроенные функции для решения проблемы, но просто заметьте, что есть одна: 

(set-difference list1 list2)
...