Всякие разные штуки сомнительной полезности сделанные в свободное от работы время.
LinkedList в AS3.
Читая про 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 вы, к сожалению, все равно не догоните... Кроме того, это справедливо только для не примитивных типов данных. По всей видимости, в плеере существует какая-то оптимизация для чисельных типов и строк.
Ниже листинги и тест.
Тест:
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(;;)
Не смотря на то, что список не самый быстрый вариант, мне кажеся, что для определенных целей он был бы удобен, например, иногда очень хочется в колбек передать еще какой-нибудь параметр, либо, наоборот, использовать уже существующий метод в качестве колбека - но, увы, у метода неподходящая сигнатура. В таком случае, используя "свой" код вы получаете больше гибкости и даже немного выигрываете в производительности.
Еще один приятный момент - операции типа Array#splice() в списке будут гораздо быстрее, чем в массиве (т.как вам не нужно будет сдвигать зачастую больше половины индексов). Неприятный момент - доступ к элементу по индексу в списке будет гораздо дольше.
Теперь о грустном: для реализации LinkedList кроме самого списка вам понадобится еще один класс-обертка хранящий ссылку на следующий элемент списка. Поэтому, использовать эту структуру с точки зрения рашода памяти не рационально. С другой стороны, если объекты-элементы списка это ваш собственный класс, то, добавить в него требуемый функционал будет очень просто, и, в таком случае перерасхода памяти не будет.
Ниже исходники списка и класса-обертки + утилита - итератор. Листинг не полный, а скорее просто демонстрация возможностей.
В следующем сообщении будут добавлены темплейты для FlashDevelop позволяющие быстро создавать строго-типизированые списки.
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; } } }
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; } } }
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 | |
А вот, собственно, и темплейты:
* Примечания к использованию - чтобы это "заработало" нужно будет создать по 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 | |
true))))
|
Последние записи от wvxvw
- Dired - текстовый проводник по файловой системе (29.06.2013)
- Навигация по HTML с WASD (09.06.2012)
- JavaScript, все не так плохо (07.06.2012)
- Что такое tarball и чем его пакуют (11.04.2012)
- Критика Presentation Model (18.02.2012)