У вас есть список URL-адресов, и вам нужно надежное время ответа 5-10 мс, поэтому выполнение списка строк и выполнение регулярного выражения (или даже сравнения строк) для каждого из них может не масштабироваться, так как список становится большим (но в любом случае стоит проверить как базовый уровень). Моя первая мысль сделать лучше: разве мы не можем как-то предварительно обработать этот список в форму, которая позволяет быстро искать? Я думаю, что мы можем.
Предположения, которые я сделал для начала:
- URL - это список токенов. Чтобы получить их, мы отбрасываем протокол, удаляем строку запроса и находим первый «/» (и, если его нет, добавляем его в конец). Материал перед "/" - это имя хоста, а материал после "/" - это путь.
- Мы получаем токены имени хоста, разделяя на ".".
- Мы получаем токены пути, разделив их на "/".
Так вот этот URL, например:
"www.stackoverflow.com/users/239289"
становится токеном:
"www", "stackoverflow", "com", "/", "users", "239289"
Обратите внимание, что единственное допустимое "/" - это то, которое разделяет имя хоста и путь.
Вот моя функция для токенизации URL - я сделал это в PHP, мой язык для быстрого создания прототипов (и многое другое). Это не идеальный код, но он выполняет свою работу достаточно хорошо:
function tokenize_url($url) {
$pos = strpos($url, '/');
if ($pos === 0) {
// It's a path-only entry.
$hostname = '*';
$path = substr($url, 1);
} else if ($pos !== false) {
// It's a normal URL with hostname and path.
$hostname = substr($url, 0, $pos);
$path = substr($url, $pos + 1);
if ($path === false) {
$path = '';
}
} else {
// No slash found, assume it's a hostname only.
$hostname = $url;
$path = '';
}
if ($hostname !== '') {
$hostname_tokens = explode('.', $hostname);
} else {
$hostname_tokens = array();
}
if ($path !== '') {
$path_tokens = explode('/', $path);
} else {
$path_tokens = array();
}
return array_merge($hostname_tokens, array('/'), $path_tokens);
}
Так что я думаю, что предварительно обработаю ваш список URL-адресов, пройдя его и маркируя каждый URL-адрес, и сохраняя его в ориентированном графе (в основном, вложенные ассоциативные массивы). Таким образом, нам нужно только пересмотреть график для точных совпадений (чуть больше, чтобы найти совпадения по шаблону), и это O (1) на каждом шаге. Мы помечаем конец наших шаблонов для сопоставления, повесив специальный символ «%!%!%» На этом узле.
Вот функция для построения графика - надеюсь, код довольно понятен:
function compile_site_list($site_list) {
$root = array();
foreach ($site_list as $url) {
$tokens = tokenize_url($url);
$node = &$root;
for ($i=0; $i<count($tokens); $i++) {
// The "%" forces PHP to evaluate this as a string, no matter what.
// Sadly, casting to a string doesn't do it!
$token = $tokens[$i] . '%';
// If this is our first time seeing this string here, make a
// blank node.
if (!(isset($node[$token]))) {
$node[$token] = array();
}
if ($i < (count($tokens) - 1)) {
// If we're not at the end yet, keep traversing down.
$node = &$node[$token];
} else {
// If we're at the end, mark it with our special marker.
$node[$token]['%!%!%'] = 1;
}
}
}
return $root;
}
Поэтому, если у вас есть список URL-адресов для сравнения, вам просто нужно один раз вызвать compile_site_list () и сохранить его в памяти, или в сериализованном массиве, или в чем-то подобном.
Теперь пришло время сопоставить URL. Во-первых, когда мы его получим, нам нужно очистить его, как я упоминал выше:
function scrub_url($url) {
// Get rid of the protocol (if present).
$pos = strpos($url, '://');
if ($pos !== false) {
$url = substr($url, $pos + 3);
}
// Get rid of any query string (if present).
$pos = strpos($url, '?');
if ($pos !== false) {
$url = substr($url, 0, $pos);
}
return $url;
}
Для поиска в структуре данных, которую мы создали, мы берем токены для URL-адреса, с которым сопоставляем, и рекурсивно ищем их на графике. Как только мы находим «%!%!%» На графике - у нас есть совпадение, и игра окончена.
Однако, если мы дойдем до конца наших токенов и не подойдем, мы вернемся назад и ищем подстановочные знаки. Если мы найдем подстановочный знак, мы позволим ему потреблять столько токенов, сколько ему нужно (за исключением символа "/"), и посмотрим, приведет ли это к совпадению.
Если ничего из этого не найдено - его нет в списке.
Вот код:
function search_compiled_list($url, $compiled_site_list) {
$url = scrub_url($url);
$tokens = tokenize_url($url);
return do_search($tokens, $compiled_site_list);
}
function do_search($tokens, $compiled_site_list) {
// Base cases for recursion:
if (isset($compiled_site_list['%!%!%'])) {
// If we're at a node that has our marker hanging off it - we found it!
return true;
} else if (count($tokens) === 0) {
// Otherwise, if we got somewhere and have no tokens left, we didn't
// find it.
return false;
}
// The "%" on the end forces PHP to evaluate this as a string, no
// matter what.
$token = $tokens[0] . '%';
if (isset($compiled_site_list[$token])) {
// Found an exact match!
$result = do_search(array_slice($tokens, 1),
$compiled_site_list[$token]);
if ($result === true) {
return true;
}
}
// Didn't find an exact match - let's check for wildcards.
if ((isset($compiled_site_list['*%'])) && ($tokens[0] !== '/')) {
// If we're matching the wildcard, let it consume as many tokens
// as it wants. The only thing it can't consume is /.
for ($i=1; $i<count($tokens); $i++) {
$result = do_search(array_slice($tokens, $i),
$compiled_site_list['*%']);
if ($result === true) {
return true;
}
}
}
return false;
}
Итак, чтобы увидеть все в действии - если у вас есть $ site_list, который является массивом ваших URL, вы должны сделать:
$url_to_check = "http://www.stackoverflow.com/users/120262?tab=accounts";
$compiled_site_list = compile_site_list($site_list);
$result = search_compiled_list($url_to_check, $compiled_site_list);
var_dump($result);
Я проверил этот код на нескольких URL-адресах, и он, кажется, работает, но я не претендую на то, что проверил его полностью. Я думаю, что мои рассуждения правильны, но, безусловно, открыты для комментариев / критики. (У меня была похожая проблема, немного подпрыгивая вокруг головы, и это было забавное упражнение.)
Конечный результат заключается в том, что эффективность алгоритма определяется не количеством URL-адресов, с которыми сопоставляется, а на самом деле длиной URL-адреса (в токенах), который вы пытаетесь сопоставить. Я выполнил некоторые неподтвержденные данные на своем ноутбуке, где я заблаговременно скомпилировал список сайтов и сохранил его сериализованным - десериализация и поиск занял в общем около 2 мс, в худшем случае.