Re: testing array of logicals

[Janto Dreijer]

John Henry wrote:
> Simon Forman wrote:
> > >
> > > False not in logflags
> > >
> >
> > Or, if your values aren't already bools
> >
> > False not in (bool(n) for n in logflags)
>
> Very intriguing use of "not in"...

Is there a reason why you didn't write
 True in (bool(n) for n in logflags)

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: testing array of logicals

[Janto Dreijer]

Janto Dreijer wrote:
> John Henry wrote:
> > Simon Forman wrote:
> > > >
> > > > False not in logflags
> > > >
> > >
> > > Or, if your values aren't already bools
> > >
> > > False not in (bool(n) for n in logflags)
> >
> > Very intriguing use of "not in"...
>
> Is there a reason why you didn't write
>  True in (bool(n) for n in logflags)

 doh! Never mind.

-- 
http://mail.python.org/mailman/listinfo/python-list

embedding console in wxpython app

[Janto Dreijer]

I'm writing a Linux filemanager using wxPython. I'd like to embed a
bash console inside it. I have found the Logilab pyqonsole
(http://www.logilab.org/projects/pyqonsole), but it uses PyQT.

Does anyone know how to do this from wx?
Is it possible to embed a PyQT widget inside wxPython?

Thanks!
Janto

-- 
http://mail.python.org/mailman/listinfo/python-list

ntp in python

[Janto Dreijer]

I want to measure the packet delivery delays over various network
links. For this I need to synchronise the times of the sender and
receiver, either against NTP or eachother.

Unfortunately I won't necessarily have root priviledges to change the
PCs' clocks. So I'm looking for a way I can determine the offset and
simply correct my measurements from my Python code.

I doubt something like
http://www.nightsong.com/phr/python/setclock.py
would give me a resolution of less than 10ms - which is what I want.

Any Python module out there that uses a more sophisticated method?

btw I can do round-trip delivery and avoid the whole clock-mismatch
issue, but this would lose information on the network's asymmetry -
which would be really nice to have.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: ntp in python

[Janto Dreijer]

Jeremy Sanders wrote:
> Janto Dreijer wrote:
>
> > I want to measure the packet delivery delays over various network
> > links. For this I need to synchronise the times of the sender and
> > receiver, either against NTP or eachother.
>
> Couldn't you just use NTP itself to get the delivery delay? You can read the
> delay out from the ntpdc console using dmpeers, or lopeers in ntpq. You
> could have two peers either side of the link and measure the delay from
> NTP.
>
> You may also be able to query remote ntp servers to get their delays to
> their peers.

Unfortunately I don't think that would work for me. I need the delay of
a stream of packets. Not just a single delay number. More specifically:
I'm testing RTP (VoIP) packet speeds and would like to predict lag
(ignoring jitter...separate measurement).

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: ntp in python

[Janto Dreijer]

Janto Dreijer wrote:
> Jeremy Sanders wrote:
> > Janto Dreijer wrote:
> >
> > > I want to measure the packet delivery delays over various network
> > > links. For this I need to synchronise the times of the sender and
> > > receiver, either against NTP or eachother.
> >
> > Couldn't you just use NTP itself to get the delivery delay? You can read the
> > delay out from the ntpdc console using dmpeers, or lopeers in ntpq. You
> > could have two peers either side of the link and measure the delay from
> > NTP.
> >
> > You may also be able to query remote ntp servers to get their delays to
> > their peers.
>
> Unfortunately I don't think that would work for me. I need the delay of
> a stream of packets. Not just a single delay number. More specifically:
> I'm testing RTP (VoIP) packet speeds and would like to predict lag
> (ignoring jitter...separate measurement).

(replying to myself here)

More importantly, it looks like some of the network firewalls I'll be
testing though block the ports typically used by NTP...I hope I'm
wrong.

Maybe I'd be better off writing my own implementation that synchronises
the two pc clocks. Any hints? :-)

-- 
http://mail.python.org/mailman/listinfo/python-list

UDP packets to PC behind NAT

[Janto Dreijer]

This is probably more of a networking question than a Python one, but
it would be nice to know if someone has done this with Python's socket
module. And besides one usually gets more information from c.l.py than
anywhere else :)

