старый добрый swap() — возможен вообще? - Страница 3

Vektor · 17.02.2011, 19:44

Цитата:

Сообщение от Zebestov

Менять надо походу четыре пары по одному условию. И если задуматься об организации swap-а для 12 переменных, с явным указанием на конкретную пару... как-то лучше как у меня сейчас:

Код AS3:

// сортируем вершины
if (sy0 > sy1) {
	swap = sy0;
	sy0 = sy1;
	sy1 = swap;
 
	swap = sx0;
	sx0 = sx1;
	sx1 = swap;
 
	swap = u0;
	u0 = u1;
	u1 = swap;
 
	swap = v0;
	v0 = v1;
	v1 = swap;
}
if (sy1 > sy2) {
	swap = sy1;
	sy1 = sy2;
	sy2 = swap;
 
	swap = sx1;
	sx1 = sx2;
	sx2 = swap;
 
	swap = u1;
	u1 = u2;
	u2 = swap;
 
	swap = v1;
	v1 = v2;
	v2 = swap;
}
if (sy0 > sy1) {
	swap = sy0;
	sy0 = sy1;
	sy1 = swap;
 
	swap = sx0;
	sx0 = sx1;
	sx1 = swap;
 
	swap = u0;
	u0 = u1;
	u1 = swap;
 
	swap = v0;
	v0 = v1;
	v1 = swap;
}

По крайней мере свернул и забыл

а быстрее точно не будет.

А если попробовать так.
При условии, что значения нужно отдать после сортировки.

Код AS3:

// меняем значения вершин
var swapSy0Sy1:Boolean=false;
var swapSy1Sy2:Boolean=false;
 
if (sy0 > sy1) {
	swapSy0Sy1=true;
}
if (sy1 > sy2) {
	swapSy1Sy2=true;
}
if(swapSy0Sy1){
cord0=sy1
cord1=sy0
}
if(swapSy1Sy2){
cord1=sy2
cord2=sy1
}

Zebestov · 17.02.2011, 19:47

Предложенный алгоритм не эквивалентен моему. Посмотри внимательней, что он делает и как )

Vektor · 17.02.2011, 20:07

Правильно, ваш алгоритм меняет значения в переменых, А на Б и Б на А.
Мой алгоритм меняет А и Б местом(А становится Б, а Б становится А), что аналогично, при условии что значения нужно отдать.
при этом не каких операций с сортировкой не ведется.

BlooDHounD · 17.02.2011, 20:07

а запись в одну строчку не прокатит? я обычно так и пишу

Zebestov · 17.02.2011, 20:18

Vektor, алгоритмы разные по результату, а не по стилю его выдачи. Подсказка: повтор первого сравнения с последующей перестановкой в конце алгоритма — это не опечатка.

BlooDHounD, да как-то хрен редьки не слаще ) все равно этот рулончик живет в свернутом виде.

i.o. · 17.02.2011, 20:55

Еще как вариант могу предложить класс NumberRef, который хранит значение числа.

NumberRef.as

Код AS3:

package  
{
	public class NumberRef 
	{
 
		public static function swap( a:NumberRef, b:NumberRef ):void
		{
			var swapTemp:Number = a.value;
			a.value = b.value;
			b.value = swapTemp;
		}
 
 
		public function NumberRef( value:Number=NaN ) 
		{
			this.value = value;
		}
 
 
		public var value:Number;
 
	}
}

Отстает от ручной перемены значений ненамного:

Array/*Number*/:

Цитата:

PlayerVersion: WIN 10,1,102,64
PlayerType: StandAlone
PlayerIsDebugger: false
---------------------
_generateRandomNums( 12000000 ) -> time: 8177 ms
_testCost$Brute() -> time: 228 ms
_testCost$Ref() -> time: 260 ms
_testSwaping$Brute() -> time: 276 ms
_testSwaping$Ref() -> time: 369 ms

Vector.<Number>:

Цитата:

