Эффективное сопоставление динамических ключей

Question

Мне надо наиболее эффективно (быстро) сопоставлять ключи со значениями, вот пример со статическими ключами:

const routes = new Map([
  ["/test0", () => console.log("passed 0")],
  ["/test1", () => console.log("passed 1")],
  ["/test2", () => console.log("passed 2")],
]);

const getRoute = (path) => {
  if (routes.has(path)) {
    routes.get(path)();
  } else {
    console.error("404");
  }
};

getRoute("/test0");

Как мне сделать динамические, вида /test/:one/:two/passed, где :one и :two могут быть любыми строками? Как эффективнее это реализовать БЕЗ ЦИКЛОВ И REGEXP в getRoute?

Answer 1

Во-первых, регекспы очень быстры и эффективны. Вы можете переписать их заново на js, но быстрее точно не получится.

Во-вторых, оптимизация может заключаться в кэшировании вашей динамики в мап. То есть, кто-то завёл очень популярный роут /test/iLove/regexp/passed, вы его один раз сматчили с эндпоинтом и записали этот матч в мап. А потом миллионы пользователей получили этот эндпоинт за константное время.

Если вы всё-таки решитесь писать свой регексп, то без циклов (рекурсии) вам не обойтись. Вам надо будет парсить path буква за буквой. Даже если у вас будут очень простые правила, то это будет медленнее аналогичного регекспа (node против c++).

^test\/(?<one>[^\/]+)\/(?<two>[^\/]+)\/passed$

Когда-то и меня вела дорога приключений... Я реализовывал с другом наперегонки очень быстрый роутинг. Мы шли ноздря в ноздрю, боролись за каждый тик. А потом мы сравнили наши поделки с регекспом. Регексп оказался быстрее в тысячи раз.

UPD: пример кода с циклом и регулярками (потом сравните это со своим решением без регулярок)

let routes = {
  '^get \/$': () => 'main',
  '^(?<method>[a-z]+) \/(?<service>[^\/]+)$': g => `${g.service}.${g.method}`,
  '^(?<method>[a-z]+) \/(?<service>[^\/]+)\/(?<id>[^\/]+)$': g => `${g.service}.${g.method}.id`,
};

let services = {
  'main': () => console.log('main'),
  'articles.get': () => console.log('articles index'),
  'articles.get.id': g => console.log('get article #' + g.id),
  'comments.post': () => console.log('add comment'),
  // +100500 разных эндпоинтов
};

function route(services, routes, url) {
  for (let pattern in routes) {
    let r = RegExp(pattern);
    let matches = r.exec(url.toLowerCase());
    if (matches !== null) {
      let service = services[routes[pattern](matches.groups)];
      if (service !== undefined) {
        return service(matches.groups);
      } else {
        break;
      }
    }
  }
  console.log('404');
}

route(services, routes, 'GET /');
route(services, routes, 'GET /articles');
route(services, routes, 'GET /articles/123');
route(services, routes, 'POST /comments');
route(services, routes, 'GET /foo/bar');

Если url'ы шаблонные, то регулярок получается немного, а дальше быстрый мап по уникальному идентификатору эндпоинта.

Answer 2

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

Для этого побьём все конечные точки на сегменты, и построим из них дерево следующей структуры (я использую typescript для описания интерфейсов):

type RouteNode = {
    routes: { [key: string]: RouteNode | undefined },
    default?: RouteNode,
    final?: { handler: Function, variableNames: string[] },
}

Здесь свойство routes отвечает за статические маршруты, вроде ваших test0-test2; свойство default отвечает за маршрут с переменной; ну а final отвечает за маршрут, который заканчивается на текущем элементе; handler - это обработчик маршрута, ну а variables - имена переменных (one, two), если они вам нужны.

Составить литерал подобного дерева маршрутов можно и вручную, но лучше поручить его составление компьютеру (в комментариях я пишу typescript-описания типов):

function emptyNode() /*: RouteNode*/ {
    return {
        routes: Object.create(null)
    }
}

function addRoute(root/*: RouteNode*/, path/*: string*/, handler/*: Function*/) {
    let node = root;
    let variableNames = [];
    for (const segment of path.split('/')) {
        if (!segment.startsWith(':')) {
            // Обычный сегмент маршрута
            node = node.routes.next ??= emptyNode();
        } else {
            // Сегмент-переменная
            node = node.default ??= emptyNode();
            variableNames.push(segment.substr(1));
        }
    }

    if (node.final)
        throw new Error("Маршрут уже существует");

    node.final = { handler, variableNames };
}

Здесь я использую Object.create(null), чтобы среди ключей не затесались такие методы как toString и пр.

Теперь, когда дерево построено, можно искать в нём совпадения:

function getRoute(root/*: RouteNode*/, path/*: string*/) {
    let node = root;
    let variableValues = [];
    for (const segment of path.split('/')) {
        const next = node.routes[segment];
        if (next) {
            // Обычный сегмент
            node = next;
        } else if (node.default) {
            // Сегмент-переменная
            node = node.default;
            variableValues.push(segment);
        } else {
            // Маршрут не найден
            return null;
        }
    }

    if (!node.final) {
        // Маршрут всё ещё не найден
        return null;
    }

    let variablesObj = Object.create(null);
    for (let i=0; i<node.final.variables.length; i++) {
        variablesObj[node.final.variableNames[i]] = variableValues[i];
    }

    return {
        handler: node.final.handler,
        variables: variableValuesObj,
    }
}

БЛОГ НА HUSL

Эффективное сопоставление динамических ключей

Ответы (2 шт):