Hey, int hash[]; 0 => hash["zero"]; 1 => hash["one"]; hash.keys @=> string keys[]; Is there anything like this, some way for an associative array to tell you what keys it has? Ge apparently mentioned it as a development goal for 6 years ago ( https://lists.cs.princeton.edu/pipermail/chuck-users/2006-March/000436.html ), but searching for "key" in the versions page shows no update in this area. Thanks, George
On Tue, Sep 25, 2012 at 09:21:17PM -0400, George Locke wrote:
Is there anything like this, some way for an associative array to tell you what keys it has?
No, I don't think so. They are convenient, as long as you remember what you put where, but you can't get a list or loop over all of them, etc. This means you can have a array of size 0 taking up a GB, with no sure way to get to this data, theoretically.
Ge apparently mentioned it as a development goal for 6 years ago ( https://lists.cs.princeton.edu/pipermail/chuck-users/2006-March/000436.html ), but searching for "key" in the versions page shows no update in this area.
I think you are right and that this leads to some interesting consequences. Since we don't have things like lists or vectors we tend to use arrays for a lot; they are our one generic higher level structure. Because of that, over the last few versions, we got extra features for them; ways to change the size and a sort of push/pop structures making them usable like a sort of stack. I feel that especially those two features imply a sort of usage where we might expect the ability to totally flush a array (for example at the start of a new movement to our piece or when a new user picks up our instrument or....) because of what you note we can not actually do that. IMHO that makes this kind of feature more coherent with the rest now than it was when Ge planned to do it. Something like; Array.named() which I imagine would return a anonymous array of strings, each of which would represent one named index. Such a thing we could loop over. I also imagine; Array.popBack("foo") which would either return the contents of the named entry "foo" and clear that entry from memory or result in a error/warning if "foo" would happen to not be a entry. I think that would bring things more in line with the rest and that this would be worthwhile, given the notes above. I just came up with these as I typed; some peer-review would be welcome. I am, BTW, not at all opposed to just having one generic higher level structure; it does add coherence and clarity and avoids conversions, assuming our one such structure behaves very well. Yours, Kas.
On 27/09/12 00:45, Kassen wrote:
I think you are right and that this leads to some interesting consequences. Since we don't have things like lists or vectors we tend to use arrays for a lot; they are our one generic higher level structure. Because of that, over the last few versions, we got extra features for them; ways to change the size and a sort of push/pop structures making them usable like a sort of stack.
...
I am, BTW, not at all opposed to just having one generic higher level structure; it does add coherence and clarity and avoids conversions, assuming our one such structure behaves very well.
Yours, Kas.
Hi! Firstly, just as an info: ChucK maps are implemented internally as red-black trees, not hash maps. Secondly, arrays/maps are not the only higher-level (aggregate) data type in ChucK. There are also classes, which are well suited for record/structure-like use cases. If you want a language with only one higher-level data type, have a look at Lua. It has "tables" which are simply RB-trees. They are used as arrays (all keys are integer and consecutively start with 1), associative arrays (some other type of key - every key may have a different type) and classes/objects (table values may be functions and there's a hierarchy of tables via "metatables"). All of this is possible by adding syntactic sugar to the language, e.g. for constructing tables. While I think that ChucK arrays should be more generic (e.g. it should be possible to construct maps using "[ ... ]" expressions), I think it's a good thing that ChucK has a separate class type, as it is much more explicit than Lua classes and (theoretically) allows better optimizations. Regarding the question of iterating maps: Of course that would be nice. But doing this by simply having a method that returns all keys as an array is inefficient, since that requires a complete traversal of the RB-tree (O(n)) to get all keys, followed by RB-tree accesses (O(log(n))) for every key. That is a complexity of O(n*(log(n) + 1)) for a complete iteration while it is theoretically possible in O(n). Doing it in O(n) however requires you to have a concept of iterators and iterator-loops, adding much complexity to the language. In the simplest case you need a special for-loop, like for (key, value in map) {...} If you need an efficient map iteration right now, consider implementing your own RB/AVL-tree data structure using ChucK classes ;-) Best regards, Robin
On Tue, Oct 02, 2012 at 04:06:57PM +0200, Robin Haberkorn wrote:
Hey!
Secondly, arrays/maps are not the only higher-level (aggregate) data type in ChucK. There are also classes, which are well suited for record/structure-like use cases.
Yes, that is true. I meant "build in" structure but should have been more clear. I remember somebody doing a implementation of lists in a class, as a proof of concept, even.
Regarding the question of iterating maps: Of course that would be nice. But doing this by simply having a method that returns all keys as an array is inefficient, since that requires a complete traversal of the RB-tree (O(n)) to get all keys, followed by RB-tree accesses (O(log(n))) for every key. That is a complexity of O(n*(log(n) + 1)) for a complete iteration while it is theoretically possible in O(n). Doing it in O(n) however requires you to have a concept of iterators and iterator-loops, adding much complexity to the language. In the simplest case you need a special for-loop, like for (key, value in map) {...}
So, you are proposing a sort of "for-each" that would do the iterating for us? Thanks for the explanation, I had no idea it was so expensive. Kas.
participants (3)
-
George Locke -
Kassen -
Robin Haberkorn