Loading ...
Sorry, an error occurred while loading the content.

Re: FCS Lecture Summary - Finalized (Rev. 4)

Expand Messages
  • Shlomi Fish
    ... Several people wrote atomic moves-based Freecell solvers and they do not work too bad. I decided to use multi-moves in the first place, because I thought
    Message 1 of 3 , Nov 3, 2001
    • 0 Attachment
      On Sat, 3 Nov 2001, mulix wrote:

      > > I later improved some of these moves and added an extra one.
      > >
      > > Due to their multi-moves heuristic nature, it is possible that some boards
      > > are solveable, yet cannot be solved by FCS.
      >
      > this is an interesting point. did you consider to there may be a brute
      > force method which might be able to solve all boards? is such a brute
      > force method feasible, in terms or time/space complexity?
      >

      Several people wrote atomic moves-based Freecell solvers and they do not
      work too bad. I decided to use multi-moves in the first place, because I
      thought they would yield better results.

      > > The State Collection Representation Improvements:
      > > -------------------------------------------------
      > >
      [ Snipped the B-search, sort-margin and balanced binary tree stuff ]
      > > A Hash Table:
      > > -------------
      > >
      > > Description: What is a Hash Table?
      > > ----------------------------------
      > >
      > > * A hash table is a vector of linked lists. Each linked list contains
      > > a set of keys (or key-value pairs).
      >
      > that's not what a hash table is. that's what an *implementation* of a
      > hash table might look like.
      >

      Well, AFAIK a hash is an implementation of the dictionary abstract data
      type (ADT). Naturally, hashes comes in many forms and sizes. I realize it
      is also possible to use open addressing for a hash. However, I do not want
      to cover the entire theory of hashing in the lecture.

      > you might be interested in checking out the lecture notes for the
      > technion's cs department's 'data structures one' class. they have very
      > good lectures on avl, b trees and hash tables. (note - last year they
      > also had quite a few small but annoyiing mistakes in the slides - i hope
      > they are better this year). the slides are here:
      > http://www.cs.technion.ac.il/~dang/courseDS/
      >

      I took the EE equivalent course (or at least half of the two equivalent EE
      courses).

      > > * The index of the list in which the key is placed is determined by
      > > a hash function. Usually, the hash function generates an integer
      > > in a very large range, and the index is taken as its modulo with the
      > > number of elements in the hash table.
      >
      > again, that's one specific implementation, not necessarily the best.
      >

      I'm not saying it is.

      > > Rehashing:
      > > ----------
      > >
      > > Sometimes, when a hash becomes two crowded, the number of elements
      > > in it is increased and all of its existing elements are placed in
      > > their new place.
      > >
      > >
      > > * I first tried using glib's hash implementation with a 4-byte wide XOR as
      > > the hash function. This generated very awful results.
      > >
      > > * Then I tried using the MD5 hash function, and got excellent results,
      > > similar to what I encountered when using a balanced binary tree.
      > >
      > > * I coded my own stripped-down hash implementation in my attempt to figure
      > > out what went wrong with using a hash. It turned out to be a bit faster
      > > than glib's hash.
      >
      > this is not suprising: you replaced a general version with a private
      > version tailored for your needs.
      >

      Perhaps, but it is also possible mine is written better.

      > >
      > > Hash Optimizations:
      > > -------------------
      > >
      > > * Storing the hash values along with the keys. That way, the hash
      > > values can be first compared before comparing the entire keys.
      >
      > that's a very nice trick, but why did you need to store the hash value
      > explicitly? isn't the hash value the index of the cell in the array? (i
      > suspect you use 'hash value' here to refer to the very large number,
      > before you did the modulu, correct?)
      >

      That's right. The hash value is the value before the modulo is taken.

      > > * Moving elements that were hit to the start of their chains.
      >
      > why?
      >

      My assumption is that elements that were hit a lot are likely to be hit
      again often. That's why I wish them to be closer to the start of the list
      as possible so that redunant images would be eliminated soon.

      > > * When re-hashing, using the same malloc'ed elements, only re-linking
      > > them to their new siblings.
      >
      > of course.
      >
      > you might wish to explain in a few words how you *profiled* your code,
      > before optimizing it (i hope you profiled it...)
      >

      Actually, many times I implemented such optimizations out of necessity, or
      because I thought they would generate good results. Then, after I compared
      them with the previous results, I realized they were better in time or in
      memory.

      Regards,

      Shlomi Fish

      > [snipped the rest as i didnt have any comments]
      >
      > --
      > mulix
      >
      > http://www.pointer.co.il/~mulix/
      > http://syscalltrack.sf.net/
      >
      >
      >
      >
      > To unsubscribe from this group, send an email to:
      > hackers-il-unsubscribe@egroups.com
      >
      >
      >
      > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
      >
      >



      ----------------------------------------------------------------------
      Shlomi Fish shlomif@...
      Home Page: http://t2.technion.ac.il/~shlomif/
      Home E-mail: shlomif@...

      If:
      1. A is A
      2. A is not not-A
      does it imply that
      1. B is B
      2. B is not not-B
    Your message has been successfully submitted and would be delivered to recipients shortly.