**mcherm : algorithms**
130

B-Heap

2 days ago by mcherm

The creator of varnish says he has a better data structure for heaps which optimizes for page faults. In general, all algorithms should be optimized for page faults not comparisons.

datastructures
programming
algorithms
performance
via:HackerNews
2 days ago by mcherm

How does Apple (privately) find your offline devices? – A Few Thoughts on Cryptographic Engineering

june 2019 by mcherm

Wild speculation about what protocol COULD protect privacy while continuously reporting on the location of RFID tags.

algorithms
security
privacy
via:HackerNews
apple
june 2019 by mcherm

How we optimized Magic Pocket for cold storage | Dropbox Tech Blog

may 2019 by mcherm

Dropbox writes how they made their cold storage be backed up in multiple data centers while using less than 2x storage space. It is also faster (for some definitions of "faster").

via:HackerNews
dropbox
algorithms
programming
may 2019 by mcherm

The One On Dynamic Programming! | Blogarithms

march 2019 by mcherm

Some good dynamic programming algorithms explained. The term seems to mean building a cash of previously calculated values when working with a recursive function.

programming
algorithms
via:HackerNews
march 2019 by mcherm

research!rsc: An Encoded Tree Traversal

february 2019 by mcherm

A tree traversal mechanism four trees with branching factor greater than 2 which behaves sort of like inorder traversal on binary trees.

programming
datastructures
algorithms
via:HackerNews
february 2019 by mcherm

The Incredible Power of Dijkstra Maps - RogueBasin

december 2018 by mcherm

For a roguelike, this is a way to give numerous mobiles varying and even conflicting goals while keeping to a reasonable amount of computation.

gameprogramming
datastructures
algorithms
programming
via:reddit
december 2018 by mcherm

Buckblog: Maze Generation: Algorithm Recap

november 2018 by mcherm

Various algorithms for developing a maze, described and illustrated with animations. An excellent demonstration of algorithms.

programming
gameprogramming
algorithms
november 2018 by mcherm

Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo) | Probably Dance

june 2018 by mcherm

Don't take mod of your hash value to select a bin in your hash table. Instead, multiply by the golden ratio.

algorithms
programming
hash
june 2018 by mcherm

A Deep Dive into Monte Carlo Tree Search

may 2018 by mcherm

A description of the algorithm that AlphaGo/AlphaZero uses, complete with sample code.

ai
programming
go
algorithms
via:HackerNews
may 2018 by mcherm

Software used in judicial decisions meets its equal in random amateurs | Ars Technica

january 2018 by mcherm

The software that predicts who will re-offend after prison is wrong 1/3 of the time. Using mechanical turk to ask random people to make predictions was just as accurate. So was just using JUST count of convictions and age.

ai
prison
algorithms
ArsTechnica
via:ArsTechnica
bigdata
january 2018 by mcherm

ffwd: delegation is (much) faster than you think | the morning paper

december 2017 by mcherm

If done well, "only one thread accesses the data structure" can actually be the FASTEST multi-threaded data structure implementation because cache effects make the single thread go so much faster.

programming
via:HackerNews
concurrency
concurrentprogramming
algorithms
threading
december 2017 by mcherm

Hexagonal Grids

september 2017 by mcherm

Some notes on programming hexagonal grids.

algorithms
gameprogramming
via:reddit
september 2017 by mcherm

100 days of algorithms – Medium

may 2017 by mcherm

Nice blog -- simple algorithms explained and coded.

programming
algorithms
may 2017 by mcherm

code challenge - Are You the One? (Mastermind Derivative) - Programming Puzzles & Code Golf Stack Exchange

march 2017 by mcherm

It's not a clever algorithm, but here's the ideal solution (by brute force) to the game Mastermind (and similar matching problems).

algorithms
march 2017 by mcherm

I Wrote The Fastest Hashtable | Probably Dance

february 2017 by mcherm

