Форум Flasher.ru - Быстро перемешать символы в строке

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Быстро перемешать символы в строке (http://www.flasher.ru/forum/showthread.php?t=202851)

flasher190

15.08.2013 12:56

Быстро перемешать символы в строке

Добрый день, столкнулся с задачей перемешивания символов в строчке размером в сотню мегабайт.
Привет -> рПвите

Само собой при помощи цикла, строчек и getCharAt это все происходит _очень_ медленно (порядка 2 минут) и сжирает феерический объем оперативы.

Код AS3:

if (!(length % 2 == 1))

                                {

                                        while (i < length)

                                        {

                                                s += base64.charAt(i + 1) + base64.charAt(i);

                                                i+=2;

                                        }

                                }

                                else

                                {

                                        while (i < length - 1)

                                        {

                                                s += base64.charAt(i + 1) + base64.charAt(i);

                                                i += 2;

                                        }

                                        s += base64.charAt(base64.length-1);

                                }

 

                                return s;

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

Код AS3:

var b_temp:ByteArray = new ByteArray();

                                var bytes:ByteArray = new ByteArray();

                                bytes.writeUTFBytes(base64);

 

                                if (!(length % 2 == 1))

                                {

                                        for (i = 0; i < bytes.length-2; i+=4)

                                        {                                

                                                b_temp.writeByte(bytes[i + 2]);

                                                b_temp.writeByte(bytes[i + 3]);

 

                                                b_temp.writeByte(bytes[i]);

                                                b_temp.writeByte(bytes[i+1]);

                                        }

                                }

                                else

                                {

                                        for (i = 0; i < bytes.length - 4; i += 4)

                                        {                                

                                                b_temp.writeByte(bytes[i + 2]);

                                                b_temp.writeByte(bytes[i + 3]);

 

                                                b_temp.writeByte(bytes[i]);

                                                b_temp.writeByte(bytes[i+1]);

                                        }

                                        b_temp.writeByte(bytes[bytes.length - 2]);

                                        b_temp.writeByte(bytes[bytes.length - 1]);

                                }

Прошу помогите добиться наиболее быстрого алгоритма.

KumoKairo

15.08.2013 13:49

Дайте ссылку пример на файла, если не трудно)
У меня есть идея насчет применения алгоритма Фишера-Йетса, но с примером было бы проще работать

flasher190

15.08.2013 14:21

KumoKairo
Ссылка на .zip архив в котором лежит json, в поле bytearray которого лежит перемешанный по данному принципу base64.
Если перемешать обратно и декодировать из base64, то получится .swf (в bytearray)

Но можете любой длинный текст засунуть в base64 и оно ничем не будет принципиально отличаться от вышеназванного ужаса.

http://sdrv.ms/17Ph50p

Спасибо :-)

wvxvw

15.08.2013 18:44

Не вдаваясь в остальные подробности...

Код:

!(X операция Y == Z)

эквивалентно

Код:

X операция Y != Z

но за меньшее количество действий.

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

Но, с точки зрения алоритмической сложности: никаких ускорений вам не светит. Скорость как была линейной, так и останется.

flasher190

16.08.2013 12:17

wvxvw
Понятно, спасибо. Вообще вроде сделать работу быстрее, тот же самый файл распаковывается средствами Flash из zip на порядок быстрее, чем выполняется такая простейшая операция. Из этого я сделал вывод, что можно сделать решение "не в лоб". А вот какое - знаний не хватает

По поводу if'а согласен, но эта часть кода выполняется один раз и потому не критично. А до рефакторинга не добрался еще.

Fogflasher

16.08.2013 12:48

flasher190, можно еще на stackoverflow спросить, правда там форум слишком отягощенный оформительскими извратами, и за неправильный формат поста могут заминусовать, и проигнорить.

mikhailk

16.08.2013 13:24

Цитата:

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

Если речь не идет о курсовой или лабораторной работе, может быть просто переформулировать задачу? Слабо себе представляю назначение данного действия и область применения.

flasher190

16.08.2013 14:00

mikhailk,
у нас хитрый способ шифровки документов (все равно бесполезный, но ТЗ такое). Уже переформулировали задачу, решили сделать по другому. Теперь программа обрабатывает все за 5-10 секунд.

