avl tree

âu rồi mới trở về những “bài tập lập trình” cơ bản, như thời ĐH, những vấn đề thú vị, nhưng cần sự tập trung cao và kéo dài khi coding. Bài toán như sau: hầu hết các hệ điều hành đều cung cấp cho người dùng hệ thống tập tin (file), các thư mục lồng nhau (nested) và chứa trong đó những thư mục con, tạo thành một hình cây (tree)! Nhưng đó là với người dùng, thực chất, hệ thống tổ chức bên dưới dạng flat – list, một danh sách phẳng, hiểu đơn giản là một cái mảng lớn không phân cấp chứa tất cả các tập tin! Mỗi tập tin ở mức quản lý thấp của HĐH chỉ có số (inode) chứ không có tên, đọc từ đầu đến cuối đĩa chỉ là cái mảng một chiều có rất nhiều phần tử. Tiếp theo đó, ở lớp (layer) kế trên, người ta mới đề cập đến tên của tập tin (file name, path).

Ví dụ như: ~/Downloads/aaa.pdf hay /System/Library/CoreServices… Từ những đường dẫn đầy đủ này truy vấn từng cấp, ra được số inode và tìm đến các khối lưu trữ thực bên dưới! Nhưng lưu và tìm thế nào cho nhanh, không phải duyệt cái mảng quá lớn? Tên tập tin, đường dẫn thư mục thực chất được tổ chức thành dạng cây AVL – AVL tree! Độ phức tạp của thuật toán tìm kiếm sẽ giảm từ O(n) xuống thành O(log(n)). Ngồi đọc lại bài xuất bản năm 1962 của hai nhà bác học Liên Xô: Georgy Adelson-Velsky và Evgenii Landis, lâu lắm rồi mới được trở lại code C đúng nghĩa! Đơn giản là tự ra bài tập để làm cho vui, tìm lại cái cảm giác lập trình chân chính, thực sự, sau nhiều năm tháng toàn code lảm nhảm Swift, Python, etc…


từ của năm

hững ngày cuối năm tương đối nhàn nhã, suy nghĩ lung tung… Báo chí phương Tây thường có chuyện bầu chọn “từ” điển hình của năm. Ngôn ngữ mà, luôn thay đổi, luôn nghĩ ra từ mới để phản ánh thực tế biến động! Nếu có bầu chọn từ điển hình trong năm của VN, tôi nghĩ nó sẽ là từ “tượng”, với định nghĩa: 1 tượng = 1 ngàn tỷ! Đây theo tôi là một từ rất hay, rất đắt, vô cùng… Vietic! Như chữ Hán cổ thì sẽ là: 萬,億,兆,京,垓,秭,穰,溝,澗,正,載,極 – vạn ức triệu kinh cai tỷ nhương câu giản chính tái cực. Nhưng tiếng Việt hiện đại không có từ nên đành phải đặt ra từ mới thôi!

Chứ suốt 4 ngàn năm lịch sử dân tộc, chưa bao giờ, chưa từng có khi nào có nhu cầu phải dùng con số lớn đến như vậy! Và dùng số lớn quá, trăm ngàn tỷ này nọ sẽ gây ra nhiều bất tiện khi ghi chép, lại rất khó hình dung về độ lớn! Nói vụ Vạn Thịnh Phát gây thiệt hại chỉ có hơn 300 tượng à, nghe có phải là nhỏ nhắn và nhẹ nhàng hơn nhiều không?! Tương tự, các con số đầu tư, đề án này nọ cũng như thế, những dự án 350 tượng, 500 tượng, nghe nó nhẹ hẫng như thinh không vậy! Năm cũ sắp qua đi, năm mới sắp đến, cùng với những sự hoang đường ngày càng khổng lồ hơn! 🙁

thiên hạ trường hà

âu lắm mới xem được một phim “chính kịch” TQ hay như thế, mà phim thế này thường sẽ không có phụ đề tiếng Việt, chả ai đi dịch cái phim mà biết chắc không có mấy khán giả xem! Không có khán giả vì không có trai xinh, gái đẹp cùng với những màn giật gân, đồng bóng khác! Nhưng đúng là khá lâu mới được xem lại những thủ pháp phim “chính kịch” TQ, nhiều năm không thấy gặp, nhiều đoạn rất thấm với cái nội dung thâm thuý của nó! Đây có lẽ là phim làm để chuẩn bị tiền đề dư luận cho dự án “Nam thuỷ Bắc điều” hiện đại của TQ. Phim lấy bối cảnh triều Thanh, Khang Hy gia, Hoàng Hà tràn bờ, nước lụt đe doạ nhiều tỉnh! Hoàng đế lệnh xuống cho các quan lại địa phương và các quan phụ trách đê điều (Hà đạo): Nhân tại đê tại, Đê vong nhân vong – 人在堤在,堤亡人亡 – Người còn thì đê còn, Đê mất thì người mất! Hà đạo tham quan, Vương Quang Dụ biết chạy không thoát tội nên đã tự sát!

