mIRC Home    About    Download    Register    News    Help

Print Thread
Hashtable not ordered. #224061 05/08/10 01:39 AM
Joined: Jan 2009
Posts: 116
Knoeki Offline OP
Vogon poet
OP Offline
Vogon poet
Joined: Jan 2009
Posts: 116
Not sure if this is since the new version or not, but I can't say I remember this behaviour, nor does it seem logical.

If you add some data to a hashtable, and then continue to retrieve it by looping through all the items (with .item / .data property), you'd expect the items to still be in the same order as you stored them. Nothing could be further from the truth, however...

Take the following code:

Code:
alias hashtest {
    var %i $iif($1 != $null, $1, 20)
    if ($hget(hashtest) != $null) {
        hfree hashtest
    }
    hmake hashtest %i
    var %c 1
    while (%c <= %i) {
        hadd hashtest $+(i,%c) $+(d,%c)
        echo -s added item $+(i,%c) with data $+(d,%c) to table hashtest.
        inc %c
    }
    var %c 1
    while (%c <= %i) {
        echo -s reading item $hget(hashtest, %c).item with data $hget(hashtest, %c).data from table hashtest.
        inc %c
    }
}


result:

Code:
added item i1 with data d1 to table hashtest.
added item i2 with data d2 to table hashtest.
added item i3 with data d3 to table hashtest.
added item i4 with data d4 to table hashtest.
added item i5 with data d5 to table hashtest.
added item i6 with data d6 to table hashtest.
added item i7 with data d7 to table hashtest.
added item i8 with data d8 to table hashtest.
added item i9 with data d9 to table hashtest.
added item i10 with data d10 to table hashtest.
added item i11 with data d11 to table hashtest.
added item i12 with data d12 to table hashtest.
added item i13 with data d13 to table hashtest.
added item i14 with data d14 to table hashtest.
added item i15 with data d15 to table hashtest.
added item i16 with data d16 to table hashtest.
added item i17 with data d17 to table hashtest.
added item i18 with data d18 to table hashtest.
added item i19 with data d19 to table hashtest.
added item i20 with data d20 to table hashtest.
reading item i20 with data d20 from table hashtest.
reading item i16 with data d16 from table hashtest.
reading item i17 with data d17 from table hashtest.
reading item i8 with data d8 from table hashtest.
reading item i14 with data d14 from table hashtest.
reading item i2 with data d2 from table hashtest.
reading item i9 with data d9 from table hashtest.
reading item i15 with data d15 from table hashtest.
reading item i3 with data d3 from table hashtest.
reading item i18 with data d18 from table hashtest.
reading item i12 with data d12 from table hashtest.
reading item i19 with data d19 from table hashtest.
reading item i13 with data d13 from table hashtest.
reading item i1 with data d1 from table hashtest.
reading item i10 with data d10 from table hashtest.
reading item i6 with data d6 from table hashtest.
reading item i11 with data d11 from table hashtest.
reading item i7 with data d7 from table hashtest.
reading item i4 with data d4 from table hashtest.
reading item i5 with data d5 from table hashtest.


I know that using the .item/.data properties are not what hashtables are specifically made for, but I'd still very much like it if this behaviour (as rarely or often it may be used by people) is modified to return items in the same order as they were stored.

I hope this makes sense ;_)



http://zowb.net

/server -m irc.p2p-network.net -j #zomgwtfbbq
(ssl on port 6697 and 7000)
Re: Hashtable not ordered. [Re: Knoeki] #224068 05/08/10 02:40 AM
Joined: Nov 2006
Posts: 1,559
H
Horstl Offline
Hoopy frood
Offline
Hoopy frood
H
Joined: Nov 2006
Posts: 1,559
Hash tables are inherently unsorted. If you search the forums a bit, you'll find several post like this.
As a cheap workaround, create your table with the size of 1 ("hmake hashtest 1" instead of "hmake hashtest %i") - although I forgot why, it will work. wink

