Отсортировать ключи из Dictionary в dense Array по значениям?

[wvxvw]

Вот, столкнулся с проблемным алгоритмом, никак не найду хорошее решение.
Что есть:

Dictionary /*Object, int*/
{
    obj1 => 100,
    obj2 => 25,
    obj3 => -1,
    obj4 => 200
}

нужно получить на выходе:

Array /*Object*/ [ obj2, obj1, obj4, obj3 ]

( любые отрицательные значения добавляются в конец массива вне зависимости от того, на сколько они отрицательные)
Как ни сделаю, все очень медленно получается...

[Gaen]

Наряду с Dictionary держать массив, и при добавлении элементов сразу вставлять их в нужное место. Проигрыш в памяти, выигрыш в вычислительных ресурсах.

[wvxvw]

Не получится, в Dictionary должны быть слабые ключи... да и таким образом мы выиграем на нахождении и проиграем при добавлении, что, вобщем-то будет так на так...

[Gaen]

Ну добавлять обычно реже приходится, чем искать
Плюс по Dictionary искать придется перебором, а в отсортированный массив можно добавлять скажем бинарными вставками.
А зачем weak keys?

[wvxvw]

Это все для той же системы сигнал-слот. Добавляются колбеки. нужно отсортировать по priority.

Да, кстати, сейчас поэксперементировал с нативным диспатчером, если добавлять с разной priority то добавление слушаетелей отнимает кучу времени... просто ну очень много. Т.е. там скорее всего сделано, как ты и предлагаешь.
Т.е. по тестам получилось:

EventDispatcher
addEventListener: 10446
dispatchEvent: 67

Signal
add: 167
call: 7975

[silin]

вариант

private function sortDict(dict:Dictionary):Array
{
	var nArr:Array = [];
	var pArr:Array = [];
	//раскидываем на два массива
	for ( var obj:Object in dict ) 
	{
		if (dict[obj] < 0)
		{
			nArr.push(obj);
		}else
		{
			pArr.push( { val:dict[obj], obj:obj } );
		}
	}
	//положительный сортируем 
	pArr.sortOn(["val"], Array.NUMERIC);
 
	var res:Array = [];
	for (var i:int = 0; i < pArr.length; i++) 
	{
		res.push(pArr[i].obj);
	}
	// добавляем отрицательный
	return res.concat(nArr);
}

[wvxvw]

Спасибо, я по похожему пути в итоге и пошел (только решил добавлять сразу в Dictionary объекты со ссылками на priority и слушателя - хотя, надо ще подумать, может быть так будет выгоднее...).

[silin]

ага, обогнать родной sort (хотя он вроде бы и просто пузырьковый) все равно не получится (если у кого есть примеры, очень хочу)
т.е. вопрос в оптимизации структуры, чтобы с меньшими потерями сгенерить массив, который этому сорту подсунуть,
тут 'объекты со ссылками на priority' скорее всего выиграют

[wvxvw]

Если в массиве только чисельные типы, то можно, мне где-то попадлася... Shell сортом. Для сложных объектов - не знаю, но и флеш сложные объекты тоже долго сортитует
Да, и флешевый сорт он какой-то не очень пузырьковый... посмотри в каком порядке он аргументы выдает в колбек... т.е. он как-то с середины начинает. В смысле, алгоритм может быть и тот же, но не классическая реализация.

PS: http://blog.inspirit.ru/?p=271

[silin]

>>http://blog.inspirit.ru/?p=271
спасибо, отличный материал
интересная вещь походу выяснилась: смотрю код, который автор дает, и вижу совершенно противоположные результаты, чем во флешке на сайте..
оказалось, что в дебаговой версии (у него пример под трейсы заточен) встроенный сорт все равно обгоняет любой самописный
//-debug=true
Flash Sort:135 (самый быстрый в релизной версии)
array.sort:90

//-debug=false
Flash Sort:47
array.sort:95

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