Re: Trees
On Mon, Jan 19, 2015 at 11:52 PM, Devin Jeanpierre wrote: > On Mon, Jan 19, 2015 at 3:08 PM, Steven D'Aprano > wrote: >> Zachary Gilmartin wrote: >> >>> Why aren't there trees in the python standard library? >> >> Possibly because they aren't needed? Under what circumstances would you use >> a tree instead of a list or a dict or combination of both? >> >> That's not a rhetorical question. I am genuinely curious, what task do you >> have that you think must be solved by a tree? > > In general, any time you want to maintain a sorted list or mapping, > balanced search tree structures come in handy. > > Here's an example task: suppose you want to represent a calendar, > where timeslots can be reserved for something. Calendar events are not > allowed to intersect. Maybe because I'm not a computer scientist, I can't immediately see why this is a "Tree" problem and not a "Database" problem. Genuinely interested. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Terry Reedy : > Others have answered as to why other special-purpose > constrained-structure trees have not been added to the stdlib. Ordered O(log n) mappings are not special-purpose data structures. I'd say strings and floats are much more special-purpose than ordered mappings, and yet Python has direct support for those. As I said, I use ordered mappings to implement timers. GvR uses the heapq module for the purpose. The downside of heapq is that canceled timers often flood the heapq structure; in networking you can easily start a thousand timers a second but virtually no timer ever expires. Python's asyncio ignores the problem, but GvR mentioned a periodic "garbage collection" as a potentially effective solution. I tested the garbage collection trick and it did seem very effective. Marko -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tuesday, January 20, 2015 at 11:38:27 AM UTC+5:30, Terry Reedy wrote: > On 1/19/2015 5:06 PM, Zachary Gilmartin wrote: > > Why aren't there trees in the python standard library? > > Sequences nested withing sequences can be regarded as trees, and Python > has these. I regard Lisp as a tree processing languages, as it must be > to manipulate, for example, code with nested structures. Yeah python has trees alright. Heres' some simple tree-code from enum import Enum class TreeTag(Enum): I = 0 # An internal node L = 1 # A leaf node def __repr__(self): return self.name I = TreeTag.I L = TreeTag.L def dfs(t): if t[0] == L: return [t[1]] else: return [t[1]] + dfs(t[2]) + dfs(t[3]) # Converting to generators is trivial = # Example tree # From http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtln8.html t1 = [L, 1] t4 = [I, 4, [L, 3],[L,5]] t2 = [I, 2, t1, t4] t8 = [I, 8, [L, 7], [L, 9]] # Top level tree t = [I, 6, t2, t8] == An REPL session >>> t [I, 6, [I, 2, [L, 1], [I, 4, [L, 3], [L, 5]]], [I, 8, [L, 7], [L, 9]]] >>> dfs(t) [6, 2, 1, 4, 3, 5, 8, 7, 9] >>> t8 [I, 8, [L, 7], [L, 9]] >>> dfs(t8) [8, 7, 9] >>> -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tuesday, January 20, 2015 at 7:03:56 PM UTC+5:30, Rustom Mody wrote: > On Tuesday, January 20, 2015 at 11:38:27 AM UTC+5:30, Terry Reedy wrote: > > On 1/19/2015 5:06 PM, Zachary Gilmartin wrote: > > > Why aren't there trees in the python standard library? > > > > Sequences nested withing sequences can be regarded as trees, and Python > > has these. I regard Lisp as a tree processing languages, as it must be > > to manipulate, for example, code with nested structures. > > Yeah python has trees alright. It may be best to read my example above in this order: 1. See the picture at http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtln8.html 2. Take the python representation of that >>> t [I, 6, [I, 2, [L, 1], [I, 4, [L, 3], [L, 5]]], [I, 8, [L, 7], [L, 9]]] Indent that a bit: [I, 6, [I, 2, [L, 1], [I, 4, [L, 3], [L, 5]]], [I, 8, [L, 7], [L, 9]]] Now compare with the picture above Only catch is you must see it 'lying down' Shouldn't be too hard given that we've all got used to seeing :-) as a smiley :-) -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Mon, Jan 19, 2015 at 6:46 PM, Mark Lawrence wrote: > I don't know if you've seen this http://kmike.ru/python-data-structures/ > but maybe of interest. > I haven't read but also possibly of interest: Data Structures and Algorithms in Python by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser (Wiley, 2013) [1] Python Algorithms: Mastering Basic Algorithms in the Python Language, 2nd Edition by Magnus Lie Hetland (Apress, 2014) [2] [1] http://www.wiley.com/WileyCDA/WileyTitle/productCd-EHEP002510.html [2] http://www.apress.com/9781484200568 -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Rustom Mody : > Yeah python has trees alright. Does Python balance them for you? Marko -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 20/01/2015 05:19, Marko Rauhamaa wrote: Mark Lawrence : On 19/01/2015 22:06, Zachary Gilmartin wrote: Why aren't there trees in the python standard library? Probably because you'd never get agreement as to which specific tree and which specific implementation was the most suitable for inclusion. Most programming languages provide one standard sorted mapping implementation. I'd have thought it would be the standard library and not the language that provided a sorted mapping. Are you also saying that this has to be implemented as a tree, such that this has to be provided by cPython, Jython, IronPython, Pypy and so on and so forth? -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tuesday, January 20, 2015 at 7:46:02 PM UTC+5:30, Marko Rauhamaa wrote: > Rustom Mody : > > > Yeah python has trees alright. > > Does Python balance them for you? No Does python support a menagerie of lists like C - singly linked, doubly linked, with header, without header etc? Or access to machine registers like assembly? And are these differences from C/Assembly in favor or against python? -- https://mail.python.org/mailman/listinfo/python-list
Re: Random ALL CAPS posts on this group
Rick Johnson writes: > No one here would justify a public business refusing to > serve or employ a person based on race, religion, sex, or > otherwise. Depends on what you mean by "or otherwise". > So why would you so easily discriminate against speech? People discriminate amongst prospective employees on the basis of what the say all the time. It's the principle method by which you assess candidates. Freedom of expression is not about requiring others to publish your words. It would be completely impractical - where would it end? Your own slot on prime time TV to rant as you choose? -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody wrote: > from enum import Enum > class TreeTag(Enum): > I = 0 # An internal node > L = 1 # A leaf node > def __repr__(self): return self.name > > I = TreeTag.I > L = TreeTag.L Explicitly tagging nodes as internal or leaves is kind of ugly and also prone to getting out of sync with the reality, which is that a node is a leaf if it doesn't have any other nodes hanging off of it. > def dfs(t): > if t[0] == L: > return [t[1]] > else: > return [t[1]] + dfs(t[2]) + dfs(t[3]) Over the entire tree, this will do O(n) list additions which implies O(n) list *copies*, which is rather inefficient. This would probably be better implemented as a recursive generator. def dfs(t): yield t[0] yield from chain.from_iterable(map(dfs, islice(t, 1, None))) > # Converting to generators is trivial > = :-) -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Marko Rauhamaa writes: > So in my Python software (both at work and at home) needs, I use a > Python AVL tree implementation of my own. My use case is timers. (GvR > uses heapq for the purpose.) Have you benchmarked your version against heapq or even the builtin sorting functions? -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Steven D'Aprano writes: > Possibly because they aren't needed? Under what circumstances would > you use a tree instead of a list or a dict or combination of both? I've sometimes wanted a functional tree in the sense of functional programming. That means the tree structure is immutable and you insert or delete nodes in O(log n) operations, by creating new trees that share almost all their data with the old tree. Once you release the old root, garbage collection frees any nodes that were in the old tree but not the new one. Use case inspired by Haskell's Happstack-store (formerly called MACID): you want a Prevayler-style in-memory key-value database. First idea: all read queries are served by pure in-memory lookups in a Python dict. Write queries update the dict and also append the command to a serial log on disk (one disk write, no seeks). If the system crashes, restart it empty, and play back the log from the beginning to restore the in-memory data. Problem with first idea: the database might be a few thousand entries but take millions of updates, if entries are modified frequently. You don't want to reload the million updates from the beginning. Next idea: dump a snapshot of the dictionary now and then, and then just reload updates starting from the last snapshot. Trouble here is that the dictionary is big enough that writing out the snapshot takes time, and you don't want to lock the whole dict against more updates while the snapshot is writing. If you do this the Java way, welcome to concurrency hell as you make finer and finer grained locks and deal with resulting deadlocks, race conditions, etc. And the dictionary still has to be synchronized to avoid reads simultaneous with updates. MACID solution: use a functional red-black tree instead of a dict. To add or update an entry, make a new tree that replaces the old tree by updating a single pointer. That allows unlimited read concurrency (reading means getting the current tree pointer and navigating the tree that you get: since that tree is immutable you can keep using it while other threads make new trees). Updates are managed by a single thread that can take its time making the new tree and writing the log, and then atomically updating the in-memory root pointer that's shared with other threads. Finally, to take a snapshot, you can just get the current root and write out its contents: since it's immutable you can do that concurrently with anything else (including updates) that might be happening. You just have a small interaction with the update thread to remember where in the log to start reading from in case of a crash and reload. Finding out about this was one of the "wow" moments that made me realize I had to learn Haskell. -- https://mail.python.org/mailman/listinfo/python-list
Student looking for a Scitki-Learn Numpy Tutor with a strong background in data science?
In a Masters for Data Science and need the help using Python/R mainly. Please forward background(education, work) teaching experence in stats, linear algebra, programming (Scikit, Panda, Numpy), timezone, and rates. -- https://mail.python.org/mailman/listinfo/python-list
RE: Random ALL CAPS posts on this group
>-Original Message- >From: Python-list [mailto:python-list- >bounces+crk=godblessthe...@python.org] On Behalf Of Rick Johnson >Sent: Monday, January 19, 2015 8:06 PM >To: python-list@python.org >Subject: Re: Random ALL CAPS posts on this group > >On Monday, January 19, 2015 at 8:16:01 PM UTC-6, Ben Finney wrote: >> Freedom of expression entails an obligation on the state to not quash >> anyone's expression. It does not affect anyone who is not the state; >> it imposes no obligation on the PSF. [...] So a forum such as this can >> block obnoxious spam, and that choice does not impact anyone's freedom >> of expression. > >Ben, i know we have not agreed much in the past, and you may be thinking >that i intend to pick a fight with you here (and i don't), however i >implore you to give more thought to the vital importance of free >expression. > >I believe that free speech is so important, so vital to the existence of >free societies, that it's practice *MUST* extend far beyond the >boundaries of the state's rule, and be fostered by *ANY* group who is in >the public domain. > >No one here would justify a public business refusing to serve or employ >a person based on race, religion, sex, or otherwise. So why would you so >easily discriminate against speech? > >I agree that these spam posts are annoying, but that is not enough of an >excuse to start limiting people's speech in a >*PUBLIC* forum. If python-list were a private group for "members only", >then by all means make up whatever rules you want to. But when shared >publicly, we have a duty to support freedom for *ALL*. We must suffer >the annoyances if we want to enjoy freedom for all. >-- >https://mail.python.org/mailman/listinfo/python-list This is not a public forum; it ia quasi-public forum. It has a structure and understanding of what the topics are. Freedom of speech does not include anytime and anyplace. This is a captive audience and we can't choose what some fool is going to bore us with. Yes we can hit the delete key in one form or another. As much as I don't want to hear our Dear Leader tonight, I will choose to listen. (and then ridicule:<)) But I don't want some psycho Islam Terrorist to stand up and commandeer the TSOTU speech just because he believes that he has the right to drivel on and on. We all agree that that is not the time, place, or topic for the speech. In civilized society, being a captive audience is not really associated with free speech. In civilized society we have a time and a place for a topic, and those that want to hear the pontificator are free to listen. You don't have the right to come in to my house and drivel: it is not the right time or place. Clayton -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Marko Rauhamaa writes: > As I said, I use ordered mappings to implement timers... The downside > of heapq is that canceled timers often flood the heapq structure..., > GvR mentioned a periodic "garbage collection" as a potentially > effective solution. You could look up the "timer wheel" approach used by the Linux kernel and by Erlang. It's less general than an ordered map, but probably faster in practice. https://lkml.org/lkml/2005/10/19/46 Has some info. I think the kernel uses a different method now though. Fwiw, I believe that the Haskell i/o manager uses an ordered map, and it gets monstrous performance: http://haskell.cs.yale.edu/wp-content/uploads/2013/08/hask035-voellmy.pdf Some comments: http://ezyang.tumblr.com/post/62152700458/haskell-mio-a-high-performance-multicore-io -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tuesday, January 20, 2015 at 10:51:13 PM UTC+5:30, Ian wrote: > On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody wrote: > > from enum import Enum > > class TreeTag(Enum): > > I = 0 # An internal node > > L = 1 # A leaf node > > def __repr__(self): return self.name > > > > I = TreeTag.I > > L = TreeTag.L > > Explicitly tagging nodes as internal or leaves is kind of ugly and > also prone to getting out of sync with the reality, which is that a > node is a leaf if it doesn't have any other nodes hanging off of it. Yeah... Just demoing a technique for more variegated trees eg an AST for some toy DSL or some such. Imagine you have 10 types of nodes and one defaults to tagless > > > def dfs(t): > > if t[0] == L: > > return [t[1]] > > else: > > return [t[1]] + dfs(t[2]) + dfs(t[3]) > > Over the entire tree, this will do O(n) list additions which implies > O(n) list *copies*, which is rather inefficient. This would probably > be better implemented as a recursive generator. Yeah > > def dfs(t): > yield t[0] > yield from chain.from_iterable(map(dfs, islice(t, 1, None))) > > > # Converting to generators is trivial > > = > > :-) Less trivial than I thought... Why does this not work? def dfsg(t): if t[0] == L: yield t[1] else: yield from dfsg(t[2]) yield from dfsg(t[3]) -- https://mail.python.org/mailman/listinfo/python-list
pickle and then object changes
Say an object like this exists: class test: a = "" b = "" You pickle it. You change the object definition to have a new field: class test a = "" b = "" c = "" You read the pickled object. Will it load but ignore the new field? That is what I want. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tuesday, January 20, 2015 at 11:46:11 PM UTC+5:30, Rustom Mody wrote: > On Tuesday, January 20, 2015 at 10:51:13 PM UTC+5:30, Ian wrote: > > On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody wrote: > > > # Converting to generators is trivial > > > = > > > > :-) > > Less trivial than I thought... > Why does this not work? > > def dfsg(t): > if t[0] == L: > yield t[1] > else: > yield from dfsg(t[2]) > yield from dfsg(t[3]) Ok got it Forgot the «yield t[1]» before the two yield-from's -- https://mail.python.org/mailman/listinfo/python-list
Re: pickle and then object changes
James Smith wrote:
> Say an object like this exists:
> class test:
> a = ""
> b = ""
>
> You pickle it.
>
> You change the object definition to have a new field:
> class test
> a = ""
> b = ""
> c = ""
>
> You read the pickled object.
> Will it load but ignore the new field?
> That is what I want.
Classes are pickled by name. You are free to replace them with whatever you
want:
>>> class Test:
... a = 1
... b = 2
...
>>> import pickle
>>> p = pickle.dumps(Test)
>>> class Test:
... a = 10
... b = 20
... c = 30
...
>>> P = pickle.loads(p)
>>> P.c
30
>>> P.a
10
>>> P is Test
True
If you introduce a new *instance* attribute that will not magically appear
on unpickling:
>>> class T:
... def __init__(self, a, b):
... self.a = a
... self.b = b
... def __str__(self): return "T(a={0.a}, b={0.b})".format(self)
...
>>> t = T(1, 2)
>>> print(t)
T(a=1, b=2)
>>> p = pickle.dumps(t)
>>> class T:
... def __init__(self, a, b, c):
... self.a = a
... self.b = b
... self.c = c
... def __str__(self): return "T(a={0.a}, b={0.b},
c={0.c})".format(self)
...
>>> print(T(10, 20, 30))
T(a=10, b=20, c=30)
>>> v = pickle.loads(p)
No problem so far as the initializer is not called so that the missing c is
not a problem. But then:
>>> print(v)
Traceback (most recent call last):
File "", line 1, in
File "", line 6, in __str__
AttributeError: 'T' object has no attribute 'c'
One easy fix is to use a class attribute as the fallback:
>>> T.c = "class attribute"
>>> print(v)
T(a=1, b=2, c=class attribute)
But remember not to try this with mutable attributes. When `c` is a list
v.c.append(42)
will affect all instances with a missing `c` instance attribute.
--
https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Exactly. There are over 23,000 different kinds of trees. There's no way you could get all of them to fit in a library, especially a standard one. Instead, we prefer to provide people with the tools they need to grow their own trees. http://caseytrees.org/programs/planting/ctp/ http://www.ncsu.edu/project/treesofstrength/treefact.htm http://en.wikipedia.org/wiki/Tree On 1/19/2015 3:01 PM, Mark Lawrence wrote: On 19/01/2015 22:06, Zachary Gilmartin wrote: Why aren't there trees in the python standard library? Probably because you'd never get agreement as to which specific tree and which specific implementation was the most suitable for inclusion. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
There are similarly many kinds of hash tables. For a given use case (e.g. a sorted dict, or a list with efficient removal, etc.), there's a few data structures that make sense, and a library (even the standard library) doesn't have to expose which one was picked as long as the performance is good. -- Devin On Tue, Jan 20, 2015 at 12:15 PM, Ken Seehart wrote: > Exactly. There are over 23,000 different kinds of trees. There's no way you > could get all of them to fit in a library, especially a standard one. > Instead, we prefer to provide people with the tools they need to grow their > own trees. > > http://caseytrees.org/programs/planting/ctp/ > http://www.ncsu.edu/project/treesofstrength/treefact.htm > http://en.wikipedia.org/wiki/Tree > > On 1/19/2015 3:01 PM, Mark Lawrence wrote: >> >> On 19/01/2015 22:06, Zachary Gilmartin wrote: >>> >>> Why aren't there trees in the python standard library? >>> >> >> Probably because you'd never get agreement as to which specific tree and >> which specific implementation was the most suitable for inclusion. >> > > -- > https://mail.python.org/mailman/listinfo/python-list -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wed, Jan 21, 2015 at 7:15 AM, Ken Seehart wrote: > Exactly. There are over 23,000 different kinds of trees. There's no way you > could get all of them to fit in a library, especially a standard one. > Instead, we prefer to provide people with the tools they need to grow their > own trees. I'm not sure whether you're talking about algorithmic or arboreal trees here... I'm fairly sure the State Library of Victoria contains 23,000 trees, albeit in a slightly modified form. But the State Library is not a standard one. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Paul Rubin : > Marko Rauhamaa writes: >> So in my Python software (both at work and at home) needs, I use a >> Python AVL tree implementation of my own. My use case is timers. (GvR >> uses heapq for the purpose.) > > Have you benchmarked your version against heapq or even the builtin > sorting functions? Yes, I did (as I mentioned in an earlier posting). For the use case I was interested in (timers in a busy server), heapq beefed with the "garbage collection" trick came out about the same as my AVL tree (native module). Marko -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Paul Rubin : > You could look up the "timer wheel" approach used by the Linux kernel > and by Erlang. It's less general than an ordered map, but probably > faster in practice. > > https://lkml.org/lkml/2005/10/19/46 > > Has some info. I think the kernel uses a different method now though. I haven't followed it closely, but I believe the realtime timers use a red-black tree. Marko -- https://mail.python.org/mailman/listinfo/python-list
How to run a python script with functions
Hi I have a file with a python scripts that has many functions in it. To run the script I did the following: 1. $ python (to initiate python, using the python command) 2. >>> import file_name (without .py) 3. >>> file_name.function_name(argument) (to run the function_name with argument (argument) My question is: Is there any other way that I can just use the function name (function_name) without having to use the file_name. part? That is, use only: >>> function_name(argument) ~faizlo -- https://mail.python.org/mailman/listinfo/python-list
Re: How to run a python script with functions
On Tuesday, 20 January 2015 17:11:58 UTC-4, faiz@gmail.com wrote: > Hi > > I have a file with a python scripts that has many functions in it. To run the > script I did the following: > 1. $ python (to initiate python, using the python command) > 2. >>> import file_name (without .py) > 3. >>> file_name.function_name(argument) (to run the function_name with > argument (argument) > > My question is: Is there any other way that I can just use the function name > (function_name) without having to use the file_name. part? That is, use only: > >>> function_name(argument) > from file_name import function1, function2 > ~faizlo -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
In article , rustompm...@gmail.com says... > > Yeah python has trees alright. > > Heres' some simple tree-code Didn't you just demonstrate that Python has no trees and instead you have to implement them yourself (or use a third-party implementation)? I don't know what's the point of all this vain and misleading play with words. Not only most languages don't implement trees in their standard libraries (its no shame, it's no sin), but also it's quite evident that there's a big difference between implementing a data structure yourself through the application of language facilities and seeing that data structure already implemented for you in the standard library. -- https://mail.python.org/mailman/listinfo/python-list
Re: How to run a python script with functions
On Tuesday, January 20, 2015 at 3:22:55 PM UTC-6, André Roberge wrote: > On Tuesday, 20 January 2015 17:11:58 UTC-4, faiz@gmail.com wrote: > > Hi > > > > I have a file with a python scripts that has many functions in it. To run > > the script I did the following: > > 1. $ python (to initiate python, using the python command) > > 2. >>> import file_name (without .py) > > 3. >>> file_name.function_name(argument) (to run the function_name with > > argument (argument) > > > > My question is: Is there any other way that I can just use the function > > name (function_name) without having to use the file_name. part? That is, > > use only: > > >>> function_name(argument) > > > > from file_name import function1, function2 > > > ~faizlo Thank you André -- https://mail.python.org/mailman/listinfo/python-list
Re: Random ALL CAPS posts on this group
On Mon, 19 Jan 2015 16:15:58 -0800, Luke Tomaneng wrote: > Has anyone noticed these? There have been about three of them recently > and they don't seem to have anything to do with Python at all. Does > anyone know if there is a good reason they are here? Abusive spam from idiots. I have a regex that simply ignores any posting with no lower case in the subject. -- Denis McMahon, denismfmcma...@gmail.com -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 20/01/15 01:49, Dan Stromberg wrote: I think probably the most common need for a tree is implementing a cache, That is probably true, at least if you're a squirrel. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 20 January 2015 at 04:21, Dan Stromberg wrote: > On Mon, Jan 19, 2015 at 6:46 PM, Mark Lawrence > wrote: >> >> I don't know if you've seen this http://kmike.ru/python-data-structures/ but >> maybe of interest. > > I've seen it. It's a nice page. > > I attempted to get my treap port in there since it has a Cython > version, but it didn't seem to take. > > I've mostly focused on pure python that runs on CPython 2.x, CPython > 3.x, Pypy, Pypy3 and Jython. http://www.grantjenks.com/docs/sortedcontainers/ SortedContainers is seriously great stuff; faster and lower memory than the Cython variants yet pure Python and more featureful. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wednesday, January 21, 2015 at 3:18:03 AM UTC+5:30, Mario wrote: > rustompmody says... > > > > Yeah python has trees alright. > > > > Heres' some simple tree-code > > Didn't you just demonstrate that Python has no trees and instead you > have to implement them yourself (or use a third-party implementation)? > > I don't know what's the point of all this vain and misleading play with > words. Point. You snipped off Terry's lines which I was replying (rather adding) to: > Sequences nested withing sequences can be regarded as trees, and Python > has these. I regard Lisp as a tree processing languages, as it must be > to manipulate, for example, code with nested structures. To those who are familiar with Lisp this is not new. To others it is likely too dense to be easily comprehensible. > Not only most languages don't implement trees in their standard > libraries (its no shame, it's no sin), but also it's quite evident that > there's a big difference between implementing a data structure yourself > through the application of language facilities and seeing that data > structure already implemented for you in the standard library. Its not a binary but a spectrum. Do the equivalent of "implement yourself with language facilities" in C or Java for the above code and you will see one end of the spectrum. Here's Haskell at the other end of the spectrum: [Renamed the (I)nternal tag to the (B)ranch tag because of I-1 visual clash] === ## The type data Tree t = L t | B t (Tree t) (Tree t) ## The depth first algorithm dfs (L x) = [x] dfs (B x lst rst) = [x] ++ dfs lst ++ dfs rst ## Example tree: t = (B 6 (B 2 (L 1) (B 4 (L 3) (L 5))) (B 8 (L 7) (L 9))) ## Example run *Main> dfs t [6,2,1,4,3,5,8,7,9] == The Haskell is bullseye¹ in capturing the essense of a tree because conceptually a tree of type t is recursive in the sense that it can contain 2 subtrees -- (B x lst rst) -- or its a base case -- L x. The same thing in C needs a mutually recursive data structure: One needs two types – a node *containing* pointers; a pointer *pointing* to node And then go from binary to n-ary trees and the shit hits the ceiling: 4-way mutual recursion: Tree-node, tree-node-pointer; list-node; list-pointer. Completely transparent in Haskell: data Nary t = Tr t [Nary t] Python's not as trivial to get right as Haskell [get one of the subtrees wrong and the error-messages are quite unhelpful] However its way better than C. So there's a spectrum C → Java → Python → Haskell → Tree-DSL² ¹ Well not quite bullseye because a mathematician would prefer a *set* of subtrees where we get at best a *list* ² eg UUAG http://www.andres-loeh.de/AGee.pdf -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Rustom Mody writes: > ## The depth first algorithm > dfs (L x) = [x] > dfs (B x lst rst) = [x] ++ dfs lst ++ dfs rst Cute. I can't resist posting the similar breadth first algorithm: bfs (L x) = [x] bfs (B x lst rst) = bfs lst ++ [x] ++ bfs rst > *Main> dfs t > [6,2,1,4,3,5,8,7,9] *Main> bfs t [1,2,3,4,5,6,7,8,9] > The Haskell is bullseye¹ in capturing the essense of a tree because > conceptually a tree of type t is recursive in the sense that it can contain > 2 subtrees -- (B x lst rst) -- or its a base case -- L x. You might like this discussion of a red-black tree implementation whose datatype makes sure the RB tree invariants are preserved. The data definition is kind of verbose, but with more recent GHC versions it can be made a lot crisper, with datakinds and type-level numeric literals. https://www.reddit.com/r/haskell/comments/ti5il/redblack_trees_in_haskell_using_gadts_existential/ -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wednesday, January 21, 2015 at 7:19:39 AM UTC+5:30, Paul Rubin wrote: > Rustom Mody writes: > > ## The depth first algorithm > > dfs (L x) = [x] > > dfs (B x lst rst) = [x] ++ dfs lst ++ dfs rst > > Cute. I can't resist posting the similar breadth first algorithm: > > bfs (L x) = [x] > bfs (B x lst rst) = bfs lst ++ [x] ++ bfs rst > > > *Main> dfs t > > [6,2,1,4,3,5,8,7,9] > > *Main> bfs t > [1,2,3,4,5,6,7,8,9] Eh?? Thats not bfs. That's inorder traversal The bfs of http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtln8.html is [6,2,8, 1,4,7,9, 3,5] -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 1/20/2015 4:47 PM, Mario wrote: In article , rustompm...@gmail.com says... Yeah python has trees alright. Heres' some simple tree-code Didn't you just demonstrate that Python has no trees and instead you have to implement them yourself (or use a third-party implementation)? I don't know what's the point of all this vain and misleading play with words. It is not play with words. A tree is a recursive - nested - hierachical data structure with the restriction of no cycles or alternate pathways. Python collections whose members are general objects, including collections, can be nested. The resulting structures *are* tree structures, if not more general directed graphs. They are quite commonly used in Python. The common question -- "How do I flatten a list" -- is asking "How to I turn a list from a tree (or DAG, but not a cyclic graph*) into a sequence of leaf objects". The question illustrates what is missing - builtin functions or methods for nested collections. I already suggested that there *might* be a useful addition in this direction. * A Python interpreter needs to take special measures to even display an infinitely recursive list without raising or even segfaulting. Most posted 'flatten' functions do not account for this possibility. >>> l = [1] >>> l.append(l) >>> l [1, [...]] > Not only most languages don't implement trees in their standard libraries Typically, built-in collection type C has members of type M that does not include type C. Therefore a C instance cannot (directly) contain a C instance. The result is that people write a 'design pattern' to overcome the limitation and enable a C to indirectly include a C. Since this limitations does not exist in Python's generalized collections of objects, the pattern is unneeded in Python. -- Terry Jan Reedy -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 21/01/2015 01:22, Joshua Landau wrote: On 20 January 2015 at 04:21, Dan Stromberg wrote: On Mon, Jan 19, 2015 at 6:46 PM, Mark Lawrence wrote: I don't know if you've seen this http://kmike.ru/python-data-structures/ but maybe of interest. I've seen it. It's a nice page. I attempted to get my treap port in there since it has a Cython version, but it didn't seem to take. I've mostly focused on pure python that runs on CPython 2.x, CPython 3.x, Pypy, Pypy3 and Jython. http://www.grantjenks.com/docs/sortedcontainers/ SortedContainers is seriously great stuff; faster and lower memory than the Cython variants yet pure Python and more featureful. Assuming the above and the testimonials are correct how the hell on earth did the author manage it? This is the one thing that *REALLY* annoys me about Python, my mind just doesn't stretch far enough to harness all of the power that's available in it. -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence -- https://mail.python.org/mailman/listinfo/python-list
python traceroute
in the program below i want it to make it work the same way as TRACERT
command . but i am not able to make it work the same way . for which i need
your help thank you
here is the program
#!/usr/bin/python
import socket
import struct
import sys
# We want unbuffered stdout so we can provide live feedback for
# each TTL. You could also use the "-u" flag to Python.
class flushfile(file):
def __init__(self, f):
self.f = f
def write(self, x):
self.f.write(x)
self.f.flush()
sys.stdout = flushfile(sys.stdout)
def main(dest_name):
dest_addr = socket.gethostbyname(dest_name)
port = 33434
max_hops = 10
icmp = socket.getprotobyname('icmp')
udp = socket.getprotobyname('udp')
ttl = 1
while True:
recv_socket = socket.socket(socket.AF_INET, socket.SOCK_RAW, icmp)
send_socket = socket.socket(socket.AF_INET, socket.SOCK_DGRAM, udp)
send_socket.setsockopt(socket.SOL_IP, socket.IP_TTL, ttl)
# Build the GNU timeval struct (seconds, microseconds)
timeout = struct.pack("ll", 5, 0)
# Set the receive timeout so we behave more like regular traceroute
recv_socket.setsockopt(socket.SOL_SOCKET, socket.SO_RCVTIMEO, timeout)
recv_socket.bind(("", port))
sys.stdout.write(" %d " % ttl)
send_socket.sendto("", (dest_name, port))
curr_addr = None
curr_name = None
finished = False
tries = 3
while not finished and tries > 0:
try:
_, curr_addr = recv_socket.recvfrom(512)
finished = True
curr_addr = curr_addr[0]
try:
curr_name = socket.gethostbyaddr(curr_addr)[0]
except socket.error:
curr_name = curr_addr
except socket.error as (errno, errmsg):
tries = tries - 1
sys.stdout.write("* ")
send_socket.close()
recv_socket.close()
if not finished:
pass
if curr_addr is not None:
curr_host = "%s (%s)" % (curr_name, curr_addr)
else:
curr_host = ""
sys.stdout.write("%s\n" % (curr_host))
ttl += 1
if curr_addr == dest_addr or ttl > max_hops:
break
if __name__ == "__main__":
main('google.com')
--
https://mail.python.org/mailman/listinfo/python-list
Re: python traceroute
On Tue, 20 Jan 2015 19:37:26 -0800, Chandrakant Tiwari wrote: > in the program below i want it to make it work the same way as TRACERT > command . but i am not able to make it work the same way . for which i > need your help thank you What is the difference between TRACERT and your Python script? What do you expect your script to do that it doesn't do, or what does it do that it shouldn't do? Please be explicit: # Wrong, don't do this. "Program should work just like TRACERT." # A little better, but still wrong. "Program should work just like TRACERT on operating system Foo version 7 when running this command: tracert -options argument" # Better. "I tried to do where I expected to get which matches this TRACERT command on , but instead I got ." Otherwise, we have to: - guess what results you want - guess what results you got - guess what causes the wrong results - guess what changes you need to make -- Steve -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tue, Jan 20, 2015 at 5:22 PM, Joshua Landau wrote: > On 20 January 2015 at 04:21, Dan Stromberg wrote: >> On Mon, Jan 19, 2015 at 6:46 PM, Mark Lawrence >> wrote: >>> >>> I don't know if you've seen this http://kmike.ru/python-data-structures/ but >>> maybe of interest. >> >> I've seen it. It's a nice page. >> >> I attempted to get my treap port in there since it has a Cython >> version, but it didn't seem to take. >> >> I've mostly focused on pure python that runs on CPython 2.x, CPython >> 3.x, Pypy, Pypy3 and Jython. > > http://www.grantjenks.com/docs/sortedcontainers/ > > SortedContainers is seriously great stuff; faster and lower memory > than the Cython variants yet pure Python and more featureful. It has an interesting comparison. I find myself wishing the graphs were higher resolution (the lines are frequently overlapping to the point that I cannot read the graphs), and that the maximum number of elements was greater than 10**6. Some of the timings end up taking less than a second even at the larger sizes. -- https://mail.python.org/mailman/listinfo/python-list
Re: Concerning Dictionaries and += in Python 2.x
On Mon, 19 Jan 2015 16:12:57 -0800, Luke Tomaneng wrote: > I have been having a bit of trouble with the things mentioned in the > title. I've uploaded a slightly different approach to your code at: http://www.sined.co.uk/tmp/shop.py.txt -- Denis McMahon, denismfmcma...@gmail.com -- https://mail.python.org/mailman/listinfo/python-list
Re: python traceroute
On Tue, 20 Jan 2015 19:37:26 -0800, Chandrakant Tiwari wrote: > in the program below i want it to make it work the same way as TRACERT > command. As an observation, you're re-inventing a wheel that already works perfectly well, in that any failings of tracert tend to be more down to the way routers are configured to handle icmp than the tracert application itself. Unless you're doing this purely as an exercise in socket programming with python, it might be better to find a new problem to solve. -- Denis McMahon, denismfmcma...@gmail.com -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tue, Jan 20, 2015 at 1:45 AM, Marko Rauhamaa wrote: > Terry Reedy : > > > Others have answered as to why other special-purpose > > constrained-structure trees have not been added to the stdlib. > > Ordered O(log n) mappings are not special-purpose data structures. I'd > say strings and floats are much more special-purpose than ordered > mappings, and yet Python has direct support for those. > Your anecdote is strong, sir. However, I use strings thousands of times, floats maybe a hundred of times, and order mappings a few times. My anecdote counters yours. A tree structure is special purpose because there is a lot of options with different characteristics that make certain implementations ideal in some cases and not in others. A float is a float, there's a standard (IEEE 754?), its not special at all. A string, I suppose, could be special, but that's a pretty nonsense view of the world since what most people use strings commonly. I'm not arguing against including a tree, but I have no advice on which one, and the one-- one!-- time I've needed a tree I got one off pypi. Not everything needs to be in the stdlib. But to call strings and floats special purpose is really a silly argument to make. -- https://mail.python.org/mailman/listinfo/python-list
