recentpopularlog in

mcherm : algorithms   130

« earlier  
B-Heap
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
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
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
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
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
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
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
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
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
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
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
Some notes on programming hexagonal grids.
algorithms  gameprogramming  via:reddit 
september 2017 by mcherm
100 days of algorithms – Medium
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
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
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
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
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
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
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
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
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
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
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
The history of syphilis testing and a computer algorithm.
history  algorithms  via:reddit 
july 2015 by mcherm
Longstanding problem put to rest | MIT News
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
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
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
Another terrible sort algorithm for the books.
algorithms  sorting  via:reddit  programming 
august 2014 by mcherm
Gabriel Gambetta - Pathfinding Demystified (Part I): Introduction
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
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
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
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
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
In Search of an Understandable Consensus Algorithm: Raft
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
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
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
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
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
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
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.
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
Ned Batchelder: Selecting randomly from an unknown sequence
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
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
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
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
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
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
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
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
Damn Cool Algorithms: Fountain Codes - Nick's Blog
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
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
"Algorithm" is Not a Four-Letter Word
A very nicely done presentation on maze algorithms.
algorithms  presentation  programming 
october 2011 by mcherm
AKS primality test - Wikipedia, the free encyclopedia
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
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
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
"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
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
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
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
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
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
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
« earlier      
per page:    204080120160

Copy this bookmark:





to read