Re: The Size/Speed Paradox
On Sat, 15 Apr 2000, Daniel Feiglin wrote: > Well, I was curious enough to click on your source code site and here is wahat I > got: > > Forbidden > > You don't have permission to access /~shlomif/fcs/ on this server. > > Ho hum. > > Dan Feiglin > Well, sorry about that, but apparently t2 does not allow to view directories which do not contain index.html files. I fixed it, but in any case vipe is now serving users' home pages so you can go to my homepage (http://t2.technion.ac.il/~shlomif/) and follow the Freecell Solver link. Regards, Shlomi Fish -- Shlomi Fish[EMAIL PROTECTED] Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: [EMAIL PROTECTED] The prefix "God Said" has the extraordinary logical property of converting any statement that follows it into a true one. = To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]
RE: The Size/Speed Paradox
> > I noticed that the program that uses the chars representation > runs much > faster than the int/short based program. For 100 given initial boards, > it finished them in 11 minutes and 12 seconds. The wider program took > more than 19 minutes when it was terminated in the middle of board No. > 62, which is a complex board that takes 42,940 checked states to > solution. I haven't looked at your source, but the program should need very much memory, less memory used->less swapping, less memory used->higher hit-rate... Regards Maxim = To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]
Re: The Size/Speed Paradox
Well, I was curious enough to click on your source code site and here is wahat I got: Forbidden You don't have permission to access /~shlomif/fcs/ on this server. Ho hum. Dan Feiglin Shlomi Fish wrote: > This is slightly off-topic but I thought it may be of interest to the > list. > > I wrote a program that automatically solves Freecell games. For those > who are not familiar with it, Freecell is a card game, in which there > are several stacks which should be moved to the decks with the aid of > freecells, which are cells that can hold one card each. > > In any case, the program operates by keeping record of the states for > which it checked whether they are solveable, so if the same state is > reached twice, it will only be checked once. (and thus also, it makes > sure there are no infinite loops). I wrote two versions of the program, > one which uses states where the representitive integers have widthes of > ints and shorts. And the second the integers are chars, and semi-chars. > (I use shifts and bit masks to get the card deck and card number). > > I noticed that the program that uses the chars representation runs much > faster than the int/short based program. For 100 given initial boards, > it finished them in 11 minutes and 12 seconds. The wider program took > more than 19 minutes when it was terminated in the middle of board No. > 62, which is a complex board that takes 42,940 checked states to > solution. > > The question is why the wide-integer based program is slower because > obviously my Pentium 166 MHz processor takes less time for 32-bit or > 16-bit integer computations and memory access than for 8-bit > ones. My best guess so far is that the majority of the time is spent > storing and searching for states, and because the char storage occupies > less space, that it is considerably faster. > > What do you think? > > You can download Freecell Solver and take a look at the source code > from the following URL: > > http://t2.technion.ac.il/~shlomif/fcs/ > > This is not going to be its permanent homepage, but I resorted to > putting it there because vipe.technion.ac.il has a momentary problem of > hosting the users' homepages. > > I discovered a few other insights while working on Freecell Solver. For > instance, I realized that one should not use qsort to insert a sort > margin into a sorted array, because it's quite slow. Instead, a > binary-search based merging function should be used. > > Another curious thing is that the program runs differently on Windows > NT than it does on i386 Linux and SPARC Solaris. On IRIX 64-bit it runs > differnetly than both of the above. I still don't know what's the cause > of this behaviour but I'm investigating it. > > Best regards, > > Shlomi Fish > > -- > Shlomi Fish[EMAIL PROTECTED] > Home Page: http://t2.technion.ac.il/~shlomif/ > Home E-mail: [EMAIL PROTECTED] > > The prefix "God Said" has the extraordinary logical property of > converting any statement that follows it into a true one. > > = > To unsubscribe, send mail to [EMAIL PROTECTED] with > the word "unsubscribe" in the message body, e.g., run the command > echo unsubscribe | mail [EMAIL PROTECTED] begin:vcard n:Feiglin;Daniel tel;cell:972 53 869986 tel;fax:972 9 862 1052 tel;home:972 9 832 0939 tel;work:972 9 861 6204 x-mozilla-html:FALSE org:Dilog Computers Ltd. adr:;;POB 36;Shavei Shomron, Mobile Post;;44858;ISRAEL version:2.1 email;internet:[EMAIL PROTECTED] title:CC & BW note:cc: to [EMAIL PROTECTED] x-mozilla-cpt:;-7424 fn:Daniel Feiglin end:vcard
Re: The Size/Speed Paradox
On Sat, 15 Apr 2000, Shlomi Fish wrote: > The question is why the wide-integer based program is slower because > obviously my Pentium 166 MHz processor takes less time for 32-bit or > 16-bit integer computations and memory access than for 8-bit > ones. My best guess so far is that the majority of the time is spent > storing and searching for states, and because the char storage occupies > less space, that it is considerably faster. The Pentium's cache is 8 bits wide (IIRC)... does everything make sense now? ;) -- crisk ._ [EMAIL PROTECTED] ._/-==\\\ _ |_.-`---^-._ The biggest lies: 11. I never inhaled. = To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]
The Size/Speed Paradox
This is slightly off-topic but I thought it may be of interest to the list. I wrote a program that automatically solves Freecell games. For those who are not familiar with it, Freecell is a card game, in which there are several stacks which should be moved to the decks with the aid of freecells, which are cells that can hold one card each. In any case, the program operates by keeping record of the states for which it checked whether they are solveable, so if the same state is reached twice, it will only be checked once. (and thus also, it makes sure there are no infinite loops). I wrote two versions of the program, one which uses states where the representitive integers have widthes of ints and shorts. And the second the integers are chars, and semi-chars. (I use shifts and bit masks to get the card deck and card number). I noticed that the program that uses the chars representation runs much faster than the int/short based program. For 100 given initial boards, it finished them in 11 minutes and 12 seconds. The wider program took more than 19 minutes when it was terminated in the middle of board No. 62, which is a complex board that takes 42,940 checked states to solution. The question is why the wide-integer based program is slower because obviously my Pentium 166 MHz processor takes less time for 32-bit or 16-bit integer computations and memory access than for 8-bit ones. My best guess so far is that the majority of the time is spent storing and searching for states, and because the char storage occupies less space, that it is considerably faster. What do you think? You can download Freecell Solver and take a look at the source code from the following URL: http://t2.technion.ac.il/~shlomif/fcs/ This is not going to be its permanent homepage, but I resorted to putting it there because vipe.technion.ac.il has a momentary problem of hosting the users' homepages. I discovered a few other insights while working on Freecell Solver. For instance, I realized that one should not use qsort to insert a sort margin into a sorted array, because it's quite slow. Instead, a binary-search based merging function should be used. Another curious thing is that the program runs differently on Windows NT than it does on i386 Linux and SPARC Solaris. On IRIX 64-bit it runs differnetly than both of the above. I still don't know what's the cause of this behaviour but I'm investigating it. Best regards, Shlomi Fish -- Shlomi Fish[EMAIL PROTECTED] Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: [EMAIL PROTECTED] The prefix "God Said" has the extraordinary logical property of converting any statement that follows it into a true one. = To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]
