DDD was new to me, and I was wondering how sorting all previously visited states could be faster than checking a hash table. The answer appears to be:
1. Duplicate detection is done delayed and in bulk, not after expanding each node
2. The linear memory access of the bulk check is more cache friendly than random-like hash table access
Allow me to quote from the first Google result:
Surprisingly, delayed duplicate detection is useful even
when all nodes fit in memory, resulting in reduced running time due to improved cache performance. In the
standard implementation of breadth-first search in memory, the Open list is stored in a hash table. As each
new node is generated, it is looked up in the hash table,
which often results in a cache miss, since the hash function is designed to randomly scatter the nodes.
1. Duplicate detection is done delayed and in bulk, not after expanding each node
2. The linear memory access of the bulk check is more cache friendly than random-like hash table access
Allow me to quote from the first Google result:
Surprisingly, delayed duplicate detection is useful even when all nodes fit in memory, resulting in reduced running time due to improved cache performance. In the standard implementation of breadth-first search in memory, the Open list is stored in a hash table. As each new node is generated, it is looked up in the hash table, which often results in a cache miss, since the hash function is designed to randomly scatter the nodes.
http://www.ijcai.org/Past%20Proceedings/IJCAI-2003/PDF/267.p...