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. Dupli

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. http://www.ijcai.org/Past%20Proceedings/IJCAI-2003/PDF/267.pdf http://www.ijcai.org/Past%20Proceedings/IJCAI-2003/PDF/267.p...