I have a server with a static "public" IP and a client behind a NAT. I
would like to send UDP packets from the server to the client. So what I
need to do is open up a "hole" in the NAT and let the server know the
target IP and port of the client where it can send its packets.

Now I have read somewhere that you can have TCP and UDP running on the
same port. Not sure if this is true. Would it be a reasonable solution
to initiate a TCP connection from the client to the server and somehow
(?) let the server figure out how the client is connecting? And then
send UDP to client over the same (IP, port)?

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: UDP packets to PC behind NAT

[Janto Dreijer]

Awesome! I haven't tested it on the actual server but I think it works.
Thanks!
I prefer a TCP connection solution and will post one if it works.

server.py

from socket import *
print "listening"
UDPSock = socket(AF_INET, SOCK_DGRAM)
UDPSock.bind(("localhost", 1234)) # visibility to outside world
payload, addr = UDPSock.recvfrom(1024)
print "message from %s: %s" % (`addr`, payload)
UDPSock = socket(AF_INET, SOCK_DGRAM) # open UDP socket
result = UDPSock.sendto("your public address is %s" % `addr`, addr)

client.py
=
from socket import *
UDPSock = socket(AF_INET, SOCK_DGRAM) # open UDP socket
result = UDPSock.sendto("what's my public address?", ("localhost",
1234))
payload, addr = UDPSock.recvfrom(1024)
print payload

results:

listening
message from ('127.0.0.1', 32787): what's my public address?

your public address is ('127.0.0.1', 32787)

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: UDP packets to PC behind NAT

[Janto Dreijer]

Oops. That second UDPSock = socket(...) in the server.py shouldn't be
there.

Janto Dreijer wrote:
> Awesome! I haven't tested it on the actual server but I think it works.
> Thanks!
> I prefer a TCP connection solution and will post one if it works.
>
> server.py
> 
> from socket import *
> print "listening"
> UDPSock = socket(AF_INET, SOCK_DGRAM)
> UDPSock.bind(("localhost", 1234)) # visibility to outside world
> payload, addr = UDPSock.recvfrom(1024)
> print "message from %s: %s" % (`addr`, payload)
> UDPSock = socket(AF_INET, SOCK_DGRAM) # open UDP socket
> result = UDPSock.sendto("your public address is %s" % `addr`, addr)
>
> client.py
> =
> from socket import *
> UDPSock = socket(AF_INET, SOCK_DGRAM) # open UDP socket
> result = UDPSock.sendto("what's my public address?", ("localhost",
> 1234))
> payload, addr = UDPSock.recvfrom(1024)
> print payload
>
> results:
> 
> listening
> message from ('127.0.0.1', 32787): what's my public address?
> 
> your public address is ('127.0.0.1', 32787)

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: UDP packets to PC behind NAT

[Janto Dreijer]

Grant Edwards wrote:
> On 2006-09-15, Christophe <[EMAIL PROTECTED]> wrote:
>
> > Initiate an UDP connection from the client to the server and
> > have the server send back the UDP packets to the address you
> > get in the "recvfrom" result.
>
> There's no such thing as a "UDP connection", so I don't
> understand what you're suggesting.

I think he means "connection" as in "associated ip/port". Which
actually does work, as I've posted.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: UDP packets to PC behind NAT

[Janto Dreijer]

Grant Edwards wrote:
> On 2006-09-15, Janto Dreijer <[EMAIL PROTECTED]> wrote:
...
> > Would it be a reasonable solution to initiate a TCP connection
> > from the client to the server and somehow (?) let the server
> > figure out how the client is connecting? And then send UDP to
> > client over the same (IP, port)?
>
> I doubt that will work unless the firewall has been
> specifically designed to recognize that pattern of activity and
> allow the incoming UDP packets.  I don't think most firewall
> have default rules that allow UDP packets to tunnel back along
> a TCP connection.

Thanks for the info!

I think you may be right. I had to configure the local firewall to
allow all connections from the server. Which kinda defeats the purpose.
If you have control over the NAT why not just assign a dedicated port?

There might still be value in this approach, however. Even though I
have control over the NAT I have multiple clients that might need to
create these connections. I would need to map ports to be able to
handle simultaneous connections.

It's Friday afternoon over here, so I may be wrong...

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: UDP packets to PC behind NAT

[Janto Dreijer]

