Có sử dụng strlen() trong điều kiện vòng lặp chậm hơn là chỉ kiểm tra ký tự null không?

Question

Tôi đã đọc rằng việc sử dụng strlen đắt hơn thử nghiệm như thế này:

Chúng tôi có một chuỗi dài x dài 100 ký tự.

Tôi nghĩ rằng

for (int i = 0; i < strlen(x); i++) 

là tốn kém hơn mã này:

for (int i = 0; x[i] != '\0'; i++) 

Có đúng? Có lẽ mã thứ hai sẽ không hoạt động trong một số trường hợp như vậy là tốt hơn để sử dụng đầu tiên?

Nó sẽ tốt hơn với bên dưới?

for (char *tempptr = x; *tempptr != '\0'; tempptr++) 

Answer 1

for (int i=0;i<strlen(x);i++) 

Mã này gọi strlen(x) mỗi lần lặp lại. Vì vậy, nếu x dài 100, strlen(x) sẽ được gọi là 100 lần. Cái này rất đắt. Ngoài ra, strlen(x) cũng đang lặp lại trên x mỗi lần giống như cách vòng lặp của bạn thực hiện. Điều này làm cho nó phức tạp O (n^2).

for (int i=0;x[i]!='\0';i++) 

Mã này không có chức năng, vì vậy sẽ nhanh hơn nhiều so với ví dụ trước. Vì nó lặp qua vòng lặp chỉ một lần, nó là O (n) phức tạp.

Answer 2

Mã đầu tiên kiểm tra độ dài của x trong mỗi lần lặp của i và phải mất O (n) để tìm 0 cuối cùng, vì vậy phải mất O (n^2), trường hợp thứ hai là O (n)

Answer 3

Tôi có thể giả sử rằng trong biến thể đầu tiên bạn tìm thấy strlen mỗi lần lặp lại, trong khi trong biến thể thứ hai bạn không làm điều đó.
Hãy thử điều này để kiểm tra:

int a = strlen(x); 
for (int i = 0; i < a; i++) {...} 

Answer 4

Nếu không có tối ưu hóa biên dịch. Có bởi vì strlen sẽ lặp lại trên mỗi byte của chuỗi mỗi lần và việc thực hiện thứ hai sẽ làm điều đó chỉ một lần.

Answer 5

Tôi đoán trình biên dịch có thể tối ưu hóa (kiểm tra Gregory Pakosz bình luận) đầu tiên của mình cho vòng lặp để bạn sẽ là như thế này:

int len = strlen(x); 
for (int i = 0; i < len; i++) 

nào vẫn là O(n).

Dù sao, tôi nghĩ rằng vòng lặp for thứ hai của bạn sẽ nhanh hơn.

Answer 6

Tất nhiên, phiên bản đầu tiên sẽ mất nhiều thời gian hơn giây thứ hai. Họ không thực sự làm điều tương tự ở tất cả - đầu tiên là tính toán chiều dài của chuỗi mỗi lần; thứ hai là (hiệu quả) làm nó chỉ một lần.

Phiên bản đầu tiên tương đương với điều này: "? Là nó hiệu quả hơn để gọi một strlen thư viện() so với thực hiện của riêng tôi"

for (int i=0; x[i] != 0; i++) 
    for (int j=0; j<i; j++) 
    ; 

Có lẽ bạn muốn nói Câu trả lời cho điều đó là, tất nhiên, "nó phụ thuộc". Trình biên dịch của bạn có thể có các phiên bản nội tại của strlen() được tối ưu hóa ngoài những gì bạn mong đợi từ nguồn, bạn có thể ở trên nền tảng mà các cuộc gọi hàm rất đắt (hiếm ngày nay), v.v.

Câu trả lời duy nhất và chính xác là "hồ sơ và tìm ra".

Answer 7

Có lần thứ hai của bạn có thể không hoạt động 100% phần trăm thời gian nhưng nó sẽ khá nhẹ. Điều này là do khi sử dụng strlen() bạn phải gọi phương thức mỗi lần. Một cách tốt hơn sẽ giống như vậy

int strLength = strlen(x); 
for (int i = 0; i < strLength; i++) 

Hy vọng điều này sẽ hữu ích.

Answer 8

Cần lưu ý rằng bạn có thể mở chính mình đến các vấn đề tràn bộ đệm nếu bạn cũng không kiểm tra chỉ mục so với kích thước của bộ đệm chứa chuỗi. Tùy thuộc vào những gì bạn đang làm với mã này, điều này có thể hoặc có thể không phải là một vấn đề thực tế, nhưng nó hiếm khi đau để có thêm kiểm tra, và đó là một thói quen tốt để có được vào.

tôi muốn đề nghị: for (i = 0; i < buf_size & & x [i] = '\ 0'; i ++)

đâu:

• buf_size là xác định trước kích thước của bộ đệm. Nếu x là một mảng, đây sẽ là sizeof(x); nếu x là một con trỏ, bạn nên có kích thước bộ đệm có sẵn.
• Tôi đã xóa tuyên bố số i khỏi vòng lặp vì chỉ có giá trị là c99 hợp lệ. Nếu bạn chỉ biên soạn dưới c99, vui lòng lưu lại trong.