Tìm kiếm nhị phân trong Erlang trong lg (n) thời gian

Question

Tôi đã tìm kiếm thông qua các công việc có thể xung quanh để tìm kiếm nhị phân ở Erlang và tôi tìm thấy http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/ Nhưng tôi đã tự hỏi liệu giải pháp trong blog có chạy trong O (lg n) hay không. Bây giờ kể từ khi lặp lại cho tìm kiếm nhị phân là: T (n) = T (n/2) + c mang lại cho tôi một thời gian thực hiện của O (lg n).

Vì trong mảng C, bạn có khả năng truy cập bất kỳ phần tử nào trong thời gian O (1). Nhưng trong xóa nếu truy cập vào giữa danh sách mất thời gian cn, sau đó tìm kiếm nhị phân chạy trong thời gian tổng thể tuyến tính như người nghèo như tìm kiếm tuyến tính.

Tôi đã xem các danh sách: nth/2 BIF để tìm mục thứ n trong danh sách nhưng tôi không chắc về thời gian thực hiện của nó.

Mọi nhận xét?

Answer 1

Có một vài cấu trúc dữ liệu cho phép truy cập O (1) trong Erlang: bảng ETS, bộ dữ liệu và tệp nhị phân.

Hiện tại, không có tiện ích nào trong số đó thực sự phù hợp cho tìm kiếm nhị phân. Bảng ETS hỗ trợ tìm kiếm ngay từ đầu và nếu không, dữ liệu sẽ được sao chép vào quy trình của bạn khi trả lại kết quả, có khả năng sẽ không tối ưu cho trường hợp sử dụng của bạn.

Tuples cho phép O (1) truy cập với element/2, nhưng sửa đổi chúng có một chi phí nhất định (đó là lý do tại sao mô-đun mảng sử dụng cây của bộ dữ liệu).

Sau đó, bạn có mã nhị phân (<<1,2,3,4,5>>), cho phép cho một cái gì đó tương tự như con trỏ số học, như trong ví dụ sau:

1> Sorted = <<$a,$b,$c,$d,$e,$f,$g,$h>>. 
<<"abcdefgh">> 
2> <<_:3/binary, X:1/binary, _/binary>> = Sorted. 
<<"abcdefgh">> 
3> X. 
<<"d">> 

Tuy nhiên, dự đoán hiệu suất khi xây dựng các hệ nhị phân là một chút sơ sài, và điều này loại số học con trỏ là khó khăn hơn để làm nếu giá trị của bạn có các loại khác nhau và kích cỡ khác nhau khi đại diện trong một nhị phân.

Đặt cược tốt nhất của bạn có thể sẽ là sử dụng danh sách giá trị, sắp xếp, sau đó sử dụng list_to_tuple/1 để điều hướng xung quanh nó với element/2.

Tuy nhiên, tôi khuyên bạn nên sử dụng cây để thực hiện tìm kiếm của mình; nó có thể sẽ đơn giản hơn nhiều để sử dụng mô-đun gb_tree để xây dựng một cây cân bằng và vẫn nhận được tìm kiếm O (log N).

Answer 2

nth là O (n). Sử dụng array module cho cấu trúc dữ liệu truy cập không đổi (mảng như trong C - gần như).