|
|
« Предыдущая тема | Следующая тема » |
Опции темы | Опции просмотра |
|
|
|||||
[+ 1.0 08.10.14]
блогер
Регистрация: Mar 2010
Адрес: x = stage.stageWidth/2 y= stage.stageHeight/2
Сообщений: 293
Записей в блоге: 2
|
вернуть максимально ближайшее значение из массива
Нужен алгоритм сортировки массива.
Есть условно массив с некоторым количеством отсортированных чисел от меньшего к большему Необходимо по ключу числу вернуть ближайшее значение. Например по ключу 16 должен вернуть число 14 по ключу 35 должен вернуть 27. Если есть идентичное число то должен вернуть его, если по ключу можно вернуть два числа, то есть по ключу 4 в данном случае можно вернуть 3 и 5, то должен вернуть наименьшее. |
|
|||||
Регистрация: Jan 2013
Сообщений: 322
|
inozemcev, это же бинарный поиск
простой перебор: (function(arr, v){ if(arr[arr.length - 1] <= v) return arr[arr.length - 1]; var i = 0; while(arr[++i] < v); return arr[(v - arr[i - 1] > arr[i] - v) ? i : i - 1]; })([3, 5, 9, 14, 27], (27-14) / 2 + 14); // 14 var arr:Vector.<Number> = new <Number>[3, 5, 9, 14, 27]; var value:Number = (27-14) / 2 + 14); // 20.5 function nearestSearch(arr:Vector.<Number>, v:Number):Number{ if(arr[arr.length - 1] <= v) return arr[arr.length - 1]; var i:uint = 0; while(arr[++i] < v); // сюда вставлять бинарный поиск return arr[(v - arr[i - 1] > arr[i] - v) ? i : i - 1]; } nearestSearch(arr, value); // 14 Последний раз редактировалось nubideus; 26.07.2014 в 19:32. |
|
|||||
Бинарный поиск мало кто может написать без ошибок.
Я бы не выпендривался и просто искал элемент, для которого (Math.abs(array[i] - value)) минимально (будет работать и не для отсортированного списка, сложность линейная) P.S. На самом деле, бинарный поиск, конечно можно написать, покрыв его дюжиной тестов. Но оно у Вас действительно критичное по производительности место, чтобы включать ради поиска этого элемента мозги? И там действительно будет больше 20-50 элементов? - Иначе бинарный поиск ничего не даст. |
|
|||||
package { import flash.display.Sprite; public class ForLoop extends Sprite { private var _arr:Array = [12, 20, 25, 32, 42]; public function ForLoop() { trace(getNearest(38)); } private function getNearest(number:int):int { var lastVal: int = _arr[0]; var result: int = lastVal; var diff: int = 0; _arr.filter( function(item:int, index:int, arr:Array):void { if (item) { diff = (item - number); var curVal:int = diff < 0 ? -diff : diff; // быстрее, чем Math.abs() if (curVal < lastVal) { lastVal = curVal; result = item; } } } ); return result; } } }
__________________
Ко мне можно и нужно обращаться на ты) |
|
|||||
Регистрация: Jan 2013
Сообщений: 322
|
function nearestSearch(arr:Vector.<Number>, v:Number):Number{ var left:uint = 0; var right:uint = arr.length; while(left < right - 1){ var middle:uint = (right - left >> 1) + left; if((v - arr[middle - 1] > arr[middle] - v)){ left = middle; }else{ right = middle; } } return arr[left]; } надо было сразу проскроллить комменты что бы время не тратить caseyryan, зачем filter, когда есть forEach? да и вообще for each. с замыканиями и лишними вызовами, оптимизация Math.abs смешно выглядит ) Последний раз редактировалось nubideus; 27.07.2014 в 20:33. |
|
|||||
Цитата:
__________________
Ко мне можно и нужно обращаться на ты) |
|
|||||
Может я чё-то пропустил в этой жизни, но зачем здесь функции, тем более анонимные, есть же цикл for each:
function getNearest(arr:Vector.<Number>, number:Number):Number { var result:Number; var resultAssigned:Boolean = false; var minDiff:Number; for each (var item:Number in arr) { var diff:Number = item - number; var diffAbs:Number = diff < 0 ? -diff : diff; if (!resultAssigned || diffAbs < minDiff) { resultAssigned = true; minDiff = diffAbs; result = item; } } return result; } |
|
|||||
Регистрация: Jan 2013
Сообщений: 322
|
(все таки сортировка это n*log(n))
в варианте с abs есть баг. [5, 4], 4.5 - с такими значениями выдаст 5, а должно 4. в варианте от caseyryan есть еще один, если первый элемент массива будет нулем, то работать не будет. долго упарывался и родил это private function nearestSearch(arr:Vector.<Number>, v:Number):Number { var pos:Number = Infinity; var neg:Number = -Infinity; var eps:Number = 2.220446049250313e-16; for (var i:uint = 0; i < arr.length; i++) { var el:Number = arr[i]; if ((el - pos) * (el - v + eps) < 0) pos = el; if ((el - neg) * (el - v - eps) < 0) neg = el; } return (v - neg > pos - v) ? pos : neg; } без эпсилонов код будет игнорировать элементы, равные v. суть в том, что оно по идее должно делать то же, что и: if (arr[i] - v >= 0 && arr[i] < pos) pos = arr[i]; if (v - arr[i] >= 0 && neg < arr[i]) neg = arr[i]; private function nearestSearch(arr:Vector.<Number>, v:Number):Number { var result:Number = NaN; var minAbs:Number = Infinity; for (var i:uint = 0; i < arr.length; i++) { var diff:Number = arr[i] - v; var abs:Number = diff < 0 ? -diff : diff; if (abs < minAbs) { minAbs = abs; result = arr[i]; } } return result; } |
|
|||||
Цитата:
Я к тому, что без дополнительных требований тут особо нечего исправлять. |
|
|||||
Регистрация: Jan 2013
Сообщений: 322
|
expl, это баг
Цитата:
Цитата:
|
Часовой пояс GMT +4, время: 02:37. |
|
« Предыдущая тема | Следующая тема » |
|
|