![]() |
Отсортировать ключи из Dictionary в dense Array по значениям?
Вот, столкнулся с проблемным алгоритмом, никак не найду хорошее решение.
Что есть: Код:
Dictionary /*Object, int*/Код:
Array /*Object*/ [ obj2, obj1, obj4, obj3 ]Как ни сделаю, все очень медленно получается... |
Наряду с Dictionary держать массив, и при добавлении элементов сразу вставлять их в нужное место. Проигрыш в памяти, выигрыш в вычислительных ресурсах.
|
Не получится, в Dictionary должны быть слабые ключи... да и таким образом мы выиграем на нахождении и проиграем при добавлении, что, вобщем-то будет так на так...
|
Ну добавлять обычно реже приходится, чем искать :)
Плюс по Dictionary искать придется перебором, а в отсортированный массив можно добавлять скажем бинарными вставками. А зачем weak keys? |
Это все для той же системы сигнал-слот. Добавляются колбеки. нужно отсортировать по priority.
Да, кстати, сейчас поэксперементировал с нативным диспатчером, если добавлять с разной priority то добавление слушаетелей отнимает кучу времени... просто ну очень много. Т.е. там скорее всего сделано, как ты и предлагаешь. Т.е. по тестам получилось: Код:
EventDispatcherКод:
Signal |
вариант
Код AS3:
|
Спасибо, я по похожему пути в итоге и пошел (только решил добавлять сразу в Dictionary объекты со ссылками на priority и слушателя - хотя, надо ще подумать, может быть так будет выгоднее...).
|
ага, обогнать родной sort (хотя он вроде бы и просто пузырьковый) все равно не получится (если у кого есть примеры, очень хочу)
т.е. вопрос в оптимизации структуры, чтобы с меньшими потерями сгенерить массив, который этому сорту подсунуть, тут 'объекты со ссылками на priority' скорее всего выиграют |
Если в массиве только чисельные типы, то можно, мне где-то попадлася... Shell сортом. Для сложных объектов - не знаю, но и флеш сложные объекты тоже долго сортитует :)
Да, и флешевый сорт он какой-то не очень пузырьковый... посмотри в каком порядке он аргументы выдает в колбек... т.е. он как-то с середины начинает. В смысле, алгоритм может быть и тот же, но не классическая реализация. PS: http://blog.inspirit.ru/?p=271 |
>>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
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.