Cấu trúc dữ liệu tốt nhất cho hàng xóm gần nhất trong 1 chiều

Question

Tôi có danh sách giá trị (1 chiều) và tôi muốn biết cấu trúc/thuật toán dữ liệu tốt nhất để tìm giá trị truy vấn gần nhất mà tôi có. Hầu hết các giải pháp (tất cả?) Tôi tìm thấy các câu hỏi ở đây dành cho 2 hoặc nhiều thứ nguyên. Ai có thể đề xuất với tôi cách tiếp cận cho trường hợp của tôi?

Bản năng của tôi cho tôi biết sắp xếp dữ liệu và sử dụng tìm kiếm nhị phân bằng cách nào đó. Bằng cách này, không có giới hạn về thời gian xây dựng hoặc chèn cho bất kỳ cây nào cần thiết, vì vậy có lẽ ai đó có thể đề xuất một cây tốt hơn so với chỉ đơn giản là một danh sách được sắp xếp.

Answer 1

Nếu bạn cần một cái gì đó nhanh hơn O (log (n)), bạn có thể dễ dàng tìm được với một mảng được sắp xếp hoặc tìm kiếm nhị phân cây, bạn có thể sử dụng van Emde Boas Tree. Cây vEB cung cấp cho bạn O (log (log (n))) để tìm kiếm phần tử gần nhất ở hai bên.

Answer 2

Sắp xếp danh sách và sử dụng tìm kiếm nhị phân để tìm phần tử bạn đang tìm kiếm, sau đó so sánh các hàng xóm bên trái và bên phải của bạn. Bạn có thể sử dụng một mảng là truy cập O (1).

Cái gì như:

int nearest(int[] list, int element) { 

    sort(list); 
    int idx = binarySearch(element, list); 

    // make sure you are accessing elements that exist 
    min = (element - list[idx-1] <= list[idx+1] - element) ? idx-1 : idx+1; 

    return list[min]; 
} 

này là O (n log n), mà sẽ được khấu hao theo nếu bạn đang đi để thực hiện nhiều cái nhìn up.

EDIT: Cho rằng bạn sẽ phải di chuyển các phân loại ra của phương pháp này

Answer 3

Như bạn đã đề cập, cách nhanh nhất và dễ nhất nên được phân loại dữ liệu và sau đó tìm kiếm bên trái và hàng xóm bên phải của một điểm dữ liệu.

Answer 4

Nếu thời gian chèn không liên quan, thì tìm kiếm nhị phân trên mảng được sắp xếp là cách đơn giản nhất để đạt được thời gian truy vấn O (log N). Mỗi lần một mục được thêm vào sắp xếp mọi thứ. Đối với mỗi truy vấn, thực hiện tìm kiếm nhị phân. Nếu tìm thấy một kết quả phù hợp, hãy trả lại. Nếu không, tìm kiếm nhị phân sẽ trả về chỉ mục của mục, nơi nó cần được chèn vào. Sử dụng chỉ mục này để kiểm tra hai mục lân cận và xác định mục nào trong số đó gần với điểm truy vấn.

Tôi cho rằng có các giải pháp với thời gian O (1). Tôi sẽ cố gắng nghĩ về điều không liên quan đến việc sử dụng quá nhiều bộ nhớ ...

Answer 5

Sử dụng OCaml của Set:

module S = Set.Make(struct type t = int let compare = compare end) 

let nearest xs y = 
    let a, yisin, b = S.split y xs in 
    if yisin then y 
    else 
     let amax, bmin = S.max_elt a, S.min_elt b in 
     if abs (amax - y) < abs (bmin - y) then amax else bmin 

Ngẫu nhiên, bạn có thể đánh giá cao nth-nearest neighbor sample từ OCaml for Scientists và The F#.NET Journal bài viết của tôi Traversing networks: nth-nearest neighbors.