爲什麼工會不返回一個唯一的列表？

爲什麼Hyperspec的以下聲明是這樣的？「如果列表1和列表2之間存在重複，則結果中只有一個重複實例存在。如果列表1或列表2中有重複條目，則冗餘條目可能會或可能不會出現在結果中。「爲什麼工會不返回一個唯一的列表？

直到我讀到這個，我假設工會應該返回一個唯一的列表，並沮喪爲什麼我的代碼沒有這樣做。刪除列表之間的重複但不在內部似乎也很奇怪。爲什麼甚至指定這個？

看起來應該能假設工會會產生一個獨特的集合元素列表，或者我錯過了什麼？

對於Hyperspec完整的頁面看到http://clhs.lisp.se/Body/f_unionc.htm

來源

2012-05-30 mcheema

如果您的代碼僅設置了唯一元素（如1 2 3），那麼UNION將保留此屬性。

如果您的代碼設置了非唯一元素（如1 2 2 3），則UNION不需要付出任何努力來強制執行結果集中的唯一性。

使用單獨的功能刪除重複項：REMOVE-DUPLICATES。

來源

2012-05-30 19:25:10

假設兩個列表是參數UNION的元素是唯一意味着，在最壞情況下，算法的複雜性（非排序，非哈希的元素）是O（n * m）。另一方面，在這種情況下刪除列表中的重複項是O（n^2）。即使在沒有重複的情況下，使聯盟刪除重複項目也會使運行時間增加約3倍，因爲大部分時間都是通過比較消耗的。

來源

2012-05-30 15:48:01 Ramarren

爲什麼不只是附加兩個列表，然後應該花費O（1）次？列表之間沒有模糊的要求阻止了這個，所以這可能是爲什麼它被包含在規範中;爲什麼買？ – mcheema

因爲APPEND不是UNION。 Union是一個集合操作，並且在集合上進行調用時（即，在測試中唯一的元素列表），它將執行集合操作。該規範允許UNION不強制參數是邏輯集，因爲這很昂貴。（同樣在O（n）中的CL APPEND中，其中n是除第一個參數以外的所有長度，默認CL中沒有真正的列表）。 – Ramarren

錯誤... @Ramarren ...鏈接列表如何「不是真正的列表」？無可否認，沒有指向尾巴的指針（至少不是默認情況下），但我很難將它們看作是真實的。 – Vatine

爲什麼工會不返回一個唯一的列表？

回答

相關問題