Форум Flasher.ru

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)
-   ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)
-   -   Отсортировать ключи из Dictionary в dense Array по значениям? (http://www.flasher.ru/forum/showthread.php?t=136296)

wvxvw 13.02.2010 21:51

Отсортировать ключи из Dictionary в dense Array по значениям?
 
Вот, столкнулся с проблемным алгоритмом, никак не найду хорошее решение.
Что есть:
Код:

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

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

Array /*Object*/ [ obj2, obj1, obj4, obj3 ]
( любые отрицательные значения добавляются в конец массива вне зависимости от того, на сколько они отрицательные)
Как ни сделаю, все очень медленно получается...

Gaen 13.02.2010 22:32

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

wvxvw 13.02.2010 22:51

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

Gaen 13.02.2010 23:38

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

wvxvw 14.02.2010 00:04

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

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

Код:

EventDispatcher
addEventListener: 10446
dispatchEvent: 67

Код:

Signal
add: 167
call: 7975


silin 14.02.2010 00:15

вариант
Код AS3:

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 14.02.2010 00:45

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

silin 14.02.2010 01:37

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

wvxvw 14.02.2010 03:15

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

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

silin 14.02.2010 13:00

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

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

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


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

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