Steve Holden wrote:
> Note that TCP and UDP port spaces are disjoint, so there's no way for
> TCP and UDP to use "the same port" - they can, however, use the same
> port number. Basically the TCP and UDP spaces have nothing to do with
> each other.
>
> Most dynamic NAT gateways will respond to an outgoing UDP datagram by
> mapping the internal client's UDP port to a UDP port on the NAT
> gateway's external interface, and setting a converse mapping that will
> allow the server to respond, even though technically there isn't a
> "connection". The NAT table entries will typically be timed out after a
> short period of non-use.

So are you saying one can't use TCP to punch a hole for UDP?

-- 
http://mail.python.org/mailman/listinfo/python-list

Fast kNN from python

[Janto Dreijer]

Hi!

I am looking for a Python implementation or bindings to a library that
can quickly find k-Nearest Neighbors given an arbitrary distance
metric between objects. Specifically, I have an "edit distance"
between objects that is written in Python.

I haven't looked at the methods in detail but I think I'm looking for
one of the data structures listed on http://en.wikipedia.org/wiki/Metric_trees
(i.e. vp-trees, cover trees, m-trees or bk trees). But I might be
wrong. An approximate kNN would also work.

If there doesn't exist such an implementation yet, any advice on a
library I can wrap myself would also be appreciated.

Thanks!
Janto

PS Before anyone suggests it, I can't use the library at
http://www.cs.umd.edu/~mount/ANN/ as it assumes Minkowski distance
functions.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Fast kNN from python

[Janto Dreijer]

On Aug 14, 3:11 pm, Tim Churches <[EMAIL PROTECTED]> wrote:
> Janto Dreijer wrote:
> > I am looking for a Python implementation or bindings to a library that
> > can quickly find k-Nearest Neighbors given an arbitrary distance
> > metric between objects. Specifically, I have an "edit distance"
> > between objects that is written in Python.
>
> Orange? Seehttp://www.ailab.si/orange/- not sure about speed, but
> quite a few parts of it are written in C, and it does kNN.
>
> Tim C

Thanks, but I'm actually thinking of "fast" as in computer science
terms. e.g. O(log(n)) lookup time. I'll probably have tens of
thousands of objects to search and the distance calculation is
relatively slow.

>From the documentation it looks like Orange does a brute force search
for the nearest k items.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Fast kNN from python

[Janto Dreijer]

On Aug 14, 8:44 pm, Miki <[EMAIL PROTECTED]> wrote:
> Hello,
>
> > I am looking for a Python implementation or bindings to a library that
> > can quickly find k-Nearest Neighbors given an arbitrary distance
> > metric between objects. Specifically, I have an "edit distance"
> > between objects that is written in Python.
>
> First Google search for "k-Nearest Neighbors python", 
> yieldedhttp://people.revoledu.com/kardi/tutorial/KNN/resources.html which
> pointed tohttp://biopython.org/DIST/docs/api/public/Bio.kNN-module.html
>
> HTH,
> --
> Miki <[EMAIL PROTECTED]>http://pythonwise.blogspot.com

Thanks. Indeed, I did see that page. Unfortunately biopython's knn
does a brute force search for the nearest k and is therefore way too
slow.

Janto

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Fast kNN from python

[Janto Dreijer]

On Aug 14, 9:27 pm, Sean Davis <[EMAIL PROTECTED]> wrote:
> On Aug 14, 6:16 am, Janto Dreijer <[EMAIL PROTECTED]> wrote:
>
>
>
> > Hi!
>
> > I am looking for a Python implementation or bindings to a library that
> > can quickly find k-Nearest Neighbors given an arbitrary distance
> > metric between objects. Specifically, I have an "edit distance"
> > between objects that is written in Python.
>
> > I haven't looked at the methods in detail but I think I'm looking for
> > one of the data structures listed 
> > onhttp://en.wikipedia.org/wiki/Metric_trees
> > (i.e. vp-trees, cover trees, m-trees or bk trees). But I might be
> > wrong. An approximatekNNwould also work.
>
> > If there doesn't exist such an implementation yet, any advice on a
> > library I can wrap myself would also be appreciated.
>
> > Thanks!
> > Janto
>
> Have you looked at using Rpy and R?  There are probably severalknn
> implementations that then become accessible to you (although I haven't
> checked recently).
>
> Sean

