strlen nhanh hơn?

Question

Điển hình strlen() di chuyển ngang từ ký tự đầu tiên cho đến khi tìm thấy \0. Điều này yêu cầu bạn phải duyệt qua từng ký tự. Trong ý nghĩa thuật toán, O (N) của nó.

Có cách nào nhanh hơn để thực hiện việc này khi đầu vào được xác định mơ hồ không. Giống như: độ dài sẽ nhỏ hơn 50 hoặc độ dài khoảng 200 ký tự.

Tôi đã nghĩ về các khối tra cứu và tất cả nhưng không nhận được bất kỳ tối ưu hóa nào.

Answer 1

Thực ra, glibc's implementation trong số strlen là một ví dụ thú vị về cách tiếp cận vector hóa.Đó là đặc biệt ở chỗ nó không sử dụng hướng dẫn vector, nhưng tìm thấy một cách để chỉ sử dụng hướng dẫn thông thường trên 32 hoặc 64 bit từ từ bộ đệm.

Answer 2

Chắc chắn. Theo dõi độ dài trong khi bạn đang viết vào chuỗi.

Answer 3

Câu trả lời ngắn gọn: không.

Câu trả lời dài hơn: bạn có thực sự nghĩ rằng nếu có một cách nhanh hơn để kiểm tra độ dài chuỗi cho các chuỗi C của barebones, một cái gì đó thường được sử dụng như thư viện chuỗi C sẽ không kết hợp nó?

Nếu không có một số kiến ​​thức bổ sung về chuỗi, bạn phải kiểm tra từng ký tự. Nếu bạn sẵn sàng duy trì thông tin bổ sung đó, bạn có thể tạo struct lưu trữ độ dài dưới dạng trường trong cấu trúc (ngoài mảng ký tự/con trỏ thực tế cho chuỗi), trong trường hợp đó bạn có thể tạo độ dài tra cứu hằng số thời gian, nhưng sẽ phải cập nhật trường đó mỗi khi bạn sửa đổi chuỗi.

Answer 4

Rõ ràng, nếu chuỗi của bạn có độ dài tối thiểu đã biết, bạn có thể bắt đầu tìm kiếm tại vị trí đó.

Ngoài ra, bạn không thể thực hiện bất kỳ điều gì; nếu bạn cố gắng làm một cái gì đó thông minh và tìm thấy một byte \0, bạn vẫn cần kiểm tra từng byte giữa bắt đầu của chuỗi và điểm đó để đảm bảo rằng không có trước đó \0.

Điều đó không có nghĩa là không thể tối ưu hóa strlen. Nó có thể được pipelined, và nó có thể được thực hiện để xử lý kích thước từ hoặc khối vector với mỗi so sánh. Trên hầu hết các kiến ​​trúc, một số kết hợp của các phương pháp này và các phương pháp tiếp cận khác sẽ mang lại một sự tăng tốc liên tục đáng kể trên một vòng lặp so sánh byte ngây thơ. Tất nhiên, trên hầu hết các nền tảng trưởng thành, hệ thống strlen đã được triển khai bằng các kỹ thuật này.

Answer 5

Bạn có thể thử sử dụng vectơ. Không chắc chắn nếu trình biên dịch sẽ có thể thực hiện nó, nhưng tôi đã làm nó bằng tay (sử dụng nội tại). Nhưng nó có thể giúp bạn chỉ cho các chuỗi dài.

Sử dụng chuỗi stl, an toàn hơn và std :: lớp chuỗi chứa độ dài của nó.

Answer 6

Jack,

strlen tác phẩm bằng cách tìm kiếm kết thúc '\ 0', đây là một thực hiện lấy từ OpenBSD:

size_t 
strlen(const char *str) 
{ 
     const char *s; 

     for (s = str; *s; ++s) 
       ; 
     return (s - str); 
} 

Bây giờ, hãy xem xét mà bạn biết chiều dài là khoảng 200 ký tự, như bạn đã nói. Giả sử bạn bắt đầu từ 200 và lặp lên và xuống cho '\ 0'. Bạn đã tìm thấy một ở 204, có nghĩa là gì? Đó là chuỗi dài 204 ký tự? KHÔNG! Nó có thể kết thúc trước đó với một '\ 0' và tất cả những gì bạn đã làm là nhìn ra ngoài giới hạn.

Answer 7

Nhận bộ xử lý Core i7.

Core i7 đi kèm với bộ chỉ lệnh SSE 4.2. Intel đã thêm bốn hướng dẫn vector bổ sung để tăng tốc các tác vụ tìm kiếm liên quan và strlen.

Dưới đây là một vài suy nghĩ thú vị về các hướng dẫn mới:

http://smallcode.weblogs.us/oldblog/2007/11/