Very nice. I have added a comment at the bottom, using a circular
queue instead of a deque may be faster.
Bye,
bearophile
--
http://mail.python.org/mailman/listinfo/python-list
In article 497af344-31b5-4d1a-9b1a-c3d82feb3...@j5g2000yqm.googlegroups.com,
Raymond Hettinger pyt...@rcn.com wrote:
The performance of an IndexableSkiplist is similar to a B+tree but the
implementation in pure python is much simpler.
Nice! Can you summarize why IndexableSkipList is simpler?
I've updated the running median recipe to use a new algorithm with O
(log n) updates for a large sliding window traversing a data stream.
See http://code.activestate.com/recipes/576930/
The engine is a new collection class called IndexableSkiplist. It is
like a regular skiplist as detailed at
Based on Perreault + Hebert, here's python code for a rather different
algorithm:
- for quantized e.g. 8-bit data
- runs faster for wider windows / slowly changing medians
- no heaps, no trees: the only import is numpy, and even that's not
essential
Yet another link: http://en.wikipedia.org/wiki/Median_filter
-- Perreault + Hebert, Median Filtering in Constant Time,
nice 6-page paper + 400 lines well-documented C code:
http://nomis80.org/ctmf.html
(for 2d images, dropping to 1d must be possible :)
They're also in opencv, which I haven't
Folks,
approximate medians -- would you settle for 49 - 51 % ? --
open up new possibilities, and there's quite a lot of work on that,
for huuuge datasets.
A class of problems:
from a data stream X1 X2 ... you want, every so often,
a histogram / quantile summary / distribution estimator such
[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.
See
On Oct 15, 12:41 pm, Raymond Hettinger pyt...@rcn.com 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
On Tuesday, 13 October 2009 17:22:55 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
On 14 Okt, 00:03, Steven D'Aprano
ste...@remove.this.cybersource.com.au wrote:
Obviously to run in O(log n) you must have already built the tree.
You don't need a tree. Quickselect is a partial quicksort.
But my memory served me badly, quickselect is O(n).
--
On Oct 13, 6:33 pm, Paul Rubin http://phr...@nospam.invalid wrote:
Janto Dreijer jan...@gmail.com 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
On Oct 13, 7:37 pm, Ethan Furman et...@stoneleaf.us 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
On Oct 14, 12:13 am, Paul Rubin http://phr...@nospam.invalid wrote:
Janto Dreijer jan...@gmail.com 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
Janto Dreijer wrote:
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
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
Janto Dreijer wrote:
On Oct 13, 7:37 pm, Ethan Furman et...@stoneleaf.us 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
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
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
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
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
On Oct 13, 8:22 am, Janto Dreijer jan...@gmail.com 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
On Tue, Oct 13, 2009 at 10:22 AM, Janto Dreijer jan...@gmail.com 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).
In the past, I've used the following
sturlamolden sturlamol...@yahoo.no 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)
On Tue, 13 Oct 2009 12:59:47 -0700, Paul Rubin wrote:
sturlamolden sturlamol...@yahoo.no 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
On Oct 13, 11:57 am, sturlamolden sturlamol...@yahoo.no wrote:
On 13 Okt, 18:33, Paul Rubin http://phr...@nospam.invalid wrote:
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
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
26 matches
Mail list logo