Interesting. I have not looked at that. I can't really find an R
package that does what I want, so any suggestions are appreciated.

Janto

-- 
http://mail.python.org/mailman/listinfo/python-list

multiple content-types break cgi.py

[Janto Dreijer]

Hi!

The Nokia Java SDK allows one to define multiple content-types in a
single HTTP header field. I'm not sure if it's standard, but it's
happening from some Java-enabled phones.

This breaks the FieldStorage class in cgi.py by not causing
self.read_urlencoded() to be called at object init. Specifically when
one gets a type value like 'text/plain, application/x-www-form-
urlencoded'.

Hacking one of the lines from:
if ctype == 'application/x-www-form-urlencoded':
self.read_urlencoded()
to
if 'application/x-www-form-urlencoded' in [s.strip() for s in
ctype.split(",")]:
self.read_urlencoded()
makes it work as expected.

The only reference to this "bug" I can find dates back to 1999:
http://tinyurl.com/3ahc3r

Regards
Janto

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: multiple content-types break cgi.py

[Janto Dreijer]

On Mar 4, 12:29 pm, Jon Ribbens <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>, Janto Dreijer wrote:
> > The Nokia Java SDK allows one to define multiple content-types in a
> > single HTTP header field. I'm not sure if it's standard, but it's
> > happening from some Java-enabled phones.
>
> > The only reference to this "bug" I can find dates back to 1999:
> >http://tinyurl.com/3ahc3r
>
> It's not a bug - sending multiple content-types is just totally broken.
> What would such a header even be supposed to mean? It's like saying
> "this is an apple orange".

Hmmm. Thanks! I suspected as much.

