Haskell ile Huffman kodu tabanlı bir sıkıştırma aracı yapmak

 (lazamar.github.io)
1 puan yazan GN⁺ 2024-07-06 | 1 yorum | WhatsApp'ta paylaş
  • Yaklaşık 150 satır Haskell ile bir Huffman coding sıkıştırıcısı geliştirerek, rastgele ikili dosyaların sabit bellekle kodlanıp çözülebildiği bir yapıyı gösteriyor
  • Huffman kodu, sık görülen değerlere kısa bit dizileri atar ve prefix-free code koşulu sayesinde çözücü bit dizilerini belirsizlik olmadan yorumlar
  • Uygulama, FreqMap, HTree, CodeMap ile frekans tablosundan ağaç oluşturur; concatMap ve özyinelemeli çözücünün lazy evaluation özelliğiyle sonuçları kademeli olarak üretir
  • İkili dosyalar Data.ByteString.Char8 ile baytların Char gibi ele alınmasıyla işlenir; sıkıştırılmış çıktının başına frekans tablosu serileştirilir ve bit dizileri bayt hizasında padding eklenerek saklanır
  • Testlerde War and Peace 3.2M'den 1.9M'ye, 106M'lik ghcup ikilisi ise 84M'ye düştü; en yüksek resident set size ise 300KB'nin altında gözlendi

Huffman kodu sıkıştırmanın temel fikri

  • Amaç, Huffman coding kullanarak yaklaşık 150 satır Haskell ile bir veri sıkıştırma aracı geliştirmektir
  • Tüm kod GitHub deposunda açık olarak paylaşılmıştır
  • Huffman kodu, her karaktere veya değere benzersiz bir bit dizisi atar
    • Sık geçen değerler kısa bit dizileri kullanır
    • Nadir geçen değerler uzun bit dizileri kullanır
    • Sık görülen değerler özgün gösterimlerinden daha az bitle ifade edildiği için sıkıştırma etkisi oluşur
  • aaab örneğinde a = 1, b = 0 seçilirse sonuç 1110 olur
    • UTF-8 ile 4 bayt gerektiren bir dizgenin yarım baytla ifade edilmesine örnektir

Prefix-free code ve Huffman ağacı

  • Çözmenin belirsiz olmaması için hiçbir kod sözcüğü başka bir kod sözcüğünün öneki olmamalıdır
    • Örneğin aaabc için a = 1, b = 10, c = 01 atanırsa 101, ac mi ba mı belirsiz hale gelebilir
  • prefix-free code, tam ikili ağaç olarak kurulabilir
    • Tüm değerler yapraklara yerleştirilir
    • Sol kenar 1, sağ kenar 0 ile etiketlenir
    • Kökten yaprağa giden yol, ilgili değerin kod sözcüğü olur
  • Huffman ağacı, düşük frekanslı değerleri alttan başlayarak birleştirme yöntemiyle oluşturulur
    • Her karakter, görünme sayısı olan weight ile birlikte düğüm yapılır
    • En küçük weight'e sahip iki düğüm bir ağaçta birleştirilir
    • Yeni ağacın weight değeri iki düğümün weight toplamıdır
    • Tek bir ağaç kalana kadar bu işlem tekrarlanır
  • Bu süreç sonunda daha sık görülen değerler köke daha yakın olur ve daha kısa kod sözcükleri alır

Haskell kodlayıcısının yapısı

  • Uygulamanın temel tipleri Bit, Code, FreqMap, CodeMap, Weight, HTree'dir
    • Bit, One veya Zerodur
    • Code, [Bit]'tir
    • FreqMap, karakter başına görünme sayısını tutan Map Char Int'dir
    • CodeMap, karakter başına kod sözcüğünü tutan Map Char Code'dur
    • HTree, Leaf Weight Char veya Fork Weight HTree HTree'dir
  • HTree, weight temelinde karşılaştırılabilir yapılarak ağaç oluşturma sürecindeki sıralama ve ekleme basitleştirilir
  • countFrequency, bir dizgedeki her karakterin görünme sayısını hesaplar
  • buildTree, FreqMap'i yaprak listesine çevirir, sıralar ve en küçük iki düğümü tekrar tekrar birleştirerek Huffman ağacını oluşturur
  • buildCodes, ağacı dolaşırken sola One, sağa Zero ekleyerek her karakterin kod sözcüğünü üretir
  • encode :: FreqMap -> String -> [Bit], FreqMap'ten ağaç ve kod haritası oluşturur; giriş dizgesindeki her karakteri kod sözcüğüyle değiştirerek bir bit listesi üretir

