có một thuật toán nhanh hơn tìm kiếm nhị phân, để tìm kiếm trong các giá trị được sắp xếp của mảng không?Tìm kiếm nhanh hơn tìm kiếm nhị phân cho danh sách có thứ tự
trong trường hợp của tôi, tôi có một giá trị được sắp xếp (có thể là bất kỳ giá trị loại) trong một mảng A, tôi cần phải trả lại n nếu giá trị tôi đang tìm kiếm nằm trong phạm vi của A[n] and A[n+1]
Bạn có thể làm tốt hơn O (log n) nếu giá trị là số nguyên, trong trường hợp đó là trường hợp xấu nhất bạn có thể đạt được, về n, là O (sqrt (log n)). Nếu không, không có cách nào để đánh bại O (log n) trừ khi có các mẫu trong chuỗi đầu vào. Có hai phương pháp được sử dụng để đánh bại O (log n) trong trường hợp các số nguyên.
Trước tiên, bạn có thể sử dụng cây nhanh nhanh có thể hoạt động bằng cách lưu trữ trong bảng băm tất cả các tiền tố mà bạn đang lưu trữ ít nhất một số nguyên với tiền tố đó. Điều này cho phép bạn thực hiện tìm kiếm nhị phân để tìm độ dài của tiền tố trùng khớp dài nhất. Điều này cho phép bạn tìm thấy sự kế thừa của một phần tử mà bạn đang tìm kiếm trong thời gian O (log w) trong đó w là số bit trong một từ. Có một số chi tiết để làm việc mặc dù để thực hiện công việc này và chỉ sử dụng không gian tuyến tính, nhưng chúng không quá tệ (xem liên kết bên dưới).
Thứ hai, bạn có thể sử dụng cây hợp nhất, sử dụng các thủ thuật bit để cho phép bạn thực hiện các phép so sánh trong một số hướng dẫn liên tục, cho thời gian chạy O (log n/log w).
Sự cân bằng tối ưu giữa hai cấu trúc dữ liệu này xảy ra khi log w = sqrt (log n), cho thời gian chạy O (sqrt (log n)).
Để biết chi tiết về việc trên, thấy các bài giảng 12 và 13 tất nhiên Erik Demaine của: http://courses.csail.mit.edu/6.851/spring07/lec.html
Tôi muốn biết thêm về cây nhiệt hạch. Có lẽ bạn muốn sẵn sàng khám phá chúng: http://stackoverflow.com/questions/3878320/understanding-fusion-trees – xscott
@xcott Im không chắc chắn bạn không quá tối ưu hóa trừ khi bạn đang viết một thư viện số chuyên nghiệp. –
Có và không. Có, tìm kiếm nhanh hơn, trung bình hơn là tìm kiếm chia đôi. Nhưng tôi tin rằng họ vẫn là O (lg N), chỉ với một hằng số thấp hơn.
Bạn muốn giảm thiểu thời gian cần tìm để tìm phần tử của bạn. Nói chung, nó là mong muốn sử dụng ít bước hơn, và một cách để tiếp cận điều này là để tối đa hóa số lượng dự kiến của các yếu tố sẽ được loại bỏ ở mỗi bước. Với bisection, luôn luôn chính xác một nửa các yếu tố được loại bỏ. Bạn có thể làm tốt hơn điều này, NẾU bạn biết điều gì đó về sự phân bố của các nguyên tố. Tuy nhiên, thuật toán để chọn phần tử phân vùng thường phức tạp hơn việc chọn điểm giữa, và độ phức tạp thêm này có thể áp đảo bất kỳ khoản tiết kiệm thời gian nào bạn mong đợi nhận được từ việc sử dụng ít bước hơn.
Thực sự, trong một vấn đề như thế này tốt hơn là tấn công các hiệu ứng bậc hai như vùng nhớ đệm, hơn là thuật toán tìm kiếm. Ví dụ, khi thực hiện tìm kiếm nhị phân lặp lại, cùng một vài phần tử (thứ nhất, thứ hai và thứ ba phần tư) được sử dụng RẤT thường xuyên, vì vậy đặt chúng trong một dòng bộ nhớ cache duy nhất có thể vượt trội hơn so với truy cập ngẫu nhiên vào danh sách.
Chia mỗi cấp thành 4 hoặc 8 phần bằng nhau (thay vì 2) và thực hiện tìm kiếm tuyến tính thông qua tìm kiếm tuyến tính cũng nhanh hơn tìm kiếm chia đôi, vì tìm kiếm tuyến tính không yêu cầu tính phân vùng và cũng có ít hơn phụ thuộc dữ liệu có thể gây ra các bộ nhớ cache.
Nhưng tất cả những điều này vẫn là O (lg N).
Trên một danh sách đơn đặt hàng, không. Nhưng có nhiều tìm kiếm nhanh hơn; bạn chỉ cần một cấu trúc dữ liệu khác với một danh sách có thứ tự. Một băm sẽ hầu như không đổi trong thời gian tra cứu, với chi phí rất nhiều bộ nhớ. Một phương pháp lai có thể lấy cách tiếp cận của một từ điển. – tchrist
@tchrist: Vấn đề đòi hỏi phải tìm ra cặp yếu tố ràng buộc chặt chẽ mục nhập tìm kiếm không có trong danh sách. Hashing chỉ tìm thấy kết quả khớp chính xác. –
Rất tiếc, bạn đã đúng. Bằng cách nào đó tôi chỉ đọc câu đầu tiên, không phải câu thứ hai. – tchrist
Bạn luôn có thể đặt chúng trong bảng băm, sau đó tìm kiếm sẽ là O (1). Nó sẽ là bộ nhớ chuyên sâu mặc dù và nếu bạn tiếp tục thêm các mục, bảng băm có thể cần phải được re-bucketed. Re-bucketing là O (n) nhưng nó sẽ được khấu hao thành O (1). Nó chủ yếu phụ thuộc vào việc bạn có thể đủ khả năng không gian đó và bộ nhớ cache tiềm năng bỏ lỡ.
Có thể mảng của anh ta không chứa giá trị n, nhưng có chứa hai giá trị có giá trị n. Nó không rõ ràng rằng băm được áp dụng ở đây. – xscott
Ồ tôi đã bỏ lỡ điều đó.Nhưng bạn vẫn có thể băm đầu tiên và quay trở lại tìm kiếm nhị phân nếu giá trị không nằm trong tập hợp khóa. Nhưng đây là một sự phức tạp thêm. Nói chung, bạn không thể làm tốt hơn entropy của việc phân phối các giá trị. Nếu bạn biết sự phân bố, bạn có thể sử dụng một cây Huffman để quyết định nơi bạn phân vùng. – srean
Nếu các giá trị trong danh sách được phân phối đồng đều thì bạn có thể thử chia tách theo trọng số thay vì phân tách nhị phân, ví dụ: nếu giá trị mong muốn là một phần ba của con đường từ giới hạn dưới hiện tại đến giá trị hiện tại thì bạn có thể thử phần tử đó cũng là phần thứ ba của con đường. Điều này có thể bị nặng trên danh sách nơi các giá trị được nhóm lại mặc dù.
Một số tối ưu hóa khác là cần thiết. Bạn không muốn chọn yếu tố gần nhất với nơi bạn đoán câu trả lời, bạn muốn kiểm tra một điểm giữa vị trí được đoán và giữa danh sách, để với p> .5 bạn loại bỏ hơn một nửa danh sách. Điểm phân vùng tối ưu chính xác phụ thuộc vào việc phân phối các giá trị trong danh sách. –
Những gì bạn mô tả chính xác là tìm kiếm nội suy. @Ben một cách hiệu quả để thực hiện đề xuất của bạn là thông qua một cây Huffman – srean
Một khả năng là xử lý nó như tìm gốc rễ của hàm. Về cơ bản, việc tìm kiếm:
a[i] <= i <= a[i + 1]
Tương đương với:
a[i] - i <= 0 <= a[i + 1] - i
Sau đó, bạn có thể thử một cái gì đó giống như phương pháp của Newton và vân vân. Các loại thuật toán này thường hội tụ nhanh hơn tìm kiếm nhị phân khi chúng hoạt động, nhưng tôi không biết một thuật toán nào được đảm bảo hội tụ cho tất cả đầu vào.
Phương pháp của Newton đòi hỏi một chức năng khác biệt, do đó, một trong những sẽ phải phù hợp với một sppolating spline đầu tiên. Nếu các giá trị là uni-modal của nó khá tốt cư xử khác nó có thể phân kỳ và hành động hoàn toàn kỳ quái. – srean
Có. Bạn có thể sử dụng spline tuyến tính, và đạo hàm tại bất kỳ điểm nào là: f '(i) = a [i + 1] - a [i] – xscott
Tuyến tính tuyến tính là tuyến tính từng phần, do đó đạo hàm của nó sẽ không liên tục. Người ta phải đi cho atleast bậc hai. Đó không phải là biggie. Điều này sẽ tương tự như [http://en.wikipedia.org/wiki/Interpolation_search] – srean
Trong tìm kiếm nhị phân bạn chia danh sách thành hai "danh sách con" và bạn chỉ tìm kiếm trên sublist có thể chứa giá trị. Tùy thuộc vào mảng của bạn lớn như thế nào, bạn có thể thấy tăng tốc nếu bạn chia mảng thành nhiều hơn hai mối nối.
Bạn có thể xác định vùng nào của mảng mà bạn phải tìm kiếm bằng cách giữ chỉ mục mà bạn tìm kiếm trước tiên. Giống như trong một cuốn sách điện thoại của một thành phố lớn, nơi bạn có thể nhìn thấy từ bên ngoài, nơi bạn phải bắt đầu tìm kiếm. (Tôi gặp khó khăn khi thể hiện ý tưởng của mình bằng văn bản và tôi không tìm thấy liên kết tiếng Anh nào giải thích tốt hơn).
Trước hết, biện pháp trước khi thực hiện tối ưu hóa.
Bạn có thực sự cần tối ưu hóa tìm kiếm đó không?
Nếu có, thì thứ hai, hãy suy nghĩ về sự phức tạp về thuật toán trước. Ví dụ. bạn có thể sử dụng cây (chẳng hạn như một số std::map) thay vì một mảng không? Nếu vậy thì tùy thuộc vào tần suất chèn/xóa tương đối so với tìm kiếm, nhưng tiền đề của việc sắp xếp mảng sắp xếp cho thấy rằng tìm kiếm thường xuyên so với thay đổi tập dữ liệu, do đó sẽ có ý nghĩa để thực hiện một số công việc bổ sung cho chèn/xóa, làm cho mỗi tìm kiếm nhanh hơn nhiều - cụ thể là thời gian logarit.
Nếu bạn thấy rằng thời gian tìm kiếm là một nút cổ chai cần giải quyết, và không, không thay đổi biểu diễn dữ liệu và danh sách ngắn, khi đó tìm kiếm tuyến tính sẽ nhanh hơn vì nó ít hoạt động hơn so sánh.
Nếu không, nếu danh sách dài hơn và không phân phối giá trị cụ thể hoặc giả định và giá trị không thể được coi là số và tiêu thụ bộ nhớ phải không đổi (quy định việc xây dựng bảng băm) , sau đó tìm kiếm nhị phân tạo ra 1 bit thông tin cho mỗi so sánh và có lẽ là tốt nhất bạn có thể thực hiện cho tìm kiếm đầu tiên.
Chúc mừng & hth.
Nếu bạn có một số lượng lớn các số để tìm, và bởi một số sán mà chúng được sắp xếp, bạn có thể làm điều đó trong O (n + m) trong đó m là số các số cần tìm. Về cơ bản chỉ là thuật toán kết hợp điển hình của bạn, với sửa đổi nhỏ để ghi lại giá trị mà mỗi số được kiểm tra sẽ được chèn vào trước đó, nếu nó được chèn vào mảng.
Bạn luôn có thể giao dịch ngoài không gian ... Và thời gian của các hoạt động khác.Giả sử tất cả các phần tử của bạn là các bit p kích thước không đổi, bạn có thể tạo một mảng lớn lưu trữ, cho mỗi giá trị có thể bạn tra cứu, chỉ mục của giá trị lớn hơn tiếp theo hiện được lưu trữ. Mảng này cần phải là 2^p * lg (n) bit, trong đó n là các giá trị số được lưu trữ. Mỗi lần chèn hoặc xóa là O (2^p) nhưng thường khoảng 2^p/n, bởi vì bạn phải cập nhật tất cả các chỉ mục đó.
Nhưng tra cứu của bạn bây giờ là O (1)!
OK, OK, nó không thực sự thực tế. Nhưng việc chia đầu vào thành các khối theo kiểu tương tự có thể làm giảm hằng số ở phía trước nhật ký của bạn. Có thể.
Điều gì về bản ngã sau? được gọi là Tìm kiếm theo hàm mũ và là một trong các biến thể tìm kiếm nhị phân. http://en.m.wikipedia.org/wiki/Exponential_search
Tìm kiếm phần tử k trong mảng được sắp xếp A có kích thước n. Tra cứu A [2^i] cho i = 0, 1, 2, ... cho đến khi bạn đi xa hơn vị trí của k trong A. sau đó thực hiện tìm kiếm nhị phân trên phần của mảng còn lại (nhỏ hơn) so với i.
int exponential_search(int A[], int key)
{
// lower and upper bound for binary search
int lower_bound = 0;
int upper_bound = 1;
// calculate lower and upper bound
while (A[upper_bound] < key) {
lower_bound = upper_bound;
upper_bound = upper_bound * 2;
}
return binary_search(A, key, lower_bound, upper_bound);
}
Bản ngã này sẽ chạy trên O (log idx) trong đó idx là chỉ số của k trong A. (cả hai chữ cái đều ở log logx). Trong trường hợp xấu nhất, algo là trong O (log idx), nếu k nằm trong số các phần tử lớn nhất của A hoặc lớn hơn bất kỳ phần tử nào A. Hằng số nhân lớn hơn tìm kiếm nhị phân nhưng bản ngã sẽ chạy nhanh hơn cho rất lớn mảng và khi tìm kiếm dữ liệu về phía đầu của mảng.
I'D muốn có một số ý tưởng về kích thước tối thiểu n trong đó bản ngã này trở nên thích hợp hơn với tìm kiếm nhị phân, nhưng tôi không biết.
Lưu ý rằng phép nhân ở đây có thể được thay thế bằng một ca nhị phân đơn giản; nó thực sự rẻ. –
Mặc dù trong trường hợp chung bạn không thể làm tốt hơn O (log N), bạn ít nhất có thể tối ưu hóa điều đó, do đó làm giảm đáng kể hằng số tỷ lệ trước mặt O (log N).
Nếu bạn phải thực hiện nhiều tìm kiếm trên cùng một mảng, chúng có thể được vector hóa bằng cách sử dụng các phần mở rộng SIMD, do đó giảm thêm chi phí tính toán. Cụ thể, nếu bạn đang xử lý các mảng các số dấu phẩy động thỏa mãn các thuộc tính nhất định, thì có nhiều cách để xây dựng một chỉ mục đặc biệt, sau đó cho phép tìm kiếm mảng trong O (1).
Tất cả các khía cạnh trên được thảo luận với kết quả kiểm tra trong: Cannizzo, 2015, Fast and Vectorizable Alternative to Binary Search in O(1) Applicable to a Wide Domain of Sorted Arrays of Floating Point Numbers Giấy đi kèm với mã nguồn trên github.
Nếu bạn có máy tính lượng tử, bạn có thể thử http://en.wikipedia.org/wiki/Grover%27s_algorithm :) –
@David: Danh sách được sắp xếp, do đó thuật toán của Grover tệ hơn tìm kiếm chia đôi. O (sqrt N)> O (lg N) –
máy trạng thái làm việc theo thứ tự độ lớn đối với tôi trên dữ liệu lớn, nhưng độ phức tạp/bộ nhớ cho các trạng thái xây dựng lớn hơn nhiều so với sắp xếp. – technosaurus