Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 11.415 phút đọc

strlen

Sau bài này bạn sẽ làm được

  • Phân biệt strlen với sizeof
  • Hiểu vì sao strlen tốn thời gian tỷ lệ với độ dài chuỗi
  • Tránh gọi strlen lặp lại trong điều kiện vòng lặp
  • Tự cài lại strlen bằng hai cách

Hàm strlen đơn giản tới mức cài lại chỉ mất bốn dòng. Nhưng đằng sau nó là một đặc điểm quan trọng của chuỗi C mà nếu bỏ qua, bạn sẽ vô tình viết ra những vòng lặp chậm gấp hàng nghìn lần cần thiết.

#Cách dùng

#include <string.h>

size_t strlen(const char *s);

Trả về số ký tự trước byte 0. Byte 0 không được tính vào. Chuỗi rỗng có độ dài 0.

strlen.c
#include <stdio.h>
#include <string.h>

int main(void)
{
    printf("%zu\n", strlen("hello"));     /* 5 */
    printf("%zu\n", strlen(""));          /* 0 */
    printf("%zu\n", strlen("a b c"));     /* 5, dấu cách cũng là ký tự */
    printf("%zu\n", strlen("dong\n"));    /* 5, ký tự xuống dòng cũng tính */

    return 0;
}

#strlen so với sizeof

strlensizeof
Là gìLời gọi hàmToán tử của ngôn ngữ
Tính lúc nàoLúc chạyLúc biên dịch, trừ mảng độ dài thay đổi
Đếm cái gìKý tự trước byte 0Số byte của toàn bộ đối tượng
Byte kết thúcKhông tínhCó tính
Chi phíTỷ lệ với độ dài chuỗiBằng không
Dùng với con trỏĐược, đếm nội dungCho ra 8, kích thước con trỏ
so-sanh.c
char  a[10] = "hello";
char *p     = "hello";

strlen(a);      /* 5 */
sizeof a;       /* 10, kích thước mảng khai báo */

strlen(p);      /* 5 */
sizeof p;       /* 8, kích thước con trỏ */

sizeof "hello"; /* 6, hằng chuỗi là mảng 6 ký tự */

#Chi phí tuyến tính

Vì chuỗi C không lưu độ dài, strlen phải đi từng byte cho tới khi gặp byte 0. Với chuỗi một triệu ký tự, nó đọc một triệu byte.

terminal
# Gọi strlen một triệu lần trên chuỗi một triệu ký tự
./do-strlen
chuoi 10 ky tu,      1 000 000 lan goi: 0.002 s
chuoi 1 000 000 ky tu, 1 000 000 lan goi: uoc tinh 20 phut

#Bẫy gọi strlen trong điều kiện vòng lặp

Gọi strlen mỗi lượt lặp
for (size_t i = 0; i < strlen(s); ++i)
    if (s[i] == 'a') ++dem;

/* Với chuỗi n ký tự, đây là n lời gọi strlen, mỗi lời gọi đọc n byte.
   Tổng cộng n² phép đọc. Với n = 100000 là mười tỷ phép đọc. */
Gọi một lần, lưu vào biến
size_t n = strlen(s);

for (size_t i = 0; i < n; ++i)
    if (s[i] == 'a') ++dem;

/* n phép đọc cho strlen, cộng n phép đọc cho vòng lặp. Tổng cộng 2n. */
terminal
# Chuỗi 200 000 ký tự
./do-bay
goi strlen moi luot : 4.318 s
goi mot lan         : 0.000 s

#Tự cài lại

my-strlen.c
/* Cách 1: bằng chỉ số */
size_t my_strlen1(const char *s)
{
    size_t n = 0;

    while (s[n] != '\0')
        ++n;

    return n;
}

/* Cách 2: bằng con trỏ, lấy hiệu hai con trỏ */
size_t my_strlen2(const char *s)
{
    const char *p = s;

    while (*p != '\0')
        ++p;

    return (size_t)(p - s);
}

Cách thứ hai là cách của thư viện chuẩn. Phép trừ hai con trỏ cùng kiểu cho ra số phần tử giữa chúng, kiểu ptrdiff_t. Chương 12 sẽ dạy kỹ về số học con trỏ.

Bộ kiểm thử

test.c
#include <assert.h>
#include <string.h>

static void kiem_thu(const char *s)
{
    assert(my_strlen1(s) == strlen(s));
    assert(my_strlen2(s) == strlen(s));
}

int main(void)
{
    kiem_thu("");                  /* chuỗi rỗng */
    kiem_thu("a");                 /* một ký tự */
    kiem_thu("hello");             /* bình thường */
    kiem_thu("a b\tc\n");          /* có khoảng trắng */
    kiem_thu("\x01\x02\x03");      /* ký tự không in được */

    char dai[10001];

    memset(dai, 'x', 10000);
    dai[10000] = '\0';
    kiem_thu(dai);                 /* chuỗi dài */

    puts("Tat ca kiem thu deu qua");

    return 0;
}

Thủ thuật đọc theo khối

theo-khoi.c
/* Ý tưởng của bản trong thư viện: kiểm tra tám byte cùng lúc.
   Biểu thức (x - 0x0101...) & ~x & 0x8080... khác 0 khi và chỉ khi
   trong tám byte của x có ít nhất một byte bằng 0. */
static int co_byte_khong(unsigned long long x)
{
    return ((x - 0x0101010101010101ULL) & ~x & 0x8080808080808080ULL) != 0;
}

Bạn chưa cần hiểu biểu thức này ngay, Chương 31 về thao tác bit sẽ giải thích. Điều đáng ghi nhận bây giờ là: cùng một bài toán, cùng một độ phức tạp, mà cách cài đặt tạo ra chênh lệch mười lần. Đó là lý do luôn nên dùng hàm thư viện thay vì bản tự viết, trừ khi bạn đang học.

Tự làm thử

  1. In strlen và sizeof của một mảng ký tự, một con trỏ và một hằng chuỗi. Giải thích cả sáu con số.
  2. Viết vòng lặp gọi strlen mỗi lượt trên chuỗi hai trăm nghìn ký tự, đo thời gian, rồi sửa và đo lại.
  3. Cài cả hai phiên bản my_strlen và chạy bộ kiểm thử so với bản chuẩn.
  4. Đo thời gian của bản tự cài và bản thư viện trên chuỗi mười triệu ký tự, tính tỷ lệ.
  5. Viết vòng lặp duyệt ngược chuỗi bằng cả hai cách trong bài, thử với chuỗi rỗng.
  6. Viết macro BAT_DAU_BANG và dùng nó để lọc các dòng bắt đầu bằng một tiền tố cho trước.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

  • strlen đếm ký tự trước byte 0 và không tính byte đó, trả về kiểu size_t không dấu.
  • sizeof tính lúc biên dịch và đếm cả byte kết thúc. strlen tính lúc chạy và không đếm.
  • Chi phí của strlen tỷ lệ với độ dài chuỗi, vì chuỗi C không lưu độ dài ở đâu cả.
  • Không bao giờ gọi strlen trong điều kiện vòng lặp. Gọi một lần hoặc dùng điều kiện s[i] != '\0'.
  • Kiểm thử hàm tự cài bằng cách so kết quả với hàm chuẩn trên nhiều trường hợp biên.