Having recently completed the listlib.bbc library (unless somebody finds a bug) an obvious thought which arises is the possibility of writing a similar library to implement Python-style dictionaries: dictlib.bbc.
My initial thinking on this is that it would be very similar to listlib except that rather than using 1-dimensional arrays it would use 2-dimensional arrays as a convenient way of representing key-value pairs (with the second subscript being 0 for the key and 1 for the value).
As Python dictionaries can be nested, it would need to play similar tricks to those used by listlib so that the value can be a number, a string or a child dictionary.
An unresolved question is how the key should be stored. If the underlying data structure is a variant array (as it is in listlib) should the key be stored as a pointer to a string - meaning that searching would be relatively slow - or as a hash for fast searching? And if stored as a hash, how and where would the original (string) key be stored?
Of course this is all dependent on there being demand for such a library. I've not exactly been overwhelmed by requests for pre-release copies of listlib (!) so I suspect that there is little interest in these attempts to make BBC BASIC more competitive with Python.
Proposal for a 'dictlib' library
-
DDRM
- Posts: 20
- Joined: Mon 17 Jun 2024, 08:02
Re: Proposal for a 'dictlib' library
That sounds like an interesting and useful thing to have - though as you say, it's not clear what the demand is! 
I guess an alternative to a 2D array might be a tuple, since your list can already contain fairly arbitrary objects? I don't think "tuple" is something that BBBasic has at the moment, but it should be implementable as a short list, or a structure? That may be slower than using a 2D array, though.
Best wishes,
D
I guess an alternative to a 2D array might be a tuple, since your list can already contain fairly arbitrary objects? I don't think "tuple" is something that BBBasic has at the moment, but it should be implementable as a short list, or a structure? That may be slower than using a 2D array, though.
Best wishes,
D
-
Richard Russell
- Posts: 457
- Joined: Tue 18 Jun 2024, 09:32
Re: Proposal for a 'dictlib' library
Indeed, with my (very) limited understanding of the subject I can't see what the benefit would be of having a distinct 'tuple' type rather than just using a short list. The only significant difference I can see is that tuples are supposed to be unchangeable once created, but there's no way that could be implemented in BBC BASIC anyway.
So, unless there's something I'm missing, I would suggest you simply use a list (via listlib) in BBC BASIC whenever you might use a tuple in Python.
Dictionaries, however, are in my judgement sufficiently different from lists to deserve their own library. Whilst you could create a dictionary from a list (either a simple list, where even-numbered items are keys and odd-numbered items are values, or a list of key+value sub-lists) searching for a specific key would be inefficient.
I do though have a query that you can probably answer. Python (3.7 or later) dictionaries are ordered, but do they need to be? Storing a dictionary in alphabetical order of key would enable much more efficient searching, because a binary-chop could be used. But if a dictionary is sorted by key, it's no longer ordered.
-
Richard Russell
- Posts: 457
- Joined: Tue 18 Jun 2024, 09:32
Re: Proposal for a 'dictlib' library
This article is interesting, but somewhat mind-boggling. If I do implement a dictlib, it won't be that complicated (or efficient).
-
DDRM
- Posts: 20
- Joined: Mon 17 Jun 2024, 08:02
Re: Proposal for a 'dictlib' library
Hi Richard,
They don't HAVE to be ordered (indeed, they weren't (at least not guaranteed to be)) until Python 3.7. Now the order is guaranteed to be the order in which the entries are made - which, as you imply, isn't necessarily the most logical ordering!
One advantage of that is that dictionaries are iterable - you can ask python to step through them one entry at a time - and this way, you can get back the data in the order it was entered, which can be useful in some cases. I suspect, though I don't think I've ever tried, that you can iterate backwards through them too, as you can through other sequential structures like lists.
Since they are implemented as hash tables in python (with O(1) complexity), it is very fast to search for an entry - probably faster than a binary search on average - so the advantages of having an alphabetical ordering (for instance) are not really great in practice. There's a nice description of this here:
https://www.geeksforgeeks.org/python/ar ... s-ordered/
So what does that mean for your implementation? I guess to some extent it depends on how big a dictionary people are likely to make. If you think they will be small, then a simple 2-column array has the advantage that it is intrinsically ordered - you just add new entries at the end - but deletions will leave gaps,which ideally you should close up, with a potentially large overhead as you move everything else up. A double-linked list is a nice option - then you could either order by order of insertion (just add at the end), or maintain it in alphabetical/alphanumeric order, and if you keep a pointer to the "middle" record and the list is ordered you can use binary search approaches, I guess, though that's unusual for linked lists. Alternatively you could keep an index of where A's, B's, C's... etc start (as I think you do for variables now?) - which would be a kind of primitive hash table, I suppose, though not an efficient one.
Best wishes,
D
They don't HAVE to be ordered (indeed, they weren't (at least not guaranteed to be)) until Python 3.7. Now the order is guaranteed to be the order in which the entries are made - which, as you imply, isn't necessarily the most logical ordering!
One advantage of that is that dictionaries are iterable - you can ask python to step through them one entry at a time - and this way, you can get back the data in the order it was entered, which can be useful in some cases. I suspect, though I don't think I've ever tried, that you can iterate backwards through them too, as you can through other sequential structures like lists.
Since they are implemented as hash tables in python (with O(1) complexity), it is very fast to search for an entry - probably faster than a binary search on average - so the advantages of having an alphabetical ordering (for instance) are not really great in practice. There's a nice description of this here:
https://www.geeksforgeeks.org/python/ar ... s-ordered/
So what does that mean for your implementation? I guess to some extent it depends on how big a dictionary people are likely to make. If you think they will be small, then a simple 2-column array has the advantage that it is intrinsically ordered - you just add new entries at the end - but deletions will leave gaps,which ideally you should close up, with a potentially large overhead as you move everything else up. A double-linked list is a nice option - then you could either order by order of insertion (just add at the end), or maintain it in alphabetical/alphanumeric order, and if you keep a pointer to the "middle" record and the list is ordered you can use binary search approaches, I guess, though that's unusual for linked lists. Alternatively you could keep an index of where A's, B's, C's... etc start (as I think you do for variables now?) - which would be a kind of primitive hash table, I suppose, though not an efficient one.
Best wishes,
D