Rough inspection suggests that calling
connection.setRequestProperty("Content-Type", "application/x-www-
form-urlencoded");
on the Nokia 6230 would actually cause the value to be *appended* and
not set.

Yuck! It looks like I'm going to have to keep a modified copy of
cgi.py if I want to support the phone. Or hack something on the Java
side.

Janto

-- 
http://mail.python.org/mailman/listinfo/python-list

threading and iterator crashing interpreter

[Janto Dreijer]

I have been having problems with the Python 2.4 and 2.5 interpreters
on both Linux and Windows crashing on me. Unfortunately it's rather
complex code and difficult to pin down the source.

So I've been trying to reduce the code. In the process it's started to
crash in different ways. I'm not sure if any of it is related. The
following is only crashing Python 2.5 (r25:51908, Sep 19 2006,
09:52:17) [MSC v.1310 32 bit (Intel)] on win32 in two different(?)
ways.



Using the login1() function will throw a bunch of exceptions the most
interesting of which is:

Exception in thread Thread-34:
Traceback (most recent call last):
  File "C:\Python25\lib\threading.py", line 460, in __bootstrap
self.run()
  File "C:\Python25\lib\threading.py", line 440, in run
self.__target(*self.__args, **self.__kwargs)
  File "Copy of scratchpad.py", line 20, in login1
random.choice(System.sessions).session_iter.next()
RuntimeError: instance.__dict__ not accessible in restricted mode

I'm not concerned with the Python exceptions, but about 40% of the
time it will launch the Visual Studio JIT Debugger with an "Unhandled
exception at 0x1e03973e in pythonw.exe: 0xC005: Access violation
reading location 0x2024."

=

Using the login2() function will sometimes (about 30% of the time)
cause the following to be printed out:
"""
Unhandled exception in thread started by
Error in sys.excepthook:

Original exception was:
"""

===

Here's the code. Will it be easier to find the problem if I tried
compiling Python myself?

from threading import Thread
import random

def session_iter(f):
# second interpreter
while 1:
yield len(f.__dict__)

class Session:
def __init__(self):
self.session_iter = session_iter(self)

class System:
sessions = []

def login1():
# first interpreter
System.sessions.append(Session())
while 1:
random.choice(System.sessions).session_iter.next()

def login2():
# first interpreter
System.sessions.append(Session())
System.sessions.pop().session_iter.next()

# main interpreter
threads = [Thread(target=login1) for t in range(2000)]
for thread in threads:
thread.start()

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: threading and iterator crashing interpreter

[Janto Dreijer]

On Mar 11, 2:20 pm, Bjoern Schliessmann  wrote:
> Janto Dreijer wrote:
> > I have been having problems with the Python 2.4 and 2.5
> > interpreters on both Linux and Windows crashing on me.
>
> I don't understand -- does the interpreter crash (segfault) or is
> just your program terminating due to unhandled exceptions?

Segfault.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: threading and iterator crashing interpreter

[Janto Dreijer]

On Mar 11, 1:46 pm, "Gabriel Genellina" <[EMAIL PROTECTED]>
wrote:
> En Sun, 11 Mar 2007 07:32:04 -0300, Janto Dreijer <[EMAIL PROTECTED]>
> escribió:
>
>
>
> > I have been having problems with the Python 2.4 and 2.5 interpreters
> > on both Linux and Windows crashing on me. Unfortunately it's rather
> > complex code and difficult to pin down the source.
>
> > So I've been trying to reduce the code. In the process it's started to
> > crash in different ways. I'm not sure if any of it is related. The
> > following is only crashing Python 2.5 (r25:51908, Sep 19 2006,
> > 09:52:17) [MSC v.1310 32 bit (Intel)] on win32 in two different(?)
> > ways.
>
> > 
>
> > Using the login1() function will throw a bunch of exceptions the most
> > interesting of which is:
>
> > Exception in thread Thread-34:
> > Traceback (most recent call last):
> >   File "C:\Python25\lib\threading.py", line 460, in __bootstrap
> > self.run()
> >   File "C:\Python25\lib\threading.py", line 440, in run
> > self.__target(*self.__args, **self.__kwargs)
> >   File "Copy of scratchpad.py", line 20, in login1
> > random.choice(System.sessions).session_iter.next()
> > RuntimeError: instance.__dict__ not accessible in restricted mode
>
>  From the error message, you appear to be using some form of restricted
> execution - RExec or similar. I didn't try that way, but using the normal
> mode, I got this different exception instead (using login1):
>
> Exception in thread Thread-85:
> Traceback (most recent call last):
>File "c:\apps\python\lib\threading.py", line 460, in __bootstrap
>  self.run()
>File "c:\apps\python\lib\threading.py", line 440, in run
>  self.__target(*self.__args, **self.__kwargs)
>File "crash.py", line 20, in login1
>  random.choice(System.sessions).session_iter.next()
> ValueError: generator already executing
>
> It appears to indicate that you must syncronize the generators.
> Adding a Lock object to Session appears to work OK:
>
> class Session:
>  def __init__(self):
>  self.lock = Lock()
>  self.session_iter = session_iter(self)
>
> def login1():
>  # first interpreter
>  System.sessions.append(Session())
>  while 1:
>  session = random.choice(System.sessions)
>  session.lock.acquire()
>  session.session_iter.next()
>  session.lock.release()
>
> Your login2 version does not generate any error on my PC.
>
> --
> Gabriel Genellina

As far as I can tell I'm not running it from restricted mode
explicitly.

The reason I'm doing the random.choice() is so I don't have a handle
("session" in this case) that would prevent it from being garbage
collected. I am not bothered by the Python-level Exceptions. I am
bothered by the interpreter throwing a segfault. What I suspect is
happening is the Session object is deallocated, while it still has a
reference from within the iterator.

It's quite difficult to reproduce these bugs consistently. You might
need to run it a few times.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: threading and iterator crashing interpreter

[Janto Dreijer]

On Mar 11, 3:27 pm, "Gabriel Genellina" <[EMAIL PROTECTED]>
wrote:
> En Sun, 11 Mar 2007 09:47:34 -0300, Janto Dreijer <[EMAIL PROTECTED]>
> escribió:
>
> > As far as I can tell I'm not running it from restricted mode
> > explicitly.
>
> This error is rather strange then:
>
> > > RuntimeError: instance.__dict__ not accessible in restricted mode
>
> "restricted mode" means that the current builtins are not the standard
> builtins.

Googling says "Some googling suggests that this error is a hint that a
Python object created in one subinterpreter is being used in a
different subinterpreter."

> > The reason I'm doing the random.choice() is so I don't have a handle
> > ("session" in this case) that would prevent it from being garbage
> > collected. I am not bothered by the Python-level Exceptions. I am
> > bothered by the interpreter throwing a segfault. What I suspect is
> > happening is the Session object is deallocated, while it still has a
> > reference from within the iterator.
>
> But on your code Session objects are never deleted; they stay inside
> System.sessions. Having an extra reference (the session variable) doesnt
> matter.

Hmmm. You're right.

> > It's quite difficult to reproduce these bugs consistently. You might
> > need to run it a few times.
>
> At least, the problem of using the same generator from different threads
> still remains, if you don't use my modified code. In general, when using
> multiple threads you always need some way to syncronize access to shared
> objects. You are lucky with Sessions because append is an atomic operation
> on lists; for more information see  
> http://effbot.org/pyfaq/what-kinds-of-global-value-mutation-are-threa...

Again you're right. But even putting a try-except:return around the
random.choice still manages to break the interpreter. I'm not looking
for any meaningful output really. I just want it not to break.

Like I said, this is just watered down code to try and isolate the
problem.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Reverse zip() ?

[Janto Dreijer]

I'd like to point out that since your where thinking in terms of
matplotlib, you might actually find numpy's own transpose useful,
instead of using zip(*seq) :)

