list - Haskell中具有重复项的交叉点的快速长度

Question

我正在编写一个主脑求解器，并在一个内部循环中计算两个列表的intersection with duplicates的长度。现在我有的功能是

overlap :: Eq c => [c] -> [c] -> Int
overlap [] _ = 0
overlap (x:xs) ys
    | x `elem` ys = 1 + overlap xs (delete x ys)
    | otherwise = overlap xs ys

有可能使它更快吗？如果有帮助， overlap的参数是相同长度的短列表，最多6个元素，并且 c类型的可能值少于10。

Answer 1

通常，几乎（几乎）不可能提高这种算法的性能：为了删除两个无序且不可哈希的列表中的重复项，可以在O（n ^ 2）中完成。

通常，您可以通过以下条件（每种条件，不同的方法）来提高性能：


例如，如果您可以确保为您创建/修改/ ...的每个列表保持元素的顺序；这可能需要一些工程。在这种情况下，该算法可以在O（n）中运行。

在这种情况下，您可以使用以下命令运行它：

--Use this only if xs and ys are sorted
overlap :: Ord c => [c] -> [c] -> Int
overlap (x:xs) (y:ys) | x < y = overlap xs (y:ys)
                      | x > y = overlap (x:xs) ys
                      | otherwise = 1 + overlap xs ys
overlap [] _ = 0
overlap _ [] = 0

通常，列表的排序可以在O（n log n）中完成，因此比O（n ^ 2）重叠算法更有效。新的重叠算法在O（n）中运行。
如果订购了 c，则也可以使用 Data.Set。在这种情况下，您可以使用在O（n log n）中运行的 fromList方法为两个列表创建一个TreeSet，然后使用 intersection函数以O（n）时间计算交集，最后使用 size函数计算大小。

--Use this only if c can be ordered
overlap :: Ord c => [c] -> [c] -> Int
overlap xs ys = size $ intersection (fromList xs) (fromList ys)