[67a5bd]: lookup.m  Maximize  Restore  History

Download this file

83 lines (78 with data), 3.5 kB

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
## Copyright (C) 2000 Paul Kienzle
##
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
## the Free Software Foundation; either version 2 of the License, or
## (at your option) any later version.
##
## This program is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
## GNU General Public License for more details.
##
## You should have received a copy of the GNU General Public License
## along with this program; if not, write to the Free Software
## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
## usage: idx = lookup(table, y)
##
## If table is strictly increasing and idx=lookup(table, y), then
## table(idx(i)) <= y(i) < table(idx(i+1))
## for all y(i) within the table. If y(i) is before the table, then
## idx(i) is 0. If y(i) is after the table then idx(i) is table(n).
## If the table is strictly decreasing, then the tests are reversed.
## No guarantees for tables which are non-monotonic or are not strictly
## monotonic.
##
## To get an index value which lies within an interval of the table
## use:
## idx = lookup(table(2:length(table)-1), y) - 1
## This puts values before the table into the first interval, and values
## after the table into the last interval.
## Changed from binary search to sort.
## Thanks to Kai Habel <kai.habel@gmx.de> for the suggestion.
## TODO: sort-based lookup is significantly slower given a large table
## TODO: and small lookup vector. This shouldn't be a problem since
## TODO: interpolation (the reason for the table lookup in the first
## TODO: place) usually involves subsampling of an existing table. The
## TODO: other use of interpolation, looking up values one at a time, is
## TODO: unfortunately significantly slower for large tables.
## TODO: sort is order O((lt+lx)*log(lt+lx))
## TODO: search is order O(lx*log(lt))
## TODO: Clearly, search is asymptotically better than sort, but sort
## TODO: is compiled and search is not. Could support both, or recode
## TODO: search in C++, or assume things are good enough as they stand.
function idx=lookup(table,xi)
if isempty (table)
idx = zeros(size(xi));
elseif is_vector(table)
[nr, nc] = size(xi);
lt=length(table);
if ( table(1) > table(lt) )
## decreasing table
[v, p] = sort ([xi(:) ; table(:)]);
idx (p) = cumsum (p > nr*nc);
idx = lt - idx (1 : nr*nc);
else
## increasing table
[v, p] = sort ([table(:) ; xi(:) ]);
idx (p) = cumsum (p <= lt);
idx = idx (lt+1 : lt+nr*nc);
endif
idx = reshape (idx, nr, nc);
else
error ("lookup: table must be a vector");
endif
endfunction
%!assert (lookup(1:3, 0.5), 0) # value before table
%!assert (lookup(1:3, 3.5), 3) # value after table error
%!assert (lookup(1:3, 1.5), 1) # value within table error
%!assert (lookup(1:3, [3,2,1]), [3,2,1])
%!assert (lookup([1:4]', [1.2, 3.5]'), [1, 3]');
%!assert (lookup([1:4], [1.2, 3.5]'), [1, 3]');
%!assert (lookup([1:4]', [1.2, 3.5]), [1, 3]);
%!assert (lookup([1:4], [1.2, 3.5]), [1, 3]);
%!assert (lookup(1:3, [3, 2, 1]), [3, 2, 1]);
%!assert (lookup([3:-1:1], [3.5, 3, 1.2, 2.5, 2.5]), [0, 1, 2, 1, 1])
%!assert (isempty(lookup([1:3], [])))
%!assert (isempty(lookup([1:3]', [])))
%!assert (lookup(1:3, [1, 2; 3, 0.5]), [1, 2; 3, 0]);