A fast hashtable: linear probing with robin hood re-location of elements, and also a limit to the probe distance (if it exceeds the limit, resize the hashtable).

hash
algorithms
programming
via:HackerNews
february 2017 by mcherm

I Wrote a Faster Sorting Algorithm | Probably Dance

january 2017 by mcherm

The author implemented radix sort (which is O(n)) in C++ and got 2x speedup over std::sort.

programming
algorithms
algorithm
via:reddit
january 2017 by mcherm

Generating fantasy maps

december 2016 by mcherm

An amazing essay in which he shows the algorithms that he uses for realistic-looking procedurally generated maps and explains how they work, with demonstrations of working code!

programming
maps
via:reddit
algorithms
december 2016 by mcherm

The Elegance of Deflate

august 2016 by mcherm

The "Deflate" algorithm (original .zip file) and how it is really well designed.

algorithms
algorithm
programming
design
compression
via:HackerNews
august 2016 by mcherm

My Biased Coin: Cuckoo Filters

may 2016 by mcherm

An alternative to the Bloom Filter which they claim works better (in practice, although it fails in theory) as long as the universe of possible values is a few billion or less.

programming
datastructures
algorithms
computerscience
probabilisticcomputing
bloomfilter
may 2016 by mcherm

FLIF - Free Lossless Image Format

october 2015 by mcherm

A format that claims to compress better than any other file format in wide use. Is brand new and has an unacceptable license (GPL).

algorithms
compression
images
via:HackerNews
october 2015 by mcherm

First new cache-coherence mechanism in 30 years | MIT News

september 2015 by mcherm

New algorithm proposed for invalidating memory caches as multiple cores coordinate. On a read, grab a "lease" for some # of cycles; to do a write, insist on having the only lease. But the trick is that the writing core can simply advance its own "clock" to do that without waiting.

programming
algorithms
via:HackerNews
september 2015 by mcherm

The Hardest Program I've Ever Written – journal.stuffwithstuff.com

september 2015 by mcherm

He goes into detail about how he spent a full year writing the line break logic for a code pretty printer. It's really interesting.

programming
algorithms
via:reddit
september 2015 by mcherm

How a Kalman filter works, in pictures | Bzarg

august 2015 by mcherm

Explaining the math behind the way we estimate a value given various measurements from various unreliable sensors.

math
via:reddit
algorithms
august 2015 by mcherm

A New Weapon In The Fight Against Syphilis

july 2015 by mcherm

The history of syphilis testing and a computer algorithm.

history
algorithms
via:reddit
july 2015 by mcherm

Longstanding problem put to rest | MIT News

june 2015 by mcherm

If P != NP then the standard (quadratic) algorithm for finding the edit distance between two strings is (asymptotically) optimal.

computerscience
algorithms
via:HackerNews
june 2015 by mcherm

You could have invented Parser Combinators

december 2014 by mcherm

A nice summary of Parser Combinators from scratch, written in Javascript to avoid the jargon.

programming
algorithms
functional
via:HackerNews
december 2014 by mcherm

Searching 20 GB/sec: Systems Engineering Before Algorithms - Scalyr Blog

october 2014 by mcherm

To search effectively, they didn't build any indexes, but the instead optimized the inner loop of a linear search through the entire set of data. The article discusses when that approach is better than using a fancy algorithm.

algorithms
scalability
optimization
via:reddit
october 2014 by mcherm

Sleepsort

august 2014 by mcherm

Another terrible sort algorithm for the books.

algorithms
sorting
via:reddit
programming
august 2014 by mcherm

Gabriel Gambetta - Pathfinding Demystified (Part I): Introduction

may 2014 by mcherm

An explanation of the A* pathfinding algorithm which is particularly readable and comes with very helpful interactive illustrations.

algorithms
via:HackerNews
programming
may 2014 by mcherm

Robin Hood Hashing should be your default Hash Table implementation | A Random Walk Through Geek-Space

april 2014 by mcherm

