in reply to Find a number in a list closest to a target
If you can require that the list be sorted, you can do something like:
The presumption here is that $best->[0] will be getting smaller and smaller, then start getting larger. If your list is sorted, then you can stop looking once the smallest difference is found - you won't be beating it.my $best = undef; for (@returns) { my $diff = abs($ctime - $_); unless (defined $best) { $best = [$_, $diff]; next; } if ($diff < $best) { $best = [$_, $diff]; next; } if ($diff > $best) { last; } } print "Best match is $best->[0] at $best->[1] away from $ctime\n";
Now, the above algorithm is a naive search, or linear search. You can look at doing a binary search, but it becomes somewhat complicated. If you have more than, say, 1000 items and that list is completely static and you look up into it more than, say, 100 times, then I'd look at doing a cached binary search. (The numbers are somewhat arbitrary. However, linear searches are actually faster than binary searches for extremely small sets, like under 30 elements. Also, it's harder to maintain a cached binary search than a early-terminating linear search, which may be a consideration.)
There are several methods to cache. One of them could be noting where several marker points are. For example, if you were doing a search across the numbers 1 to 100, you'd note where 10, 20, 30, 40, 50, etc would be. This is especially important if your array is sparsely populated in some areas, but densely populated in others. This would allow you to find out which subset of the search area you need to focus in. Depending on how large your search area is, you might have second-level markers, possibly only in dense subsections.
The goal here is that if you have a large number of elements to check against, you want to reduce the number of comparisons you make. This allows you to reduce your search time. But, remember that for smaller sets (under 100 elements), most search algorithms tend to run within acceptable times, regardless if they're O(n) or O(log n ** 0.1). (Big-O of the tenth root of the log of n ... very very fast!) At those sizes, your bottlenecks start being I/O and your comprehension, not the search algorithm being used.
------
We are the carpenters and bricklayers of the Information Age.
Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.
Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.
|
|---|