source: python/aubio/median.py @ 9ae6e03

feature/autosinkfeature/cnnfeature/cnn_orgfeature/constantqfeature/crepefeature/crepe_orgfeature/pitchshiftfeature/pydocstringsfeature/timestretchfix/ffmpeg5pitchshiftsamplertimestretchyinfft+
Last change on this file since 9ae6e03 was 0484dc1, checked in by Paul Brossier <piem@altern.org>, 19 years ago

use a copy for the median
use a copy for the median

  • Property mode set to 100644
File size: 2.0 KB
Line 
1"""Copyright (C) 2004 Paul Brossier <piem@altern.org>
2print aubio.__LICENSE__ for the terms of use
3"""
4
5__LICENSE__ = """\
6         Copyright (C) 2004 Paul Brossier <piem@altern.org>
7               
8         This program is free software; you can redistribute it and/or modify
9         it under the terms of the GNU General Public License as published by
10         the Free Software Foundation; either version 2 of the License, or
11         (at your option) any later version.
12
13         This program is distributed in the hope that it will be useful,
14         but WITHOUT ANY WARRANTY; without even the implied warranty of
15         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16         GNU General Public License for more details.
17
18         You should have received a copy of the GNU General Public License
19         along with this program; if not, write to the Free Software
20         Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21"""           
22
23"""
24original author Tim Peters
25modified by Paul Brossier <piem@altern.org>
26inspired from http://www.ics.uci.edu/~eppstein/161/python/peters-selection.py
27"""
28
29def short_find(a, rank):
30    """ find the rank-th value in sorted a """
31    # copy to b before sorting
32    b = a[:]
33    b.sort()
34    return b[rank - 1]
35
36def percental(a, rank):
37    """ Find the rank'th-smallest value in a, in worst-case linear time. """
38    n = len(a)
39    assert 1 <= rank <= n
40    if n <= 7:
41        return short_find(a, rank)
42
43    ## Find median of median-of-7's.
44    ##medians = [short_find(a[i : i+7], 4) for i in xrange(0, n-6, 7)]
45    #median = find(medians, (len(medians) + 1) // 2)
46   
47    # modified to Find median
48    median = short_find([a[0], a[-1], a[n//2]], 2)
49
50    # Partition around the median.
51    # a[:i]   <= median
52    # a[j+1:] >= median
53    i, j = 0, n-1
54    while i <= j:
55        while a[i] < median:
56            i += 1
57        while a[j] > median:
58            j -= 1
59        if i <= j:
60            a[i], a[j] = a[j], a[i]
61            i += 1
62            j -= 1
63
64    if rank <= i:
65        return percental(a[:i], rank)
66    else:
67        return percental(a[i:], rank - i)
68
Note: See TracBrowser for help on using the repository browser.