Подскажите эффективный способ упорядочения объектов в контейнере

[mikhailk]

Задача стандартная. Есть containerObjects, в котором порядка 10-40 объектов. В общем случае все они могут двигаться.

По таймеру вызываем функцию, которая заменяет индексы у объектов containerObjects в соответствии с их позицией y (чем больше y - тем больше индекс).

Вариант 1 я сделал с массивом, но он мне реально не понравился, поскольку вылезли тормоза:

	var objectsList:Array = new Array();
	for(var i:int=0;i<containerObjects.numChildren;i++) {
		var currObj:Object = containerObjects.getChildAt(i);
		var objectY:int = currObj.y;
		objectsList.push({object:currObj, objY:objectY});
	}			
	objectsList.sortOn(["objY"]);
	for(var i = 0; i < objectsList.length; i++) {
		containerObjects.setChildIndex(object, i);
	}

Потом я еще поэксперементировал со swapChildren (тут в одной из тем было), но тоже получается не очень.

Интересует максимально простое решение.

[Котяра]

при большом количестве объектов для пересортировки нужно использовать разделение на сетки
кроме того сортировать только те объекты у которых реально поменялись координаты y c прошлой сортировки.

[mikhailk]

ну, у меня все-таки не 5000 объектов, к счастью... )))

конкретный пример

10 объектов, индексы упорядочены по возрастанию. Объект с индексом 1 встал перед объектом с индексом 5, а объект с индексом 8 встал за ними обоими. Поменялись координаты у объектов 1 и 8, но сортировать нужно 1, 5 и 8. Это я к тому, что сортировкой только переместившихся не обойтись, наверное.

[bicubic_bublic]

сортировка массива. сложность: n * ln(n);
изменение положение одного элемента в упорядоченном массиве: ln(n)

[mikhailk]

это понятно
просто в примере, который я привел, нужно еще выяснить, кто с кем перекрывается. Двигались-то 1-й и 8-й, а упорядочивать нужно 1-й, 5-й и 8-й. Т.е, этого 5-го еще нужно вычислить.

или я неправильно понял?

или так?

1. вычленяем те объекты, которые двигались
2. каждого из них по очереди упорядочиваем в массиве, начиная с того, у которого y меньше и далее по возрастанию

[Zebestov]

private function sortChildren(mc:MovieClip):void
{
   var arr:Array = [];
   var num:uint = mc.numChildren;
   var i:uint;
   var chld:MovieClip;
   for (i = 0; i < num; i++)
   {
      chld = mc.getChildAt(i);
      arr.push([chld.y, chld]);
   }
   arr.sort();
   for (i = 0; i < num; i++)
   {
      mc.setChildIndex(arr[i][1], num-1)
   }   
}

честно - не проверял нифига на скорость, но может так будет хоть немного быстрее?
а то как-то у тебя выходит, что для серьезных методов объектов маловато, но несерьезные все равно тормозят =) вот еще один несерьезный... по сути немного модифицированый твой.

[mikhailk]

ок, проверю потом ))
реализовал уже через swapChildren по каждому двигающемуся объекту.
но теперь приходится тащить признаки перемещения и отслеживать их.

кстати, про оптимизацию, где-то проскакивало, что еще while(i--) работает быстрее, чем for(i...

[gloomyBrain]

Для 40 объектов - как могут быть тормоза? =)
Попробуйте изначально все объекты пихать в массив (при создании) - тогда Вам не нужно будет при каждой сортировке создавать новый массив из дисплей листа.

[Котяра]

вот у меня (для теста) 50 персов двигаются. При каждом движении (перерисовка по таймеру раз в 10 мс - тоже для теста, в реале можно увеличить) идёт пересчёт глубины для поменявших позицию y.
Тормоза, в принципе, заметны когда двигаются все 50, хотя не совсем ясно в чём дело: или в сортировке или в отрисовке (хотя отрисовка идёт постоянно, даже для стоящих на месте)
примерчик (1.5. Мб)
ps: глюкает хост (временно недоступен)

[derhab]

метод в классе контейнера детей которого нужно сортировать, list - список всех объектов подлежащих сортировке...они туда сразу после добавления на сцену заносятся

public function zSort():void
{	
	list.sortOn('y', Array.NUMERIC);
	var l:int = list.length;
 
	while (l--) {
		var o:DisplayObject = list[l] as DisplayObject;
		if (getChildAt(l) != o) setChildIndex(o, l);
	}
}

хотя не совсем ясно в чём дело: или в сортировке или в отрисовке

так отключи сортировку и станет ясно