Lazy evaluation ile kademeli işleme

  • Kodlamadaki temel dönüşüm concatMap codeFor str ifadesidir
    • Kavramsal olarak bu, [Char]'ı [[Bit]]'e dönüştürüp ardından tekrar [Bit] olarak düzleştirme sürecidir
    • Haskell'in lazy evaluation özelliği sayesinde bu işlem, tüm girdiyi önce tamamen kodlayıp sonra birleştirerek çalışmaz
  • Küçük listeler soldan sağa ilerlerken büyük sonuç listesine düzleştirilir
    • Sonuç listesinin tail kısmı henüz değerlendirilmemiş thunk olarak kalır
    • Gereken değer istendiğinde sonraki kısım hesaplanır
  • Çözücü de aynı şekilde sonucu kademeli üretir
    • decode :: FreqMap -> [Bit] -> String, bitlere göre ağaçta sola veya sağa gider
    • Yaprağa ulaşıldığında karakter çıktı olarak verilir ve yeniden kökten başlanır
    • Huffman ağacının weight değeri kadar karakter çözümlenene dek tekrar eder
  • Çözücü, giriş bit listesinin sonuna göre değil karakter sayısına göre durur
    • Çünkü serileştirme aşamasında bayt hizalaması için sona padding bitleri eklenir
  • go fonksiyonu, yaprağa ulaştığında head'i belli olan bir liste ile tail için özyinelemeli çağrıyı döndürdüğünden, tüm özyineleme bitmeden de sonuç değerlendirilebilir

İkili dosya işleme ve serileştirme

  • İkili veri, olası 256 bayttan birinin tekrarlandığı bir yapı olarak görülebilir
  • Data.ByteString.Char8, ByteString üzerinde Char işlemleri yapmayı sağlar ve tüm Char değerleri 8 bit'e kırpılır
    • Bu özellik sayesinde metin odaklı kodlayıcı büyük değişiklik olmadan ikili veriye de uygulanabilir
  • Sıkıştırılmış dosyada önce çözme için gerekli FreqMap yer alır, ardından kodlanmış bit dizisi gelir
  • serializeFreqMap, frekans tablosunu şu biçimde yazar
    • Harita uzunluğu Word8 olarak saklanır, ancak ifade aralığını ayarlamak için 1 çıkarılarak yazılır
    • Her öğede anahtar Word8, frekans değeri ise 64 bit big-endian tamsayı olarak saklanır
  • serialize, binary paketindeki Put monadı ile ByteString üretir
    • Bitleri teker teker okuyup bir baytı doldurur
    • 8 bit tamamlanınca putWord8 ile yazar
    • Son baytta kalan boşluk Zero ile padding yapılarak doldurulur

Deserileştirme ve sabit bellek stratejisi

  • deserializeFreqMap, serileştirilmiş frekans tablosunu Data.Binary.Get ile okur
    • Önce uzunluğu okur ve gerçek öğe sayısını bulmak için 1 ekler
    • Her öğeden Word8 anahtarını ve 64 bit frekans değerini okuyarak FreqMap'i geri oluşturur
  • Girdinin kalan tamamı Get ile işlenmez; bunun yerine ByteString içinden offset sonrasındaki bölüm alınır ve bit listesine dönüştürülür
  • deserialize, (FreqMap, [Bit]) döndürür; buradaki [Bit], tamamı hemen hesaplanmayan lazy listedir
    • Bu listenin uzunluğunu istemek, tüm listeyi değerlendirmeyi gerektireceği için bundan kaçınılmalıdır
  • Tüm girdi üzerinde Get kullanılmamasının nedeni, monaddaki bind'in sırayı zorunlu kılmasıdır
    • Böylece tüm giriş işlenmeden listenin döndürülmesi mümkün olmazdı
  • Sabit bellek stratejisi, çıktı bitleri yazıldıkça girdinin yalnızca bir sonraki küçük parçasını değerlendirmeye dayanır
    • ByteString'in bir kısmı değerlendirilir ve ilgili dosya parçası okunur
    • İşlenen çıktı dosyaya yazılır
    • Artık başvurulmayan giriş parçaları ve bit listeleri çöp toplayıcı tarafından geri alınabilir
  • FreqMap, bayt bazında en fazla 256 öğe içerdiğinden ek yük sabit boyutta kalır

