Tìm kiếm nhị phân tuyến tính Vs qua JavaScript
JavaScript đi kèm với một số công cụ ngoại vi khá tiện dụng để tìm kiếm thông qua một mảng. Nhưng với một tập dữ liệu lớn, các phương thức O (n) như indexOf , find , hoặc một vòng lặp cơ bản không phải là tốt nhất hoặc thậm chí là khả thi. Thay vào đó, ta có thể sử dụng tìm kiếm binary để xem qua một mảng mà không cần xem những gì ta rõ ràng không cần, cho ta một giải pháp O (logn).
Yêu cầu
Tôi sẽ sử dụng Ký hiệu Big O khi so sánh hiệu suất và độ phức tạp, bạn có thể xem qua ở đây .
Dữ liệu thực hành
Dưới đây là một số bộ dữ liệu được sắp xếp và chưa được sắp xếp, cả hai đều có 50 mục, mà tôi sẽ tham khảo.
const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2]; const sortedArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50]; Tìm kiếm tuyến tính
Đây là giải pháp bạo lực tiêu chuẩn, tôi chắc rằng bạn đã thực hiện cả nghìn lần. Ta chỉ nói với nó, "Tôi cần một cái gì đó, vì vậy hãy xem xét từng thứ một cho đến khi bạn tìm thấy nó". Nếu có nhiều món hơn một triệu lần, thì nó sẽ lâu hơn một triệu lần, mà không ai sẽ đưa ra. Dữ liệu có được sắp xếp hay không cũng không có gì khác biệt.
const linear = (arr, target) => { let steps = 0; for (let i = 0; i < arr.length; i++) { steps++; if (arr[i] === target) return `Found: ${arr[i]} in ${steps} steps`; }; }; console.log(linear(unsortedArr, 40)); // 40 steps in 40 Milliseconds console.log(linear(sortedArr, 40)); // 40 steps in 40 Milliseconds Tìm kiếm binary
Brute-ép theo cách của bạn để đạt được một kết quả rõ ràng là một giải pháp rất chậm và không thể thay đổi được. Thay vì lãng phí tài nguyên khi nhìn vào dữ liệu rõ ràng không phải những gì ta muốn, ta có thể sử dụng phương pháp 'chia để trị' để khiến mỗi hoạt động tập trung vào việc bỏ qua những gì ta không muốn thay vì đau đớn tìm kiếm những gì ta muốn.
Ta có ba thành phần chính, hai con trỏ và một trục. Mỗi con trỏ bắt đầu ở một trong hai đầu của mảng với trục xoay ở giữa. Sau đó, ta kiểm tra xem những gì ta muốn cao hơn hay thấp hơn so với trục của ta , nếu cao hơn thì con trỏ bên trái được di chuyển đến vị trí của trục trong khi trục được di chuyển đến giữa mới. Ta tiếp tục chạy điều này cho đến khi trục quay của ta bằng mục tiêu của ta .
Với mỗi bước, ta cắt tập dữ liệu của bạn làm đôi, hoàn toàn bỏ qua những gì ta không cần, tạo cho ta độ phức tạp về thời gian là O (logn). Nếu ta chạy tìm kiếm một số trong mảng một triệu mục mất mười bước, thì một tỷ mục tìm kiếm có thể chỉ mất 15-20 bước.
const binary = (arr, target) => { let start = 0; let end = arr.length; let pivot = Math.floor((start + end) / 2); let steps = 0; for (let i = 0; i < arr.length; i++) { if (arr[pivot] !== target) { if (target < arr[pivot]) end = pivot; else start = pivot; pivot = Math.floor((start + end) / 2); steps++; }; if (arr[pivot] === target) return `Found: ${target} in ${steps} steps`; }; return 'Nothing Found'; }; console.log(linear(unsortedArr, 40)); // Nothing Found console.log(binary(arr, 44)); // 5 steps in 8 Milliseconds console.log(binary(arr, 43)); // 2 steps in 7 Milliseconds Tìm kiếm binary đi kèm với nhược điểm lớn là chỉ cho phép ta thực hiện việc này trên các mảng đã sắp xếp, nhưng có các giải pháp khác dựa trên việc sắp xếp trước dữ liệu trước khi tìm kiếm.
Kết luận
Đây chỉ là một cách áp dụng tìm kiếm binary nhưng ý tưởng có thể được cấu hình lại cho các cấu trúc dữ liệu khác nhau, miễn là nó được sắp xếp. Trong tương lai, tôi hy vọng ta có thể khám phá bằng cách sử dụng kỹ thuật này để duyệt các bộ dữ liệu nâng cao hơn với tốc độ nhanh như chớp ⚡.
Các tin liên quan
Hiểu Đệ quy & Ghi nhớ qua JavaScript2020-01-26
Đọc và xử lý tệp với API JavaScript FileReader
2020-01-23
Tìm hiểu ký hiệu Big O qua JavaScript
2020-01-20
Cách sử dụng API BroadcastChannel trong JavaScript
2020-01-13
Đa năng hóa chuỗi trong JavaScript bằng Simplur
2020-01-10
Hướng dẫn nhanh về phương pháp đối sánh chuỗi trong JavaScript
2020-01-07
Tham quan API quyền JavaScript
2020-01-05
V8 của V8: Chuỗi liên kết tùy chọn và kết hợp Nullish trong JavaScript
2019-12-29
Phân tích cú pháp, xác thực, thao tác và hiển thị ngày và giờ trong JavaScript với Day.js
2019-12-28
Cách bắt đầu với API hiệu suất JavaScript
2019-12-25