untested:

t = linspace(0,2*pi*3)
seq = asarray(zip(t, sin(t)))

t, y = seq.T # or seq.transpose() or numpy.transpose(seq)
pylab.plot(t,y)

Regards
Janto

Andreas Waldenburger wrote:
> On Wed, 3 Dec 2008 02:11:51 -0800 (PST) alex23 <[EMAIL PROTECTED]>
> wrote:
>
> > On Dec 3, 6:51 pm, Andreas Waldenburger <[EMAIL PROTECTED]> wrote:
> > > On Tue, 02 Dec 2008 18:16:13 -0800 Bryan Olson
> > > > zip as its own inverse might be even easier to comprehend if we
> > > > call zip by its more traditional name, "transpose".
> > >
> > > Sounds like a Py4k change to me.
> >
> > Nah, just add the following to your sitecustomize.py:
> >
> >transpose = zip
> >
> > :)
>
> Gaaahh!
>
> :)
> /W
>
> --
> My real email address is constructed by swapping the domain with the
> recipient (local part).
--
http://mail.python.org/mailman/listinfo/python-list

eval modifies passed dict

[Janto Dreijer]

It seems eval is modifying the passed in locals/globals. This is
behaviour I did not expect and is really messing up my web.py app.

Python 2.5.1 (r251:54863, Mar  7 2008, 04:10:12)
[GCC 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> d = dict(a=1)
>>> d.keys()
['a']
>>> eval("a", d)
1
>>> d.keys()
['a', '__builtins__']

That can't be right.

Regards
Janto
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: eval modifies passed dict

[Janto Dreijer]

On Apr 14, 5:48 pm, [EMAIL PROTECTED] wrote:
> On 14 avr, 17:23, Janto Dreijer <[EMAIL PROTECTED]> wrote:
>
> > It seems eval is modifying the passed in locals/globals. This is
> > behaviour I did not expect and is really messing up my web.py app.
>
> > Python 2.5.1 (r251:54863, Mar  7 2008, 04:10:12)
> > [GCC 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)] on linux2
> > Type "help", "copyright", "credits" or "license" for more information.>>> d 
> > = dict(a=1)
> > >>> d.keys()
> > ['a']
> > >>> eval("a", d)
> > 1
> > >>> d.keys()
>
> > ['a', '__builtins__']
>
> > That can't be right.
>
> From the documentation of eval[1]
> "If the globals dictionary is present and lacks '__builtins__', the
> current globals are copied into globals before expression is parsed."
>
> [1]http://docs.python.org/lib/built-in-funcs.html

Thanks!

I'll take it to the webpy group as one of their methods unexpectedly
propagates this effect.

Janto
-- 
http://mail.python.org/mailman/listinfo/python-list

efficient running median

[Janto Dreijer]

I'm looking for code that will calculate the running median of a
sequence, efficiently. (I'm trying to subtract the running median from
a signal to correct for gradual drift).

My naive attempt (taking the median of a sliding window) is
unfortunately too slow as my sliding windows are quite large (~1k) and
so are my sequences (~50k). On my PC it takes about 18 seconds per
sequence. 17 of those seconds is spent in sorting the sliding windows.

I've googled around and it looks like there are some recent journal
articles on it, but no code. Any suggestions?