In a hash table, even out the lengths of probe chains by swapping elements when you find a longer probe chain. Lower variance in chain length leads to better performance, partly because of memory caches.

hash
datastructures
programming
algorithms
via:HackerNews
april 2014 by mcherm

Redis new data structure: the HyperLogLog - Antirez weblog

april 2014 by mcherm

A really good (probabilistic) data structure for counting unique items (such as number of unique values in a database column) using a small amount of memory. Includes interesting details about tuning it to be accurate in different ranges by combining two algorithms.

programming
datastructures
algorithms
probabilisticcomputing
via:HackerNews
april 2014 by mcherm

Domain specific evaluation orders | David R. MacIver

january 2014 by mcherm

A really interesting performance improvement: recognize when instances are just intermediate results, and switch around the data structures and/or algorithms and/or evaluation order to optimize performance in these cases.

programming
performance
via:DavidMacIver
DavidMacIver
algorithms
optimization
january 2014 by mcherm

Changes to String in Java 1.7.0_06 - Java Performance Tuning Guide

november 2013 by mcherm

In 1.7.0_06, java changed String so substrings can no longer share memory. Their analysis says almost all strings are small so it gave little benefit.

java
jdk
optimization
algorithms
via:reddit
programming
november 2013 by mcherm

Big-O Algorithm Complexity Cheat Sheet

may 2013 by mcherm

A table of big-O values for common algorithms.

computerscience
programming
algorithms
via:reddit
may 2013 by mcherm

In Search of an Understandable Consensus Algorithm: Raft

april 2013 by mcherm

Proposes Raft, an algorithm for distributed consensus that is simpler than Paxos. The algorithm design was motivated by "understandability" and I feel it achieves that.

computerscience
algorithms
algorithm
via:reddit
april 2013 by mcherm

Short algorithm, long-range consequences - MIT News Office

march 2013 by mcherm

An example of how math can change everything. In this case, they invented a MUCH simpler algorithm, which also happened to be faster.

math
algorithms
via:HackerNews
march 2013 by mcherm

Theresa Christy of Otis Elevator: Making Elevators Go | Creating - WSJ.com

december 2012 by mcherm

I've always found this job fascinating, and now I've read an article about someone who does it: writing the algorithms to control elevators.

programming
algorithms
via:slashdot
december 2012 by mcherm

1MB Sorting Explained

october 2012 by mcherm

Storing a large list of integers in far less memory than you would think would be possible.

programming
algorithm
algorithms
datastructures
via:reddit
october 2012 by mcherm

A Garden Variety of Bloom Filters | Matthias Vallentin

september 2012 by mcherm

Some things you can do with bloom filters, like counting bloom filters and ones where older values "age out" at random.

probabilisticcomputing
programming
algorithms
via:HackerNews
bloomfilter
september 2012 by mcherm

Little-Known Awesome Algorithms: Fenwick Range Trees – Rapidly Find Cumulative Frequency Sums | Swageroo Algorithms

september 2012 by mcherm

A data structure to keep a running total of values seen and quickly answer "how many were seen between x and y?

algorithms
datastructures
via:HackerNews
september 2012 by mcherm

Damn Cool Algorithms: Cardinality Estimation - Nick's Blog

september 2012 by mcherm

You have a huge collection of values and some are duplicates. How can you use probabilistic computing to estimate the number of unique values VERY cheaply?

algorithms
algorithm
probabilisticcomputing
math
programming
via:HackerNews
NickJohnson
september 2012 by mcherm

Probabilistic M2M Relationships Using Bloom Filters | Zack’s Blog.

august 2012 by mcherm

Use a bloom filter instead of a join table to (with a small percentage of false positives) join tables with very little space overhead.

via:HackerNews
algorithms
probabilisticcomputing
database
august 2012 by mcherm

Damn Cool Algorithms: Homomorphic Hashing - Nick's Blog

august 2012 by mcherm

A complicated hash algorithm described extremely well.