Dosya sıkıştırma/açma CLI'ı

  • compress, giriş dosyasını iki kez okur
    • İlk geçişte FreqMap oluşturulur
    • İkinci geçişte veri bu FreqMap ile kodlanır
  • Dosyayı yalnızca bir kez okuyup aynı referansı encode'a vermek, frekans tablosu oluşturulduktan sonra da tüm giriş dosyasına referansı korumayı gerektirir; bu da tüm dosyanın bellekte tutulması anlamına gelir
  • İki kez okuma yaklaşımı, hem frekans tablosu oluştururken hem de kodlama yaparken işlenmiş belleğin süreç içinde serbest bırakılmasına olanak tanır
  • decompress, sıkıştırılmış dosyayı okur; deserialize ile FreqMap ve bit listesini alır, ardından decode sonucunu dosyaya kaydeder
  • CLI şu argümanları alır
    • compress FILE FILE
    • decompress FILE FILE
  • Yalnızca GHC ile gelen paketleri kullandığı için cabal olmadan ghc -O2 Main.hs -o main ile derlenebilir

Çalışma sonuçları ve bellek kullanımı

  • Tolstoy'un War and Peace metin dosyası testinde, sıkıştırma ve açma sonrası diff sonucu aynıdır
    • Özgün WarAndPeace.txt: 3.2M
    • Sıkıştırılmış dosya: 1.9M
    • Açılmış dosya: 3.2M
    • Boyut yaklaşık %40 azalır
  • Daha büyük bir ikili dosya olan ghcup üzerinde de sıkıştırma ve açma çalışır
    • Özgün ghcup: 106M
    • Sıkıştırılmış dosya: 84M
    • Açılmış dosya: 106M
    • Sıkıştırma süresi yaklaşık 15.173 saniye, açma süresi yaklaşık 14.555 saniyedir
  • +RTS -s ölçümüne göre ghcup işlenirken en yüksek resident set size 300KB'nin altındadır
  • Her iki süreç de çalışırken 10MB'den az bellek kullanır
  • Zamanın nerede harcandığı ayrı bir profilde görülebilir

