Re: Pattern matching ........

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

I just use the hash to speed up the pattern matching.  Each
pattern is on one or more hash chains (more than one if there
is a don't care in one or more of the hashing positions).

The 8 bit hash gives me something like 50x or 100x speedup
in pattern matching over just trying every pattern at every
board position in every orientation.  This was enough to make
pattern matching less than 1% of the runtime, so there is
no need for a bigger hash.

The bigger the hash, the more likely that it will include don't cares
in the pattern, so there will be more patterns on multiple hash
lists, wasting memory.

Most of my patterns are much smaller than 8x8, so they have a lot of don't 
care points in them.

David

At 08:49 AM 3/13/99 EST, Compgo123@xxxxxxxxxxxxxxxxx wrote:
>David Fotland said:
>
>> I used 8x8 bit map and a 8 bit hash table.......
>
>If 8 bit hash is more efficient than 16, 32, or 64 bits (is it with a 32 bit
>bus and cpu?), I have a suggestion. Why not use multple hash tables. The
first
>table is 8 bit. The second is 16 bit, and so on. Only those passed the first
>table are checked with the next table.
>
>Dan Liu
>
>