Tuần phủ An Huy – Cận Tử Viên mấy chục ngày ở tại công trường đốc thúc hộ đê, nhưng cuối cùng đê vẫn vỡ! Tử Viên bị dòng nước cuốn đi, nhưng may mắn được cứu sống, bị áp giải về kinh để điều tra! Quần thần nghị luận: giết hay không giết!? Ai ai cũng muốn giết, làm con dê tế thần, giết là bịt luôn đầu mối không truy ra được những quan nào đã ăn bớt việc sửa đê! Chỉ có một người khuyên can Khang Hy không giết, giết rồi dư luận sẽ bảo rằng hoàng đế: Sát nhân hữu phương, Trị hà vô lực – 杀人有方,治河无力 – Có cách để giết người, nhưng vô phương trị thuỷ! Từ đó bắt đầu một đại công trình kéo dài hơn mấy chục năm, Trị lý Hoàng hà! Xem để thấy rằng với những công trình quốc kế dân sinh to lớn, người TQ làm với trách nhiệm và quyết tâm lớn lao! Khác với thời cổ đại, đơn giản chỉ là đắp đê cho cao và khơi thông dòng chảy cho rộng, việc trị thuỷ hiện đại có nhiều chuyện phức tạp hơn thế…

jacquard loom

âu về trước có viết bài nói về công nghiệp dệt may đã là động cơ chủ yếu của Cách mạng Công nghiệp Anh như thế nào, góp phần hình thành nên một xã hội bắt đầu có nhu cầu tiêu dùng, mà tiêu dùng đầu tiên là ăn mặc đẹp đẽ, sang trọng. Nhưng đôi khi nhìn lại, ta sẽ thấy sự phát triển kỳ diệu của các ngành công nghệ khác nhau như những tấm gương lấp lánh phản chiếu lẫn nhau nhiều cấp! Dưới đây nói về sự phát triển của ngành dệt đã góp phần tạo ra công nghệ thông tin hiện đại như thế nào! Trung Quốc phát minh ra các kiểu dệt gấm, Trung Đông có những kiểu dệt thảm rất đẹp! Để tạo ra những hoa văn đầy sắc màu đó, đơn giản là điều chỉnh cách thức các sợi vải ngang, dọc, chéo đan xen vào nhau! Đến năm 1804, thương gia Pháp Joseph Marie Jacquard phát minh ra cái máy dệt mang tên mình!

Nhìn từ trên xuống, có thể hình dung tấm gấm như một ma trận điểm (dot matrix), mà ‘on’ hay ‘off’ là trạng thái nổi hay chìm của các sợi vải đan xen vào nhau! Jacquard đã dùng chuỗi các bìa giấy đục lỗ (punched card) để mã hoá các thông tin hoa văn này, cho phép dệt ra những kiểu hoa văn tuỳ ý! Đây cũng xem như là máy dùng bìa đục lỗ đầu tiên, chỉ cần thay một băng giấy khác là có thể dệt ra được kiểu hoa văn tương ứng! Bìa đục lỗ được sử dụng như cách mã hoá đầu vào – input, rồi sau đó được sử dụng để mã hoá đầu ra – output! Đến năm 1888 thì Herman Hollerith người Mỹ sử dụng nguyên tắc bìa đục lỗ tương tự để làm ra máy thống kê sử dụng để điều tra dân số, máy chạy nhanh hơn 10 lần so với dùng người để tính toán thủ công! Tiền thân của các loại máy tính hiện đại đã ra đời… từ nghề dệt như thế!

bolero

ác ku Bolero xứ Vịt bắt đầu tung hô, tôi cũng là “bolero” nhé! Mịa, éo tự luận ra được ngu chỗ nào mà lúc nào cũng bám lấy cái danh hão, nhạc thì như đống cxx, nội dung rỗng tuếch, toàn những loại “ốc mượn hồn”, ăn cắp, vay mượn lung tung, nhận càng nhận vơ, chẳng có cái nội dung gì cho nên thân, toàn thứ lảm nhảm, xàm xí, thiểu năng!

