Tạo tiện ích nén dựa trên mã Huffman bằng Haskell

 (lazamar.github.io)
1 điểm bởi GN⁺ 2024-07-06 | 1 bình luận | Chia sẻ qua WhatsApp
  • Trình bày cấu trúc triển khai bộ nén Huffman coding bằng khoảng 150 dòng Haskell, xử lý mã hóa/giải mã tệp nhị phân bất kỳ với bộ nhớ hằng số
  • Mã Huffman gán chuỗi bit ngắn cho các giá trị xuất hiện thường xuyên, và nhờ điều kiện prefix-free code, bộ giải mã có thể diễn giải chuỗi bit một cách không nhập nhằng
  • Phần triển khai tạo cây từ bảng tần suất bằng FreqMap, HTree, CodeMap, rồi tạo kết quả dần dần bằng đánh giá lười của concatMap và bộ giải mã đệ quy
  • Tệp nhị phân được xử lý bằng Data.ByteString.Char8, xem byte như Char; kết quả nén tuần tự hóa bảng tần suất ở phần đầu, còn chuỗi bit được padding theo đơn vị byte để lưu
  • Trong thử nghiệm, War and Peace giảm từ 3.2M xuống 1.9M, tệp nhị phân ghcup 106M giảm xuống 84M, và resident set size tối đa quan sát được dưới 300KB

Ý tưởng cơ bản của nén bằng mã Huffman

  • Mục tiêu là triển khai một tiện ích nén dữ liệu bằng khoảng 150 dòng Haskell sử dụng Huffman coding
  • Toàn bộ mã nguồn được công khai trong kho GitHub
  • Mã Huffman gán một chuỗi bit duy nhất cho từng ký tự hoặc giá trị
    • Giá trị xuất hiện thường xuyên dùng chuỗi bit ngắn
    • Giá trị hiếm xuất hiện dùng chuỗi bit dài
    • Hiệu quả nén xuất hiện khi các giá trị phổ biến được biểu diễn bằng ít bit hơn biểu diễn ban đầu
  • Trong ví dụ aaab, nếu đặt a = 1, b = 0 thì kết quả là 1110
    • Đây là ví dụ biểu diễn một chuỗi cần 4 byte theo UTF-8 chỉ bằng nửa byte

Prefix-free code và cây Huffman

  • Để việc giải mã không nhập nhằng, không codeword nào được là tiền tố của codeword khác
    • Ví dụ, nếu với aaabc ta gán a = 1, b = 10, c = 01, thì 101 có thể trở nên nhập nhằng, không rõ là ac hay ba
  • Prefix-free code có thể được tạo bằng cây nhị phân đầy đủ
    • Đặt tất cả giá trị ở các lá
    • Gán nhãn cạnh trái là 1, cạnh phải là 0
    • Đường đi từ gốc tới lá trở thành codeword của giá trị đó
  • Cây Huffman được tạo theo cách nhóm dần từ dưới lên, bắt đầu với các giá trị có tần suất thấp
    • Tạo mỗi ký tự thành một nút kèm weight là số lần xuất hiện
    • Ghép hai nút có weight nhỏ nhất thành một cây
    • Weight của cây mới là tổng weight của hai nút
    • Lặp lại cho đến khi chỉ còn một cây
  • Qua quá trình này, các giá trị xuất hiện thường xuyên hơn sẽ nằm gần gốc hơn và có codeword ngắn hơn