Daha da geliştirilebilecek noktalar

  • Uygulamanın amacı olabildiğince basit ve anlaşılır bir sıkıştırma aracı sunmaktı; verimliliği artırmak için daha karmaşık bir uygulama gerekir
  • Olası iyileştirmeler şunlardır
    • Çok iş parçacıklılık: Dosya bölümleri paralel çözülebilir; ancak rastgele bir konumda kod sözcüğü sınırları bilinmediği için sıkıştırılmış dosyanın başına bölüm sınırları ve beklenen çözülmüş boyut tablosu eklenmelidir
    • Tek geçişli kodlama: Tüm baytların frekansı 1 olan başlangıç frekans tablosuyla başlanır; her bayt görüldüğünde önce kodlanır, sonra frekans tablosu güncellenir
    • Canonical Huffman codes: Çözmede ağacı O(log n) ile dolaşmak yerine kodu bir vektör indeksi olarak kullanıp O(1) erişim hedeflenebilir; ayrıntılar için Canonical Huffman code sayfasına bakılabilir
    • Daha hızlı kod üretimi: Tek geçişli kodlamada CodeMap üretimi çok daha hızlı olmalıdır ve ağacı oluşturmadan kod sözcüğü üretmenin daha hızlı yolları vardır
  • İleride uyarlamalı sözlük yaklaşımı olan LZ77 kullanılarak Huffman kodlarıyla birlikte gzip de geliştirilebilir

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-06
Hacker News yorumları

  • Bu iş için ağaç ayırmayı ve işaretçileri takip etmeyi azaltan dizi tabanlı yerinde çalışan bir algoritma var
    Üniversitede ağaç tabanlı yaklaşımı öğrendiğimde başka bir yöntem olduğunu bilmiyordum; başkaları için de böyle olup olmadığını merak ediyorum
    Ağaç yöntemi sezgisel ve anlamaya yardımcı oluyor, ama sıkıştırmanın en önemli olduğu durumlar genellikle verinin çok olduğu ve hızlı çalışmasını istediğiniz durumlardır; bu yüzden yerinde dizilerle ele almak daha mantıklı olabilir
    In-Place Calculation of Minimum-Redundancy Codes, Moffat, Katajainen, 1995
    http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

    • Genel olarak Moffat ve Turpin’in On the Implementation of Minimum Redundancy Prefix Codes makalesi de bakmaya değer
      Charles Bloom bunu güçlü biçimde tavsiye etmiş, daha sonra açıklama da eklemişti
      https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
    • JPEG standardı ITU T.81’de (1992) bu algoritma akış şemasıyla açıklanıyor; dolayısıyla dizi tabanlı Huffman hakkındaki bilgi 80’lerde bile bir ölçüde biliniyormuş gibi görünüyor
    • Yazının son kısmında bahsediliyor ve okura alıştırma olarak bırakılmış
    • “Bunun sizin kaçınız için de geçerli olduğunu merak ediyorum” cümlesi liste kavrayışı gibi duyuluyor

  • “Hiçbir kod sözcüğünün başka bir kod sözcüğünün öneki olmaması gerekir ki belirsiz olmasın” ifadesi, sıkı anlamda doğru değil
    Sözde tekil çözülebilir kodlar belirsiz değildir ve önek kodlarının üst kümesidir
    Basit bir örnek, bir önek kodunu ters çevirmektir. Yazıdaki örnek için bu a 1, b 00, c 10 olur
    anın kodu c kodunun öneki olsa da, kod dizisini ters sırayla işlerseniz hâlâ belirsizlik olmadan çözülebilir. Ne önek kodu ne de bunun tersi olan tekil çözülebilir kodlar görmek ilginç olurdu

    • Bir önek kodu ile bir sonek kodunu bileştirirseniz, gereksiz yere verimsiz olmadan böyle kodlar oluşturabilirsiniz
      A 0, B 01, C 11 olsun; sonra a A 0, b BA 010, c BB 0101, d BC 0111, e C 11 olarak alırsanız {a=0,b=010,c=0101,d=0111,e=11} elde edilir
      Arkadan başlayarak 0->A gibi tekil biçimde çözüp, sonra önden başlayarak A->a gibi tekrar tekil biçimde çözmek yeterli olduğundan, bunun tekil çözülebilir olduğu açık
      Uzunluk açısından en iyi önek kodu {a=0,b=110,c=1110,d=1111,e=10} ile aynıdır; yani aynı olasılık dağılımı için birden fazla en iyi koddan biridir
      Aynı zamanda a=0, b=010 nedeniyle ne önek kodu ne de sonek kodudur. Aslında genel durumda her iki yönde de kademeli çözme mümkün değildir; cee...ee? ile bee...ee? veya ?cc...cca ile ?cc...ccb ayrımını yapmak için tek bir sembolü belirlerken bile sonsuz ileri/geri bakış gerekebilir
      Bağımsız olarak en iyi olan bir önek kodu ile bağımsız olarak en iyi olan bir sonek kodunu bileştirmenin her zaman en iyiliği koruyup korumadığını bilmiyorum; ama dejeneratif 1:1 kodlar hariç aklıma gelen en basit durumlarda iyi çalıştı
    • Sandığımdan daha ilginç bir problem. Öncelikle ters bir yanıt olarak a 101, b 1 gibi bir örnek mümkün
      Ama bu kötü bir kod. Çünkü her zaman a=1, b=0 yapmak daha iyidir
      Kraft eşitsizliği, tekil çözülebilir yapılabilecek kod uzunlukları kümelerini söyler ve Huffman kodlama ile bu kümelerin tamamına ulaşılabilir. Dolayısıyla sembol kodluyorsanız, ANS veya aritmetik kodlama gibi başka bir yönteme geçmediğiniz sürece önek olmayan kod kullanmak için bir neden yoktur
      Yine de en iyi Huffman koduyla aynı uzunluk kümesine sahip olup ne önek kodu ne de onun tersi olan sonek kodu olan tekil çözülebilir bir kod var mı bilmiyorum
      Zaman ayırsaydım https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm’a bakıp kaba kuvvetle bir karşı örnek arar ya da algoritmanın çalışma biçiminden bir kanıt çıkarırdım
    • Garip bir örnek ama a 1, b 101 nasıl olur diye düşünüyorum
      Ne önek serbest ne de sonek serbest, ama 0 her göründüğünde bu bir bnin görünmesiyle eşleşiyor
      Elbette açıkça verimsiz; bu yüzden asıl merak ettiğim, önek serbest de sonek serbest de olmayan en iyi kod var mı
      Arayınca https://blog.plover.com/CS/udcodes.html içinde a 0011, b 011, c 11, d 1110 şeklinde tekil çözülebilir bir kod örneği verildiğini gördüm
      Tek önek ilişkisi yalnızca cnin dnin öneki olması olduğundan “neredeyse” önek serbest sayılır. Mesaj 1 ile başlıyorsa ilk 0ı bulup, ondan önceki 1 sayısının tek mi çift mi olduğuna bakmak yeterli gibi; bu yüzden tekil çözülebilirliğini anlıyorum
      Ancak bunun hangi olasılık dağılımı için en iyi olduğunu nasıl göstereceğimi kriptografi bilgim fazla paslandığı için hatırlamıyorum
    • İlginç, ama genelde kullanılmamasının nedeni muhtemelen belirsizliği gideren bit gelene kadar çok uzun bir bit dizisi okumanız gerekebilmesi
      Örneğin 100000000000000001 gibi bir durumda, ilk kodun a mı yoksa c mi olduğunu anlamak için sıfırların bittiği yere kadar hepsini okumak gerekir

  • Bu yazıdaki gibi Haskell programını adım adım yazdıran benzer eğitimlerden, monad transformer veya lens gibi daha ileri özellikleri ele alan kaynaklar var mı merak ediyorum

    • Haskell in Depth kitabını öneririm. Monad transformer’ları 6. bölümde, lens’leri 3. ve 14. bölümlerde ele alıyor
      Template Haskell, eşzamanlılık gibi başka ileri özellikleri de kapsıyor; ayrıca Haskell’de SQL veritabanlarıyla çalışmayı anlatan bir bölüm de var
    • https://github.com/turion/rhine-koans bakmaya değer
      FRP kütüphanesi Rhine için bir eğitim; yorumları ve testleri iyi hazırlanmış

  • Coursera'nın Scala tabanlı fonksiyonel programlama kursunda da oldukça benzer bir Huffman kodlama ödevi var; otomatik değerlendirme aracı da bulunduğundan, kendisi çözmek isteyenler için iyi bir seçenek
    https://www.coursera.org/learn/scala-functional-programming?...

  • Huffman kodunu son kullandığım yer MICMAC işlemcisinin makroprogramıydı; yani assembly metnini en az mikrodöngü ve en az mikrokomutla çalıştırmak içindi
    Çalıştırılan makrokomutların histogramından başladım ve hatırladığım kadarıyla önce C ile bir yorumlayıcı yazarak her komutun kaç kez çalıştırıldığını saydım
    Sonra gerekli tüm ISA makro işlemlerini uygulayan, aşamalı kod çözme yapan bir mikrokod programı oluşturdum. Oluşturduğum makrokomut ISA'sı byte odaklı değil, sanırım bit düzeyindeydi
    Gerçekte yavaş ve kullanışsız olurdu; ancak Huffman kodunun avantajı, değer dağılımına göre önek derinliğini ayarlayabilmesi ve böylece 1 bitlik önek yüzünden bir tarafa yığılmış bir kod oluşturmak zorunda bırakmamasıdır
    Ayrıca mikroprogram, süperskaler olmayan işlem hattı işlemci modeli olduğu için dal tahminini de ele almak zorundaydı. Dal yanlış tahmin edilirse, doğru dal ileriye yayılırken işlem hattı durması nedeniyle döngüler boşa harcanır

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

  • Haskell programcıları burada toplanacak gibi, o yüzden sormak istiyorum: Günümüzde Haskell, optimizasyona önem veren bir programcının elinde ne kadar hızlı?
    Özellikle matris işlemleri gibi sayısal hesaplama ve SIMD’den fayda sağlayan işlerdeki performansını merak ediyorum

    • Haskell’in hızı sistem dilleriyle rekabet edebilir, ancak asıl güçlü yanının soyutlama kolaylığı olduğunu akılda tutmak gerekir
      Birçok parçayı tutarlı ve iyi düzenlenmiş bir program olarak bir araya getirmeyi kolaylaştırması asıl mesele. Bu yalnızca sıkı döngüler için değil, programın bütünü için önemli
      Haskell’in FFI’ı iyi olduğu için, doğası gereği imperatif optimizasyon gerektiren kısımlarda çöp toplayıcısı olmayan dillere inilebilir. Bu kısımlar iyi tiplere sahip bir kütüphaneyle sarılırsa, tipleri uyan Haskell kodunun her yerinde o ham performanstan yararlanılabilir
      Meta’da yüksek performanslı Haskell uygulamaları geliştirirken bunu yaptık. Güzel, büyük ve hızlı Haskell programları yazdık; ancak bazı özelleşmiş bölümlere C++ bileşenleri koyduk. Zamanın %99’unu Haskell tarafında bunları daha kullanışlı bir uygulama hâline getirmeye harcadık
    • Günlük backend, web ve CLI işlerinde Haskell performansından memnunum. Ama performans odaklı kod yazarken Rust’a inerim
      Yine de Haskell yavaş sayılmaz. Dosyadaki 1 bitlerinin sayısını sayan küçük bir program örnek verilebilir
      -msse4.2 ile derleyince donanım popcount komutunu düzgün kullanıyor ve 1 GB’lık giriş dosyasını 0m0,090s içinde işliyor. MB düzeyinde yuvarlamayla heap kullanımı 0
      -msse4.2 olmadan derleyince 0m0,293s sürüyor
      Matris hesaplamasını kendim denemedim ama başlangıç noktası olarak repa, accelerate, massiv paketlerine bakardım
      https://hackage.haskell.org/package/repa
      https://hackage.haskell.org/package/accelerate
      https://hackage.haskell.org/package/massiv
    • ZuriHac’te Sam Derbyshire ile tanıştım; SIMD desteği için zorlu mimari çalışmaların tamamının bittiğini söyledi
      https://gitlab.haskell.org/ghc/ghc/-/issues/7741
      GHC 9.12’ye girebilir. Ancak yalnızca 128 bit vektörleri hedefliyor ve başkaları katkı vermezse ağırlıkla kayan nokta işlemlerine yönelik olacak gibi
      Yama burada
      https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
    • Gerçekçi bakarsak, C dâhil hangi dil olursa olsun, derleyicinin optimize ettiği kod BLAS gibi kütüphanelerdeki elle optimize edilmiş kod kadar hızlı olamaz
      Belli bir seviyede ana dil seçimi çok da önemli değildir. Hızı gerçekten ciddiye alıyorsanız hesaplamayı zaten dışarıya devredersiniz
      Dünyada hesaplama kaynağını en çok tüketen alanlardan biri olması muhtemel yapay zeka kodlarının, düşük seviye hesaplama kütüphaneleri dışında Python ile yazılabilmesinin nedeni de bu
      Doğrudan yanıt vermek gerekirse, GHC derleyicisi çok iyi. Yüksek seviyeli kod oldukça iyi çalışıyor ve gerçekçi uygulamaların çoğunda performans darboğazı tek genişlikli işlem ile SIMD arasındaki fark değil, mimari sorunlar oluyor. Haskell’in “mimari asimptotiği” oldukça avantajlı
      GHC’nin SIMD desteğine sahip olduğunu ya da bu desteği edinmekte olduğunu düşünüyorum, ama performansı değerlendirirken buna odaklanmazdım
      Haskell’de matris çarpma algoritmasını kendim yazmazdım; ama hızı ciddiye alıyorsam Rust veya C’de de kendim yazmazdım
      Sayısal hesaplama çoğu zaman performans ölçütü olarak görülüyor, ancak pratikte gerçekten orada darboğaz yaşayan çok az kişi var; eğer darboğaz oradaysa da hangi yüksek seviyeli dili kullandığınız pek önemli değil
    • Haskell, yüksek seviyeli deklaratif kod yazmak istediğinizde gerçekten parlıyor
      Bu tarzın performansı genelde CLI veya web backend işleri için yeterli. Oldukça hızlı düşük seviyeli kod yazmak için araçları da var, ama biraz hantal; sadece onu yapmak istiyorsanız muhtemelen en iyi araç değildir
      Yine de optimize edilmesi gereken birkaç yoğun hotspot olduğunda oldukça iyi
      CPU profilleme araçları iyi olduğu için CPU hotspot’larını bulup optimize etmek nispeten rahat. Buna karşılık lazy evaluation yüzünden ortaya çıkması daha kolay olan tuhaf bellek sızıntılarını izlemek çok bunaltıcı olabilir
      benchmarks game sonuçlarına bakınca, en hızlı Haskell uygulamaları genelde en hızlı C sürümlerinden 2–5 kat yavaş ve oldukça imperatif bir tarzda yazılmış
      https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

  • “Creating prefix-free codes” bölümündeki tabloda bir yazım hatası var gibi. D, 0110 değil 0010 olmalı

    • Bu yüzden 0110ın nasıl belirsiz olamayacağını uzun süre düşündüm; şimdi anladım

  • Görseldeki kadının tişörtünde ne olduğunu merak ediyorum
    Doğrudan bağlantı: https://lazamar.github.io/images/data-compressor.svg