programming
algorithms
via:NickJohnsonz
NickJohnsonz
august 2012 by mcherm

Ned Batchelder: Selecting randomly from an unknown sequence

august 2012 by mcherm

Algorithm for choosing a random line from a file (of unknown length) without reading the file twice.

algorithms
programming
NedBatchelder
via:NedBatchelder
august 2012 by mcherm

Sieving out prime factorizations

august 2012 by mcherm

An algorithm and an efficient data structure for precomputing prime factorization of all numbers less than N.

algorithms
datastructures
programming
via:DavidMacIver
DavidMacIver
august 2012 by mcherm

Sorting and searching at the library

august 2012 by mcherm

The algorithms that the library uses for sorting: they're not what you would expect, and they are highly optimized.

algorithms
library
via:reddit
august 2012 by mcherm

The Opposite of a Bloom Filter – Something Similar

july 2012 by mcherm

You want the contrapositive of a bloom filter: massive number of values, finite memory consumption, want to recognize if items are in the set, willing to risk reporting it NOT in set when it is, but not the opposite. Use hash table but on collisions just replace it. Question: how is this better than a LRU cache?

algorithm
algorithms
datastructures
bloomfilter
probabilisticcomputing
via:HackerNews
july 2012 by mcherm

SSDs and Distributed Data Systems - Jay Kreps

june 2012 by mcherm

Serious thoughts about how the different characteristics of SSD drives (compared to magnetic disk) will change the architecture, algorithms, and data structures that apps must use.

hardware
algorithms
via:JayKreps
JayKreps
june 2012 by mcherm

Ned Batchelder: Recursive dogma

may 2012 by mcherm

He asked why his recursive function failed with 2**30 as input. They jumped on him as doing it wrong. But turns out he was allocating memory for lists where he could instead have been computing the answer in closed form (either with or without recursion).

via:NedBatchelder
programming
algorithms
functional
NedBatchelder
may 2012 by mcherm

Programmer’s Toolbox Part 3: Consistent Hashing « tomkleinpeter.com

march 2012 by mcherm

A good explanation of how to distribute items among a group of servers so you can safely add and remove servers.

programming
algorithms
scalability
via:HackerNews
march 2012 by mcherm

Why we didn't use a bloom filter: A Dash of Technology

march 2012 by mcherm

Directly looping through the items was faster because memory access was linear, not random. NOTE: today, memory access is the true bottleneck for nearly all algorithms.

algorithms
performance
programming
bloomfilter
via:HackerNews
march 2012 by mcherm

Regular Expression Matching with a Trigram Index

january 2012 by mcherm

How Google Code Search worked.

search
google
programming
algorithms
regex
via:HackerNews
january 2012 by mcherm

Damn Cool Algorithms: Fountain Codes - Nick's Blog

january 2012 by mcherm

A wonderful algorithm, this is a way to transmit lots of chunks from a file, lose some percentage (lossy transmission) and still reconstruct the file (probabilistically) once just slightly over the file-size of data has been successfully transmitted. Not mentioned in the article is that the algorithm is patented.

algorithms
algorithm
programming
filesharing
probabilisticcomputing
math
law
ip-law
patent
january 2012 by mcherm

Darts, Dice, and Coins

december 2011 by mcherm

A WONDERFUL essay on an algorithm for rolling a weighted die in O(1). The presentation is so well motivated that it is one of the best mathematical essays I have ever read.

via:HackerNews
math
algorithms
algorithm
programming
datastructures
december 2011 by mcherm

Darts, Dice, and Coins: A beautiful article on a beautiful algorithm | Hacker News

december 2011 by mcherm

I recommend a truly wonderful article about algorithms.

via:HackerNews
math
mypostings
algorithms
blogworthy
december 2011 by mcherm

reference request - What's new in purely functional data structures since Okasaki? - Theoretical Computer Science - Stack Exchange

december 2011 by mcherm