PlayerVersion: WIN 10,1,102,64
PlayerType: StandAlone
PlayerIsDebugger: false
---------------------
_generateRandomNums( 12000000 ) -> time: 702 ms
_testCost$Brute() -> time: 821 ms
_testCost$Ref() -> time: 890 ms
_testSwaping$Brute() -> time: 876 ms
_testSwaping$Ref() -> time: 965 ms

_testCost*() - оценка времени работы функции без свапинга
_testSwaping*() - оценка времени работы функции со свапингом
При вычитании одного из другого, можем оценить насколько отличается время самого свапинга.

Заодно выяснилось (в принципе оно давно было известно), что Vector.<> по времени доступа - тормоз. Но зато скорость записи случайных чисел достойна всех похвал

Код класса с тестами:

Main.as

Код AS3:

package 
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.system.Capabilities;
	import flash.system.System;
	import flash.text.TextField;
	import flash.utils.getTimer;
	import flash.utils.setTimeout;
 
	[SWF(width='620', height='420', frameRate='30', scriptTimeLimit='60', scriptRecursionLimit='1000')]
	public class Main extends Sprite 
	{
 
		public function Main():void 
		{
			_txtOutput = new TextField();
			_txtOutput.x = 10;
			_txtOutput.y = 10;
			_txtOutput.width = 600;
			_txtOutput.height = 400;
			_txtOutput.text = "";
			_txtOutput.border = true;
			this.addChild( _txtOutput );
 
			_addLog( "PlayerVersion: " + Capabilities.version );
			_addLog( "PlayerType: " + Capabilities.playerType );
			_addLog( "PlayerIsDebugger: " + Capabilities.isDebugger );
			_addLog( "---------------------" );
 
			setTimeout( _startTest, 1000 );
		}
 
 
 
		private var _txtOutput:TextField;
 
		private var _randomNums:Array/*Number*/;
	//	private var _randomNums:Vector.<Number>;
 
 
 
		private function _startTest():void
		{
			var tm:uint;
			var total:uint = 12 * 1000 * 1000;
 
			tm = getTimer();
			_generateRandomNums( total );
			_addLog( "_generateRandomNums( " + total + " ) -> time: " + (getTimer() - tm) + " ms" );
 
			tm = getTimer();
			_testCost$Brute();
			_addLog( "_testCost$Brute() -> time: " + (getTimer() - tm) + " ms" );
 
			tm = getTimer();
			_testCost$Ref();
			_addLog( "_testCost$Ref() -> time: " + (getTimer() - tm) + " ms" );
 
			tm = getTimer();
			_testSwaping$Brute();
			_addLog( "_testSwaping$Brute() -> time: " + (getTimer() - tm) + " ms" );
 
			tm = getTimer();
			_testSwaping$Ref();
			_addLog( "_testSwaping$Ref() -> time: " + (getTimer() - tm) + " ms" );
		}
 
		private function _addLog( message:String ):void
		{
			_txtOutput.appendText( message + "\n" );
		}
 
		private function _generateRandomNums( total:uint=1000 ):void
		{
			_randomNums = [];
		//	_randomNums = new Vector.<Number>( total, true );
 
			while( total-- )
			{
				_randomNums[total] = Math.random();
			}
		}
 
		private function _testCost$Brute():void
		{
			var sx0:Number;
			var sx1:Number;
			var sx2:Number;
 
			var sy0:Number;
			var sy1:Number;
			var sy2:Number;
 
			var u0:Number;
			var u1:Number;
			var u2:Number;
 
			var v0:Number;
			var v1:Number;
			var v2:Number;
 
			var swap:Number;
 
 
			var i:int = -1;
			var l:int = int(_randomNums.length / 12);
			while( ++i < l )
			{
				sx0 = _randomNums[i + 0];
				sx1 = _randomNums[i + 1];
				sx2 = _randomNums[i + 2];
 
				sy0 = _randomNums[i + 3];
				sy1 = _randomNums[i + 4];
				sy2 = _randomNums[i + 5];
 
				u0 = _randomNums[i + 6];
				u1 = _randomNums[i + 7];
				u2 = _randomNums[i + 8];
 
				v0 = _randomNums[i + 9];
				v1 = _randomNums[i + 10];
				v2 = _randomNums[i + 11];
			}
		}
		private function _testSwaping$Brute():void
		{
			var sx0:Number;
			var sx1:Number;
			var sx2:Number;
 
			var sy0:Number;
			var sy1:Number;
			var sy2:Number;
 
			var u0:Number;
			var u1:Number;
			var u2:Number;
 
			var v0:Number;
			var v1:Number;
			var v2:Number;
 
			var swap:Number;
 
 
			var i:int = -1;
			var l:int = int(_randomNums.length / 12);
			while( ++i < l )
			{
				sx0 = _randomNums[i + 0];
				sx1 = _randomNums[i + 1];
				sx2 = _randomNums[i + 2];
 
				sy0 = _randomNums[i + 3];
				sy1 = _randomNums[i + 4];
				sy2 = _randomNums[i + 5];
 
				u0 = _randomNums[i + 6];
				u1 = _randomNums[i + 7];
				u2 = _randomNums[i + 8];
 
				v0 = _randomNums[i + 9];
				v1 = _randomNums[i + 10];
				v2 = _randomNums[i + 11];
 
 
				// сортируем вершины
				if (sy0 > sy1)
				{
					swap = sy0;
					sy0 = sy1;
					sy1 = swap;
 
					swap = sx0;
					sx0 = sx1;
					sx1 = swap;
 
					swap = u0;
					u0 = u1;
					u1 = swap;
 
					swap = v0;
					v0 = v1;
					v1 = swap;
				}
				if (sy1 > sy2)
				{
					swap = sy1;
					sy1 = sy2;
					sy2 = swap;
 
					swap = sx1;
					sx1 = sx2;
					sx2 = swap;
 
					swap = u1;
					u1 = u2;
					u2 = swap;
 
					swap = v1;
					v1 = v2;
					v2 = swap;
				}
				if (sy0 > sy1)
				{
					swap = sy0;
					sy0 = sy1;
					sy1 = swap;
 
					swap = sx0;
					sx0 = sx1;
					sx1 = swap;
 
					swap = u0;
					u0 = u1;
					u1 = swap;
 
					swap = v0;
					v0 = v1;
					v1 = swap;
				}
			}
		}
 
		private function _testCost$Ref():void
		{
			var sx0:NumberRef = new NumberRef();
			var sx1:NumberRef = new NumberRef();
			var sx2:NumberRef = new NumberRef();
 
			var sy0:NumberRef = new NumberRef();
			var sy1:NumberRef = new NumberRef();
			var sy2:NumberRef = new NumberRef();
 
			var u0:NumberRef = new NumberRef();
			var u1:NumberRef = new NumberRef();
			var u2:NumberRef = new NumberRef();
 
			var v0:NumberRef = new NumberRef();
			var v1:NumberRef = new NumberRef();
			var v2:NumberRef = new NumberRef();
 
			var i:int = -1;
			var l:int = int(_randomNums.length / 12);
			while( ++i < l )
			{
				sx0.value = _randomNums[i + 0];
				sx1.value = _randomNums[i + 1];
				sx2.value = _randomNums[i + 2];
 
				sy0.value = _randomNums[i + 3];
				sy1.value = _randomNums[i + 4];
				sy2.value = _randomNums[i + 5];
 
				u0.value = _randomNums[i + 6];
				u1.value = _randomNums[i + 7];
				u2.value = _randomNums[i + 8];
 
				v0.value = _randomNums[i + 9];
				v1.value = _randomNums[i + 10];
				v2.value = _randomNums[i + 11];
			}
		}
		private function _testSwaping$Ref():void
		{
			var sx0:NumberRef = new NumberRef();
			var sx1:NumberRef = new NumberRef();
			var sx2:NumberRef = new NumberRef();
 
			var sy0:NumberRef = new NumberRef();
			var sy1:NumberRef = new NumberRef();
			var sy2:NumberRef = new NumberRef();
 
			var u0:NumberRef = new NumberRef();
			var u1:NumberRef = new NumberRef();
			var u2:NumberRef = new NumberRef();
 
			var v0:NumberRef = new NumberRef();
			var v1:NumberRef = new NumberRef();
			var v2:NumberRef = new NumberRef();
 
			var i:int = -1;
			var l:int = int(_randomNums.length / 12);
			while( ++i < l )
			{
				sx0.value = _randomNums[i + 0];
				sx1.value = _randomNums[i + 1];
				sx2.value = _randomNums[i + 2];
 
				sy0.value = _randomNums[i + 3];
				sy1.value = _randomNums[i + 4];
				sy2.value = _randomNums[i + 5];
 
				u0.value = _randomNums[i + 6];
				u1.value = _randomNums[i + 7];
				u2.value = _randomNums[i + 8];
 
				v0.value = _randomNums[i + 9];
				v1.value = _randomNums[i + 10];
				v2.value = _randomNums[i + 11];
 
 
				// сортируем вершины
				if( sy0.value > sy1.value )
				{
					NumberRef.swap( sy0, sy1 );
					NumberRef.swap( sx0, sx1 );
					NumberRef.swap( u0, u1 );
					NumberRef.swap( v0, v1 );
				}
				if( sy1.value > sy2.value )
				{
					NumberRef.swap( sy1, sy2 );
					NumberRef.swap( sx1, sx2 );
					NumberRef.swap( u1, u2 );
					NumberRef.swap( v1, v2 );
				}
				if( sy0.value > sy1.value )
				{
					NumberRef.swap( sy0, sy1 );
					NumberRef.swap( sx0, sx1 );
					NumberRef.swap( u0, u1 );
					NumberRef.swap( v0, v1 );
				}
			}
		}
	}
 
}

