TheSwamp
Code Red => AutoLISP (Vanilla / Visual) => Topic started by: Mark on March 11, 2005, 08:35:01 AM
-
Write a function that returns the closest integer to n given a list of integers.
Example:
(setq lst '(45 23 63 5 8 56 74 32 96 144 95))
return the number closest to 10;
answer = 8.
Have fun. :D
-
Oops.
-
Rules? 8)
-
Rules?
Nope!! Go for it, let's see what ya got. :D
commence posting, post at will..............
-
commence posting, post at will..............
NO! NO! NOT AT ME! :lol: :lol:
Seriously.
Here's mine:
(setq lst '(45 23 63 5 8 56 74 32 96 144 95))
(defun closest (nlst / int pos)
(initget (+ 1 4))
(setq int (getint "\nEnter a number: "))
(setq pos (vl-position
0
(vl-sort-i (mapcar '(lambda (n) (abs (- n int))) nlst) '>)
)
)
(princ (strcat "The number closest to "
(itoa int)
" is "
(itoa (nth pos nlst))
"."
)
)
)
-
Here's one that works with negatives as well:
(setq lst2 '(-45 -23 -63 5 -8 56 74 32 -96 -144 95))
(defun closest2 (nlst / int pos)
(initget 1)
(setq int (getint "\nEnter a number: "))
(setq pos (vl-position
(apply 'min
(setq pos (mapcar 'abs (mapcar '(lambda (n) (- n int)) nlst)))
)
pos
)
)
(princ (strcat "The number closest to "
(itoa int)
" is "
(itoa (nth pos nlst))
"."
)
)
)
-
I came up with two versions.
;; version one
(defun nearest (num lst / a)
(foreach x lst
(if (or (null a)
(< (abs(- num x)) (car a))
)
(setq a (list (abs(- num x)) x))
)
)
(cadr a)
)
and after some thought version 2
(defun nearest2 (num lst / a)
(car (vl-sort lst '(lambda (x y) (< (abs(- num x)) (abs(- num y)) ))))
)
-
< ... >
and after some thought version 2
(defun nearest2 (num lst / a)
(car (vl-sort lst '(lambda (x y) (< (abs(- num x)) (abs(- num y)) ))))
)
That is SO pretty !!
-
so there is less computation
(defun test (n l)
(nth (car (vl-sort-i (mapcar '(lambda (a) (abs (- n a))) l) '<)) l)
)
-
Seems to me this could return zero or two. IOW, both answers are correct within context.
Command: (nearest2 1 '(0 2 3))
0
-
Thanks Kerry.
As always very nice Evgeniy.
That appears to be correct Joe.
-
I would probably use a genric function like this.
(defun round (value to)
(if (zerop to) value
(* (atoi (rtos (/ (float value) to) 2 0)) to)))
It works works with integer or real values passed. Plus it's numerically correct rounding. Not a qurirk of code rounding.
-
I think Evgeniy has put this one to bed :wink:
-
ugly but should be the fastest in most cases
(defun nearest133 (num lst / a b c)
(setq b (car lst)
a (abs (- num b))
)
(while (setq lst (cdr lst))
(if (< (setq c (abs (- num (car lst)))) a)
(setq b (car lst)
a c
)
)
)
b
)
-
Late entry, really just a modification of Will's :-P
(defun Closest-LEEMAC (num lst / vlst)
(nth
(vl-position
(apply (function min)
(setq vlst
(mapcar
(function
(lambda (x) (abs (- x num)))) lst))) vlst) lst))
-
My bet is on VovKa :wink: While wins in 9/10 cases...
-
Here's my entry:
(defun wiz-near (n lst / b c d)
(setq a (list n n)
b 1e6
)
(mapcar '(lambda (x)
(if (<= (setq c (distance a (list n x))) b)
(setq b c
d x
)
)
)
lst
)
d
)
-
Very original Wizman I like it!
This is what I get:
Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST133-VOVKA 10 LST).....1263 / 2.77 <fastest>
(CLOSEST-LEEMAC 10 LST).......1388 / 2.52
(WIZ-NEAR 10 LST).............1435 / 2.43
(CLOSEST2-WHDJR 10 LST).......1451 / 2.41
(NEAREST-CAB 10 LST)..........1497 / 2.33
(TEST-EVGENIY 10 LST).........1841 / 1.90
(NEAREST2-CAB 10 LST).........3494 / 1.00 <slowest>
-
Thanks Lee, good solution by all too:
edit: just seen others works on reals too, got to rest now
-
A quick (and poor) attempt to be clever :wink:
#include <iostream>
#include <cstdlib>
using namespace std;
// C++ Attempt!
int main( )
{
float lst[11] = {45,23,63,5,8,56,74,32,96,144,95}, n=10, a, b;
int i;
a = abs(n-lst[0]);
for (i=1; i<11; i++)
if (abs(n-lst[i]) < a) a = lst[i];
cout << a;
return 0;
}
Have no idea how to time it to compare with the others though...
-
only , benchmark...
(defun test1 (n l )
(setq l (vl-sort l (function <)))
(while (< (cadr l) n) (setq l (cdr l)))
(if (< (abs (- n (car l))) (abs (- n (cadr l))))
(car l)
(cadr l)
)
)
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
(TEST1 N L)..........1329 / 1.08 <fastest>
(NEAREST133 N L).....1438 / 1 <slowest>
-
Haha! Cheeky trick :-) Get rid of the values that just clutter the list ;-)
-
(defun test1 (n l )
(setq l (vl-sort l (function <)))
(while (< (cadr l) n) (setq l (cdr l)))
(if (< (abs (- n (car l))) (abs (- n (cadr l))))
(car l)
(cadr l)
)
)
i just knew that Evgeniy would beat us all :)
-
although...
(test1 5 '(1 2 3))
-
although...
(test1 5 '(1 2 3))
fix:
(defun test1 (n l )
(setq l (vl-sort l (function <)))
(while (and (cddr l)(< (cadr l) n)) (setq l (cdr l)))
(if (< (abs (- n (car l))) (abs (- n (cadr l))))
(car l)
(cadr l)
)
)
comparison
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
(TEST1 N L)..........1359 / 1.06 <fastest>
(NEAREST133 N L).....1437 / 1 <slowest>
_$
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
(TEST1 N L)..........1453 / 1.09 <fastest>
(NEAREST133 N L).....1578 / 1 <slowest>
-
(defun wiz-near2 (n lst / b c d)
(setq b 1e6)
(mapcar (function(lambda (x)
(if (< (setq c (abs (- n x ))) b)
(setq b c
d x
)
)
))
lst
)
d
)
-
A quick (and poor) attempt to be clever :wink:
nice 8-)
static bool closesTo10 ( int elem1, int elem2)
{
return abs(elem1 - 10) < abs(elem2 -10);
}
static void ArxBlockExt_doit(void)
{
int a[] = {45,23,63,5,8,56,74,32,96,144,95};
std::sort(a, a + sizeof(a) / sizeof(a[0]),closesTo10);
acutPrintf(_T("\n%d"),a[0]);
}
-
A quick (and poor) attempt to be clever :wink:
nice 8-)
Thanks Daniel - but amateur compared to yours.... :-)
-
i had a dream last night :)
(defun nearest41 (num lst / p a b)
(cond ((vl-position num lst) num)
((zerop (setq lst (vl-sort (cons num lst) '<)
p (vl-position num lst) ; faster than Evgeniy's when (> p 2)
)
)
(cadr lst)
)
((= (last lst) num) (nth (1- p) lst))
((> (- (setq a (nth (1+ p) lst)) num) (- num (setq b (nth (1- p) lst)))) b)
(t a)
)
)
(setq lst '(10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170)
num 31 ;and above
)
-
i had a dream last night :)
It was colored dream? :)
Good job VovKa!
-
It was colored dream?
yeah, parenthesis were red, functions - blue, variables - black :)
-
:-D Wish all mine were like that.
-
Very nice VovKa! 8-)
-
Good Work vovka, good sleep + good code :-)
-
I get this result:
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(TEST1-EVGENIY 10 LST)........1217 / 2.91 <fastest>
(NEAREST41-VOVKA 10 LST)......1232 / 2.87
(NEAREST133-VOVKA 10 LST).....1280 / 2.77
(CLOSEST-LEEMAC 10 LST).......1341 / 2.64
(WIZ-NEAR2 10 LST)............1373 / 2.58
(WIZ-NEAR 10 LST).............1435 / 2.47
(CLOSEST2-WHDJR 10 LST).......1451 / 2.44
(NEAREST-CAB 10 LST)..........1513 / 2.34
(TEST-EVGENIY 10 LST).........1841 / 1.92
(NEAREST2-CAB 10 LST).........3541 / 1.00 <slowest>
-
Lee, we both will be happier if you benchmark the above with 100 instead of 10 :)
-
Lee, we both will be happier if you benchmark the above with 100 instead of 10 :)
Nice one :wink:
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST133-VOVKA 100 LST).....1248 / 2.75 <fastest>
(NEAREST41-VOVKA 100 LST)......1264 / 2.72
(CLOSEST-LEEMAC 100 LST).......1342 / 2.56
(WIZ-NEAR2 100 LST)............1342 / 2.56
(CLOSEST2-WHDJR 100 LST).......1404 / 2.45
(TEST1-EVGENIY 100 LST)........1451 / 2.37
(WIZ-NEAR 100 LST).............1466 / 2.34
(NEAREST-CAB 100 LST)..........1514 / 2.27
(TEST-EVGENIY 100 LST).........1747 / 1.97
(NEAREST2-CAB 100 LST).........3433 / 1.00 <slowest>
-
i have different results
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST41 100 LST)..........1656 / 1.19 <fastest>
(CLOSEST-LEEMAC 100 LST).....1734 / 1.14
(NEAREST133 100 LST).........1750 / 1.13
(WIZ-NEAR2 100 LST)..........1812 / 1.09
(TEST1 100 LST)..............1969 / 1.00 <slowest>
it looks like autolisp code's speed is cpu dependant
-
>VovKa, Lee Mac
Show the arguments with which you have received your results.
I have several options, which in various cases faster your.
-
>VovKa, Lee Mac
Show the arguments with which you have received your results.
I have several options, which in various cases faster your.
Evgeniy,
I have just used the list as Mark posted in the first post :-)
-
Ok :-)
(defun test3 (n l / a b)
(if (vl-position n l)
n
(cond ((not (setq l (vl-sort (cons n l) (function <))
a (cadr (member n l))
) ;_ setq
) ;_ not
(cadr (member n (reverse l)))
)
((not (setq b (cadr (member n (reverse l)))))a)
((if(< (abs (- n a)) (abs (- n b))) a b))
) ;_ cond
) ;_ if
)
(setq l '(45 23 63 5 8 56 74 32 96 144 95) n 100)
(BenchMark '((nearest41 n l)(Closest-LEEMAC n l)(test3 n l)))
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
(TEST3 N L)..............1500 / 1.22 <fastest>
(NEAREST41 N L)..........1531 / 1.19
(CLOSEST-LEEMAC N L).....1829 / 1 <slowest>
_$
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
(TEST3 N L)..............1532 / 1.2 <fastest>
(NEAREST41 N L)..........1547 / 1.19
(CLOSEST-LEEMAC N L).....1844 / 1 <slowest>
_$
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
(TEST3 N L)..............1515 / 1.21 <fastest>
(NEAREST41 N L)..........1531 / 1.19
(CLOSEST-LEEMAC N L).....1829 / 1 <slowest>
_$
-
(defun wiz-near3 (n lst / a d e)
(cond ((vl-position n lst) n)
((setq lst (vl-sort (cons n lst) (function >))
lst (cons -1e6 (reverse (cons 1e6 lst)))
a (vl-position n lst)
)
(if (< (abs (- (setq d (nth (1+ a) lst)) n))
(abs (- (setq e (nth (1- a) lst)) n))
)
d
e
)
)
)
)
-
You guys want to verify this?
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(WIZ-NEAR3 100 LST)...........1201 / 1.12 <fastest>
(NEAREST41-VOVKA 100 LST).....1216 / 1.10
(TEST3-EVGENIY 100 LST).......1280 / 1.05
(CLOSEST-LEEMAC 100 LST)......1342 / 1.00 <slowest>
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(WIZ-NEAR3 100 LST)...........1185 / 1.15 <fastest>
(NEAREST41-VOVKA 100 LST).....1232 / 1.10
(TEST3-EVGENIY 100 LST).......1264 / 1.07
(CLOSEST-LEEMAC 100 LST)......1357 / 1.00 <slowest>
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(WIZ-NEAR3 100 LST)...........1170 / 1.15 <fastest>
(NEAREST41-VOVKA 100 LST).....1201 / 1.12
(TEST3-EVGENIY 100 LST).......1264 / 1.06
(CLOSEST-LEEMAC 100 LST)......1341 / 1.00 <slowest>
-
upgraded cond to ifs
(defun nearest42 (num lst / p a b)
(if (vl-position num lst)
num
(if (zerop (setq lst (vl-sort (cons num lst) (function <))
p (vl-position num lst) ; faster than Evgeniy's when (> p 2)
; faster than wizman's when (not (equal p (length lst) 3))
)
)
(cadr lst)
(if (= (last lst) num)
(nth (1- p) lst)
(if (> (- (setq a (nth (1+ p) lst)) num) (- num (setq b (nth (1- p) lst))))
b
a
)
)
)
)
)
-
(setq lst '(10 20 30 40 50 60 70 80 90 100))
(foreach num lst
(print (setq num (1+ num)))
(benchmark '((wiz-near3 num lst) (nearest42 num lst)))
)
11 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST42 NUM LST).....1485 / 1.03 <fastest>
(WIZ-NEAR3 NUM LST).....1531 / 1.00 <slowest>
21 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST42 NUM LST).....1500 / 1.04 <fastest>
(WIZ-NEAR3 NUM LST).....1562 / 1.00 <slowest>
31 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST42 NUM LST).....1500 / 1.02 <fastest>
(WIZ-NEAR3 NUM LST).....1531 / 1.00 <slowest>
41 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST42 NUM LST).....1516 / 1.03 <fastest>
(WIZ-NEAR3 NUM LST).....1562 / 1.00 <slowest>
51 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST42 NUM LST).....1500 / 1.03 <fastest>
(WIZ-NEAR3 NUM LST).....1547 / 1.00 <slowest>
61 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST42 NUM LST).....1515 / 1.03 <fastest>
(WIZ-NEAR3 NUM LST).....1563 / 1.00 <slowest>
71 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST42 NUM LST).....1531 / 1.02 <fastest>
(WIZ-NEAR3 NUM LST).....1563 / 1.00 <slowest>
81 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST42 NUM LST).....1546 / 1.01 <fastest>
(WIZ-NEAR3 NUM LST).....1563 / 1.00 <slowest>
91 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(WIZ-NEAR3 NUM LST).....1547 / 1.00 <fastest>
(NEAREST42 NUM LST).....1547 / 1.00 <slowest>
101 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
(NEAREST42 NUM LST).....1484 / 1.06 <fastest>
(WIZ-NEAR3 NUM LST).....1578 / 1.00 <slowest>
-
Ok :-)
(defun test3 (n l / a b)
(if (vl-position n l)
n
(cond ((not (setq l (vl-sort (cons n l) (function <))
a (cadr (member n l))
) ;_ setq
) ;_ not
(cadr (member n (reverse l)))
)
((not (setq b (cadr (member n (reverse l)))))a)
((if(< (abs (- n a)) (abs (- n b))) a b))
) ;_ cond
) ;_ if
)
Evgeniy, i tested your code and got the same results as Lee did
i just can't see how member can outrun vl-position
-
Evgeniy, i tested your code and got the same results as Lee did
i just can't see how member can outrun vl-position
Indeed, now I got the results that are similar to yours.
Perhaps I was wrong.
I'm sorry, I'm sorry.
I have a new idea :
(defun test4 (n l / a b i)
(cond ((not (setq l (vl-sort (cons (float n) l) (function <))
i (vl-position (float n) l)
a (nth (1- i) l)
) ;_ setq
) ;_ not
(nth (1+ i) l)
)
((not (setq b (nth (1+ i) l))) a)
((if (< (abs (- n a)) (abs (- n b)))
a
b
) ;_ if
)
) ;_ cond
)
-
Evgeniy, excelent move with float :)
now it's faster than mine
but bad news for (test4 1 '(1 2 3))
-
(defun wiz-near4 (n lst / a d e f g)
(if (vl-position n lst)
n
(setq lst (vl-sort (cons n lst) (function >))
lst (cons -1e6 (reverse (cons 1e6 lst)))
a (vl-position n lst)
d (nth (1+ a) lst)
e (nth (1- a) lst)
f (- d n)
g (if (equal e n f)
e
d
)
)
)
)
..be back tom..
-
I am sure that there are far faster and better on here, but I thought I would try my hand at it before reading the entier thread, so here is my entry:
(defun c:inttst (/ a lst ct b c d e)
(setq a (getint "\nEnter integer: ")
lst '(45 23 63 5 8 56 74 32 96 144 95)
ct 0
ct2 (- (length lst) 1)
lst (vl-sort lst '<)
pos (vl-position a lst)
b (nth 0 lst)
d (- b a)
c (nth ct2 lst)
e (- a c))
(cond
((/= pos nil)
(princ (strcat "\nThere was an exact match: " (itoa (nth pos lst))))
)
(T
(while (< ct (length lst))
(cond
((> (nth ct lst) a)
(setq b (nth ct lst)
d (- b a))
)
)
(setq ct (+ ct 1))
)
(while (> ct2 -1)
(cond
((< (nth ct2 lst) a)
(setq c (nth ct2 lst)
e (- a c))
)
)
(setq ct2 (- ct2 1))
)
(if (< d e)
(princ (strcat "\nThe closest number to " (itoa a) " is: " (itoa (nth (- ct 1) lst))))
(princ (strcat "\nThe closest number to " (itoa a) " is: " (itoa (nth (+ ct2 1) lst))))
)
)
)
(princ)
)
It works, but now I am going to go through the thread and see if there is one that looks like it will run faster. This is actually something that can be helpful in some routines that I am working on.
-
Chris,
It'd be better if your function took two arguments (the number and lst), and didn't have user input/print out - then it can be tested in a benchmarking function :-)
-
Any room for some Ruby?
class Array
def nearest(input)
self.sort_by{|x| (x-input).abs}.first
end
end
numbers = [45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95]
input = 10
puts numbers.nearest input # returns 8
puts [1,2,3].nearest 5 #returns 3
-
Evgeniy, excelent move with float :)
now it's faster than mine
but bad news for (test4 1 '(1 2 3))
(defun test4 (n l / a b i)
(cond ((zerop (setq l (vl-sort (cons (float n) l) (function <))
i (vl-position (float n) l)
)
)
(cadr l)
)
((not (setq a (nth (1- i) l)
b (nth (1+ i) l)
)
)
a
)
((if (< (abs (- n a)) (abs (- n b)))
a
b
)
)
)
)
-
:)
and who said dead threads shouldn't be resurrected :?
-
:)
and who said dead threads shouldn't be resurrected :?
I love all threads *Challenge* :-)
-
i've changed cond to ifs and stolen wizman's equal
(defun test413 (n l / a b i)
(if (zerop (setq l (vl-sort (cons (float n) l) (function <))
i (vl-position (float n) l)
)
)
(cadr l)
(if (or (not (setq a (nth (1- i) l)
b (nth (1+ i) l)
)
)
(equal n a (- b n))
)
a
b
)
)
)
-
i think that would be it Vovka, i like also EE's float: (vl-position 1.0 '(1 1 1 1.0)) ;3
-
ever useful to you:
(vl-sort '(0 1 2 0 1 2)'<) ;; =>> '(1 2 3)
but
(vl-sort '(0. 1. 2. 0. 1. 2.)'<) ;; =>> '(0.0 1.0 1.0 2.0 2.0)
-
ever useful to you:
(vl-sort '(0 1 2 0 1 2)'<) ;; =>> '(1 2 3)
< .. >
uhmmm ... that's (0 1 2) , yes ?
-
uhmmm ... that's (0 1 2) , yes ?
I was not sufficiently attentive.
Thank you!
-
:)
and who said dead threads shouldn't be resurrected :?
I love all threads *Challenge* :-)
Me too :-) 8-)
-
An alternate approach, just for fun.
(defun ClosestInt (n lst / tmp)
;; Returns first closest number in list
(nth (vl-position
(eval
(cons 'min
(setq tmp (mapcar '(lambda (x) (abs (- n x))) lst))
)
)
tmp
)
lst
)
)
-
Nice solution Steve !
-
Thanks Kerry. I had not read solutions posted by others until now. Just noticed whdjr posted a very similar solution. : )
Nice solution Steve !
-
A flexible C++ Template method from the attached Playground3.cpp file.
Templates closeToMethod1, 2, and 3 are implemented in Playground1.cpp,
and closeToMethod4, 5, 6 are in Playground2.cpp. Each template is implemented
slightly different so I could look at the disassembled code of the release builds.
Overall generated code is very similar amongst 1, 2, 3, and 6. 3 and 6 require
external linkage of the array, while the rest can use local arrays. 4 and 5 did
not inline the calls to closestTo, probably because arr was unknown to the
template at compile time.
Hm, also, for 1, 2, and 3 I noticed that the loops where unrolled for 8 or
less array elements, and also unrolled for 10 and 12 elements, didn't check any
others.
#include "stdafx.h"
#include <iostream>
template<int N, int nArraySize, const int * aar>
struct closeToMethod3 {
static int op(void) {
int nVal = INT_MIN;
for(int i = 0; i < nArraySize; i++) {
nVal = closestTo(aar[i], nVal);
}
return nVal;
}
static int closestTo (const int elem1, const int elem2)
{
return abs(elem1 - N) < abs(elem2 - N) ? elem1 : elem2;
}
};
extern int g_array[] = {45,23,63,5,8,56,74,32,96,144,95};
int _tmain(int argc, _TCHAR* argv[])
{
using namespace std;
const int aVal1 = closeToMethod3<10, sizeof(g_array) / sizeof(g_array[0]), g_array>::op();
const int aVal2 = closeToMethod3<20, sizeof(g_array) / sizeof(g_array[0]), g_array>::op();
const int aVal3 = closeToMethod3<30, sizeof(g_array) / sizeof(g_array[0]), g_array>::op();
cout << aVal1 << endl;
cout << aVal2 << endl;
cout << aVal3 << endl;
cout << closeToMethod3<40, sizeof(g_array) / sizeof(g_array[0]), g_array>::op() << endl;
return 0;
}
-
A flexible C++ Template method from the attached Playground3.cpp file.
Nice! 8-)
Templates are next on my list to learn.
-
A flexible C++ Template method from the attached Playground3.cpp file.
Nice! 8-)
Templates are next on my list to learn.
I spent all day yesterday trying to make a templated version that would get the
answer at compile time (0 runtime overhead). Long story short, templale
programming has a very strict set of rules, don't go looking for loop holes
cause you (me --> :| <--) won't find ANY, ie. you cannot get to elements of an
array or string with template metaprogramming, but you can fake it with
boost MPL.
Wish I'd found this page earlier
http://www.boost.org/development/int_const_guidelines.html
-
Answer computed at compile time (C++), 0 runtime overhead.
First the compiler generated code
; 147 : // Given a set of elements, find the one closest to the 1st element
; 148 : // ie, closest to 10
; 149 : int nNearest = ClosestInt_11<10, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
mov DWORD PTR _nNearest$[ebp], 8
; 150 : // more values to test with
; 151 : nNearest = ClosestInt_11<-4, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
mov DWORD PTR _nNearest$[ebp], 5
; 152 : nNearest = ClosestInt_11<144, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
mov DWORD PTR _nNearest$[ebp], 144 ; 00000090H
; 153 : nNearest = ClosestInt_11<30, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
mov DWORD PTR _nNearest$[ebp], 32 ; 00000020H
and the C++ Template code. Since TMP is new to me and they can't operate on array elements, ie no way to do recursion with array or string contents, this is a pretty heavy handed solution. Boost MPL makes this much easier to do.
#include "stdafx.h"
//////////////////////////////////////////////////////////////////////////
// Compile time IF THEN ELSE conditional
//////////////////////////////////////////////////////////////////////////
template<bool condition, int Then, int Else>
struct IF_THEN_ {
enum { value = Then };
};
template<int Then, int Else>
struct IF_THEN_<false, Then, Else> {
enum { value = Else };
};
//////////////////////////////////////////////////////////////////////////
// Compile time absolute value
//////////////////////////////////////////////////////////////////////////
template<int N>
struct ABS_
{
enum {
value = IF_THEN_<(N < 0), -N, N>::value
};
};
//////////////////////////////////////////////////////////////////////////
// Given N which is closer? n1 or n2
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2>
struct ClosestInt_2
{
enum {
/** Easier to read
//v1 = ABS_<n1 - N>::value,
//v2 = ABS_<n2 - N>::value,
//value = IF_THEN_<v1 < v2, n1, n2>::value
*/
// but probably more efficent
value = IF_THEN_< ABS_<n1 - N>::value < ABS_<n2 - N>::value, n1, n2 >::value
};
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3>
struct ClosestInt_3
{
enum { value = ClosestInt_2<N, n1, ClosestInt_2<N, n2, n3>::value>::value };
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4>
struct ClosestInt_4
{
enum {
value =
ClosestInt_2<N, n4, ClosestInt_2<N, n2,
ClosestInt_2<N, n2, n1>
::value>::value>::value
};
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5>
struct ClosestInt_5
{
enum {
value =
ClosestInt_2<N, n5, ClosestInt_2<N, n4, ClosestInt_2<N, n2,
ClosestInt_2<N, n2, n1>
::value>::value>::value>::value
};
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6>
struct ClosestInt_6
{
enum {
value =
ClosestInt_2<N, n6, ClosestInt_2<N, n5, ClosestInt_2<N, n4,
ClosestInt_2<N, n2, ClosestInt_2<N, n2, n1>
::value>::value>::value>::value>::value
};
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6, int n7>
struct ClosestInt_7
{
enum {
value =
ClosestInt_2<N, n7, ClosestInt_2<N, n6, ClosestInt_2<N, n5,
ClosestInt_2<N, n4, ClosestInt_2<N, n2, ClosestInt_2<N, n2, n1>
::value>::value>::value>::value>::value>::value
};
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6, int n7, int n8>
struct ClosestInt_8
{
enum {
value =
ClosestInt_2<N, n8, ClosestInt_2<N, n7, ClosestInt_2<N, n6,
ClosestInt_2<N, n5, ClosestInt_2<N, n4, ClosestInt_2<N, n2,
ClosestInt_2<N, n2, n1>
::value>::value>::value>::value>::value>::value>::value
};
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6, int n7, int n8, int n9>
struct ClosestInt_9
{
enum {
value =
ClosestInt_2<N, n9, ClosestInt_2<N, n8, ClosestInt_2<N, n7,
ClosestInt_2<N, n6, ClosestInt_2<N, n5, ClosestInt_2<N, n4,
ClosestInt_2<N, n2, ClosestInt_2<N, n2, n1>
::value>::value>::value>::value>::value>::value>::value>::value
};
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6, int n7, int n8, int n9, int n10>
struct ClosestInt_10
{
enum {
value =
ClosestInt_2<N, n10, ClosestInt_2<N, n9, ClosestInt_2<N, n8,
ClosestInt_2<N, n7, ClosestInt_2<N, n6, ClosestInt_2<N, n5,
ClosestInt_2<N, n4, ClosestInt_2<N, n2, ClosestInt_2<N, n2, n1>
::value>::value>::value>::value>::value>::value>::value>::value>::value
};
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6, int n7, int n8, int n9, int n10, int n11>
struct ClosestInt_11
{
enum {
value =
ClosestInt_2<N, n11, ClosestInt_2<N, n10, ClosestInt_2<N, n9,
ClosestInt_2<N, n8, ClosestInt_2<N, n7, ClosestInt_2<N, n6,
ClosestInt_2<N, n5, ClosestInt_2<N, n4, ClosestInt_2<N, n2,
ClosestInt_2<N, n2, n1>
::value>::value>::value>::value>::value>::value>::value>::value>::value>::value
};
};
void main()
{
// Given a set of elements, find the one closest to the 1st element
// ie, closest to 10
int nNearest = ClosestInt_11<10, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
// more values to test with
nNearest = ClosestInt_11<-4, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
nNearest = ClosestInt_11<144, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
nNearest = ClosestInt_11<30, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
}