What's been done on immutable data structures since Okasaki? Here's the answer.

via:reddit
datastructures
programming
algorithms
december 2011 by mcherm

VP trees: A data structure for finding stuff fast - Steve Hanov's Programming Blog

december 2011 by mcherm

Works on any data where you can define distance.

programming
datastructures
algorithms
december 2011 by mcherm

Next permutation: When C++ gets it right

november 2011 by mcherm

Cool way to loop through the permutations.

algorithms
programming
personal_net
via:reddit
november 2011 by mcherm

"Algorithm" is Not a Four-Letter Word

october 2011 by mcherm

A very nicely done presentation on maze algorithms.

algorithms
presentation
programming
october 2011 by mcherm

AKS primality test - Wikipedia, the free encyclopedia

january 2011 by mcherm

There is a deterministic, polynomial-time algorithm for testing primality. I hadn't known that before.

cryptography
math
algorithms
via:Wikipedia
january 2011 by mcherm

Yacc is dead: An update

december 2010 by mcherm

More details about that parsing technique that uses "the derivative of a grammer". By this point, they have a working example in highly readable Scala code that's less than 100 lines long, along with some good analysis of the runtime complexity of the approach. It sounds amazingly good.

programming
computerscience
parsing
algorithms
via:HackerNews
december 2010 by mcherm

First improvement of fundamental algorithm in 10 years

september 2010 by mcherm

Someone has found a truly new algorithm for the "max flow" problem, which is apparently a commonly recurring optimization problem. There is, however, no actual paper I could find telling how it actually works.

algorithms
programming
computerscience
math
via:HackerNews
september 2010 by mcherm

The Treacherous Optimization » ridiculous_fish

august 2010 by mcherm

"Old age and treachery will beat youth and skill every time." - a look at how grep is optimized. Answer: very cleverly.

algorithms
performance
unix
programming
via:HackerNews
august 2010 by mcherm

SNA Projects Blog : Beating Binary Search

june 2010 by mcherm

Better than binary search: interpolation search is log(log(n)) if the array is randomly but uniformly populated.

programming
computerscience
algorithms
june 2010 by mcherm

You're Doing It Wrong - ACM Queue

june 2010 by mcherm

In general, we need to quit treating memory access as a constant-time operation: it depends entirely on whether it triggers a page fault! In particular, the binary heap (used for things like web caches) can be made vastly more efficient if we alter the datstructure to maximize the chance that the data we need is on a limited number of memory pages.

algorithms
datastructures
programming
via:reddit
ACMQueue
june 2010 by mcherm

Worst Case Complexity « Gödel’s Lost Letter and P=NP

june 2010 by mcherm

A possible alternate means for analyzing algorithms: based, not on WORST case (which is unreasonably bad) or average case (which may be too good) but on an opponent with only polynomial-time resources available.

complexity
computerscience
math
algorithms
via:DebasishGhosh
june 2010 by mcherm

PyPy Status Blog: An Efficient and Elegant Regular Expression Matcher in Python

may 2010 by mcherm

An implementation of (plain, non-backtracking) regular expressions that really is linear in the size of the string and of the regular expression, even for pathological cases. Very well explained.

programming
algorithms
pypy
regexp
may 2010 by mcherm

Simple Simhashing - a knol by Ryan Moulton

april 2010 by mcherm

You have lots of items, and want to group similar ones together, but in O(N) time so you can't do pairwise compares. Express each as a set (perhaps a collection of binary properties). Run a hash function on each member of the set. Find the k elements that gave the lowest hash values. All sets sharing these same k min items are in a group together.

probabilisticcomputing
algorithms
april 2010 by mcherm

How robots think: an introduction

march 2010 by mcherm

Describes the approaches that have turned out to make robotics successful. Basically, it's to embrace uncertainty and calculate everything as a probability.

algorithms
bayesian
ArsTechnica
via:ArsTechnica
robots
programming
ai
march 2010 by mcherm

Copy this bookmark: