Меню
Что нового?

быстрая перекодировка строки по таблице

Funbit

Новичок
быстрая перекодировка строки по таблице

Всем доброго дня!

Вопрос заключается в следующем. На входе есть строка (длиной около 800 000 символов). Нужно найти наиболее быстрый способ сделать перекодировку всех символов строки по таблице, т.е. нечто похожее на перекодирку Win->Koi и т.п., только по своей таблице.

Например,
пусть есть строка на входе: "ABCAABD" ,
таблица перекодировки:
A->1,
B->2,
C->3,
D->4,
соответственно, после перекодировки должна получиться другая строка:
"1231124".

Сейчас остановился на следующем варианте:

PHP: 
$conversion_table = array ( 'a' => chr(0),
 'b' => chr(1), 
  'c' => chr(2), 
   /*... и т.д. ...*/
   'z' => chr(26) );

$output_string = '';
for ($i=0; $i<strlen($input_string); $i++) {
   $output_string .= $conversion_table[$input_string[$i]];
}
Вариант работает, но для строки длиной в 850 000 символов код выполняется около 2-3 секунд. Есть ли более быстрые способы такого преобразования ? Или это предел скорости ?

Заранее спасибо.
 

VadimSh

Новичок
используй регулярные выражения (лучше перловые, они быстрей)
 
440hz

440hz

php.ru
Funbit

1. зачем два раза i++? (уже убрал?)

2. $output_string .= ($input_string[$i]-'A'); если есть именно такая закономерность.

p.s. а откуда такая задача? можно полюбопытствовать?

-~{}~ 12.01.06 14:11:

Автор оригинала: VadimSh
используй регулярные выражения (лучше перловые, они быстрей)
Нажмите для раскрытия...
никакая регулярка не быстрее прямой обработки.
 

Funbit

Новичок
спасибо за ответы

440hz
1. ошибся просто кода писал, роли не играет в общем-то (пофиксил код в вопросе)

2. я ищу универсальный вариант, ибо таблица может сильно изменятся
 
440hz

440hz

php.ru
Funbit
ну у тебя и так в лоб написано, куда уж быстрее ...
наверное можно str_replace массив подсунуть. у нее реализация пониже уровнем будет, наверное что-нить выиграешь.
 

Funbit

Новичок
440hz
задача связана с работой, т.е. сам себе задал такую задачу :)
 
440hz

440hz

php.ru
Funbit
PHP: 
$p1 = array('A','B','C','D');
$p2 = array('0','1','2','3');

$str = 'ABBCCDDAA';

print str_replace($p1,$p2,$str);
011223300
 
440hz

440hz

php.ru
Автор оригинала: Funbit
440hz
да, я уже понял, сейчас как раз занимаюсь тестами
Нажмите для раскрытия...
PHP: 
$p1 = array('A','B','C','D');
$p2 = array('0','1','2','3');

for($i=0;$i<850000;$i++) $str .= $p1[mt_rand(0,3)];

$start1 = microtime();
$buf = str_replace($p1,$p2,$str);
$stop1  = microtime();

$speed1 = $stop1 - $start1;

$start2 = microtime();
$buf = str_replace($p1,$p2,$str);
$stop2  = microtime();

$speed2 = $stop2 - $start2;

print "\n SPEED1: $speed1";
print "\n SPEED2: $speed2";

print "\n";
для 850000 неплохо? 8)

SPEED1: 0.085255
SPEED2: 0.083728

850000 -> 0.085xxx наводит на мысль ...
 

Funbit

Новичок
я выиграл больше, новое время 520мс! ура =)

+ еще 200мс ушло вот на такое преобразование:
PHP: 
preg_replace('/([a-zA-Z0-9\+\=]{3})/i', '\x00\1', str_replace($table1, $table2, $encoded));
этот результат меня вполне устраивает,

еще раз спасибо!

-~{}~ 12.01.06 14:34:

PS. у меня словарь перекодировки не 4 символа как я привел в примере, а 64
 

SiMM

