Memory is storage capacity available to hold program data during execution. Algorithm design must consider not only asymptotic growth but also the bytes consumed by a concrete representation. section 4.2.1 section 5.1.2
A representation can deliberately spend memory to save time. Storing one cell per array position uses more space than packing eight cells into each byte, but avoids expensive bit-twiddling arithmetic. section 4.2.1
Concrete memory analysis exposes costs hidden by an abstract data structure:
- A 65,536-cell grid could fit in 8,192 bytes, while the naïve implementation allocates 133,128 bytes—more than sixteen times as much. section 4.2.1
- For n cells, that implementation uses O(n) memory overall and performs O(n) work per tick. section 4.2.1
- A sorted C# word list pays for two-byte characters, string metadata, and references; a large list can therefore consume several megabytes before search costs are considered. section 5.1.2
- A trie deduplicates prefixes but can still waste space: ENABLE produces 387,881 nodes, and 111,507 terminal leaves consume more than a million bytes. section 5.2.4
Choosing space over bit manipulation
Representing each Life cell directly in arrays consumes roughly 133,128 bytes instead of the theoretical 8,192-byte packed representation. The larger layout is accepted because memory is cheaper than the repeated bit operations needed to decode packed cells. section 4.2.1
Listing 5.1 A sorted word list
class SortedWordList : IWords
{
private List<string> words;
public SortedWordList(List<string> words) #1
{
this.words = words;
}
public bool Contains(string word) => words.BinarySearch(word) >= 0; #2
public IEnumerable<string> StartsWith(string prefix)
{
int i = words.BinarySearch(prefix);
if (i < 0)
i = ~i; #3
for (; i < words.Count; i += 1)
{
string w = words[i];
if (!w.StartsWith(prefix)) #4
yield break;
yield return w;
}
}
public IEnumerator<string> GetEnumerator() => words.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
Inspect the sorted C# word-list implementation to see the reference-based representation whose memory cost is later estimated. section 5.1.2
