如何优化Scheme中获取两列表互斥非共有元素的函数？

Great catch—your current implementation works, but as you suspected, its efficiency isn't ideal. Let's break down why, then explore a few optimized approaches tailored to different use cases.

Why Your Current Code Is Slow #

Your uncommon_list function uses memv (a linear search) and remove (another full list traversal) in each recursive step. For lists of length n and m, this leads to a time complexity of O(n*m)—which gets really slow as your lists grow larger. Additionally, creating new lists with remove on every recursive call adds unnecessary memory overhead.

Optimized Approach 1: Built-in Set Operations (For Unique Elements) #

If you're working with lists where elements are unique (or you don't mind deduplicating), Scheme implementations like Racket have built-in set utilities that make this trivial and efficient:

(define (uncommon-list list1 list2)
  (let ((set1 (list->set list1))
        (set2 (list->set list2)))
    (set->list (set-symmetric-difference set1 set2))))

How This Works: #

• list->set converts each list to a set (O(n log n) time for each list, since sets rely on sorted or hashed storage for fast lookups).
• set-symmetric-difference directly computes elements present in exactly one set (O(n + m) time).
• set->list converts the result back to a list.
• Overall time complexity: O(n log n + m log m)—a massive improvement over O(n*m) for large lists.

Optimized Approach 2: Hash Tables (For Multiset Symmetric Difference) #

If you need to preserve duplicate elements (matching your original code's behavior, where duplicate elements are paired and removed), a hash table to count element occurrences is the way to go. This runs in O(n + m) time—the best possible for this problem:

(define (uncommon-list list1 list2)
  (let ((counts (make-hash)))
    ; Count occurrences in list1 (increment by 1)
    (for-each (lambda (x)
                (hash-update! counts x add1 0))
              list1)
    ; Subtract occurrences from list2 (decrement by 1)
    (for-each (lambda (x)
                (hash-update! counts x sub1 0))
              list2)
    ; Generate the result list from the count differences
    (apply append
           (hash-map->list
            (lambda (k v)
              (cond
                ((positive? v) (make-list v k))  ; Extra elements in list1
                ((negative? v) (make-list (- v) k))  ; Extra elements in list2
                (else '())))  ; Elements present equally in both lists
            counts))))

How This Works: #

• We use a hash table to track the net count of each element (list1 occurrences minus list2 occurrences).
• For elements with a positive count: they appear more times in list1—we add them to the result that many times.
• For elements with a negative count: they appear more times in list2—we add the absolute value of the count to the result.
• Elements with a zero count are present equally in both lists, so we ignore them.

Optimized Approach 3: Hash Tables for Fast Lookup (Preserving Element Order) #

If you want to keep the original order of elements (matching your recursive implementation's output order), you can use hash tables for O(1) membership checks instead of linear searches:

(define (uncommon-list list1 list2)
  (let ((set1 (make-hash))
        (set2 (make-hash)))
    ; Populate hash tables for instant lookups
    (for-each (lambda (x) (hash-set! set1 x #t)) list1)
    (for-each (lambda (x) (hash-set! set2 x #t)) list2)
    ; Collect elements from list1 not in list2, then elements from list2 not in list1
    (append (filter (lambda (x) (not (hash-has-key? set2 x))) list1)
            (filter (lambda (x) (not (hash-has-key? set1 x))) list2))))

Note: #

This approach treats elements as unique (like the set method), so duplicates in a single list will be preserved if they don't exist in the other list. For example, (uncommon-list '(a a) '(b)) returns (a a).

内容的提问来源于stack exchange，提问作者nitronoid