A blog about programming, reading, and other things.
Posted on April 26, 2024 Quick Links sorted_containers on Github sorted_containers on RubyGems sorted_containers Documentation Introduction I converted Grant Jenks’s Python library Sorted Containers to Ruby. If you are interested in the details of this data structure, I recommend reading his website. His documentation is much more detailed, and I used it as a reference for this implementation. The…
Posted on May 15, 2015 tl;dr: Complete implementation is at the bottom. Red-Black trees are notorious for being nightmares of pointer manipulation. Instructors will show the theory, but won’t torture their students to implement one. Interviewers will avoid asking about it. They probably couldn’t do it themselves. You should be vaguely familiar with how you might balance a tree. The details,…
Posted on May 13, 2015 On the front page of Haskell.org , you will see this implementation of the sieve of Eratosthenes: primes = sieve [ 2 .. ] where sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p /= 0 ] When you see this for the first time it’s amazing. But it’s not the sieve of Eratosthenes . The problem with the algorithm is the way it crosses-off numbers. In the true sieve of Eratosthenes…