BugTrack/2311

generate_trie_regex 関数を再帰処理でない形にして、処理速度を速くする†

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

メッセージ†

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 = '(?!)';

こんな感じのチェック*1をする時間を作り出せるだけいいかなと思い提案しておきます。

まだ穴があったり、効率化できるかもしれませんが、改造してテスト用に使っていた関数を挙げておきます。

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;
}

• BugTrack
• 開発版
  • リポジトリ
  • 開発日記
• :CategoryDev
  • PukiWiki2
  • PukiWiki/1.5
  • PukiWiki/1.4
  • PukiWiki/1.3
  • メーリングリスト
  • 開発談義
  • 雑談
• 開発者向け情報
  • Books
  • プラグイン

最新の16件