Many years ago I worked on a piece of software that simulated networks. As networks got bigger it would run out of memory. Turned out it did something like

Many years ago I worked on a piece of software that simulated networks. As networks got bigger it would run out of memory. Turned out it did something like CONNECTION *c = malloc(num_nodes * num_nodes * sizeof(CONNECT_STRUCT)); And almost the entire matrix was empty because most things in a network aren't connected to each other. I spent a a few minutes replacing that with a hash table on the (i, j) node pair.