比较集合的功能；帮助提高效率 [英] A function to compare sets; help improving efficiency

问题描述

我正在尝试编写一个比较两个列表以查看它们是否表示相同集合的函数.即'(a b c d d)和'(d c b a d)代表相同的集合.元素可以是任意顺序.

I am attempting to write a function which compares two lists to see if they represent the same set. That is '(a b c d d) and '(d c b a d) represent the same set. The elements can be in any order.

这就是我所拥有的，可以正常工作:

This is what I have, which works:

(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操作是否确实删除了任何内容，一次用于递归测试其余列表(没有该元素).

The reason I do not like this is that (remove (car list1) list2 :count 1)) is being computed twice - once to test if the remove operation truly removed anything, and once to recursively test the rest of the list(s) sans that element.

任何人都可以提出一种无需使用其他算法即可改善这一点的方法吗?

Can anyone suggest a way to improve this without using a different algorithm?

推荐答案

(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))))
    )
)

首先让我们正确设置其格式:

First let's format it correctly:

(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)))))

如果您使用两次表单，并且想要更改它，那么您需要存储一个值. LET是为此而构建的.如果它不适合一个COND，则需要第二个.

If you use a form twice and you want to change that, then you need to store a value. LET is the construct for that. If it doesn't fit into one COND, then you need a second one.

(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)))))))

现在，EQ不能用于比较列表.使用EQUAL.

Now, EQ can't be used to compare lists. Use 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:

COND is overkill here, use 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)))))

现在，您只需要使函数执行家庭作业中要求的功能即可.但这还是你的功课.

Now, you only need to make the function do what was asked in the homework. But it is your homework anyway.

这篇关于比较集合的功能；帮助提高效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！