Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flash > ActionScript 3.0

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 26.07.2014, 17:21
inozemcev вне форума Посмотреть профиль Отправить личное сообщение для inozemcev Найти все сообщения от inozemcev
  № 1  
Ответить с цитированием
inozemcev
[+ 1.0 08.10.14]
 
Аватар для inozemcev

блогер
Регистрация: Mar 2010
Адрес: x = stage.stageWidth/2 y= stage.stageHeight/2
Сообщений: 293
Записей в блоге: 2
По умолчанию вернуть максимально ближайшее значение из массива

Нужен алгоритм сортировки массива.

Есть условно массив с некоторым количеством отсортированных чисел от меньшего к большему

Код AS3:
     var arr:Array = [3, 5, 9, 14, 27]
Необходимо по ключу числу вернуть ближайшее значение. Например по ключу 16 должен вернуть число 14 по ключу 35 должен вернуть 27. Если есть идентичное число то должен вернуть его, если по ключу можно вернуть два числа, то есть по ключу 4 в данном случае можно вернуть 3 и 5, то должен вернуть наименьшее.

Старый 26.07.2014, 18:31
nubideus вне форума Посмотреть профиль Отправить личное сообщение для nubideus Найти все сообщения от nubideus
  № 2  
Ответить с цитированием
nubideus

Регистрация: 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
Код AS3:
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.
Старый 27.07.2014, 18:33
expl вне форума Посмотреть профиль Отправить личное сообщение для expl Найти все сообщения от expl
  № 3  
Ответить с цитированием
expl

блогер
Регистрация: Feb 2006
Сообщений: 1,474
Записей в блоге: 3
Бинарный поиск мало кто может написать без ошибок.
Я бы не выпендривался и просто искал элемент, для которого (Math.abs(array[i] - value)) минимально
(будет работать и не для отсортированного списка, сложность линейная)

P.S. На самом деле, бинарный поиск, конечно можно написать, покрыв его дюжиной тестов. Но оно у Вас действительно критичное по производительности место, чтобы включать ради поиска этого элемента мозги? И там действительно будет больше 20-50 элементов? - Иначе бинарный поиск ничего не даст.

Старый 27.07.2014, 19:19
caseyryan вне форума Посмотреть профиль Отправить личное сообщение для caseyryan Найти все сообщения от caseyryan
  № 4  
Ответить с цитированием
caseyryan
 
Аватар для caseyryan

Регистрация: Jun 2012
Адрес: Новосибирск
Сообщений: 6,644
Записей в блоге: 4
Код AS3:
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;
		}
	}
}
__________________
Ко мне можно и нужно обращаться на ты)

Старый 27.07.2014, 19:51
nubideus вне форума Посмотреть профиль Отправить личное сообщение для nubideus Найти все сообщения от nubideus
  № 5  
Ответить с цитированием
nubideus

Регистрация: Jan 2013
Сообщений: 322
Код AS3:
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.
Старый 27.07.2014, 21:14
caseyryan вне форума Посмотреть профиль Отправить личное сообщение для caseyryan Найти все сообщения от caseyryan
  № 6  
Ответить с цитированием
caseyryan
 
Аватар для caseyryan

Регистрация: Jun 2012
Адрес: Новосибирск
Сообщений: 6,644
Записей в блоге: 4
Цитата:
зачем filter, когда есть forEach?
Просто первое, что пришло в голову) Этот вариант, конечно же не претендует на победу в олимпиаде Но эту задачу все равно решает
__________________
Ко мне можно и нужно обращаться на ты)

Старый 28.07.2014, 02:27
expl вне форума Посмотреть профиль Отправить личное сообщение для expl Найти все сообщения от expl
  № 7  
Ответить с цитированием
expl

блогер
Регистрация: Feb 2006
Сообщений: 1,474
Записей в блоге: 3
Может я чё-то пропустил в этой жизни, но зачем здесь функции, тем более анонимные, есть же цикл for each:
Код AS3:
		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;
		}
Хотя уже не важно - бинарный поиск уже написали

Старый 01.08.2014, 01:07
nubideus вне форума Посмотреть профиль Отправить личное сообщение для nubideus Найти все сообщения от nubideus
  № 8  
Ответить с цитированием
nubideus

Регистрация: Jan 2013
Сообщений: 322
(все таки сортировка это n*log(n))

в варианте с abs есть баг. [5, 4], 4.5 - с такими значениями выдаст 5, а должно 4.
в варианте от caseyryan есть еще один, если первый элемент массива будет нулем, то работать не будет.

долго упарывался и родил это
Код AS3:
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;
}
быстрее abs примерно на 30%.
без эпсилонов код будет игнорировать элементы, равные v.

суть в том, что оно по идее должно делать то же, что и:
Код AS3:
if (arr[i] - v >= 0 && arr[i] < pos) pos = arr[i];
if (v - arr[i] >= 0 && neg < arr[i]) neg = arr[i];
код asb(с багом):
Код AS3:
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;
}
все благодаря тому, что (mid - right) * (mid - left) <= 0 делает так: left >= mid && mid <= right || right >= mid && mid <= left.

Старый 02.08.2014, 00:45
expl вне форума Посмотреть профиль Отправить личное сообщение для expl Найти все сообщения от expl
  № 9  
Ответить с цитированием
expl

блогер
Регистрация: Feb 2006
Сообщений: 1,474
Записей в блоге: 3
Цитата:
в варианте с abs есть баг. [5, 4], 4.5 - с такими значениями выдаст 5, а должно 4.
А вы уверены что это баг? Меня в школе учили что 4.5 округляется до 5, а не до 4, хотя вроде-бы на равном расстоянии от обоих чисел

Я к тому, что без дополнительных требований тут особо нечего исправлять.

Старый 02.08.2014, 01:02
nubideus вне форума Посмотреть профиль Отправить личное сообщение для nubideus Найти все сообщения от nubideus
  № 10  
Ответить с цитированием
nubideus

Регистрация: Jan 2013
Сообщений: 322
expl, это баг
Цитата:
Сообщение от inozemcev Посмотреть сообщение
если по ключу можно вернуть два числа, то есть по ключу 4 в данном случае можно вернуть 3 и 5, то должен вернуть наименьшее.
Цитата:
Меня в школе учили что 4.5 округляется до 5, а не до 4
[4, 5], 4.5 - с такими значениями выдаст 4, а должно было 5

Создать новую тему Ответ Часовой пояс GMT +4, время: 16:11.
Быстрый переход
  « Предыдущая тема | Следующая тема »  
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 16:11.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.