March 29, 2024, 03:11:04 AM

News:

Own IWBasic 2.x ? -----> Get your free upgrade to 3.x now.........


Associative Arrays verification

Started by J B Wood (Zumwalt), January 29, 2007, 12:58:25 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

J B Wood (Zumwalt)

CPointerAssoc pDict;
pDict.Create(100);

So, this means that my associative arrays are static lists and not dynamic?
If I know a size for instance:

CPointerAssoc pDict;
int thisSize;
thisSize=10;
pDict.Create(thisSize);

That should work I would imagine.
Reason why I am asking, is that I have some code I am converting, and it reads structured data from a flie, in this structured data is an unknown number of object, but after I read it all in, I know the number that existed in the file, so the 10 in this example would be a count of objects.

Hopefully I am making sense, just doing some clerification before I program it in Aurora, I know I could program and test, but its nearly 3000 lines of code to convert before I test, didn't want to code it then find out I can't do what I was looking to do.

Thanks

Ionic Wind Support Team

No.  The paramter to create is the hash table size, not the amount of elements you are storing which is unlimited.  From the Aurora users guide:

Quote
Number of entries in the hash table. For best performance, the hash table size should be a prime number. To minimize collisions the size should be roughly 20 percent larger than the largest anticipated data set.  (optional default=17)

It is the same parameter as the DictCreate function in Emergence.  They are based on the same code.

Paul.
Ionic Wind Support Team

J B Wood (Zumwalt)

That didn't make sense to me.
Number of elements = 20 for instance, so the hash table size in create would be 24?

CPointerAssoc pDict;
int thisSize;
thisSize=(insize of 24);
pDict.Create(thisSize);

that is 24 empty structure items in the list ready to be populated

I am misunderstanding what you are talking about, that is how I read the instructions, if I have a structure that is going into the hash table, and it will contain 20 copies of that structure, each with its own data, then my hash table create should be 24, leaving 4 empty elements

what am I missing?

J B Wood (Zumwalt)


//Associative array test (Dictionary)
struct myObj
{
string name;
string value;
}

global sub main()
{
CStringAssoc dict;
dict.Create(100);
dict.Add("John","Red");
dict.Add("Joe","Green");
dict.Add("Sue","Yellow");
dict.Add("Phil","Purple");
dict.Add("Jerry","Orange");
dict.Add("Lisa","Blue");
//dict.Add("Jerry","Light Blue");
print(dict.Lookup("Jerry"));
print();
print("All associations:");
UINT pos = dict.GetStartAssoc();
while(pos)
{
void *pAssoc = dict.GetNextAssoc(pos);
print(dict.GetKey(pAssoc)," = ",dict.GetValue(pAssoc));
}
print();
//test integer assoc
CIntAssoc idict;
idict.Create(100);
idict.Add("Tuscon",100);
idict.Add("Buffalo",79);
idict.Add("Tampa",85);
idict.Add("Hollywood",70);
idict.Add("Chicago",68);
idict.Add("Dallas",89);

print(idict.Lookup("Buffalo"));
print();
print("All associations:");
pos = idict.GetStartAssoc();
while(pos)
{
pAssoc = idict.GetNextAssoc(pos);
print(idict.GetKey(pAssoc)," = ",idict.GetValue(pAssoc));
}

                // Added by Zumwalt
CPointerAssoc pDict;
pDict.Create(2);
myObj *testobj;
testobj=NEW(myObj,1);
testobj->name="Jon";
testobj->value="Wood";
pDict.Add("0", testobj);
testobj=NEW(myObj,1);
testobj->name="Jim";
testobj->value="Miller";
pDict.Add("1", testobj);

print();
print("All associations:");
pos = pDict.GetStartAssoc();
while(pos)
{
pAssoc = pDict.GetNextAssoc(pos);
testobj = pDict.GetValue(pAssoc);
print(pDict.GetKey(pAssoc)," = ",testobj->name, " & ",testobj->value);
}

while GetKey() == "";
if (testObj != null)
{
delete testobj;
}

}


This works, so what is wrong with how I have it?
I am just trying to fully understand if I am doing this wrong.

Ionic Wind Support Team

Your misunderstanding how associative arrays work.  You can leave it at the default, and still have unlimited storage, it would just be a bit slower than if you picked a larger hash table size.

Each hash table 'slot' contains its own linked list.  When your string key is 'hashed' a numeric identifier corresponding to a slot is generated and that determines which list it goes in.  When you lookup an element the key is hashed to come up with the slot, and then the list in that slot is iterated to find the matching entry.

If your hash table is too small then each list ends up being larger and hence it takes longer to lookup an element of the array.  If your hash table is too large then you will have a lot of empty 'slots' with no lists in them which justs wastes memory, not much memory of course, but still something to watch for.  Larger hash table sizes will always be faster than smaller ones given the same amount of data.

The 20% larger recommendation comes from Microsoft.  As a general rule I try and figure each slot containing a list of 10 or less entries.  So if I expect to be storing 10000 entries then I would set my hash table size to be 1000 which allows 10 elements in each hash list.

All of this is handled automatically.   You never see or have to manage the internal linked lists the hash table manages.

Paul.
Ionic Wind Support Team

J B Wood (Zumwalt)

Your correct, I am misunderstanding, but what I got out of your instruction is that if I leave it blank, it will keep the default of 17, this prime number is fine since I don't plan on having more than 200 items in the list at any given time, but if I get more than 200, I might want to move up to the next prime.

Ionic Wind Support Team

Yes the default is 17.  If you find it isn't efficient enough then tweak it for more 'lookup' speed.  It doesn't have to be a prime number, just that even numbers tend to create an unbalanced table where more data ends up in the first n slots where n is a prime number.

Paul.
Ionic Wind Support Team

LarryMc

LarryMc
Larry McCaughn :)
Author of IWB+, Custom Button Designer library, Custom Chart Designer library, Snippet Manager, IWGrid control library, LM_Image control library

Zen

When i was at college we got told this in terms of barns, hay bails and needles. Obviously from the phrase 'looking for a needle in a hay stack'. The more bails you had in each barn, the longer it would take to find the needle. Made sense to me i guess!

Lewis

LarryMc

Seems to me the structure works like b-tree indexing.
LarryMc
Larry McCaughn :)
Author of IWB+, Custom Button Designer library, Custom Chart Designer library, Snippet Manager, IWGrid control library, LM_Image control library

J B Wood (Zumwalt)

Thats what it smells like, either way, it works for what I am doing so I am very pleased.