Haskell：两个整数列表之间的匹配数？

发布于 2024-12-21 17:22:29 字数 151 浏览 0 评论 0原文

假设我有两个整数列表：

4 12 24 26 35 41

42 24 4 36 2 26

这两个列表之间有 3 个匹配项。

如何计算 Haskell 中任意两个列表之间的匹配数？

谢谢。

原文

Say I have two lists of integers:

4 12 24 26 35 41

42 24 4 36 2 26

There are 3 matches between the two lists.

How do I count the number of matches between any two list in Haskell?

Thanks.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

反差帅 2024-12-28 17:22:29

如果您不需要处理多个元素，最简单的方法是计算交集的长度

import Data.List

matches :: Eq a => [a] -> [a] -> Int
matches xs ys = length (intersect xs ys)

如果您还有一个 ，则使用 Set 作为中间结构会更有效Ord 实例：

import qualified Data.Set as S

matches :: Ord a => [a] -> [a] -> Int
matches xs ys = S.size (S.intersection (S.fromList xs) (S.fromList ys))

如果您需要处理重复，使用 Map 计算每个元素出现的次数将是一个不太困难的修改。

If you don't need to take care of multiple elements, the easy way is to calculate the length of the intersection

import Data.List

matches :: Eq a => [a] -> [a] -> Int
matches xs ys = length (intersect xs ys)

Somewhat more efficient is using Sets as intermediate structures, if you also have an Ord instance:

import qualified Data.Set as S

matches :: Ord a => [a] -> [a] -> Int
matches xs ys = S.size (S.intersection (S.fromList xs) (S.fromList ys))

If you need to take care of repetitions, using a Map counting the number of occurrences for each element would be a not too difficult modification.

回复收藏 0 原文

灯下孤影 2024-12-28 17:22:29

处理列表会非常痛苦，因为你需要遍历所有的列表。像这样的东西通过形成所有相等的对然后计算大小来打印出正确的答案。

let xs = [1,2,3,4]
let ys = [1,2,3,4]
length [x | x <- xs, y <- ys, x == y]

从性能的角度来看，这样做是相当尴尬的。对于大型列表，您最好使用集合，因为您可以比使用列表 (O(N)) 更快地测试成员资格（通常为 O(lg N)，有时为 O(1) ）。

It's going to be quite painful with lists as you've going to need to go through them all the pairs. Something like this prints out the right answer by forming all pairs where they are equal and then counting the size.

let xs = [1,2,3,4]
let ys = [1,2,3,4]
length [x | x <- xs, y <- ys, x == y]

It's quite awkward to do it this way from a performance point of view. For large lists you're better off using a set as you can test membership quicker (typically O(lg N), sometimes O(1) ) than you can with a list (O(N)).

回复收藏 0 原文

情绪失控 2024-12-28 17:22:29

Data.List 中的函数 intersect 返回两个给定列表之间的交集。

import Data.List (intersect)

numberOfIntersections :: (Eq a) => [a] -> [a] -> Int
numberOfIntersections xs ys = length $ intersect xs ys

main = do
    print $ numberOfIntersections [4, 12, 24, 26, 35, 41] [42, 24, 4, 36, 2, 26]

The function intersect from Data.List returns the intersection between two given lists.

import Data.List (intersect)

numberOfIntersections :: (Eq a) => [a] -> [a] -> Int
numberOfIntersections xs ys = length $ intersect xs ys

main = do
    print $ numberOfIntersections [4, 12, 24, 26, 35, 41] [42, 24, 4, 36, 2, 26]

回复收藏 0 原文

盛装女皇 2024-12-28 17:22:29

如果您想要一个仅使用列表的解决方案，并且不像 Data.List.intersect 那么慢，您可以使用以下命令：

intersectSorted [] _ = []
intersectSorted _ [] = []
intersectSorted (x : xs) (y : ys) = case compare x y of
  LT -> intersectSorted xs (y : ys)
  EQ -> x : intersectSorted xs ys
  GT -> intersectSorted (x : xs) ys

intersect a b = intersectSorted (sort a) (sort b)

If you want a solution using only lists, which is not so slow as Data.List.intersect, you can use this:

intersectSorted [] _ = []
intersectSorted _ [] = []
intersectSorted (x : xs) (y : ys) = case compare x y of
  LT -> intersectSorted xs (y : ys)
  EQ -> x : intersectSorted xs ys
  GT -> intersectSorted (x : xs) ys

intersect a b = intersectSorted (sort a) (sort b)

回复收藏 0 原文

~没有更多了~