Có thư viện Haskell cho phép tôi có một Bản đồ từ phạm vi đến giá trị không? (Ưu tiên một chút hiệu quả.)Thư viện Bản đồ Phạm vi Haskell
let myRangeMap = RangeMap [(range 1 3, "foo"),(range 2 7, "bar"),(range 9 12, "baz")]
in rangeValues 2
==> ["foo","bar"]
Tác vụ này được gọi là truy vấn đâm trên một khoảng thời gian. Một cấu trúc dữ liệu hiệu quả cho nó được gọi là (một chiều) segment tree.
SegmentTree package cung cấp triển khai cấu trúc dữ liệu này, nhưng tiếc là tôi không thể tìm ra cách sử dụng cấu trúc dữ liệu này. (Tôi cảm thấy rằng giao diện của gói này không cung cấp mức trừu tượng phù hợp.)
Có lẽ rangemin library làm những gì bạn muốn?
Tốt cũ Data.Map (và nó hiệu quả hơn Data.IntMap anh em họ) có chức năng
splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
mà chia bản đồ thành submaps các phím ít hơn/lớn hơn một chìa khóa nhất định. Điều này có thể được sử dụng cho một số loại phạm vi tìm kiếm.
Vâng, Data.Map chắc chắn là hữu ích ở đây. Tôi đã sử dụng khá thành công cho việc định tuyến kiểu "địa chỉ gần nhất" đối với việc định tuyến các thông báo mạng. 'minView' và' maxView' cùng với các anh em họ '* WithKeys' của chúng cũng hữu ích. –
Tôi đã viết thư viện để tìm kiếm trong khoảng thời gian chồng chéo, vì các gói hiện tại không phù hợp với nhu cầu của tôi. Tôi nghĩ rằng nó có thể có một giao diện dễ tiếp cận hơn ví dụ SegmentTree:
http://www.chr-breitkopf.de/comp/IntervalMap/index.html
Nó cũng có sẵn trên Hackage: http://hackage.haskell.org/package/IntervalMap
Tôi luôn thích nghe về cấu trúc dữ liệu lần đầu tiên. Rất tuyệt. –