Series Phản Phác Quy Chân – Tại sao cộng string lại chậm
series
6
string
2
code
39
C
29
program
1
White

Huy Hoàng Phạm viết ngày 08/04/2016

Series Phản Phác Quy Chân – Tại sao cộng string lại chậm

Lý giải chút về tên series

返璞归真 – Phản phác quy chân: Nghĩa là điểm cao nhất cũng chính là điểm xuất phát, được ứng dụng trong rất nhiều lĩnh vực. Trong võ học, nó có nghĩa là đạt tới cảnh giới "Tối thượng" trong truyền thuyết, quên đi tất cả võ học trong thiên hạ, bản thân đã không còn chiêu thức cụ thể, chỉ dựa vào ý cảnh mà đơn giản xử lý.

Võ học được thành lập từ các chiêu thức cơ bản, tuyệt thế võ công cũng từ các chiêu thức cơ bản mà ra. Code học cũng tạo thành từ bit/byte cơ bản, chương trình phức tạp đến mấy cũng dịch được ra bytecode. Đôi khi, ta đã quá quen với việc dùng thư viện, dùng framework mà quên thì những thứ nằm sâu bên dưới, không nắm được bản chất. Có những vấn đề mà phải nắm rõ bản chất của nó ta mới có thể giải quyết được.

Như cái tên "Phản Phác Quy Chân", series này không giới thiệu công nghệ hay ngôn ngữ mới, mà sẽ tập trung quay lại những cái bản chất, đơn giản, tinh túy nhất mà ít người quan tâm để ý (Bên tiếng Anh có một từ tương tự : Back to Basic, bỏ qua những cái phức tạp, quay lại những cái cơ bản để hiểu tận gốc vấn đề).

01_s_by_darkdamage-d5yo32c

Ở bài viết đầu, mình sẽ nhắc sơ lại về string, cũng như giải thích lý do vì sao việc cộng string sẽ ảnh hưởng tới bộ nhớ và performance của hệ thống (Hình minh họa và bài viết méo liên quan với nhau đâu, vì tác giả thích thế :v).

Chuyện về String

Ngày xửa ngày xưa, thời còn học Java, ta thường được nghe dạy rằng khi cộng chuỗi, phải dùng StringBuilder và append, thay vì cộng String. Lý do là vì String là kiểu immutable, giá trị của nó không thay đổi, khi cộng string ta tạo một string mới trong bộ nhớ. Còn StringBuilder là kiểu mutable, do đó khi ta dùng append, giá trị của nó thay đổi chứ không tạo ra string mới. Do đó dùng StringBuilder sẽ tiết kiệm bộ nhớ và chạy nhanh hơn.

Không tin à, hãy xem 2 đoạn code dưới đây, đoạn code dùng StringBuilder chỉ mất 4ms để chạy, còn đoạn code sử dụng String mất tới 4828ms (Nguồn).

int total = 50000; 

String s = "";  
for (int i = 0; i < total; i++) { s += String.valueOf(i); }  
// 4828ms 

StringBuilder sb = new StringBuilder();  
for (int i = 0; i < total; i++) { sb.append(String.valueOf(i)); }  
// 4ms 

Ta tạm gật gù đồng ý "Ồ, ra thế". Tuy nhiên, có bao giờ ta tự hỏi, tại sao cộng string lại chậm hay không? Hãy cùng đọc bài viết và tìm hiểu nhé.

Cộng string thì có vấn đề gì

Để giải thích vấn đề này, ta hãy thử trải nghiệm cảm giác "Phản phác qui chân": Bỏ qua một bên những công nghệ mới mẻ hoành tráng, những framework đồ sộ, những ngôn ngữ ảo diệu, quay lại từ cái thời ngày xửa ngày xưa còn dùng DevC, còn làm việc với byte và bộ nhớ. Đúng vậy, những kiến thức về byte, về bộ nhớ là nền tảng cho hệ thống kiến thức của bạn.

Hãy nhớ lại cách C lưu trữ string: String là một mảng các byte, có kí tự cuối cùng là kí tự null. Với cách lưu trữ này, để biết được độ dài của string, ta phải chạy một vòng lặp bắt đầu từ con trỏ chứa byte đầu tiên cho tới khi gặp kí tự null. Dưới đây là một phiên bản của hàm strcat, hàm cộng chuỗi trong C.

void strcat( char* dest, char* src )
{
     while (*dest) dest++;
     while (*dest++ = *src++);
}

Đọc code và suy ngẫm nhé. Dòng đầu tiên, code sẽ chạy từ đầu cho tới khi gặp phải null character cuối string dest, sau đó nó sẽ copy từng byte của string src và string dest. Hai vòng lặp, độ phức tạp chỉ là O(n), đâu có gì ghê gớm nhỉ?? Tuy nhiên, khi ta thực hiện việc cộng chuỗi nhiều lần, với chuỗi dài thì sao?