Thanks
Janto
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: efficient running median

[Janto Dreijer]

On Oct 13, 9:59 pm, Paul Rubin  wrote:
> sturlamolden  writes:
> > > The obvious way to compute a running median involves a tree structure
> > > so you can quickly insert and delete elements, and find the median.
> > > That would be asymtotically O(n log n) but messy to implement.
>
> > QuickSelect will find the median in O(log n) time.
>
> That makes no sense, you can't even examine the input in O(log n) time.

True. I think he means O(n).
I've tried wrapping the lesser-known nth_element function from the C++
STL (http://www.cppreference.com/wiki/stl/algorithm/nth_element).
Unfortunately it seems the conversion to std::vector is quite
slow...I'll have a look again. Will probably have to rewrite my whole
median_filter function in C++ to avoid unnecessary conversions.

> Anyway, the problem isn't to find the median of n elements.  It's to
> find n different medians of n different sets.  You might be able to
> get close to linear time though, depending on how the data acts.

Yes, that's what I've been hoping for. If I want it raaally fast
I'll have to figure out how to do that.

Thanks
Janto
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: efficient running median

[Janto Dreijer]

On Oct 13, 8:29 pm, Dale Dalrymple  wrote:
> On Oct 13, 8:22 am, Janto Dreijer  wrote:
>
> > I'm looking for code that will calculate the running median of a
> > sequence, efficiently. (I'm trying to subtract the running median from
> > a signal to correct for gradual drift).
> > ...
> >  Any suggestions?
>
> For a reference try:
>
>  Comparison of algorithms for standard median filtering
> Juhola, M.   Katajainen, J.   Raita, T.
> Signal Processing, IEEE Transactions on
> Jan. 1991, Volume: 39 , Issue: 1, page(s): 204 - 208
> Abstract
>
> An algorithm I have used comes from:
>
>  On computation of the running median
> Astola, J.T.   Campbell, T.G.
> Acoustics, Speech and Signal Processing, IEEE Transactions on
> Apr 1989, Volume: 37,  Issue: 4, page(s): 572-574
>
> This is a dual heap approach. No code though. There are some obvious
> (yeah, right) errors in their pseudo-code.
>
> The point of the dual heap algorithm (loosely put) is to reduce the
> computation to slide the window 1 element to be proportional to 2
> bubble sorts of log window size instead of a window size sort.
>
> Good luck.
>
> Dale B. Dalrymple

Thanks. I'll have a look.

I found a PDF by Soumya D. Mohanty entitled "Efficient Algorithm for
computing a Running Median" (2003) by Googling. It has code snippets
at the end, but it's not going to be a simple cut-and-paste job. It
will take some work figuring out the missing parts.

Regards
Janto
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: efficient running median

[Janto Dreijer]

On Oct 13, 6:12 pm, Peter Otten <__pete...@web.de> wrote:
> Janto Dreijer wrote:
> > I'm looking for code that will calculate the running median of a
> > sequence, efficiently. (I'm trying to subtract the running median from
> > a signal to correct for gradual drift).
>
> > My naive attempt (taking the median of a sliding window) is
> > unfortunately too slow as my sliding windows are quite large (~1k) and
> > so are my sequences (~50k). On my PC it takes about 18 seconds per
> > sequence. 17 of those seconds is spent in sorting the sliding windows.
>
> > I've googled around and it looks like there are some recent journal
> > articles on it, but no code. Any suggestions?
>
> If you aren't using numpy, try that. Showing your code might also be a good
> idea...
>
> Peter

I placed the test code and its output here:
http://bitbucket.org/janto/snippets/src/tip/running_median.py

I also have a version that uses numpy. On random data it seems to be
about twice as fast as the pure python one. It spends half the time
sorting and the other half converting the windows from python lists to
numpy arrays.
If the data is already sorted, the version using python's builtin sort
outperforms the numpy convert-and-sort by about 5 times. Strangely
satisfying :)