Thế rồi lên wiki cả tiếng Anh, tiếng Việt, bịa ra một thứ như “đúng rồi”! Chắc là chưa nghe “bolero” của người khác bao giờ, hoặc cũng có nghe nhưng không có khả năng nhìn ra được sự khác biệt! Chả trách cố sống cố chết bám víu vào mớ ngôn từ nhảm nhí, chả trách ai đưa cái cxx gì cũng nghe, cũng tin, dân trí nó đang ở tầm như thế!

… hiện thực

iết tiếp post trước để nói rõ hơn về kỹ thuật và công nghệ! Công nghệ là quan trọng, nhưng nó cũng chỉ là tập hợp các giải pháp kỹ thuật từ nhỏ đến lớn trong đó! Không thể bỏ lơ công nghệ, nhưng muốn hiểu nó kỹ càng là phải đi từ đầu, tức là hiểu kỹ thuật, hiểu những nguyên tắc vận hành cơ bản bên dưới! Nên ai đó mà bảo rành công nghệ mà không rành kỹ thuật, điều đó tôi không tin, không hiểu chuyện nhỏ, làm sao hiểu chuyện lớn?! Chính những người không làm được chuyện nhỏ, nên cứ lấy chuyện lớn để khoả lấp, vung vít lên! Ngày xưa thì là các ngôn ngữ Visual, nào là XML, SOAP, etc… ngày nay thì AI, Blockchain, ChatGPT, etc… Cứ lặp đi lặp lại nhưng kiểu thiểu năng thấy phát chán, họ nghĩ rằng người ta không biết công phu của họ tới đâu hay sao!? Chán nhất là những thể loại AI thế này thế kia… nói mãi mà chẳng có gì cụ thể cả! Cụ thể ví dụ như: thuật toán nhận dạng khuôn mặt của tôi có độ chính xác 99.9%! Hay AI của tôi giúp giảm 10% thời gian hàng hoá lưu kho, tiết kiệm chừng này chi phí logistics. Hay AI của tôi giúp tối ưu lộ trình shipper giao hàng, tiết kiệm chừng này thời gian, chừng này xăng dầu!

ó phải đi vào từng bài toán cụ thể, chả ai lặp đi lặp lại mãi những từ AI – Trí tuệ nhân tạo mà éo nói được nội dung gì! Nói có thể mọi người không tin, nhưng em đã từng gặp rất nhiều coder VN, toán cộng trừ nhân chia đơn giản không làm được, chưa nói thuật toán gì cao siêu, làm cái vòng lặp tính tổng cũng chưa được: bảng cân đối trong ngày có 50 giao dịch con, mỗi giao dịch con lợi nhuận 1, 2%… tổng lợi nhuận trong ngày = 1 + 2 + … = 50% (!!!) tính kiểu này thì thành tỷ phú hết! Hoàn toàn không có một chút khái niệm toán cấp 1 nào trong đầu, viết đoạn code 5 ~ 10 dòng không được, nhưng công nghệ nào cũng biết cả đấy! 🙁 Cái giáo dục nào đã tạo ra những loại như thế, giờ báo chí bắt đầu rên rỉ, nào là VN không tự sản xuất được, không tạo ra được sản phẩm gì! Nói thì mọi người bảo là xỉa xói, cực đoan nhưng nhìn kỹ lại sẽ thấy: tất cả đều là nhân – quả hiển nhiên, khi bỏ lơ những điều nhỏ nhoi nhưng căn bản tất nhiên sẽ dẫn đến thảm trạng như vậy! Mà căn bản nhất của giáo dục chính là dạy cách làm người! Đương nhiên, thủ phạm không hoàn toàn là giáo dục, giáo dục thực ra cũng là nạn nhân của một xã hội suy đồi mà thôi!

mơ mộng …