Rzer · 17.02.2011, 21:08

Код AS3:

var a:int = 10;
var b:int = 20;
 
a = swap(b, b = a);
 
trace(a, b);
 
 
public function swap (val1:Number, val2:Number):int {
	return val1;
}

i.o. · 17.02.2011, 21:30

Код AS3:

var a:int = 10;
var b:int = 20;
 
a = b + 0*(b = a);
 
trace(a, b);

Vektor · 17.02.2011, 21:44

Вот тут выкладываю, логику моего алгоритма.

Код AS3:

// меняем значения вершин
var swapSy0Sy1:Boolean=false;
var swapSy0Sy2:Boolean=false;
var swapSy1Sy2:Boolean=false;
 
 
if (sy0 > sy1) {
	swapSy0Sy1=true;
}else {
//Нечего не меняем.
}
if(swapSy0Sy1){
  if (sy0 > sy2) {
swapSy0Sy2=true;
  } else {
//Выдаем значения.
     sy0(= sy1)
     sy1(= sy0)
     sx0(= sx1)
     sx1(= sx0)
     u0(=u1)
     u1(=u0)
     v0(=v1)
     v1(=v0)
 
}
}
if(swapSy0Sy2){
  if (sy1 > sy2) {
swapSy1Sy2=true;
  } else {
//Выдаем значения.
         sy0(=sy2)
	sy2(=sy0)
	sx0(=sx2)
	sx2(=sx0)
	u0(=u2)
	u2(=u0)
	v0(=v2)
	v2(=v0)
 
}
}
if(swapSy1Sy2){
//Выдаем значения.
         sy1(=sy2)
	sy2(=sy1)
	sx1(=sx2)
	sx2(=sx1)
	u1(=u2)
	u2(=u1)
	v1(=v2)
	v2(=v1)
 
}

Если, что-то неверно в логике пишите.

P/S Конечно, тут кое что нужно дописать, но алгоритм рассчитан, сортировать не сортируя, человек должен скомпилить логику и выдать нагора результат, при условии что нужна скорость. Компьютер может делать умножения, но зачем это делать, если нужен только результат...

Rzer · 17.02.2011, 21:47

Тогда уж: a = a + b - (b = a); Чтобы без умножения)) это нужно на олимпиадах по информатике давать =)