Всем спасибо :) Но все равно обидно, что AVM2 работает в разы медленней Java, не говоря уже о нативном коде.

MikroAcse

16.08.2013 14:11

Используйте воркеры (Workers).

alexcon314

16.08.2013 14:22

Цитата:

Если перемешать обратно и декодировать из base64, то получится .swf (в bytearray)

Т.е. перемешивание должно быть обратимым? Это попытка "шифрования данных" такая? С последующим "дешифрованием"? Типа так:
swf (bytes) -> original string (base64) -> shuffled string -> original string (base64) -> swf (bytes)
А вообще, вот.

UPD. опоздал с постом :)

flasher190

16.08.2013 14:32

alexcon314
Да, перемешивание обратимым
Это лишь кусочек "шифрования" и данные перемешиваются по специальному алгоритму, со сдвигами, с шифровалкой по ключу и кучей других телодвижений :) Но это все равно глупость, ибо декомпил вскроет все тайны, а делаем мы офлайн ПО и с сервера ничего не получить. Заказчик обосновывает "это чтобы залетные юзвери не воровали, а если кто-либо целенаправленно будет - найдем и засудим". Так и живем.

MikroAcse
Недавно пытался использовать для другого проекта, но до конца не смог разобраться (использование воркеров выглядят как извращенный бубен в обход каких-то ограничений платформы)

alexcon314

16.08.2013 15:08

Для оффлайн ПО, где юзается флеш, есть AIR (и не только, см. например Zinc) Там возможностей работы с системой намного больше. Это я к тому, что ресурсоемкие задачи по шифрованию/дешифрованию там можно вынести в нативный для платформы код и не мучить флеш с его AS3 :). Например, написав .dll на с++ (в айр это именуется ANE). Кстати, и многопоточность нативно можно прикрутить при желании.

flasher190

16.08.2013 15:15

alexcon314
Именно под AIR я и пишу. Не знал, что можно включить в сборку нативные dll. Надо будет поэксперементировать, огромное спасибо :-)

Кстати, если интересно, то пишу вот такую вот читалку книг.

alexcon314

16.08.2013 17:34

Т.е. я так понимаю, шифруются книжки? Тогда ANE - самое то.

flasher190

16.08.2013 17:58

alexcon314, да, спасибо огромное. Только вопрос встает в кроссплатформенность (включая линукс)

alexcon314

16.08.2013 18:53

А вот тут туго. Адоб не поддерживает AIR на Linux. Так что ... плохо, вобщем, с линуксом.
Разве, только на Java написать ANE. Но и это, на мой взгляд, очень тернистый путь. Альтернатива - Wine, ну, может быть еще mono. Правда при этом приложение будет работать не нативно, а в другой виртуальной машине.
Флеш так-то вообще с линуксов уходит.
Zinc в этом отношении выглядит предпочтительней, хотя...
Туго, короче, с линуксом.

MikroAcse

16.08.2013 21:14

Цитата:

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

Ну а что ты думал? Сначала все плохо, а через пол-годика уже будет прекрасная технология :)

C4Grey

16.08.2013 23:32

Возможно, для ускорения работы алгоритмов еще стоит попробовать domain memory

MikroAcse

17.08.2013 10:09

Цитата:

Сейчас не поддерживает. Но есть прошлые версии AIR для иксов. Никто не мешает под них писать.

Это не совсем правильно. Кому нужно писать под то, что не поддерживается?

wvxvw

17.08.2013 13:27

Из всего, что можно сделать для Линукса на флеше - Вайн самое работоспособное решение. Но есть другой момент... нормальный пользователь Линукса вряд ли будет устанавливать программы не из известных ему репозиториев. Как правило это только репозиторий системы + один-два общеизвестных, вроде Launchpad / Rpmfusion. Проприетарный софт ставят только те, кого заставляют это делать / нет другого решения. Например, в лаборатории могут установить всем сотрудникам какую-нибудь специальную программу, или, драйвера для какого-нибудь куска железа, ну, или игрушки.
Если это программа не на столько полезна / незаменима для линуксовой аудитории, я думаю, про этот сегмент рынка можно не вспоминать.

Хотя, конечно, люди разные бывают...

wvxvw

17.08.2013 14:27

Я так понял, что речь шла о десктопных приложениях.

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

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