Optimization changes an implementation to reduce work or improve performance. The useful question is not merely whether code can be made faster, but which structure or rule makes a different approach possible. section 4.0 section 4.4.2
Two recurring optimization patterns appear:
- Exploit a special case: HashLife returns an empty center immediately when an entire quad is empty, avoiding recursive work in sparse grids. section 4.4.2
- Change the representation: a DAWG replaces equivalent suffix nodes with canonical shared nodes, reducing redundant graph structure. section 5.4.1 section 5.4.3
- Preserve useful behavior while optimizing: the DAWG can reuse the existing WordGraph operations for Contains and StartsWith. section 5.4.3
Optimizing a DAWG incrementally
When adding sorted words, first follow their common prefix. Then inspect the previous word’s suffix, recursively replace equivalent nodes with canonical nodes, and append the new suffix. Recursion matters because removing a node can reveal a new equivalence farther toward the root. section 5.4.3 section 5.4.1
Listing 5.8 Building the DAWG algorithm
sealed class DawgBuilder
{
private class NodeEquality : IEqualityComparer<Node> { … }
private Node root = new();
private HashSet<Node> canonicalNodes =
new HashSet<Node>(new NodeEquality()); #1
private DawgBuilder() { }
public static Node MakeDawg(IEnumerable<string> words) #2
{
var db = new DawgBuilder();
foreach (var word in words)
db.Add(word); #3
db.FixUpLastWord(db.root); #4
return db.root;
}
private void Add(string word)
{
int i = 0;
Node n = root;
for (; i < word.Length; i += 1) #5
{
if (!n.HasEdge(word[i]))
break;
n = n.FollowEdge(word[i]);
}
FixUpLastWord(n); #6
for (; i < word.Length; i += 1) #7
n = n.AddNewNode(word[i]);
n.IsEnd = true;
}
private void FixUpLastWord(Node n)
{
if (n.Count == 0) #8
return;
char c = n.LastEdgeLabel;
Node s = n.FollowEdge(c); #9
FixUpLastWord(s); #10
Node? canonical;
canonicalNodes.TryGetValue(s, out canonical); #11
if (canonical == null)
canonicalNodes.Add(s); #12
else
n.ReplaceEdge(c, canonical); #13
}
}
Inspect the C# builder to see optimization placed between common-prefix discovery and new-suffix insertion, with canonical nodes stored in a HashSet. section 5.4.3
