Grep chạy quá nhanh như thế nào?

Question

Tôi thực sự ngạc nhiên bởi chức năng của GREP trong shell, trước đây tôi sử dụng phương pháp chuỗi con trong java nhưng bây giờ tôi sử dụng GREP cho nó và nó thực hiện trong vài giây, nó nhanh hơn mã java mà tôi đã từng sử dụng (theo kinh nghiệm của tôi tôi có thể sai mặc dù)

Điều đó đang được nói rằng tôi đã không thể tìm ra cách nó đang xảy ra? cũng không có sẵn trên web.

Có ai có thể giúp tôi với điều này không?

Answer 1

Giả sử câu hỏi của bạn có liên quan đến GNU grep cụ thể. Đây là một lưu ý của tác giả, Mike Haertel:

GNU grep là nhanh vì AVOIDS LOOKING AT EVERY INPUT BYTE.

GNU grep là nhanh vì nó thực hiện các lệnh rất ít CHO MỖI BYTE rằng nó không nhìn vào.

GNU grep sử dụng thuật toán Boyer-Moore nổi tiếng, trông đầu tiên cho chữ cái cuối cùng của chuỗi đích và sử dụng bảng tra cứu để cho biết mức độ vượt xa đầu vào bất cứ khi nào tìm thấy a ký tự không khớp.

GNU grep cũng bỏ vòng lặp bên trong của Boyer-Moore và thiết lập các mục bảng đồng bằng Boyo-Moore theo cách sao cho không cần làm kiểm tra thoát vòng lặp ở mọi bước chưa được kiểm tra. Kết quả của điều này là rằng, trong giới hạn, grep GNU trung bình ít hơn 3 x86 hướng dẫn được thực thi cho mỗi byte đầu vào mà nó thực sự xem xét (và nó bỏ qua hoàn toàn byte).

GNU grep sử dụng các cuộc gọi hệ thống đầu vào Unix thô và tránh sao chép dữ liệu sau khi đọc. Hơn nữa, GNU grep AVOIDS BREAKING INPUT INTO LINES. Tìm kiếm dòng mới sẽ làm chậm grep xuống theo hệ số là nhiều lần, bởi vì để tìm các dòng mới, nó sẽ phải xem xét mỗi byte!

Vì vậy, thay vì sử dụng đầu vào dòng theo định hướng, GNU grep đọc dữ liệu thô thành một bộ đệm lớn, tìm kiếm bộ đệm sử dụng Boyer-Moore, và chỉ khi nó tìm thấy một trận đấu nào nó đi và tìm kiếm các dòng mới bounding (Các tùy chọn dòng lệnh nhất định như -n tắt tối ưu hoá này.)

Câu trả lời này là tập hợp con thông tin được lấy từ here.

Answer 2

Để thêm vào câu trả lời tuyệt vời của Steve.

Nó có thể không được biết đến rộng rãi nhưng grep là hầu như luôn luôn nhanh khi grepping cho một còn mẫu dây hơn một ngắn , bởi vì trong một mô hình lâu hơn, Boyer-Moore có thể bỏ qua về phía trước trong những bước tiến dài để đạt được thậm chí tốt hơn sublinear tốc độ:

Ví dụ:

# after running these twice to ensure apples-to-apples comparison 
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log 
28 
0.168u 0.068s 0:00.26 

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log 
28 
0.100u 0.056s 0:00.17 

Biểu mẫu dài hơn nhanh hơn 35%!

Bằng cách nào? Boyer-Moore bảo vệ một bảng chuyển tiếp từ chuỗi mẫu và bất cứ khi nào có sự không khớp, nó chọn bỏ qua dài nhất có thể (từ lần cuối cùng đến trước) trước khi so sánh một char trong đầu vào với char trong phần bỏ qua bàn.

Dưới đây là a good video explaining Boyer Moore

Một quan niệm sai lầm phổ biến (ví GNU grep) là fgrep nhanh hơn grep. f trong fgrep không phù hợp với 'nhanh', nó là viết tắt của 'cố định' (xem trang người đàn ông), và vì cả hai đều là cùng một chương trình, và cả hai đều sử dụng Boyer-Moore, không có sự khác biệt về tốc độ giữa chúng khi tìm kiếm chuỗi cố định không có ký tự đặc biệt regexp. Lý do duy nhất tôi sử dụng fgrep là khi có một char đặc biệt regexp (như ., [] hoặc *) Tôi không muốn nó được hiểu như vậy. Và thậm chí sau đó, hình thức di động/tiêu chuẩn hơn của grep -F được ưu tiên hơn fgrep.