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

Вернуться   Форум Flasher.ru > Блоги > e4xu

Всякие разные штуки сомнительной полезности сделанные в свободное от работы время.
Оценить эту запись

LinkedList в AS3.

Запись от wvxvw размещена 26.12.2009 в 02:29
Обновил(-а) wvxvw 26.12.2009 в 02:32

Читая про HaXe узнаешь много нового про AS3 Вот, недавно прочитал о том, как работает массив в AS3:
http://ncannasse.fr/blog/flash_9_optimizations?lang=en
И, естесственно, попробовал воплотить идею в жизнь:
Для тех, кто не в курсе, что такое LinkedList (или просто List)
http://en.wikipedia.org/wiki/Linked_...sts_vs._arrays

Итак, вобщем списки должны быть медленнее массивов в плане итерации, кроме того, для универсальной реализации списка в AS3 нам еще и прийдется пожертвовать большим количеством памяти, т.как на каждый элемент списка (если этот элемент не подготовлен специально для использования в нем - об этом дальше) прийдется создать по "объекту-указателью". Но, есть ситуации, когда оно того стоит.
Пример - вам нравится функциональный дизайн в работе с массивами, но, как вы уже наверное знаете, в виду того, что вызов функции в AS3 медленный, этот подход, как правило, не практичен. Используя список, вы сможете ускорить аналог Array#map() в 1,5-2 раза! Но обычный for(;;) и for-each вы, к сожалению, все равно не догоните... Кроме того, это справедливо только для не примитивных типов данных. По всей видимости, в плеере существует какая-то оптимизация для чисельных типов и строк.

Ниже листинги и тест.

Тест:
Код AS3:
package tests 
{
	//{ imports
	import flash.display.Sprite;
	import flash.geom.Rectangle;
	import flash.text.TextField;
	import flash.utils.getTimer;
	import org.wvxvws.data.DataList;
	import org.wvxvws.data.ListIterator;
	//}
 
	/**
	 * TestLinkedList class.
	 * @author wvxvw
	 * @langVersion 3.0
	 * @playerVersion 10.0.32
	 */
	public class TestLinkedList extends Sprite
	{
		//--------------------------------------------------------------------------
		//
		//  Constructor
		//
		//--------------------------------------------------------------------------
 
		public function TestLinkedList() 
		{
			super();
			var dl:DataList;
			var a:Array = [];
			var i:int = 100000;
			var s:String;
			var tf:TextField = new TextField();
			super.addChild(tf);
			while (i--) a.push(new Rectangle());
			dl = DataList.fromArray(a, Rectangle);
 
			var t:int = getTimer();
			a.map(forMap);
			s = (getTimer() - t).toString() + "\r";
 
			t = getTimer();
			dl.map(forMap);
			s += (getTimer() - t).toString() + "\r";
 
			t = getTimer();
			for each (var r:Rectangle in a) this.forMap(r);
			s += (getTimer() - t).toString() + "\r";
 
			t = getTimer();
			for (i = 0; i < 100000; i++) this.forMap(a[i], i);
			s += (getTimer() - t).toString() + "\r";
			tf.text = s;
		}
 
		//--------------------------------------------------------------------------
		//
		//  Public methods
		//
		//--------------------------------------------------------------------------
 
		public function forMap(item:Rectangle, index:int = 0, all:Array = null):void
		{
 
		}
	}
}
* Почему вместо трейса используется текстовое поле? - дело в том, что скорость вызова функции сильно отличается в режиме дебаггера и в обычном. Естественно, потому, что дебаггер не просматривает нативные методы массива. Если вы попробуете заменить вывод в текстовое поле выводом в консоль, то увидите совсем другие результаты.

Код:
32..50 - Array#map()
20..24 - DataList#map()
13..14 - for-each
11     - for(;;)
За 10 запусков на моем 2.13х2 интеле я получил вот такие вот результаты.

Не смотря на то, что список не самый быстрый вариант, мне кажеся, что для определенных целей он был бы удобен, например, иногда очень хочется в колбек передать еще какой-нибудь параметр, либо, наоборот, использовать уже существующий метод в качестве колбека - но, увы, у метода неподходящая сигнатура. В таком случае, используя "свой" код вы получаете больше гибкости и даже немного выигрываете в производительности.
Еще один приятный момент - операции типа Array#splice() в списке будут гораздо быстрее, чем в массиве (т.как вам не нужно будет сдвигать зачастую больше половины индексов). Неприятный момент - доступ к элементу по индексу в списке будет гораздо дольше.