char bigString[1000];     
bigString[0] = '\0';
strcat(bigString,"John, ");
strcat(bigString,"Paul, ");
strcat(bigString,"George, ");
strcat(bigString,"Joel ");

Mỗi lần gọi strcat, vòng lặp sẽ chạy từ đầu cho tới cuối chuỗi, chuỗi càng dài thì vòng lặp chạy càng lâu. Tới khi chuỗi string vô cùng lớn thì việc cộng chuỗi diễn ra rất nặng nề và chậm chạp. Bác Joel có một câu chuyện cười (mình đọc chả thấy vui) để mô tả vấn đề này.

Một cô tóc vàng mới vào nghề sơn vạch phân tuyến trên đường cao tốc. Ngày đầu, cô sơn được 10 dặm, ngày hôm sau cô chỉ sơn được 7 dặm. Ông chủ nghĩ rằng cô mệt, nên cho nghỉ một ngày. Sau hôm đó, cô ta làm cũng chỉ được 5 dặm. Cứ thế mỗi ngày cô lại làm ít hơn. Ông chủ gọi cô tới hỏi:

– Có chuyện gì xảy ra thế? Tại sao năng suất của cô giảm từng ngày?

– Tôi tưởng là ông phải biết chứ! Đơn giản là càng ngày, tôi càng đi xa cái thùng sơn hơn.

Tương tự như trong truyện, string gốc càng dài thì vòng lặp phải chạy càng lâu. Do đó, để giải quyết vấn đề này, một số phiên bản khác của hàm strcat đã được tạo ra:

char* mystrcat( char* dest, char* src )
{
     while (*dest) dest++;
     while (*dest++ = *src++);
     return --dest;
}

char bigString[1000];   
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

Với cách viết này, sau khi cộng chuỗi, ta trả ra vị trí con trỏ cuối cùng. Mỗi lần cộng thêm, vòng lặp chỉ cần chạy từ con trỏ được trả cho tới cuối chuỗi src thôi, không còn lặp nhiều như thuật toán ban đầu nữa.

facebook-edgerank

Kết luận

Lâu lâu tìm hiểu về những khái niệm/ngôn ngữ bậc thấp cũng khá hay phải không nào. May mắn là chúng ta được sử dụng C#, Java tự giải phóng bộ nhớ, lại có khá nhiều thư viện hỗ trợ. Nhiều bác vẫn còn viết C, C++, truy cấp bộ nhớ bằng tay rất cực (Cực nhưng lương cao chót vót đấy nhé). Tuy nhiên, nếu mình là người viết code, trong 90% các trường hợp, mình vẫn sẽ dùng String hoặc String.Format thay vì StringBuilder!! Vì sao?? Chịu khó chờ nhé, mình sẽ dành một bài viết khác để giải thích chuyện này.

Bài viết tham khảo nhiều từ blog Joel on Software của bác Joel, một người vừa cứng technical vừa giỏi điều hành và quản lý: http://www.joelonsoftware.com/articles/fog0000000319.html. Bài viết gốc mổ xẻ khá nhiều vấn đề về performance, bộ nhớ liên quan tới string, cơ mà mình thấy không có ích mấy nên không đưa vào bài viết nhé.

Bản gốc: Blog Tôi đi code dạo.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Huy Hoàng Phạm

54 bài viết.
922 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
74 8
SOLID là gì – Áp dụng các nguyên lý SOLID để trở thành lập trình viên code “cứng” Trong quá trình học, hầu như các bạn sinh viên đều được học một s...
Huy Hoàng Phạm viết gần 3 năm trước
74 8
White
58 8
Nhập đề Kinh thư ghi lại rằng, con đường tu chân có 3 cảnh giới: Luyện khí, Trúc cơ và Kết đan. Luyện khí là quá trình rèn thân luyện thể, cho phà...
Huy Hoàng Phạm viết hơn 2 năm trước
58 8
White
53 23
Luận về comment code (Phong cách kiếm hiệp) Comment code luôn là vấn đề gây tranh cãi sứt đầu mẻ trán trong giới võ lâm. Xưa kia, thuở còn mài đít...
Huy Hoàng Phạm viết gần 3 năm trước
53 23
Bài viết liên quan
White
8 0
Microservices hiện được quan tâm trong giới phần mềm, công nghệ với nhiều bài viết, blog, thảo luận, truyền thông, hội thảo. Kỳ vọng về khả năng củ...
Tân Nguyễn viết 5 tháng trước
8 0
White
7 4
Chuyện ngày xưa Đã từng có thời, code là một việc cực kỳ mệt nhọc và nhàm chán. Đã từng có thời, lập trình việc phải làm việc với từng byte từng ...
Huy Hoàng Phạm viết 2 năm trước
7 4
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
54 bài viết.
922 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!