ghĩ lại thời còn đi học ở ĐH KHTN, mặc dù tôi học hành dạng không quá xuất sắc, nhưng nghĩ lại cái thời đó vẫn xem là một điểm sáng! Cái suy nghĩ cho rằng cần phải học công nghệ, “đi tắt đón đầu”, học các ngành có thể ứng dụng thực tế ngay, đó là một kiểu suy nghĩ không hoàn toàn đúng, cũng có thể nói là có nhiều sai lầm! Trị trường cần cái gì thì dạy cái đó, nó chỉ là một nửa của vấn đề! Một nửa còn lại là học hành cũng chính là không gian rộng mở đề phát triển cá nhân, để mơ mộng, chính vì thế nên học Bách khoa ra thì gọi là Bachelor of Science, mà học Tự nhiên ra thì gọi là Bachelor of Art, vì Art là nó… trên tầm Science, ít nhất trên danh định là như thế! 🙂 Tôi thường nói là giáo dục là phải mơ mộng và tưởng tượng! Nhưng như thế nào là giáo dục kiểu “mơ mộng”?! Đương nhiên đây là kiểu từ ngữ không chính xác, nhưng ý muốn nói rằng: học không nhất thiết chỉ nhắm vào các ngành cần ứng dụng ngay, không nhất thiết phải quá nặng về công nghệ! Chỉ cần dạy thật kỹ về Toán Tin và về kỹ thuật lập trình, những lớp bài toán kinh điển, còn dùng ngôn ngữ công nghệ gì, thực chất không quá quan trọng.

inh viên mới ra trường thường choáng ngợp với số lượng tài liệu về công nghệ, cần phải có thời gian làm quen, cần phải có kỹ năng ngôn ngữ khá tốt! Nhưng khi đã hiểu rồi thì sẽ thấy nó lại quay về những điều rất cơ bản! Thực ra, “công nghệ” chính là một cách “nô dịch”, người ta làm ra công nghệ để cho những nơi có trình độ kém hơn xài, còn bản thân nơi kém hơn đó… không tự tạo ra được công nghệ! Mà muốn tự tạo ra được công nghệ thì phải có công phu, mà công phu đầu tiên là nắm cho thật kỹ kiến thức nền tảng và cách áp dụng nó! Nên cái thực trạng SV công nghệ VN hiện tại, cái gì cũng biết, công nghệ nào cũng rành, nhưng làm việc thực tế, giải quyết những bài toán thực tế thì… như gà mắc tóc! Điều nguy hiểm là họ sa đà vào một mớ ngôn từ “đao to búa lớn” mà không hiểu thực chất bên dưới, mà để hiểu thực chất bên dưới cần phải có quá trình, cần nhất là dẹp ngay những thứ ngôn từ vô nghĩa lảm nhảm trên bề mặt và đi vào tìm hiểu nguyên lý, bản chất, đi lại từ đầu những vấn đề đơn giản, cơ bản nhất! Giống như kiểu học võ: bài bản nào cũng biết, chiêu thức nào cũng hay, chỉ có điều… đứng tấn không vững! 😀

luhn algorithm

gày xưa mua một cái thẻ cào điện thoại, nạp sai số là sẽ không nhận được tiền! Làm sao để nó biết số nhập sai hay đúng, về mặt thuật toán cũng không phải là quá đơn giản, đầu tiên sẽ dùng một dạng thuật toán Luhn để kiểm tra xem việc nhập dãy số có đúng hay không! Trong dãy số, thường là số cuối cùng đóng vai trò check – digit! Ngày nay, Luhn và các phiên bản phát triển nâng cao của nó được dùng ở khắp mọi nơi: trên số passport, số CCCD, số mã vạch, số thẻ ngân hàng…

Trên hầu hết tất cả các dạng mã định danh khác như ISIN (International security identification number). Nhưng cần phân biệt rõ đây không phải là một phương pháp bảo mật, chỉ là thủ thuật kiểm tra để phát hiện việc nhập liệu là đúng hay sai! Cơ bản là giờ mạng internet đã rất nhanh, kiểm tra không quá mất thời gian, nhưng ngày xưa khi mạng còn chậm, cần phải kiểm tra ngay tại phía client (web browser, máy POS) để giúp phát hiện lỗi từ sớm mà không cần phải truy vấn server!

chân hoàn truyện