Re: Hashtable not ordered. [Re: Horstl] #224077 05/08/10 05:53 AM
Joined: Feb 2006
Posts: 546
J
jaytea Offline
Fjord artisan
Offline
Fjord artisan
J
Joined: Feb 2006
Posts: 546
it's due to the way hash tables are stored internally. every item name you add is passed through a simple hashing algorithm to produce an integer whose range of values is exactly the number of 'slots' in your hash table. if the resulting integer collides with another previously hashed item name, the corresponding data is stored at the same location and is linked to the ones that already exist. this linked list does preserve order, with the obvious trade off of mIRC having to traverse a list to retrieve data from an item name. you lose the actual utility of a hash table, which is its ability to reference data from the item name in constant time. the time it takes with a size 1 hash table is now proportional to the number of items in the table

if you need some semblance of order, you're better of using a @window which allows you to insert/remove items comfortably



"The only excuse for making a useless script is that one admires it intensely" - Oscar Wilde
Re: Hashtable not ordered. [Re: Horstl] #224078 05/08/10 06:00 AM
Joined: Oct 2003
Posts: 3,918
A
argv0 Offline
Hoopy frood
Offline
Hoopy frood
A
Joined: Oct 2003
Posts: 3,918
A lot of this is just reiterating jaytea's points, by the way.

Items are mapped into N buckets where N is the table size.

Size of 1 == 1 bucket == (itemN mod 1)

But on the flipside that means you lose the entire performance benefit of using hash tables. In fact, it's likely to be slower than something like a variable, since any item access will necessarily be on the order of O(n), and looping over items will be O(n^2)

Which means, it's not recommended at all.

Use dynamic variable names or @windows as jaytea suggested. AFAIK $var(%prefix.*,N) should maintain order.


- argv[0] on EFnet #mIRC
- "Life is a pointer to an integer without a cast"
Re: Hashtable not ordered. [Re: argv0] #224083 05/08/10 06:29 AM
Joined: Feb 2006
Posts: 546
J
jaytea Offline
Fjord artisan
Offline
Fjord artisan
J
Joined: Feb 2006
Posts: 546
$var( , N) does indeed refer to the order in which the variables were set (local variables first) but this is similar to the hash table approach insofar as you can only add to and remove from the end of the list


"The only excuse for making a useless script is that one admires it intensely" - Oscar Wilde
Re: Hashtable not ordered. [Re: jaytea] #224084 05/08/10 06:52 AM
Joined: Oct 2003
Posts: 3,918
A
argv0 Offline
Hoopy frood
Offline
Hoopy frood
A
Joined: Oct 2003
Posts: 3,918
Well, the corollary is that you should really not be mutating lists while you iterate over them in general. Adding an item leads to possible infinite-addition scenarios and removing an item throws off your index counter, potentially causing you to skip an item.

Usually rather than mutating the list directly as you loop it, you would generate a separate list of keys to iterate over which never changes, and then you can modify the list to your hearts content.


- argv[0] on EFnet #mIRC
- "Life is a pointer to an integer without a cast"
Re: Hashtable not ordered. [Re: Horstl] #224104 05/08/10 12:39 PM
Joined: Jan 2009
Posts: 116
Knoeki Offline OP
Vogon poet
OP Offline
Vogon poet
Joined: Jan 2009
Posts: 116
Originally Posted By: Horstl
Hash tables are inherently unsorted. If you search the forums a bit, you'll find several post like this.


I had searched, wasn't able to find anything.. oh well, will try harder next time ;_)

Quote:
As a cheap workaround, create your table with the size of 1 ("hmake hashtest 1" instead of "hmake hashtest %i") - although I forgot why, it will work. wink


It does work, although now it's in reverse order (which is at least *something* ;_))

And to the others: thanks for explaining. I didn't realize there was a reason for the unorderdness. I did know that replacing an item doesn't change it's position, although I somehow had hoped that new items would be added to the bottom of the table. Can't be helped.

Reason I use hashtables is mostly because it seems a bit more organized to me than global variables. It's funny though how first people told me I should use hashtables instead of dynamic vars, and now the other way around ;_) (no problem with vars of any kind (dynamic or not) btw, just prefer to not use them as globals).