Cấu trúc encoder Haskell

  • Các kiểu chính trong phần triển khai là Bit, Code, FreqMap, CodeMap, Weight, HTree
    • Bit là One hoặc Zero
    • Code là [Bit]
    • FreqMap là Map Char Int, lưu số lần xuất hiện theo từng ký tự
    • CodeMap là Map Char Code, lưu codeword theo từng ký tự
    • HTree là Leaf Weight Char hoặc Fork Weight HTree HTree
  • HTree được làm cho có thể so sánh theo weight, giúp đơn giản hóa việc sắp xếp và chèn trong quá trình tạo cây
  • countFrequency tính số lần xuất hiện của từng ký tự trong chuỗi
  • buildTree chuyển FreqMap thành danh sách lá rồi sắp xếp, sau đó liên tục hợp nhất hai nút nhỏ nhất để tạo cây Huffman
  • buildCodes duyệt cây, gắn One ở bên trái và Zero ở bên phải để tạo codeword cho từng ký tự
  • encode :: FreqMap -> String -> [Bit] tạo cây và code map từ FreqMap, rồi thay từng ký tự trong chuỗi đầu vào bằng codeword để tạo danh sách bit

Xử lý dần dần bằng đánh giá lười

  • Phép biến đổi cốt lõi của mã hóa là concatMap codeFor str
    • Về mặt khái niệm, đây là quá trình chuyển [Char] thành [[Bit]] rồi làm phẳng lại thành [Bit]
    • Nhờ đánh giá lười của Haskell, nó không hoạt động theo cách mã hóa toàn bộ đầu vào trước rồi mới ghép lại
  • Các danh sách nhỏ được xử lý từ trái sang phải và làm phẳng vào danh sách kết quả lớn
    • Tail của danh sách kết quả vẫn là thunk chưa được đánh giá
    • Khi giá trị cần thiết được yêu cầu, phần tiếp theo mới được tính
  • Bộ giải mã cũng tạo kết quả dần dần theo cùng cách
    • decode :: FreqMap -> [Bit] -> String di chuyển sang trái hoặc phải trong cây tùy theo bit
    • Khi tới lá, nó xuất ký tự rồi bắt đầu lại từ gốc
    • Lặp cho đến khi tổng số ký tự đã giải mã bằng weight của cây Huffman
  • Bộ giải mã dừng dựa trên số ký tự, chứ không phải cuối danh sách bit đầu vào
    • Vì ở bước tuần tự hóa có thêm bit padding ở cuối để căn theo byte
  • Hàm go khi tới lá sẽ trả về một danh sách có head đã biết cùng lời gọi đệ quy ở tail, nên có thể đánh giá kết quả trước khi toàn bộ đệ quy kết thúc

Xử lý tệp nhị phân và tuần tự hóa

  • Dữ liệu nhị phân có thể được xem là sự lặp lại của một trong 256 byte khả dĩ
  • Data.ByteString.Char8 cho phép xử lý ByteString bằng các phép toán Char, và mọi Char đều bị cắt xuống 8 bit
    • Nhờ đặc tính này, có thể áp dụng cho dữ liệu nhị phân mà không cần thay đổi nhiều bộ mã hóa dành cho văn bản
  • Trong tệp nén, FreqMap cần cho giải mã được đặt trước, sau đó là chuỗi bit đã mã hóa
  • serializeFreqMap ghi bảng tần suất theo định dạng sau
    • Độ dài map được lưu dưới dạng Word8, nhưng lưu giá trị đã trừ 1 để hiệu chỉnh phạm vi biểu diễn
    • Mỗi mục lưu khóa dưới dạng Word8, và giá trị tần suất dưới dạng số nguyên 64-bit big-endian
  • serialize tạo ByteString bằng monad Put của package binary
    • Đọc từng bit để lấp đầy một byte
    • Khi đủ 8 bit thì ghi bằng putWord8
    • Byte cuối được padding phần còn lại bằng Zero