iếm khi xem phim cung đấu nào “say mê” như Chân Hoàn truyện 😃! Mọi người là biết em “xem thường” tất cả những thể loại cung đấu, gia đấu, cổ trang, ngôn tình, tiên hiệp, kiếm hiệp, xuyên không, etc… và tất cả những thể loại “kỳ quái” khác mà điện ảnh phổ thông TQ sản sinh ra! Ấy thế mà xem phim này kỹ lưỡng, cứ một vài phút lại bấm dừng để đọc phụ đề tiếng Hoa xem nó viết cái gì! Những tình tiết gay cấn, giật gân em chả quan tâm, dung nhan, trang phục đẹp đẽ em cũng chả quan tâm, nói như một câu thoại rất nổi tiếng trong phim: 你如今几岁了? – Nhĩ như kim kỷ tuế liễu!? Anh đến nay đã bao tuổi rồi ấy nhỉ!? (là câu cảm thán, không phải hỏi tuổi thật). Quan tâm ở đây là các lời thoại, ngôn từ diễn tả những tình huống phức tạp trong cuộc sống, thành ngữ, cổ văn, thơ ca, điển cố, sự tích… được sử dụng trong kịch bản phim! Người TQ họ có một thế giới siêu phong phú, phức tạp những cách diễn đạt để mô tả những mối quan hệ xã hội chồng chéo, phức tạp, tế nhị…

Những tình huống có tính chất kinh điển của lịch sử, của cuộc sống! Chính cái nguồn khổng lồ những cách diễn đạt ấy làm cho đời sống tâm hồn họ phong phú! Chính cái kho ngữ vựng – corpus to lớn ấy nói lên được sự nhận thức có chiều sâu về thế giới xung quanh! Từ cái phim Chân Hoàn truyện này, giới trẻ TQ “lượm” ra được vô số câu thoại “đắt giá” đề xài trong những tình huống cuộc sống hàng ngày, trở thành một kiểu “thành ngữ mới”! Phần lớn những lời thoại “đắt” trong phim đều viện dẫn văn thơ cổ và gần như không thể dịch, hầu như là mất khi chuyển ngữ sang tiếng Việt. Và cái kho corpus này VN tuy cũng có học, nhưng chỉ được phần rất nhỏ! Đơn cử một ví dụ: Cẩm thượng tú hoa vô nhân ký, Tuyết trung tống thán tình ý thâm – 锦上绣花无人记,雪中送炭情意深。。。 – Thêu hoa trên gấm không ai nhớ (gấm là loại vải dệt nhiều hoa văn, thêu hoa trên gấm ám chỉ việc làm hoa mĩ nhưng thừa thải, sáo rỗng), Ngày tuyết lạnh gởi than củi đến mới thực là chân tình!

xe lửa

nh chàng người Anh, chắc đã sống ở Trung Quốc khá lâu và khá rành văn hoá TQ, và cái kiểu khôi hài, châm biếm ngấm ngầm: các bạn hãy nhìn mà xem, các thể loại tàu và xe ở TQ, và nhìn lại xe lửa ở nước Anh mà xem, ôi, cái nước Anh khốn khổ của tôi, ấy vậy mà nó lại là nơi phát minh ra tàu hoả đấy, ôi, ôi cái nước Anh thảm hại của tôi! 😃 Rất nhiều người, thậm chí nhiều người châu Âu, đi TQ về đều thấy như thế: thành phố sạch sẽ, ngăn nắp, được tổ chức tốt, an ninh và an toàn tuyệt đối, camera giám sát khắp mọi nơi, mua một cái SIM điện thoại xài tạm một tuần cũng phải xác minh nhân thân, người dân thân thiện, hiếu khách, tuy chưa so được, nhưng một số mặt, nhất là an ninh công cộng và thanh toán không tiền mặt là đã vượt qua châu Âu!

Quay lại cái xứ Vịt trời đánh, đĩ điếm và lưu manh vẫn lộng hành nơi nơi, truyền thông bẩn và giang hồ mạng vẫn tìm cách gieo rắc FUD: Fear, Uncertainty, and Doubt! Cái này dịch như nhạc sĩ Phạm Duy là rất hay, rất đắt, chúng ta đang sống trong một thời đại: Sợ hãi, Hoài nghi, và Khinh thị, chính thực là như thế! Mà những thành phần bất hảo của xã hội, chúng nó vẫn y một chiến thuật cũ rích, cứ lảm nhảm suốt những thứ tào lao thiên địa, không bằng không cứ, đánh vào đám đông với dân trí thấp lè tè ngọn cỏ! Muốn xử đám này thì buộc phải mạnh tay như TQ: chứng cứ đâu, xác minh nhân thân mày là ai!? Nói nghe có vẻ khắt khe, nhưng không có quyết tâm dẹp bỏ những thứ xàm xí, lưu manh thì làm sao đạt được tiến bộ xã hội!?