Post Reply 
Associative array / dictionary / hash / map
04-28-2018, 02:53 AM
Post: #1
Associative array / dictionary / hash / map
A very useful data structures for programming is the associative array often called a dictionary or hash. I was missing it on the Prime and although there are references to a Prime command called 'table' it doesn't seem to work for me and word has it that it is deprecated anyway. So I wrote a really simple dictionary implementation that simply uses lists. We can't use matrices because they only allow numbers. So it has to be done with lists, which can store anything.

Typical dictionaries have a special syntax separating the key from the value e.g. notice the colon :
Code:

{'one': 1, 'two': 2, 'three': 3}

The trick in my implementation is that every second item in the list is interpreted as the value. No special syntax required. Then just indent the list in such a way that the pairing of keys and values is apparent.

Code:

export dict(lzt,key)
begin
    local i;
    for i from 1 to size(lzt) step 2 do
      if lzt(i)=key then return lzt(i+1); end;
    end;
    return "";
end;

export dicttest1()
begin
    local dict1 := {
        "andy", 100,
        "sam", 200,
        "mary", 3300
    };
    print();
    print("looking up andy got \"" + dict(dict1, "andy") + "\"");
    print("looking up sam got \"" + dict(dict1, "sam") + "\"");
    print("looking up zxc got \"" + dict(dict1, "zxc") + "\"");
end;

Of course this implementation is not efficient - real hash tables are fast and don't need to search through each entry. But that is a bigger project and involves handling hash collisions etc. This implementation is fast enough for simple purposes. The next steps might be to support assignment and common operations like length, del, values() to return a list of values, keys() to return a list of keys etc. Since there is no OO in Prime I suppose all these operations would become separate functions. I may get around to writing them but feel free to contribute individual functions to this thread! FYI here is the complete list of dictionary functions that e.g. Python dictionaries support, and most languages (Php, Javascript, Ruby...) have identical functionality.
Find all posts by this user
Quote this message in a reply
04-28-2018, 06:55 AM
Post: #2
RE: Associative array / dictionary / hash / map
Open Settings, select algebraic entry, after that you can do:
t["one"]:=1;
t["two"]:=2;
If t is a table, t[index] will return the value stored, or 0 if nothing is stored. The idea is to store sparse matrices with these kinds of objects for efficiency:
t:=convert(identity(3),table);
t*t;
t+t;
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)