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



*1 例としてはこんないい加減なのでもいいかな~と

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2008-07-14 (月) 23:53:32
Site admin: PukiWiki Development Team

PukiWiki 1.5.2+ © 2001-2019 PukiWiki Development Team. Powered by PHP 5.6.40-0+deb8u7. HTML convert time: 0.153 sec.

OSDN