Giải tuần tự hóa và chiến lược bộ nhớ hằng số

  • deserializeFreqMap đọc bảng tần suất đã tuần tự hóa bằng Data.Binary.Get
    • Đầu tiên đọc độ dài, cộng thêm 1 để tính số mục thực tế
    • Với mỗi mục, đọc khóa Word8 và giá trị tần suất 64-bit để khôi phục FreqMap
  • Phần còn lại của toàn bộ đầu vào không được xử lý bằng Get; thay vào đó, phần sau offset được lấy từ ByteString và chuyển thành danh sách bit
  • deserialize trả về (FreqMap, [Bit]), trong đó [Bit] là danh sách lười không được tính toàn bộ ngay lập tức
    • Nếu yêu cầu độ dài của danh sách này thì phải đánh giá toàn bộ danh sách, nên cần tránh
  • Lý do không dùng Get cho toàn bộ đầu vào là bind của monad sẽ ép thứ tự
    • Cấu trúc sẽ chỉ có thể trả về danh sách sau khi xử lý xong toàn bộ đầu vào
  • Chiến lược bộ nhớ hằng số là mỗi khi ghi bit đầu ra, chỉ đánh giá phần nhỏ tiếp theo của đầu vào
    • Một phần ByteString được đánh giá và mảnh tệp tương ứng được đọc
    • Đầu ra đã xử lý được ghi vào tệp
    • Các mảnh đầu vào và danh sách bit không còn được tham chiếu có thể được garbage collector thu hồi
  • FreqMap có tối đa 256 mục theo byte, nên chỉ tạo overhead kích thước hằng số

CLI nén và giải nén tệp

  • compress đọc tệp đầu vào hai lần
    • Lượt đầu tạo FreqMap
    • Lượt thứ hai mã hóa dữ liệu bằng FreqMap đó
  • Nếu chỉ đọc tệp một lần và truyền cùng tham chiếu cho encode, sau khi tạo bảng tần suất vẫn phải giữ tham chiếu tới toàn bộ tệp đầu vào, nên cần giữ cả tệp trong bộ nhớ
  • Cách đọc hai lần cho phép giải phóng bộ nhớ đã xử lý trong cả hai bước tạo bảng tần suất và mã hóa
  • decompress đọc tệp nén, lấy FreqMap và danh sách bit bằng deserialize, rồi lưu kết quả decode ra tệp
  • CLI nhận các đối số sau
    • compress FILE FILE
    • decompress FILE FILE
  • Vì chỉ dùng các package đi kèm GHC, có thể biên dịch bằng ghc -O2 Main.hs -o main mà không cần cabal

Kết quả chạy và mức dùng bộ nhớ

  • Trong thử nghiệm với tệp văn bản War and Peace của Tolstoy, kết quả diff sau nén và giải nén là giống nhau
    • Bản gốc WarAndPeace.txt: 3.2M
    • Tệp nén: 1.9M
    • Tệp giải nén: 3.2M
    • Kích thước giảm khoảng 40%
  • Việc nén và giải nén cũng hoạt động với tệp nhị phân lớn hơn ghcup
    • Bản gốc ghcup: 106M
    • Tệp nén: 84M
    • Tệp giải nén: 106M
    • Thời gian nén khoảng 15.173 giây, thời gian giải nén khoảng 14.555 giây
  • Theo +RTS -s, resident set size tối đa trong khi xử lý ghcup là dưới 300KB
  • Hai tiến trình dùng dưới 10MB bộ nhớ khi chạy
  • Có thể xem vị trí tiêu tốn thời gian trong profile riêng

