* generate_trie_regex 関数を再帰処理でない形にして、処理速度を速くする [#w9edd2e4]

- ページ: [[BugTrack2]]
- 投稿者: 名無しさん
- 優先順位: 低
- 状態: 提案
- カテゴリー: 本体新機能
- 投稿日: 2008-07-14 (月) 23:53:32
- バージョン: 

** メッセージ [#v7d7f1c2]
generate_trie_regex 関数とそれを再帰処理でなくしたテスト用の関数を、呼び出して試した分では生成時間が、約5千ページの時で約15秒 → 約2秒、約7千5百ページの時で約35秒 → 約2秒、に短縮されました。ただし、メモリ使用量については比較調査できていません。

さすがに5千ページとかになると[[BugTrack2/81]] のような問題が起こりそうですが、get_autolink_pattern 関数で
	$regex_test = @preg_replace('/(' . $result . ')|(' . $result_a . ')/x', '', '');
	if (! is_string($regex_test)) $result = $result_a = '(?!)';
こんな感じのチェック((例としてはこんないい加減なのでもいいかな~と))をする時間を作り出せるだけいいかなと思い提案しておきます。

まだ穴があったり、効率化できるかもしれませんが、改造してテスト用に使っていた関数を挙げておきます。
 function _test(& $array, $offset = 0, $sentry = NULL, $pos = 0)
 {
 	if (! is_array($array) || empty($array)) return '(?!)'; // Zero
 
 	// $array = array_unique($words);
 	// sort($words, SORT_STRING);
 
 	$count = count($array);
 	if ($offset < 0) $offset = 0;
 	if ($sentry === NULL || $sentry > $count) $sentry = $count;
 	if ($pos < 0) $pos = 0;
 
 	if ($offset >= $sentry) return '(?!)';
 
 	// Too short. Skip this
 	$skip = ($pos >= mb_strlen($array[$offset]));
 	if ($skip) ++$offset;
 
 	$index = $offset;
 	$regex = '';
 	$multi = FALSE;
 	$stack = array();
 
 	while ($index < $sentry) {
 		if ($index != $offset) {
 			$multi = TRUE;
 			$regex .= '|'; // OR
 		}
 
 		// Get one character from left side of the value
 		$char = mb_substr($array[$index], $pos, 1);
 
 		// How many continuous keys have the same letter
 		// at the same position?
 		for ($i = $index; $i < $sentry; ++$i)
 			if (mb_substr($array[$i], $pos, 1) !== $char) break;
 
 		if ($index < ($i - 1)) {
 			// Some more keys found
 			// Recurse
 			$regex .= str_replace(' ', '\\ ',
 	            preg_quote(str_replace('\\', '\\\\', $char), '/'));
 
 			// Save now parameter
 			$stack[] = array($offset, $sentry, $regex, $skip, $multi);
 
 			++$pos;
 
 			// Too short. Skip this
 			$skip = ($pos >= mb_strlen($array[$index]));
 			if ($skip) ++$index;
 
 			$offset = $index;
 			$sentry = $i;
 			$regex = '';
 			$multi = FALSE;
 
 			continue;
 		}
 
 		// Not found
 		$regex .= str_replace(' ', '\\ ',
 	            preg_quote(str_replace('\\', '\\\\', mb_substr($array[$index], $pos)), '/')
 	       );
 		$index = $i;
 
 		while ($index >= $sentry && ! empty($stack)) {
 			if ($skip || $multi) $regex = '(?:' . $regex . ')';
 			if ($skip) $regex .= '?'; // Match for $pages[$offset - 1]
 			$tmp = $regex;
 
 			list($offset, $sentry, $regex, $skip, $multi) = array_pop($stack);
 			$regex .= $tmp;
 			--$pos;
 		}
 	}
 
 	while (! empty($stack)) {
 		if ($skip || $multi) $regex = '(?:' . $regex . ')';
 		if ($skip) $regex .= '?'; // Match for $pages[$offset - 1]
 		$tmp = $regex;
 
 		list($offset, $sentry, $regex, $skip, $multi) = array_pop($stack);
 		$regex .= $tmp;
 	}
 
 	if ($skip || $multi) $regex = '(?:' . $regex . ')';
 	if ($skip) $regex .= '?'; // Match for $pages[$offset - 1]
 
 	return $regex;
 }

--------

#comment

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Site admin: PukiWiki Development Team

PukiWiki 1.5.4+ © 2001-2021 PukiWiki Development Team. Powered by PHP 5.6.40-0+deb8u12. HTML convert time: 0.070 sec.

OSDN