Теперь о грустном: для реализации LinkedList кроме самого списка вам понадобится еще один класс-обертка хранящий ссылку на следующий элемент списка. Поэтому, использовать эту структуру с точки зрения рашода памяти не рационально. С другой стороны, если объекты-элементы списка это ваш собственный класс, то, добавить в него требуемый функционал будет очень просто, и, в таком случае перерасхода памяти не будет.

Ниже исходники списка и класса-обертки + утилита - итератор. Листинг не полный, а скорее просто демонстрация возможностей.
В следующем сообщении будут добавлены темплейты для FlashDevelop позволяющие быстро создавать строго-типизированые списки.
Код AS3:
package org.wvxvws.data 
{
	//{ imports
	import flash.events.EventDispatcher;
	import flash.utils.getQualifiedClassName;
	//}
 
	/**
	 * DataList class.
	 * @author wvxvw
	 * @langVersion 3.0
	 * @playerVersion 10.0.32
	 */
	public class DataList extends EventDispatcher
	{
		//--------------------------------------------------------------------------
		//
		//  Public properties
		//
		//--------------------------------------------------------------------------
 
		public function get length():uint { return _length; }
 
		//--------------------------------------------------------------------------
		//
		//  Protected properties
		//
		//--------------------------------------------------------------------------
 
		protected static const pool:DataList = new DataList(ListCell);
 
		protected var _first:ListCell;
		protected var _type:Class;
		protected var _length:uint;
		protected var _iterator:ListIterator;
 
		//--------------------------------------------------------------------------
		//
		//  Internal properties
		//
		//--------------------------------------------------------------------------
 
		internal function get first():ListCell { return _first; }
 
		//--------------------------------------------------------------------------
		//
		//  Constructor
		//
		//--------------------------------------------------------------------------
 
		public function DataList(type:Class) 
		{
			super();
			this._type = type;
			this._first = new ListCell(null, null);
		}
 
		//--------------------------------------------------------------------------
		//
		//  Public static methods
		//
		//--------------------------------------------------------------------------
 
		public static function fromArray(input:Array, type:Class):DataList
		{
			var dl:DataList = new DataList(type);
			var cell:ListCell = dl._first;
			var newCell:ListCell;
			for each (var o:Object in input)
			{
				if (!(o is type)) continue;
				if (pool.length) newCell = pool.pop();
				else newCell = new ListCell(null, null);
				cell.target = o;
				cell.next = newCell;
				cell = newCell;
			}
			return dl;
		}
 
		//--------------------------------------------------------------------------
		//
		//  Public methods
		//
		//--------------------------------------------------------------------------
 
		public function add(item:Object, position:int = -1):void
		{
			if (!(item is _type)) return;
			position = Math.min(Math.max(-1, position), this._length);
			var freeCell:ListCell;
			var seekCell:ListCell;
			var i:int;
			var nextCell:ListCell = _first;
			var prevCell:ListCell;
 
			if (pool.length) freeCell = pool.pop();
			else freeCell = new ListCell(item, null);
			if (position < 0)
			{
				seekCell = this._first;
				this._first = freeCell;
			}
			else
			{
				while (nextCell.next)
				{
					prevCell = nextCell;
					nextCell = nextCell.next;
					if (++i == position)
					{
						seekCell = nextCell;
						break;
					}
				}
			}
			freeCell.next = seekCell;
			if (prevCell) prevCell.next = freeCell;
			this._length++;
			super.dispatchEvent(new SetEvent(SetEvent.ADD, position));
		}
 
		public function remove(item:Object):Object
		{
			if (!(item is _type)) return null;
			var i:int;
			var cell:ListCell = _first;
			var prev:ListCell;
			var ret:Object;
			while (cell.next)
			{
				prev = cell;
				cell = cell.next;
				i++;
				if (cell.target === item)
				{
					ret = cell.target;
					prev.next = cell.next;
					this._length--;
					break;
				}
			}
			if (this._iterator && cell && this._iterator.current === cell)
			{
				this._iterator.reset();
			}
			super.dispatchEvent(new SetEvent(SetEvent.REMOVE, i));
			return ret;
		}
 
		public function seek(position:int):Object
		{
			var i:int;
			var cell:ListCell = _first;
			while (cell.next)
			{
				cell = cell.next;
				if (++i == position) return cell.target as _type;
			}
			return null;
		}
 
		public function find(item:Object):int
		{
			var i:int;
			var cell:ListCell = _first;
			while (cell.next)
			{
				cell = cell.next;
				i++;
				if (cell.target === item) return i;
			}
			return -1;
		}
 
		public function getIterator(reset:Boolean = true):ListIterator
		{
			if (!this._iterator) this._iterator = new ListIterator(this);
			if (reset) this._iterator.reset();
			return this._iterator;
		}
 
		public function clean(usePool:Boolean = true):void
		{
			this._length = 0;
			var cell:ListCell = this._first;
			var nextCell:ListCell;
			while (cell.next)
			{
				nextCell = cell.next;
				cell.next = null;
				cell.target = null;
				if (usePool) pool.add(cell);
				cell = nextCell;
			}
		}
 
		public function map(callback:Function):void
		{
			var cell:ListCell = this._first;
			var i:int;
			while (cell.next)
			{
				callback(cell.target, i);
				i++;
				cell = cell.next;
			}
		}
 
		public override function toString():String
		{
			var ret:String = "DataList<" + getQualifiedClassName(_type) + ">{";
			var i:int;
			var cell:ListCell = _first;
			while (cell.next)
			{
				ret += i + ": " + cell.target + ", ";
				cell = cell.next;
				i++;
			}
			if (ret.charAt(ret.length - 1) === " ")
				ret = ret.substr(0, ret.length - 2);
			return ret + "}";
		}
 
		//--------------------------------------------------------------------------
		//
		//  Protected methods
		//
		//--------------------------------------------------------------------------
 
		protected function pop():ListCell
		{
			if (!this._length) return null;
			var ret:ListCell = this._first;
			this._first = this._first.next;
			this._length--;
			if (this._iterator && this._iterator.current === ret)
			{
				this._iterator.reset();
			}
			return ret;
		}
	}
}
Код AS3:
package org.wvxvws.data 
{
	/**
	 * ListCell class.
	 * @author wvxvw
	 * @langVersion 3.0
	 * @playerVersion 10.0.32
	 */
	public class ListCell
	{
		//--------------------------------------------------------------------------
		//
		//  Public properties
		//
		//--------------------------------------------------------------------------
 
		public var target:Object;
		public var next:ListCell;
 
		//--------------------------------------------------------------------------
		//
		//  Constructor
		//
		//--------------------------------------------------------------------------
 
		public function ListCell(target:Object, next:ListCell)
		{
			super();
			this.target = target;
			this.next = next;
		}
	}
}
Код AS3:
package org.wvxvws.data 
{
	/**
	 * ListIterator class.
	 * @author wvxvw
	 * @langVersion 3.0
	 * @playerVersion 10.0.32
	 */
	public class ListIterator
	{
		//--------------------------------------------------------------------------
		//
		//  Public properties
		//
		//--------------------------------------------------------------------------
 
		public function get position():int { return _position; }
 
		//--------------------------------------------------------------------------
		//
		//  Protected properties
		//
		//--------------------------------------------------------------------------
 
		protected var _list:DataList;
		protected var _position:int = -1;
		protected var _current:ListCell;
 
		//--------------------------------------------------------------------------
		//
		//  Internal properties
		//
		//--------------------------------------------------------------------------
 
		internal function get current():ListCell { return _current; }
 
		//--------------------------------------------------------------------------
		//
		//  Constructor
		//
		//--------------------------------------------------------------------------
 
		public function ListIterator(list:DataList) 
		{
			super();
			this._list = list;
			this._current = list.first;
		}
 
		//--------------------------------------------------------------------------
		//
		//  Public methods
		//
		//--------------------------------------------------------------------------
 
		public function next():Object
		{
			var ret:Object;
			if (!this._current.next) return null;
			ret = this._current.target;
			this._position++;
			this._current = this._current.next;
			return ret;
		}
 
		public function reset():void
		{
			this._current = this._list.first;
			this._position = -1;
		}
 
		public function getCurrent():Object { return _current.target; }
 
		public function hasNext():Boolean { return this._current.next !== null; }
	}
}
Всего комментариев 2

Комментарии

Старый 28.12.2009 06:18 wvxvw вне форума
wvxvw
 
Аватар для wvxvw
А вот, собственно, и темплейты:
* Примечания к использованию - чтобы это "заработало" нужно будет создать по 1 экземпляру из каждого темплейта. Сразу же после создания нового класса появится следующий prompt-диалог, где нужно ввести тип списка. Пример, если вы хотите создать List<String> - нужно впечатать String.
Дальше - классы будут созданы с правильными именами, но, к сожалению, они не будут совпадать с именами файлов. Возможно я что-нибудь придумаю по этому поводу, но пока что-то ничего в голову не приходит - так что, вам прийдется откыть каждый из соданых классов, скопировать имя класса и переименовать файл используя имя класса - не удобно, но лучшего я предложить не могу...

Темплейты:
http://e4xu.googlecode.com/files/list-templates.zip
(Все одной пачкой не влезли - так что выложил сюда)

http://code.google.com/p/e4xu/source...rg/wvxvws/data
(Тут находится рабочая версия, с дополнениями и поправками)
Старый 28.12.2009 13:50 tas вне форума
tas
true))))
 

 


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


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