15 puzzle solver: Difference between revisions
→The Plan
(→The Code: Ah, EQUIVALENCE.) |
|||
Line 261:
Such a guide function is rather like a "distance" function, so along these lines, when a minimum-step move sequence is found, the distances of each position from ZERO are calculated by various distance functions and the results shown in the output. Notably, function ZDIST calculates an encodement of the board position by referring to the layout of the ZERO position. It relies on the first square of a position having sixteen possible values, then the second square has fifteen and so on down; the number of possible layouts is 16! rather than 16<sup>16</sup>. Given the list of values of the squares in the ZERO sequence, values that have been taken are marked off (in array AVAIL) and the count of possibilities remaining as each square is identified reduces. The ZDIST number is like an encodement of an integer from its digits, but with a successively-reducing base.
As an experiment, when the Red Tide
The ZDIST function would be a candidate for a hash function, as it looks to give a good spray. But it requires rather more computation. It is always possible to calculate a "perfect" hash function, one that not only gives a distinct integer value for every possible key but also produces no gaps, so if there are N keys, there are N hash values in the range 1:N (or 0:N - 1) and the mapping is one to one. There even exist "hyper perfect" hash functions, that possess useful ordering properties: an example is the conversion of dates to a [[Calendar#Fortran|day number]], which is one-to-one, without gaps, and ordered by date. However, the calculation of such perfection may be lengthy, so a fast hash is preferable, except for special cases.
In the event, when running, TaskInfo showed that almost all of the time was spent in the filesystem's I/O procedures, no "user time" was visible. The hash calculation indeed was fast, but the I/O was slow. Probably because the disc file was scattered in blocks across the disc device (actually a solid-state drive) and finding the appropriate block took a lot of messing about. In the past, a large disc file would be in one or very few pieces on the actual disc, with a straightforward direct calculation between a record number and a disc's corresponding cylinder, surface, track and sector. These days, the operating system uses "spare" memory to hold the content of recently-used disc blocks, but alas, each index file is 781MB, and the stash files are over 3,000MB. Some systems have many gigabytes of memory, but this one has 4GB.
===The Code===
| |||