I'm hoping to find a trick to do better than scipy.signal.medfilt.
Looking at its code (PyArray_OrderFilterND in
http://svn.scipy.org/svn/scipy/trunk/scipy/signal/sigtoolsmodule.c)
there may be hope. It looks like they're sorting the entire window
instead of doing a QuickSelect (which I could do with STL's
nth_element).

Janto
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: efficient running median

[Janto Dreijer]

On Oct 13, 6:33 pm, Paul Rubin <http://phr...@nospam.invalid> wrote:
> Janto Dreijer  writes:
> > I'm looking for code that will calculate the running median of a
> > sequence, efficiently. (I'm trying to subtract the running median from
> > a signal to correct for gradual drift).
>
> Is that a known and valid technique of correcting for drift?  Maybe
> what you really want is a high-pass filter, to remove very low
> frequency components (drift) from the signal.  You can do that with
> standard digital filters.  Using something depending on ordering
> within the samples (i.e. the median) seems weird to me, but I'm no
> expert.

Well, I don't have a lot of theoretical reasoning behind wanting to
use a median filter. I have some experience applying it to images with
very good results, so that was the first thing I tried. It felt right
at the time and the results looked good. Also, most of the elements in
the sequence are supposed to be near zero, so the median is supposed
to give the amount of drift.

That said, you're probably right. I should have first tried to apply a
HPF.

> The obvious way to compute a running median involves a tree structure
> so you can quickly insert and delete elements, and find the median.
> That would be asymtotically O(n log n) but messy to implement.

Messy. Yes. I tried and failed :P

Thanks
Janto
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: efficient running median

[Janto Dreijer]

On Oct 13, 7:37 pm, Ethan Furman  wrote:
> Janto Dreijer wrote:
> > I'm looking for code that will calculate the running median of a
> > sequence, efficiently. (I'm trying to subtract the running median from
> > a signal to correct for gradual drift).
>
> > My naive attempt (taking the median of a sliding window) is
> > unfortunately too slow as my sliding windows are quite large (~1k) and
> > so are my sequences (~50k). On my PC it takes about 18 seconds per
> > sequence. 17 of those seconds is spent in sorting the sliding windows.
>
> > I've googled around and it looks like there are some recent journal
> > articles on it, but no code. Any suggestions?
>
> > Thanks
> > Janto
>
> You might look athttp://pypi.python.org/pypi/blist/0.9.4
>
> ~Ethan~

Very nice! I assume you mean I can use it to quickly insert items into
the sliding window?

Thanks
Janto
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: efficient running median

[Janto Dreijer]

On Oct 14, 12:13 am, Paul Rubin <http://phr...@nospam.invalid> wrote:
> Janto Dreijer  writes:
> > Well, I don't have a lot of theoretical reasoning behind wanting to
> > use a median filter. I have some experience applying it to images with
> > very good results, so that was the first thing I tried. It felt right
> > at the time and the results looked good.
>
> If this is image data, which typically would have fairly low
> resolution per pixel (say 8-12 bits), then maybe you could just use
> bins to count how many times each value occurs in a window.  That
> would let you find the median of a window fairly quickly, and then
> update it with each new sample by remembering the number of samples
> above and below the current median, etc.

Thanks, unfortunately it's not image data. It's electrocardiogram
sequences. So it's sequences of floats.

Janto
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: efficient running median

[Janto Dreijer]

On Oct 14, 4:53 pm, Peter Otten <__pete...@web.de> wrote:
> Some numbers:
>
> 10.197 seconds for running_median_scipy_medfilt
> 25.043 seconds for running_median_python
> 13.040 seconds for running_median_python_msort
> 14.280 seconds for running_median_python_scipy_median
> 4.024 seconds for running_median_numpy
> 0.221 seconds for running_median_insort
>
> What would be an acceptable performance, by the way?
>

That's great!
Well, the faster it works, the better. It means I can process more
data before getting frustrated. So if you have a faster version I'd
like to see it :)

Thankyou!
Janto
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: efficient running median

[Janto Dreijer]

On Oct 15, 12:41 pm, Raymond Hettinger  wrote:
> [Janto Dreijer]
>
> > I found a PDF by Soumya D. Mohanty entitled "Efficient Algorithm for
> > computing a Running Median" (2003) by Googling. It has code snippets
> > at the end, but it's not going to be a simple cut-and-paste job. It
> > will take some work figuring out the missing parts.
>
> Seehttp://code.activestate.com/recipes/576930/for working Python
> code
> adapted from that paper.
>
> Raymond

Wow! Thanks. I'll have a look.

Janto
-- 
http://mail.python.org/mailman/listinfo/python-list