Tôi có một khoảng thời gian Trong = (an, bn). Tôi cần phải chạy rất nhiều cái nhìn up nơi tôi đang cung cấp một thời gian t và cần phải nhanh chóng trở lại khoảng thời gian có chứa t, ví dụ, những khoảng thời gian như vậy mà một < = t < = tỷ.Cấu trúc dữ liệu cho khoảng thời gian nhanh chóng tra cứu
Cấu trúc hoặc thuật toán dữ liệu tốt cho điều này là gì?
Nếu điều quan trọng, trong trường hợp của tôi, an và bn là số nguyên.
Những gì bạn đang tìm kiếm là Interval Tree (là một loại Range Tree).
Chúng có thời gian tra cứu logarit giống như các cấu trúc cây khác (ví dụ: cây RB), vì vậy bạn sẽ thấy hiệu suất có thể so sánh để sử dụng một cái gì đó như Bản đồ cây Java hoặc bản đồ STL.
Có triển khai C++ một cây khoảng cách tại http://www.mit.edu/~emin/source_code/cpp_trees/index.html, được liên kết từ http://stackoverflow.com/questions/212808/help-finding-c-interval-tree-algorithm-implementation –
Tốt. Cảm ơn các liên kết! – tgamblin
Liên kết cho [Triển khai C#] (http://www.emilstefanov.net/Projects/RangeSearchTree.aspx) không hoạt động nữa. – krlzlx
Về cơ bản, đây là câu hỏi phân vùng không gian. Bạn có một không gian rộng lớn với các thùng chứa và một điểm cụ thể trong không gian đó, nó sẽ chạm vào những thùng chứa nào? Rất nhiều trò chơi phải giải quyết vấn đề này, vì vậy sẽ không có ý tưởng tồi khi bắt đầu ở đó. Tìm các bài viết về "phát hiện va chạm pha rộng".
Cách đơn giản nhất để làm điều này là chia không gian số của bạn thành một số lượng không đổi các phần. Mỗi phần biết được những bộ nào giao nhau với nó, một cái gì đó mà bạn tính toán bất cứ khi nào một bộ mới được thêm vào. Bây giờ, thay vì kiểm tra từng bộ đơn khi bạn có một điểm, bạn chỉ cần kiểm tra các bộ chứa trong phần mà điểm đó đang ở.
Một thuật toán tổng quát và hiệu quả khác được sử dụng là Phân tách không gian nhị phân. Thuật toán này chia nhỏ không gian của bạn thành hai mặt. Mỗi bên sẽ biết những bộ nào giao nhau với nó. Bạn có thể lặp lại quá trình này một cách đệ quy đến độ chính xác mong muốn của bạn (mặc dù nó không có ý nghĩa để tạo ra một phân khu nhỏ hơn phạm vi của tập nhỏ nhất của bạn).
Vấn đề của bạn chỉ là một chiều, do đó, nó đơn giản hơn một chút so với các vấn đề phân vùng không gian được tìm thấy trong hầu hết các trò chơi. Bạn có thể chỉ có một BST đơn giản và trong mỗi lá nhớ danh sách các khoảng thời gian bên trái từ lá.
nếu bạn có khoảng A (0, 10) và B (5, 15) thì lá của cây sẽ là (0 có danh sách trống), (5 với A), (10 với A, B) và (15 với B).
Bạn được chào đón để kiểm tra C# implementation I've posted on CodePlex for IntervalTree mà giải quyết vấn đề này một cách chính xác.
Ido.
Hạn chế về bộ nhớ? – ChaosPandion
Không có ràng buộc về bộ nhớ –
Giải pháp Java: https://stackoverflow.com/questions/13399821/data-structures-that-can-map-a-range-of-keys-to-a-value – Vadzim