Haskell: Số trận đấu giữa hai danh sách ints?

Question

Nói rằng tôi có hai danh sách các số nguyên:

4 12 24 26 35 41 

42 24 4 36 2 26 

Có 3 trận đấu giữa hai danh sách.

Làm cách nào để đếm số lượng kết quả trùng khớp giữa hai danh sách trong Haskell?

Cảm ơn.

Answer 1

Nếu bạn không cần phải chăm sóc nhiều yếu tố, một cách dễ dàng là để tính toán chiều dài của ngã tư

import Data.List 

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

Hơi hiệu quả hơn là sử dụng Set s như cấu trúc trung gian, nếu bạn cũng có một Ord dụ:

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)) 

Nếu bạn cần phải chăm sóc bản lặp đi lặp lại, sử dụng một Map đếm số lần xuất hiện cho mỗi phần tử sẽ là một thay đổi không phải là quá khó khăn.

Answer 2

Sẽ rất khó khăn với các danh sách vì bạn sẽ cần phải thực hiện tất cả các cặp. Một cái gì đó như thế này in ra câu trả lời đúng bằng cách hình thành tất cả các cặp mà họ bằng nhau và sau đó đếm kích thước.

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

Đó là khá khó khăn khi phải làm theo cách này từ một quan điểm thực hiện xem. Đối với các danh sách lớn, bạn nên sử dụng một bộ như bạn có thể kiểm tra thành viên nhanh hơn (thường là O (lg N), đôi khi O (1)) so với bạn có thể với một danh sách (O (N)).

Answer 3

Chức năng intersect từ Data.List trả về giao điểm giữa hai danh sách nhất định.

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] 

Answer 4

Nếu bạn muốn có một giải pháp sử dụng chỉ liệt kê, mà không phải là quá chậm như Data.List.intersect, bạn có thể sử dụng này:

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)