Re: [Tutor] data structures general query
On 26Jun2019 11:01, Mats Wichmann wrote: On 6/26/19 4:40 AM, mhysnm1...@gmail.com wrote: Link lists I would guess be useful in an index for a database? I believe the "classic" use case is memory management - keeping track of chunks of memory. Flipping this, your typical ordered database index (unless the tech has advanced further) is a B+ tree possibly with a doubly linked list threaded through the leaf nodes. So a B+ tree is a sorted tree structure which is maintained in a balanced way so that the depth is pretty consistent across the tree, in turn so that there is not particularly long branch equivalent to have particular keys which are very expensive to look up. Unlike a binary tree a B+ tree has many keys at each node because this makes for efficient storage of the nodes in "blocks", whatever size is useful, and is also makes the tree shallower, making lookups cheaper. The leaf nodes point at the associated records (or possibly just hold keys if there are no records), and the doubly linked list of leaf nodes means you can traverse forwards or backwards from one leaf to the next in either order. Which makes find ranges of keys efficient: "SELECT ... WHERE key >= value ORDER BY key DESC" and its many variants. As has been pointed out by others, the various computer science basic structures are often built up into something different or more complex depending on what your data access pattern will be. It is important to understand the basic structures so that you can reason about their trade offs, and in turn understand more complex related structures. This goes both ways: in design you choose a structure to support what you're going to do. In use, you might choose to approach a problem differently depending on what data structure is used to arrange the data, because some actions are cheap in some structures and expensive in others, so you choose the efficient action where possible. Cheers, Cameron Simpson ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] data structures general query
On 26/06/2019 19:46, Mats Wichmann wrote:
> I forgot to add the snide-comment part of "what are these good for":
>
> (a) binary search trees are excellent for Computer Science professors
> who want to introduce recursion into their classes.
>
> (b) all the classic data structures are candidates for being job
> interview questions ("implement a linked list in Python on the whiteboard")
That's a good point that I intended to make in my response but forgot.
In practice, Python's data structure can mimic these classic data
structures and do so more efficiently than trying to write them
from scratch in Python.
So while they all have Computer Science theoretic pros and cons, in
practice, Python programmers tend to ignore them and use lists, sets,
tuples and dictionaries. And if they need anything more complex
classes or pre-built modules. It's a very rare problem that needs
a traditional data structure in Python.
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] data structures general query
On 6/26/19 11:59 AM, William Ray Wing via Tutor wrote:
> One of the most useful (to me) structures is the double-ended queue ("from
> collections import deque”). It creates a queue that can quickly remove an
> item from one end and add an item to the other. Particularly useful for
> displaying a sliding window into time series data, or a moving track of the
> most recent n observations of a physical measurement.
>
> Bill
Indeed. deques are often implemented using double-linked lists, the
Python version is (though you can't get at the details easily).
I forgot to add the snide-comment part of "what are these good for":
(a) binary search trees are excellent for Computer Science professors
who want to introduce recursion into their classes.
(b) all the classic data structures are candidates for being job
interview questions ("implement a linked list in Python on the whiteboard")
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] data structures general query
> On Jun 26, 2019, at 6:40 AM, mhysnm1...@gmail.com wrote:
>
> All,
>
>
>
> General computer science question for data structures.
>
> When would you use the below structures and why? If you can provide a real
> life example on when they would be used in a program This would be great. I
> am not after code, just explanation.
>
One of the most useful (to me) structures is the double-ended queue ("from
collections import deque”). It creates a queue that can quickly remove an item
from one end and add an item to the other. Particularly useful for displaying
a sliding window into time series data, or a moving track of the most recent n
observations of a physical measurement.
Bill
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] data structures general query
On 6/26/19 4:40 AM, mhysnm1...@gmail.com wrote: > All, > > > > General computer science question for data structures. > > When would you use the below structures and why? If you can provide a real > life example on when they would be used in a program This would be great. I > am not after code, just explanation. > > > > Link lists > > Double link-lists This becomes a question of what kind of data you have and what you need to do with it. Python has "lists", which are what most people think of as arrays - you reference them by index. Lists have fast access: if you know you want the 7th element, you just ask for that. Then if you want to insert a new element following that, the whole array past that point has to move to make room - the grunt work is normally abstracted away by languages that have array datatypes, but it is still happening, same for deleting, so lots of random inserts/deletes (except at the end) are "expensive". In linked lists, insert is cheap. You just take the existing element's "next" field and stick that into the new element's "next" field, and then stick the new element into the existing element's "next" field. However, deleting an still isn't cheap: unless your traversal mechansm saves it on the way to finding a certain element, you have to start from the beginning and walk through to find the previous element, because it's this one which has to have its "next" field changed. A doubly linked list however makes removal trivial - you already have a reference to that element via the "previous" field. For both kinds of linked lists, searching is expensive as you have to walk the chain. The fastest data structure for searching is when the lookup is hashed - this is what the Python dict type allows for, as the keys are hashed as they're stored (leading to the sometimes surprising rule for Python dicts that "key must be hashable"). Other popular data structures are queues and stacks. Note there are also circular lists, which only means the tail hooks back into the head. So your choices depend on what the usage pattern of your data is. The fact that Python doesn't have link lists, neither natively or in the standard library, suggests the designers didn't think they represented a common enough usage pattern for users of the language. > Binary trees > > What other trees are their other than hierarchical tree (file systems) Can let this go without mentioning the Merkle tree, darling of anyone who's ever dabbled in blockchain :) > Link lists I would guess be useful in an index for a database? I believe the "classic" use case is memory management - keeping track of chunks of memory. > Binary trees useful for searches? it's useful for searches if the "is A less than B" comparison is a useful property of the data you are representing. If not, it isn't useful at all as you have no way to construct the tree :) ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] data structures general query
On 26/06/2019 11:40, mhysnm1...@gmail.com wrote: > When would you use the below structures and why? If you can provide a real > life example on when they would be used in a program This would be great. > Link lists Link lists are very flexible and ideal for when you have a varying amount of data and don;t want to reserve space for a maximum amount when you only use a fraction of it. Examples are process lists in an OS. Jobs in a queue (although technically queues are data structures in their own right!) Think of situations where you use a list in everyday life - a shopping list. You add items in an ad-hoc way and don't know in advance how any items you will eventually have. The advantages are that they have a low memory footprint, easy to move things around (including deletion), insertion is quick if adding to the top. Searching not so much. > Double link-lists Same as single linked lists except you can access both ends so a sorted list becomes much faster to search but at the cost of making inserts and moves etc slightly more complex(but only slightly). Real world uses? Hmmm, for me not so many. I'll let somebody else suggest something! > Binary trees Good for searching. Not so good for insertions/moves. Always a danger of the tree becoming unbalanced in which case it tends towards becoming a linked list. Real world use - heirarchical or ordered data arriving at random. Trees are inherently ordered so inserting the data puts it "in order" Code tends to be more complex than for lists though and is often recursive in nature which can be an issue for big trees. > What other trees are their other than hierarchical tree (file systems) Thee are whole families of trees including multi child trees such as yours. AVL trees (if memory serves) try to force the tree to be balanced. Non binary trees need selector functions etc (often hash based). Real world use - database caches, network management heirarchies parsing structures. -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ http://www.amazon.com/author/alan_gauld Follow my photo-blog on Flickr at: http://www.flickr.com/photos/alangauldphotos ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
[Tutor] data structures general query
All, General computer science question for data structures. When would you use the below structures and why? If you can provide a real life example on when they would be used in a program This would be great. I am not after code, just explanation. Link lists Double link-lists Binary trees What other trees are their other than hierarchical tree (file systems) Link lists I would guess be useful in an index for a database? Binary trees useful for searches? Sean ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