http://zowb.net

/server -m irc.p2p-network.net -j #zomgwtfbbq
(ssl on port 6697 and 7000)
Re: Hashtable not ordered. [Re: Knoeki] #224114 05/08/10 02:14 PM
Joined: Oct 2004
Posts: 8,330
Riamus2 Offline
Hoopy frood
Offline
Hoopy frood
Joined: Oct 2004
Posts: 8,330
Hash tables have benefits over variables and variables have benefits over hash tables. It all depends on what you are doing.

If you need a sorted hash table, you do have the option of saving it to a file and using /filter to sort it (include the original line number in /filter so you can reference the right item in the hash table). This works very well for something like storing scores for a game and then listing the top 10 (or bottom 10) scores. You can store the scores as normal in the hash table, then to show the top 10, you just save the table, /filter it, reference the first 10 items in the list in the hash table and you're done. Nice and easy. This example also puts in an automatic n/a if there isn't a score available (for example, if you only had 5 people with scores after scores are reset, then it would list a Top 10, but would show n/a for the last 5 scores until more people have scores).

For example, here's a way to see the Top 10 scores in a hash table filled with scores:

Code:
alias Top10 {
  hsave -n Scores Scores.txt
  filter -ffcuten 1 32 Scores.txt Scores.txt
  var %c = 1, %t = 10
  while (%c <= %t) {
    echo -a %c :: $iif($hget(Scores,$gettok($read(Scores.txt,nt,%c),1,32)).item,$v1,n/a)
    inc %c
  }
}


To use, fill a hash table called Scores up with nicks and scores (item = nick, data = score) and then use /Top10 . Obviously, you can adjust how it displays the scores depending how you want it to show up. Normally you'd want to have it on one line with some kind of nice formatting done to it. I just made something quick so you can see how it works.

How it works:

You save the hash table as data only (the scores, but not the nicks). The data will be in the same order as it was in the hash table, so item 1 in the hash table will be line 1 when saved.

Next, you filter that file so that it sorts it in numerical descending order (-ue) (remove -e if you want the bottom 10). You'll want to sort based on column one with space delimiter (-t 1 32) and you'll want to clear the file since you're overwriting the same file (-ff) with the sorted data (-c). Finally, you want to insert the original line number into the new file (-n).

Now that it's sorted, if you look at the new file, it will be in the format of:

Original_Line_# Score

Example:

8 3156
1 2345
4 104
3 46
2 32

Finally, you will want to pull up the nick for the scores when displaying them. The nick is the item in the table, so we would $read() the first line (8 3156 in the above example). We will use just the line number (8) from that, so we need $gettok() to get that line number. Then, we look it up in the hash table with $hget(Scores,8).item which will tell us the nick who is 8th in the table, but first in the scores list.

I know that's a long drawn out explanation, but it should answer any questions someone has about how it works so they can make it work the way they want with the data they have. And you can, of course, have a Top 5 or Top 100 or Bottom 5 or whatever else you want just by adjusting either the /filter (ascending vs. descending) or the loop (%t).

Just be aware that by doing it this way, if you somehow manage to change the hash table in the miliseconds it takes to filter and display the scores, it will show the wrong scores. So make sure that you have the scores displayed at a time when the hash table won't be updated (after or before a game, between questions in trivia, etc).

A note on using $read() -- If you're displaying many scores [lines of data], then you may want to consider other methods of reading the file (such as /fopen, /fread, /fclose commands) to speed things up and avoid multiple accesses of the file. There are other methods as well. For only showing 5-10 scores, it really doesn't matter all that much, but it's something to consider.

-----------------------------------
One last note. If you want to list a table in the same order the data was stored, you can actually use this same method. Just store your DATA field as $ctime DATA. By including $ctime, then you are sorting based on a number just like if it was a score. Use ascending or descending order depending on which way you want the table to be displayed (first to last or last to first). And make sure you adjust your $hget()'s so they ignore $1 in the DATA.