Новичок
> наверное можно str_replace массив подсунуть
Если таблица имеет вид
A->B,
B->C,
C->A
то str_replace работать не будет.
[m]strtr[/m]
Правда это медленно.
 
440hz

440hz

php.ru
SiMM
ага
$p1 = array('A','B','C');
$p2 = array('B','C','A');
$str = 'ABCABC';

AAAAAA

запомним ...

как же она внутри устроена? 8)
 

Funbit

Новичок
SiMM
да, рано обрадовался :(
вариант, который был достигнут выше - работает неверно, т.к. у меня некоторые символы входят и в первую и во вторую таблицу, которые передаются в str_replace.

Выходит придется возвращаться к старому варианту с ручной перестановкой в цикле.

Но вопрос еще открыт
 

boda

Новичок
я бы str_tr использовал: замена будет происходить только единожды на каждое вхождение
 

zarus

Хитрожопый макак
Насколько быстро работает функция strtr?
PHP: 
  function trans($str) {
   $tr = array(
               "A"=>"1","B"=>"2","C"=>"3","D"=>"4",
               );
    return strtr($str,$tr);
  }
-~{}~ 12.01.06 15:18:

Автор оригинала: 440hz
SiMM
ага
$p1 = array('A','B','C');
$p2 = array('B','C','A');
$str = 'ABCABC';

AAAAAA

запомним ...

как же она внутри устроена? 8)
Нажмите для раскрытия...
Банально, по порядку заменяются все пары в тексте
1. A->B : BBCBBC
2. B->C : CCCCCC
3. C->A : AAAAAAA
 

Funbit

Новичок
А я и не знал, что можно посимвольный массив передавать в strtr (в моем хелпе такого примера нету, а на php.net имеется).

Итак, ура, рабочая версия, всего 500мс (вместе с preg_replace):
PHP: 
$conversion_table = array ( 'a' => chr(0), 'b' => chr(4), 'c' => chr(8), 'd' => chr(12), 
									'e' => chr(16), 'f' => chr(20), 'g' => chr(24), 'h' => chr(28), 
									'i' => chr(32), 'j' => chr(36), 'k' => chr(40), 'l' => chr(44), 
									'm' => chr(48), 'n' => chr(52), 'o' => chr(56), 'p' => chr(60), 
									'q' => chr(64), 'r' => chr(68), 's' => chr(72), 't' => chr(76), 
									'u' => chr(80), 'v' => chr(84), 'w' => chr(88), 'x' => chr(92), 
									'y' => chr(96), 'z' => chr(100), '+' => chr(104), '=' => chr(108), 
									'A' => chr(112), 'B' => chr(116), 'C' => chr(120), 'D' => chr(124), 
									'E' => chr(128), 'F' => chr(132), 'G' => chr(136), 'H' => chr(140), 
									'I' => chr(144), 'J' => chr(148), 'K' => chr(152), 'L' => chr(156), 
									'M' => chr(160), 'N' => chr(164), 'O' => chr(168), 'P' => chr(172), 
									'Q' => chr(176), 'R' => chr(180), 'S' => chr(184), 'T' => chr(188), 
									'U' => chr(192), 'V' => chr(196), 'W' => chr(200), 'X' => chr(204), 
									'Y' => chr(208), 'Z' => chr(212), '0' => chr(216), '1' => chr(220), 
									'2' => chr(224), '3' => chr(228), '4' => chr(232), '5' => chr(236), 
									'6' => chr(240), '7' => chr(244), '8' => chr(248), '9' => chr(252) );
	
		$decoded_stream = preg_replace('/([^\x01]{3})/', "\x00\\1", strtr($encoded_stream, $conversion_table));
 

Alexandre

PHPПенсионер
если дело исключительно в скорости
я бы потратил время и написал модуль

вообще интерестное исследование...

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

Соответственно - реги (более высокий уровень обработки) отпадают сразу

остается найти такую php-функцию, которая взяла бы на себя большую часть обработки.

если делать обработку в цикле, то не стоит забывать, что пхп интерпретатор, а он работает значительно медленне чем встроенные средства.
 
Войдите или зарегистрируйтесь для ответа.
Сверху