Итак, сегодня меня спросили, что лучше всего найти совпадение закрытия в коллекции.
Например, у вас есть такой массив:
1, 3, 8, 10, 13, ...
Какой номер ближе всего к 4?
Коллекция является числовой, неупорядоченной и может быть любой. То же самое с номером, который нужно сопоставить.
Давайте посмотрим, с чем мы можем столкнуться, с разных языков выбора.
11 байт в J:
C=:0{]/:|@-
Примеры:
>> a =: 1 3 8 10 13
>> 4 C a
3
>> 11 C a
10
>> 12 C a
13
моя разбивка для непрофессионала:
0{ First element of
] the right argument
/: sorted by
| absolute value
@ of
- subtraction
Более короткий Python: 41 символ
f=lambda a,l:min(l,key=lambda x:abs(x-a))
Моя попытка в python:
def closest(target, collection) :
return min((abs(target - i), i) for i in collection)[1]
Groovy 28B
f={a,n->a.min{(it-n).abs()}}
Некоторые С# Linq... слишком много способов сделать это!
decimal[] nums = { 1, 3, 8, 12 };
decimal target = 4;
var close1 = (from n in nums orderby Math.Abs(n-target) select n).First();
var close2 = nums.OrderBy(n => Math.Abs(n - target)).First();
Console.WriteLine("{0} and {1}", close1, close2);
Еще больше способов, если вы используете список вместо этого, поскольку простые массивы ol не имеют .Sort()
Предполагая, что значения начинаются в таблице с именем T с столбцом N, и мы ищем значение 4, то в Oracle SQL оно принимает 59 символов:
select*from(select*from t order by abs(n-4))where rownum=1
Я использовал select * для уменьшения требований к пробелам.
PostgreSQL:
select n from tbl order by abs(4 - n) limit 1
В случае, когда две записи имеют одинаковое значение для "abs (4 - id)", выход будет определяющим и, возможно, не постоянным. Чтобы исправить это, я предлагаю нечто вроде непроверенного предположения:
select n from tbl order by abs(4 - n) + 0.5 * 4 > n limit 1;
Это решение обеспечивает производительность порядка O (N log N), где O (log N) возможно, например: fooobar.com/questions/203859/...
Поскольку мне действительно нужно было это сделать, вот мой PHP
$match = 33;
$set = array(1,2,3,5,8,13,21,34,55,89,144,233,377,610);
foreach ($set as $fib)
{
$diff[$fib] = (int) abs($match - $fib);
}
$fibs = array_flip($diff);
$closest = $fibs[min($diff)];
echo $closest;
Ruby, как и Python, имеет метод min для Enumerable, поэтому вам не нужно делать сортировку.
def c(value, t_array)
t_array.min{|a,b| (value-a).abs <=> (value-b).abs }
end
ar = [1, 3, 8, 10, 13]
t = 4
c(t, ar) = 3
Язык: C, Char count: 79
c(int v,int*a,int A){int n=*a;for(;--A;++a)n=abs(v-*a)<abs(v-n)?*a:n;return n;}
Подпись:
int closest(int value, int *array, int array_size);
Использование:
main()
{
int a[5] = {1, 3, 8, 10, 13};
printf("%d\n", c(4, a, 5));
}
Scala (62 символа), основанный на идее решений J и Ruby:
def c(l:List[Int],n:Int)=l.sort((a,b)=>(a-n).abs<(b-n).abs)(0)
Использование:
println(c(List(1,3,8,10,13),4))
Вышеприведенный код не работает для плавающих чисел.
Итак, здесь мой пересмотренный PHP-код для этого.
function find_closest($match, $set=array()) {
foreach ($set as $fib) {
$diff[$fib] = abs($match - $fib);
}
return array_search(min($diff), $diff);
}
$set = array('2.3', '3.4', '3.56', '4.05', '5.5', '5.67');
echo find_closest(3.85, $set); //return 4.05
PostgreSQL:
Это было указано RhodiumToad на FreeNode и имеет производительность порядка O (log N)., намного лучше, чем другой ответ PostgreSQL здесь.
select * from ((select * from tbl where id <= 4
order by id desc limit 1) union
(select * from tbl where id >= 4
order by id limit 1)) s order by abs(4 - id) limit 1;
Оба условия должны быть "или равны" для более эффективного управления случаем id. Это также имеет обработку в случае, когда две записи имеют одинаковое значение для "abs (4 - id)", а затем ответ на другой ответ PostgreSQL.
Python by me и https://stackoverflow.com/users/29253/igorgue, основанный на некоторых других ответах здесь. Всего 34 символа:
min([(abs(t-x), x) for x in a])[1]
EDITED = в цикле for
int Closest(int val, int[] arr)
{
int index = 0;
for (int i = 0; i < arr.Length; i++)
if (Math.Abs(arr[i] - val) < Math.Abs(arr[index] - val))
index = i;
return arr[index];
}
Запись в Haskell (проверена):
import Data.List
near4 = head . sortBy (\n1 n2 -> abs (n1-4) `compare` abs (n2-4))
Сортирует список, помещая числа ближе к 4 возле фронта. head принимает первый элемент (ближайший к 4).
Рубин
def c(r,t)
r.sort{|a,b|(a-t).abs<=>(b-t).abs}[0]
end
Не самый эффективный метод, но довольно короткий.
возвращает только одно число:
var arr = new int[] { 1, 3, 8, 10, 13 };
int numToMatch = 4;
Console.WriteLine("{0}",
arr.Select(n => new{n, diff = Math.Abs(numToMatch - n) }).OrderBy(x => x.diff).ElementAt(0).n);
возвращает только одно число:
var arr = new int[] { 1, 3, 8, 10, 13 };
int numToMatch = 4;
Console.WriteLine("{0}",
arr.OrderBy(n => Math.Abs(numToMatch - n)).ElementAt(0));
Perl - 66 символов:
perl -e 'for(qw/1 3 8 10 13/){$d=($_-4)**2; $c=$_ if not $x or $d<$x;$x=$d;}print $c;'
Здесь другой ответ Haskell:
import Control.Arrow
near4 = snd . minimum . map (abs . subtract 4 &&& id)
Haskell, 60 символов -
f a=head.Data.List.sortBy(compare`Data.Function.on`abs.(a-))
Kdb +, 23B:
C:{x first iasc abs x-}
Использование:
q)a:10?20
q)a
12 8 10 1 9 11 5 6 1 5
q)C[a]4
5
В Java используйте навигационную карту
NavigableMap <Integer, Integer>navMap = new ConcurrentSkipListMap<Integer, Integer>();
navMap.put(15000, 3);
navMap.put(8000, 1);
navMap.put(12000, 2);
System.out.println("Entry <= 12500:"+navMap.floorEntry(12500).getKey());
System.out.println("Entry <= 12000:"+navMap.floorEntry(12000).getKey());
System.out.println("Entry > 12000:"+navMap.higherEntry(12000).getKey());
Python, не уверен, как форматировать код, и не уверен, что код будет работать как есть, но логика должна работать, и там, возможно, встроенные, которые это делают так или иначе...
list = [1,4,10,20]
num = 7
for lower in list:
if lower <= num:
lowest = lower #closest lowest number
for higher in list:
if higher >= num:
highest = higher #closest highest number
if highest - num > num - lowest: # compares the differences
closer_num = highest
else:
closer_num = lowest
int numberToMatch = 4;
var closestMatches = new List<int>();
closestMatches.Add(arr[0]); // closest tentatively
int closestDifference = Math.Abs(numberToMatch - arr[0]);
for(int i = 1; i < arr.Length; i++)
{
int difference = Math.Abs(numberToMatch - arr[i]);
if (difference < closestDifference)
{
closestMatches.Clear();
closestMatches.Add(arr[i]);
closestDifference = difference;
}
else if (difference == closestDifference)
{
closestMatches.Add(arr[i]);
}
}
Console.WriteLine("Closest Matches");
foreach(int x in closestMatches) Console.WriteLine("{0}", x);
Некоторые из вас, похоже, не читают, что список unordered (хотя, например, я могу понять ваше замешательство). В Java:
public int closest(int needle, int haystack[]) { // yes i've been doing PHP lately
assert haystack != null;
assert haystack.length; > 0;
int ret = haystack[0];
int diff = Math.abs(ret - needle);
for (int i=1; i<haystack.length; i++) {
if (ret != haystack[i]) {
int newdiff = Math.abs(haystack[i] - needle);
if (newdiff < diff) {
ret = haystack[i];
diff = newdiff;
}
}
}
return ret;
}
Не совсем точный, но эй его Java.
Общий Lisp, используя итерационную библиотеку.
(defun closest-match (list n)
(iter (for i in list)
(finding i minimizing (abs (- i n)))
41 символ F #:
let C x = Seq.min_by (fun n -> abs(n-x))
как в
#light
let l = [1;3;8;10;13]
let C x = Seq.min_by (fun n -> abs(n-x))
printfn "%d" (C 4 l) // 3
printfn "%d" (C 11 l) // 10
printfn "%d" (C 12 l) // 13
рубин. Один проход. Хорошо обрабатывает отрицательные числа. Возможно, не очень короткий, но, безусловно, красивый.
class Array
def closest int
diff = int-self[0]; best = self[0]
each {|i|
if (int-i).abs < diff.abs
best = i; diff = int-i
end
}
best
end
end
puts [1,3,8,10,13].closest 4