Những điểm có thể cải thiện thêm

  • Mục tiêu triển khai là một tiện ích nén đơn giản và rõ ràng nhất có thể; để tăng hiệu quả sẽ cần triển khai phức tạp hơn
  • Các hướng cải thiện khả dĩ gồm
    • Đa luồng: giải mã song song các đoạn tệp, nhưng vì không thể biết ranh giới codeword tại vị trí tùy ý, cần thêm vào đầu tệp nén một bảng chứa ranh giới đoạn và kích thước giải mã dự kiến
    • Mã hóa một lượt: bắt đầu với bảng tần suất ban đầu trong đó mọi byte có tần suất 1, và mỗi khi thấy một byte thì mã hóa trước rồi cập nhật bảng tần suất
    • Canonical Huffman codes: thay vì duyệt cây trong O(log n) khi giải mã, có thể nhắm tới truy cập O(1) bằng cách dùng code làm chỉ mục vector; nội dung liên quan có trong Canonical Huffman code
    • Tạo code nhanh hơn: với mã hóa một lượt, cần tạo CodeMap nhanh hơn nhiều, và có những cách nhanh hơn để tạo codeword mà không dựng cây
  • Trong tương lai, nếu dùng LZ77, một phương pháp từ điển thích ứng, có thể triển khai gzip cùng với mã Huffman

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-07-06
Các ý kiến trên Hacker News

  • Có một thuật toán tại chỗ dựa trên mảng cho việc này, giúp giảm việc cấp phát cây và lần theo con trỏ
    Khi học cách tiếp cận dựa trên cây ở đại học, tôi không biết là có cách khác, và tôi cũng tò mò liệu những người khác có như vậy không
    Cách dùng cây trực quan và giúp dễ hiểu, nhưng những tình huống mà nén là quan trọng nhất thường là khi có nhiều dữ liệu và muốn chạy nhanh, nên xử lý bằng mảng tại chỗ có thể hợp lý hơn
    In-Place Calculation of Minimum-Redundancy Codes, Moffat, Katajainen, 1995
    http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

    • Nói chung, On the Implementation of Minimum Redundancy Prefix Codes của Moffat và Turpin cũng đáng tham khảo
      Charles Bloom đã khuyến nghị rất mạnh, và sau đó còn viết thêm phần giải thích
      https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
    • Chuẩn JPEG ITU T.81 (1992) mô tả thuật toán này bằng lưu đồ, nên có vẻ kiến thức về Huffman dựa trên mảng đã được biết đến phần nào từ thập niên 80
    • Nó được nhắc ở phần cuối bài viết và được để lại như một bài tập cho độc giả
    • Câu “tôi tò mò liệu điều đó cũng đúng với bao nhiêu người trong các bạn” nghe như một list comprehension

  • Nói rằng “không được để bất kỳ code word nào là tiền tố của một code word khác thì mới không mơ hồ” thì xét nghiêm ngặt là không chính xác
    Cái gọi là mã giải mã duy nhất là không mơ hồ, và là siêu tập của mã tiền tố
    Một ví dụ đơn giản là mã thu được bằng cách đảo ngược mã tiền tố. Với ví dụ trong bài thì sẽ là a 1, b 00, c 10
    Mã của a là tiền tố của mã c, nhưng nếu xử lý chuỗi mã theo thứ tự ngược, vẫn có thể giải mã mà không mơ hồ. Sẽ thú vị nếu xem các mã giải mã duy nhất không phải là mã tiền tố, cũng không phải là dạng đảo ngược của nó

    • Nếu hợp thành một mã tiền tố và một mã hậu tố, có thể tạo ra loại mã như vậy mà không bị kém hiệu quả một cách không cần thiết
      Đặt A 0, B 01, C 11, rồi tiếp tục đặt a A 0, b BA 010, c BB 0101, d BC 0111, e C 11, ta được {a=0,b=010,c=0101,d=0111,e=11}
      Rõ ràng là có thể giải mã duy nhất, vì có thể giải mã duy nhất từ phía sau theo kiểu 0->A, rồi lại giải mã duy nhất từ phía trước theo kiểu A->a
      Về độ dài thì giống mã tiền tố tối ưu {a=0,b=110,c=1110,d=1111,e=10}, nên với cùng một phân bố xác suất, đây là một trong nhiều mã tối ưu
      Đồng thời, do a=0, b=010, nó không phải là mã tiền tố cũng không phải là mã hậu tố. Thực ra nói chung không thể giải mã tăng dần theo cả hai chiều; để phân biệt cee...ee? với bee...ee?, hay ?cc...cca với ?cc...ccb, có thể cần nhìn trước vô hạn chỉ để xác định một ký hiệu
      Tôi không biết việc hợp thành một mã tiền tố tối ưu độc lập với một mã hậu tố tối ưu độc lập có luôn giữ được tính tối ưu hay không, nhưng trong những trường hợp đơn giản nhất tôi nghĩ ra, trừ các mã suy biến 1:1, thì nó hoạt động tốt
    • Đây là vấn đề thú vị hơn tôi tưởng. Trước hết, như một câu trả lời mang tính đối nghịch, có thể đưa ra ví dụ như a 101, b 1
      Nhưng đó là mã tệ. Vì luôn đặt a=1, b=0 thì tốt hơn
      Bất đẳng thức Kraft cho biết các tập độ dài mã có thể được tạo sao cho giải mã duy nhất, và mã hóa Huffman có thể đạt được tất cả các tập như vậy. Vì vậy, nếu đang mã hóa ký hiệu, thì không có lý do để dùng mã không phải tiền tố, trừ khi chuyển sang phương pháp khác như ANS hoặc mã hóa số học
      Tuy nhiên, tôi không biết liệu có tồn tại mã giải mã duy nhất có cùng tập độ dài với một mã Huffman tối ưu, nhưng không phải là mã tiền tố cũng không phải là mã hậu tố đảo ngược của nó hay không
      Nếu bỏ thời gian, có lẽ tôi sẽ xem https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm, rồi tìm phản ví dụ bằng brute force hoặc nghĩ ra chứng minh từ cách thuật toán hoạt động
    • Một ví dụ kỳ lạ, nhưng tôi tự hỏi a 1, b 101 thì sao
      Nó không prefix-free cũng không suffix-free, nhưng mỗi khi 0 xuất hiện thì tương ứng với việc b xuất hiện
      Tất nhiên rõ ràng là không hiệu quả, nên cuối cùng điều đáng tò mò là liệu có mã tối ưu nào không prefix-free cũng không suffix-free hay không
      Tìm thử thì thấy https://blog.plover.com/CS/udcodes.html đưa ra ví dụ mã giải mã duy nhất a 0011, b 011, c 11, d 1110
      Quan hệ tiền tố duy nhất chỉ là trường hợp c là tiền tố của d, nên nó “gần như” prefix-free. Nếu thông điệp bắt đầu bằng 1, có vẻ chỉ cần tìm số 0 đầu tiên rồi xem số lượng 1 trước đó là lẻ hay chẵn, nên tôi hiểu được tính giải mã duy nhất
      Nhưng kiến thức mật mã học của tôi đã quá rỉ sét nên không nhớ cách chứng minh mã này là tối ưu cho phân bố xác suất nào
    • Thú vị đấy, nhưng lý do nó thường không được dùng có lẽ là vì có thể phải đọc một chuỗi bit rất dài cho đến khi xuất hiện bit giải quyết được sự mơ hồ
      Ví dụ với 100000000000000001, để biết mã đầu tiên là a hay c, phải đọc hết đến chỗ các số 0 kết thúc

  • Tôi tò mò liệu có tài liệu nào tương tự kiểu tutorial viết dần một chương trình Haskell như bài này, nhưng xử lý các tính năng nâng cao hơn như monad transformer hoặc lens không

    • Tôi khuyên đọc sách Haskell in Depth. Monad transformer được bàn ở chương 6, còn lens ở chương 3 và 14
      Sách cũng đề cập các tính năng nâng cao khác như Template Haskell, concurrency, và có cả chương về xử lý cơ sở dữ liệu SQL trong Haskell
    • https://github.com/turion/rhine-koans đáng xem
      Đây là tutorial cho thư viện FRP Rhine, có chú thích và test được viết tốt

  • Khóa lập trình hàm dựa trên Scala của Coursera cũng có một bài tập mã hóa Huffman khá tương tự, và có cả hệ thống chấm tự động, nên phù hợp cho những ai muốn tự thử giải
    https://www.coursera.org/learn/scala-functional-programming?...

  • Lần cuối tôi dùng mã Huffman là cho macroprogram của bộ xử lý MICMAC, tức để thực thi văn bản assembly với số microcycle và số microinstruction tối thiểu
    Tôi bắt đầu từ histogram các macroinstruction đã được thực thi, và theo trí nhớ thì trước tiên tôi viết một interpreter bằng C để đếm mỗi lệnh được chạy bao nhiêu lần
    Sau đó, tôi tạo một chương trình microcode giải mã tiệm tiến triển khai tất cả các phép toán macro ISA cần thiết. Macroinstruction ISA tôi tạo ra hình như không hướng byte mà theo từng bit
    Trong thực tế có lẽ nó chậm và bất tiện, nhưng ưu điểm của mã Huffman là có thể điều chỉnh độ sâu tiền tố theo phân bố giá trị, nên không cần tạo mã bị lệch về một phía vì tiền tố 1 bit
    Ngoài ra, microprogram là mô hình bộ xử lý pipeline không superscalar, nên cũng phải xử lý dự đoán nhánh. Nếu dự đoán sai nhánh, sẽ lãng phí chu kỳ do pipeline bị dừng trong lúc nhánh đúng được truyền về phía trước

  • https://rosettacode.org/wiki/Huffman_coding

  • Có vẻ sẽ có nhiều lập trình viên Haskell tụ họp ở đây nên tôi muốn hỏi: Haskell ngày nay nhanh đến mức nào nếu được dùng bởi một lập trình viên chú ý đến tối ưu hóa?
    Đặc biệt tôi tò mò về hiệu năng của các tác vụ hưởng lợi từ SIMD và tính toán số học, như phép toán ma trận

    • Tốc độ của Haskell có thể cạnh tranh với các ngôn ngữ hệ thống, nhưng cần nhớ rằng lợi thế cốt lõi của nó là dễ trừu tượng hóa
      Điểm mấu chốt là dễ lắp ghép nhiều phần thành một chương trình nhất quán và được tổ chức tốt. Điều này quan trọng cho toàn bộ chương trình, không chỉ những vòng lặp chặt chẽ
      Haskell có FFI tốt, nên những phần về bản chất cần tối ưu hóa theo kiểu mệnh lệnh có thể hạ xuống một ngôn ngữ không có garbage collection. Nếu bọc những phần đó trong một thư viện có kiểu tốt, bạn có thể tận dụng hiệu năng thô đó ở bất cứ đâu trong mã Haskell khớp kiểu
      Khi xây dựng các ứng dụng Haskell hiệu năng cao ở Meta, chúng tôi đã làm như vậy. Viết một chương trình Haskell đẹp, lớn và nhanh, nhưng chèn các thành phần C++ vào một số phần chuyên biệt. 99% thời gian được dành ở phía Haskell để ghép chúng thành một ứng dụng hữu ích hơn
    • Với các tác vụ backend, web, CLI hằng ngày, tôi hài lòng với hiệu năng của Haskell. Nhưng khi viết mã lấy hiệu năng làm trung tâm, tôi hạ xuống Rust
      Dù vậy Haskell không phải là chậm. Có thể lấy một chương trình nhỏ đếm số bit 1 trong một tệp làm ví dụ
      Khi biên dịch với -msse4.2, nó dùng đúng lệnh phần cứng popcount và xử lý tệp đầu vào 1GB trong 0m0,090s. Heap dùng 0 nếu làm tròn theo đơn vị MB
      Nếu biên dịch không có -msse4.2, mất 0m0,293s
      Tôi chưa tự thử tính toán ma trận, nhưng nếu làm điểm khởi đầu thì có lẽ tôi sẽ xem repa, accelerate, massiv
      https://hackage.haskell.org/package/repa
      https://hackage.haskell.org/package/accelerate
      https://hackage.haskell.org/package/massiv
    • Tôi đã gặp Sam Derbyshire tại ZuriHac và nghe nói toàn bộ phần công việc kiến trúc khó cho hỗ trợ SIMD đã hoàn tất
      https://gitlab.haskell.org/ghc/ghc/-/issues/7741
      Có thể sẽ vào GHC 9.12. Tuy nhiên, nó chỉ nhắm tới vector 128-bit, và trừ khi có người khác đóng góp, có lẽ chủ yếu sẽ xoay quanh phép toán số thực dấu phẩy động
      Bản vá ở đây
      https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
    • Thực tế thì với bất kỳ ngôn ngữ nào, kể cả C, mã do compiler tối ưu hóa cũng không thể nhanh bằng mã tối ưu thủ công trong các thư viện như BLAS
      Ở một mức nào đó, lựa chọn ngôn ngữ chủ không còn quá quan trọng. Vì nếu thật sự nghiêm túc về tốc độ, phần tính toán dù sao cũng sẽ được giao ra bên ngoài
      Đó cũng là lý do mã AI, vốn rất có thể thuộc nhóm tiêu tốn nhiều tài nguyên tính toán nhất thế giới, vẫn có thể được viết bằng Python ngoại trừ các thư viện tính toán cấp thấp
      Trả lời trực tiếp thì compiler GHC rất tốt. Mã cấp cao chạy khá ổn, và trong hầu hết ứng dụng thực tế, nút thắt hiệu năng là vấn đề kiến trúc chứ không phải chuyện phép toán độ rộng đơn so với SIMD. “Độ tiệm cận về kiến trúc” của Haskell khá có lợi
      Tôi nghĩ GHC đã có hoặc đang dần có hỗ trợ SIMD, nhưng tôi sẽ không tập trung vào đó khi đánh giá hiệu năng
      Tôi sẽ không tự viết thuật toán nhân ma trận bằng Haskell, nhưng nếu nghiêm túc về tốc độ thì tôi cũng sẽ không tự viết bằng Rust hay C
      Tính toán số học thường được xem như chỉ số hiệu năng, nhưng trên thực tế rất ít người bị nghẽn ở đó; còn nếu đúng là nghẽn ở đó thì việc dùng ngôn ngữ cấp cao nào cũng không quan trọng lắm
    • Haskell thật sự tỏa sáng khi bạn muốn viết mã khai báo cấp cao
      Hiệu năng của phong cách này thường là đủ cho các tác vụ CLI hoặc backend web. Cũng có các công cụ để viết mã cấp thấp khá nhanh, nhưng chúng hơi thô, nên nếu chỉ muốn dùng chúng thì nhiều khả năng đây không phải công cụ tốt nhất
      Tuy nhiên, khi có vài hotspot tập trung cần tối ưu hóa thì nó khá ổn
      Công cụ profiling CPU tốt, nên việc tìm và tối ưu hóa hotspot CPU tương đối dễ chịu. Ngược lại, việc truy vết các rò rỉ bộ nhớ kỳ lạ dễ phát sinh hơn do đánh giá lười có thể rất bực bội
      Nhìn vào kết quả benchmarks game, các bản triển khai Haskell nhanh nhất nhìn chung chậm hơn bản C nhanh nhất khoảng 2–5 lần và được viết theo phong cách rất mệnh lệnh
      https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

  • Có vẻ bảng trong phần “Creating prefix-free codes” có lỗi đánh máy. D phải là 0010, không phải 0110

    • Vì thế tôi đã vò đầu bứt tai khá lâu để hiểu làm sao 0110 lại có thể không mơ hồ, giờ thì đã hiểu

  • Tôi tò mò thứ trên áo của cô gái trong ảnh là gì
    Link trực tiếp: https://lazamar.github.io/images/data-compressor.svg