Invision Support
#Invision on irc.irchighway.net
Re: Hashtable not ordered. [Re: jaytea] #224124 05/08/10 02:49 PM
Joined: Nov 2006
Posts: 1,559
H
Horstl Offline
Hoopy frood
Offline
Hoopy frood
H
Joined: Nov 2006
Posts: 1,559
Yeah, I should have mentioned the performance issue. Sometimes the "single bucket" method is of use (quick inter-event storage of results of sockreads; keeping a short "recent xyz" list and the like), but in most cases it is inferior.

The @window method is versatile (/*line commands and /filter, no disk access required), but has two downsides: the user may close your hidden window by accident in the window menu; and the infamous "No. of windows limit" may quick become a problem if you e.g. you want to feed several datasets per network/channel. For a single sort operation it's less problematic.
I share the OPs dislike of setting a ton of global vars, and in general I use a method like Riamus2 described: dump the table to a file (or a @window :D) and /filter or whatever is required.

However, what method (or combination of methods) will work "best" depends on many things (number and size of data to store, frequency of access and modification, required performance - just to name a few) and the only way to find out for a particular case is to try (and bench) several.

Re: Hashtable not ordered. [Re: Horstl] #224216 06/08/10 03:18 PM
Joined: Jan 2009
Posts: 116
Knoeki Offline OP
Vogon poet
OP Offline
Vogon poet
Joined: Jan 2009
Posts: 116
I've found a way to do this.

writing to a file and using /filter is out of the question, it's too slow to be executed at 50 fps ;_)


http://zowb.net

/server -m irc.p2p-network.net -j #zomgwtfbbq
(ssl on port 6697 and 7000)
Re: Hashtable not ordered. [Re: Knoeki] #224585 14/08/10 10:47 AM
Joined: Apr 2003
Posts: 342
M
MeStinkBAD Offline
Fjord artisan
Offline
Fjord artisan
M
Joined: Apr 2003
Posts: 342
Code:
alias hashtest {
    var %i $iif($1 != $null, $1, 20)
    if ($hget(hashtest) != $null) {
        hfree hashtest
    }
    hmake hashtest %i
    var %c 1
    while (%c <= %i) {
        hadd hashtest $+(i,$base(%c,10,10,7)) $+(d,%c)
        echo -s added item $+(i,$base(%c,10,10,7)) with data $+(d,%c) to table hashtest.
        inc %c
    }
    var %c 1
    while (%c <= %i) {
        echo -s reading item $hget(hashtest, %c).item with data $hget(hashtest, %c).data from table hashtest.
        inc %c
    }
}


There... happy?


Beware of MeStinkBAD! He knows more than he actually does!
Re: Hashtable not ordered. [Re: MeStinkBAD] #224797 18/08/10 09:41 PM
Joined: Sep 2009
Posts: 52
Z
ziv Offline
Babel fish
Offline
Babel fish
Z
Joined: Sep 2009
Posts: 52
First off, there's a possible problem here if he triggers that code again, while the first time is still running, thanks to the /hfree there.

Secondly, creating a second hash table to sort the first? Oo that seems awfully inefficient.

I deal with indexes plenty, and the trick I use is very simple.
hadd table index-pos.item-name item-value
(example: /hadd Scores 5.PlayerName Player)

But there are two clear flaws with this method:
1) It doesn't offer the kind of sorting /filter does, only indexing.

2) If you remove an object from the list, and it's not the last one on it, then you'll have a Nulled out item breaking your loop.
My solution to this problem is an 'if $hget(table,i.item) != $null' check while I'm looping through the list.

This method does mean you don't have to sort out the list with something as bothersome as some of the codes displayed here, simply keep an index item in the list, and use it to determine the item-name.
Also, it means you can keep more then a single list in the same table.

If you find yourself having loads of Nulled-out items in the list, you can use a binvar as an indexing variable, storing a tokenized list of all the items that actually exist.
Removing, adding, replacing and sorting binvars isn't that complicated at all, neither is tokenizing it and treating it as $1-.
This will make things bigger, in actual size, but it'll still run faster.

Good luck,
ziv.

Last edited by ziv; 18/08/10 09:49 PM.