Re: Need someone very familiar with arrays

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance


"Robert Morley" <rmorley@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
news:eMW1OXJJIHA.4592@xxxxxxxxxxxxxxxxxxxxxxx
Finally went over your post and the articles in Ralph's post today. Sounds
like your technique is pretty much the same as the first link in Ralph's post.
I never would've thought of using an array as the basis for the list; I was
just thinking too low-level where you've got pointers and maybe a hash table
or two and that's it. It's not really all that different to use an
array...just different enough that I had a lot of trouble wrapping my mind
around what was going on until eventually the puzzle pieces finally clicked
together for me.

So far, I've never had any significant need in VB to have a custom linked
list, and the Collection item (or a collection class based on it) has been
sufficient for my needs...a little slow at times, but acceptable for what I
was doing. It's certainly a technique I'll keep in mind should I ever need a
faster Collection-type object.

Next project: figure out how to actually implement a hash table. :-) I
understand the concept fully (I'm a DBA, I'd bloody well better!), but getting
from an item to it's hash has always been on a "somebody else did it for me"
basis. There was an example in one of the links in Ralph's post that I'll
have a look at. No need to provide links for this one, guys...a) I'm not
looking at it today, and b) I'm sure I can find hash examples quite easily by
Google. :-)



Rob


I would not have done a linked list of my own, had I not needed the
double-linking aspect: given some object (probably one the user clicked on in a
list), find the object before it and after it. In a collection, this would mean
indexing, which is painfully slow with the standard VB collection if has more
than a few items in it.

The one nice thing is that you can tune the list for a specific data type and
key type, in my case object references and long integer keys. A generic one has
to work with variants. If you can compile with the integer overflow and array
bounds checks switched off, you can get pretty good performance as well.

Hashing is quite an art form. You can get a PhD doing nothing but hash table
algorithms. For generic lists, the hash itself can be quite a challenge, since
the provided key can be almost anything. If you are doing your own list for a
specific purpose, you can get by with something homemade. Given some range of
input, devise a method to create an index from the key that falls within the
current size of the table, such that similar but different keys tend to produce
different values (ala check sums), and the overall distribution is uniform.

That step gets you a starting point in the actual table. Since some keys produce
the same start index, you also have to decide what will happen when the first
slot is already filled (for inserts), or has the wrong key (when retrieving).
This too can be elaborate, if you want a really efficent hash table, or it can
be a simple hunt from the start point, if you don't mind getting some big
clusters.

It is classic comp. sci., and it can be fun to work it all out, if you have some
time to spare fiddling with it. :)



.

Relevant Pages

  • Re: [Full-Disclosure] Show me the Virrii!
    ... the resources necessary to assemble definitive lists of ... audit process execution at just the right time. ... To complete what turned out to be a three-part-series on using hash ... BOOL validatehash(HANDLE hProfile,char *sHash,DWORD hashlen); ...
    (Full-Disclosure)
  • Re: Using regex special characters from a string
    ... Effective Perl Programming, 2nd Ed., Item 9: ... list of the array elements that evaluate to true. ... and lists as a whole, rather than executing code over each item ... Because to find an element in a hash does not require iterating over the ...
    (perl.beginners)
  • Re: Help me with Concatenating strings
    ... So maybe you should rather use a list or array with dynamic size, ... in fact i'm using arrays to build hash table because the file i'm ... i have two input arrays for the hash char *keys and char *values being, ... then i extract a list (self ordered linked lists) of all pathes (the ...
    (comp.programming)
  • Re: adjustable array vs hash-table
    ... of the hash-table are equal to indices in the array 0.1.2.3.4... ... As you can see, in Mathematica, there is no hash table. ... list that is used by what other lang might call vector, sequence, ... • hashtable ⇒ a list with element being lists, ...
    (comp.lang.lisp)
  • Re: serious self confusion over line counts and hashs.
    ... Hash keys must be unique. ... If you are worried about key collision (two keys the same), always test whether a key already exists before inserting it into a hash. ... File::Slurp can either return the contents of a file as a single scalar or as an array, ... way really since the lists can be pretty long. ...
    (perl.beginners)