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

一般来说，(几乎)不可能提高这种算法的性能:为了删除两个无序和不可散列列表中的重复项，可以在 < em>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以及。在这种情况下，您可以使用 fromList运行时间复杂度为 O(n log n) 的方法为两个列表创建 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)