10-кратный прирост производительности благодаря 100 строкам кода

внешний интерфейс программист GitHub открытый источник

Задайте вопрос

Начнем с распространенного вопроса на собеседовании и реального требования:

Вам нужно отобразить 5000 или более фрагментов данных на внешнем интерфейсе.Структура данных каждого фрагмента данных представляет собой объект со свойствами в различных форматах. Значение каждого свойства, в свою очередь, может быть примитивным типом, объектом или даже массивом. Здесь объекты или элементы внутри массива могут продолжать содержать объекты или массивы и допускать бесконечную вложенность. Например

{
  "name": {
    "firstName": "yi",
    "lastName": "li"
  },
  "age": 23,
  "roles": ['developer', 'admin'],
  "projects": [{
    "name": "demo",
    "repo": ""
  }]
}

На странице имеется окно поиска, и пользователи могут найти данные, содержащие этот контент, введя поисковый контент. Обратите внимание, что до тех пор, пока любое значение свойства любого объекта данных (например, в приведенной выше структуре данных, еслиname, age, rolesЗначение любого атрибута) содержит это ключевое слово. Если значением атрибута является массив или объект, то элементы массива или значение объекта продолжают выполнять обнаружение соответствия для входного содержимого и рекурсивно обнаруживать, пока есть совпадение, данные считаются совпадение

Как спроектировать эту функцию, чтобы сделать функцию поиска максимально быстрой?

Решения

Если у вас есть небольшая чувствительность к программисту, в это время у вас должны быть две мысли:

  • Обход и обход в глубину являются наиболее прямыми способами.
  • Если требование достаточно быстрое для прохождения, я теряю

Действительно, обход является самым простым, но и самым медленным. Таким образом, один из обычных методов оптимизации состоит в обмене пространства на время, а другой метод... Подробнее об этом позже.

Здесь мы пытаемся оптимизировать поиск, строя словарное дерево (Trie).

Если вы не знаете, что такое дерево словаря, вот краткое введение: Предположим, у нас есть простой объект, и соответствие ключ-значение выглядит следующим образом:

Мы строим дерево по буквам «ключа» по порядку, а значение листового узла может быть значением «ключа».

Затем независимо от того, что пользователь хочет получить в это время, чтобы получить доступ к значению любого атрибута, если, начиная с корневого узла дерева и посещая конечные узлы дерева в соответствии с порядком, в котором появляются буквы атрибута, значение атрибута можно получить. например, когда мы хотим получить доступteaВремя:

Но в сценарии, который нам нужно решить, нам не нужно заботиться о «свойстве», нас интересует только то, соответствует ли «значение» искомому содержимому. Итак, нам просто нужно построить дерево словаря для «значений».

Предположим, у вас есть следующие значения объекта

const o = {
  message: 'ack'
  fruit: 'apple',
  unit: 'an',
  name: 'anna',
}

Установленная древовидная структура выглядит следующим образом:

root--a
      |--c
         |--k
      |--p
         |--p
            |--l
               |--e    
      |--n
         |--n
            |--a

когда пользователь ищетappleкогда, изaстартовый доступ, последний доступ к письмамe, если в дереве есть соответствующий узел, значит попадание, когда пользователь ищетahaпри посещенииhКогда соответствующий узел не может быть найден в дереве, это означает, что объект не соответствует критериям поиска.

Но на практике у нас будет много значений объекта, и между несколькими значениями объекта могут быть повторяющиеся значения, поэтому при сопоставлении нам нужно вернуть все возможные результаты сопоставления. Например

[
  {
    id: 1,
    message: 'ack'
    fruit: 'apple',
    unit: 'an',
    name: 'anna',
  },
  {
    id: 2,
    message: 'ack'
    fruit: 'banana',
    unit: 'an',
    name: 'lee',
  },
]

Вышеуказанные два объекта имеют одинаковое значениеackиan, поэтому мы также добавляем информацию об идентификаторе объекта в конечные узлы дерева.

root--a
      |--c
         |--k (ids: [1,2])
      |--p
         |--p
            |--l
               |--e (ids: [1])
      |--n (ids: [1, 2])
         |--n
            |--a (ids: [1])

так что когда пользователь ищетan, мы можем вернуть все совпадения

Хорошо, когда у нас есть идея, мы начинаем реализовывать код.

Код

поддельные данные

Одна из первых проблем, которую необходимо решить, — если 5000 единиц данных будут быстро подделаны? Здесь мы используемrandomuser.me/api/API с открытым исходным кодом. Для простоты давайте просто вернемсяgender, email, phone, cell, natЗначения примитивных типов данных без возврата вложенных структур (объектов и массивов). Обратите внимание, что это делается только для удобства отображения и понимания кода, а сложная структура опущена, что также позволяет избежать сложного кода. После добавления сложной структуры код сильно не меняется, но добавляется логика обхода и рекурсивная логика.

проситьслучайный пользователь./API/?результат…Результат выглядит следующим образом:

{
  "results": [
    {
      "gender": "male",
      "email": "enzo.dumont@example.com",
      "phone": "02-65-13-26-00",
      "cell": "06-09-02-19-99",
      "nat": "FR"
    },
    {
      "gender": "male",
      "email": "gerald.omahony@example.com",
      "phone": "011-376-3811",
      "cell": "081-697-1414",
      "nat": "IE"
    }
    //...
  ]
}

Структура данных конечного узла

Согласно описанию в идее, структура данных описывается следующим образом:

class Leaf {
  constructor(id = "", value = "") {
    this.ids = id ? [id] : [];
    this.value = value;
    this.children = {};
  }
  share(id) {
    this.ids.push(id);
  }
}

shareметод используется для добавления нескольких идентичных совпадающих объектов в конечный узелid

вспомогательная функция

В процессе кодирования нам понадобятся некоторые вспомогательные функции, такие как:

  • isEmptyObject: определить, является ли это пустым объектом
  • distinct: удалить повторяющиеся элементы из массива

Эти две функции можно позаимствоватьlodashРеализация библиотеки классов, даже если она реализована вручную, очень проста, поэтому я не буду здесь вдаваться в подробности.

Еще одним важным методом являетсяnormalize, я больше привыкnormalizeПереведите на «сглаживание» (а не «стандартизация»), потому что это более образно. Этот метод используется для разделения объектов в массиве на отношения сопоставления между идентификаторами и объектами.

такой как

[
  {
    id: 1,
    message: 'ack'
    fruit: 'apple',
    unit: 'an',
    name: 'anna',
  },
  {
    id: 2,
    message: 'ack'
    fruit: 'banana',
    unit: 'an',
    name: 'lee',
  },
]

После выравнивания до

{
  '1': {
    id: 1,
    message: 'ack'
    fruit: 'apple',
    unit: 'an',
    name: 'anna',
  },
  '2': {
    id: 2,
    message: 'ack'
    fruit: 'banana',
    unit: 'an',
    name: 'lee',   
  }
}

Причина этого в том, что когда результат поиска возвращает массив идентификаторов:[1, 2, 3], нам нужно только пройти и вернуть результат, который будет сглажен по идентификаторуMapНайдите соответствующие данные немедленно. В противном случае необходимо продолжать обход исходного массива данных, чтобы найти соответствующие данные.

так какrandomuser.meВозвращаемая информация не содержит идентификационной информации, поэтому мы временно используем информацию об электронной почте в качестве уникального идентификатора.normalizeРеализация выглядит следующим образом:

function normalize(identify, data) {
  const id2Value = {};
  data.forEach(item => {
    const idValue = item[identify];
    id2Value[idValue] = item;
  });
  return id2Value;
}

построить дерево

Секрета в этой части кода нет, он строит дерево по рекурсивному алгоритму.

fetch("https://randomuser.me/api/?results=5000&inc=gender,email,phone,cell,nat")
  .then(response => {
    return response.json();
  })
  .then(data => {
    const { results } = data;
    const root = new Leaf();
    const identifyKey = "email";

    results.forEach(item => {
      const identifyValue = item[identifyKey];
      Object.values(item).forEach(itemValue => {
        // 注意这里会把 Number 和 Boolean 类型也字符串化
        const stringifiedValue = String(itemValue);
        let tempRoot = root;
        const arraiedStringifiedValue = Array.from(stringifiedValue);
        arraiedStringifiedValue.forEach((character, characterIndex) => {
          const reachEnd =
            characterIndex === arraiedStringifiedValue.length - 1;
          if (!tempRoot.children[character]) {
            tempRoot.children[character] = new Leaf(
              reachEnd ? identifyValue : "",
              character
            );
            tempRoot = tempRoot.children[character];
          } else {
            if (reachEnd) {
              tempRoot.children[character].share(identifyValue);
            }
            tempRoot = tempRoot.children[character];
          }
        });
      });
    });

нечеткий поиск

В поиске части кода нет секрета, просто следуйте карте:

function searchBlurry(root, keyword, userMap) {
  const keywordArr = Array.from(String(keyword));
  let tempRoot = root;
  let result = [];

  for (let i = 0; i < keywordArr.length; i++) {
    const character = keywordArr[i];
    if (!tempRoot.children[character]) {
      break;
    } else {
      tempRoot = tempRoot.children[character];
    }
    if (keywordArr.length - 1 === i) {
      result = [
        ...tempRoot.ids,
        ...collectChildrenInsideIds(tempRoot.children)
      ];
    }
  }
  return distinct(result).map(id => {
    return userMap[id];
  });
}

Обратите внимание, что естьcollectChildrenInsideIdsметод, который используется для сбора идентификаторов всех дочерних узлов листового узла. Это сделано потому, что текущая операция является нечетким сопоставлением, когда вы ищетеaчас,apple, anna, ackВсе совпадают.

Обычные методы поиска и подводные камни словарных деревьев

Чтобы сравнить эффективность и проверить правильность результатов поиска, нам все еще нужно написать обычный метод обхода поиска:

function regularSearch(searchKeyword) {
  const regularSearchResults = [];
  results.forEach(item => {
    for (const key in item) {
      const value = item[key];
      if (String(value).startsWith(searchKeyword)) {
        regularSearchResults.push(item);
        break;
      }
    }
  });
  return regularSearchResults
}

Обратите внимание, что при проверке соответствия значения объекта поисковому запросу мы использовалиstartsWith, вместоindexOf, ** Это связано с тем, что недостаток словарного дерева заключается в том, что оно может сопоставлять только слова, начинающиеся с искомого слова! **Например, при поискеa, может соответствовать толькоapple,annaне соответствуетbanana. Для простоты сравнения мы должны использоватьstartsWith

Сравнение производительности

Результаты сравнения производительности интересны:

  • Когда объем данных небольшой, эффективность поиска не будет иметь большого значения.
  • Когда объем данных велик, например 5000 элементов, когда условия поиска очень короткие, напримерa, то эффективность поиска по дереву словаря будет ниже, чем при обходном поиске, то есть это займет много времени; когда поисковый термин станет конкретным, напримерali, эффективность поиска словарного дерева будет выше, чем обходного поиска

Проблема низкой эффективности нетрудно догадаться почему: при поиске простых слов будет доступно меньше листовых узлов, поэтому можно только сканироватьchildrenСоберите все возможные идентификаторы дочерних узлов, процесс обхода на этом шаге занимает большую часть времени.

Но нам все еще нужно выполнить требования запроса этой части, поэтому нам нужно сделать некоторые оптимизации для этого сценария.

Оптимизация сценариев для коротких поисков

Давайте вспомним простой сценарий поиска.Узким местом производительности является то, что нам нужно обойти все дочерние узлы под листовым узлом. С ним легко справиться, так как после завершения построения дерево не изменится, то нам нужно только заранее вычислить sub-id каждого листового узла Это второй тип схемы оптимизации, упомянутый в начале статьи, то есть предварительный расчет.

Я написал новый метод, который рекурсивно добавляет идентификаторы всех своих дочерних элементов к каждому конечному узлу:

function decorateWithChildrenIds(root) {
  const { children } = root;
  root.childrenIds = collectChildrenInsideIds(root.children);
  for (const character in children) {
    const characterLeaf = children[character];
    characterLeaf.childrenIds = collectChildrenInsideIds(
      characterLeaf.children
    );
    decorateWithChildrenIds(characterLeaf);
  }
}

Затем, после построения дерева, используйте этот метод, чтобы «украсить» все конечные узлы.

в заключении

После предварительного вычисления в случае 5000 фрагментов данных, будь то короткий поиск или длинный поиск, эффективность поиска по дереву словаря в основном составляет около 1 мс, в то время как обычный обходной поиск составляет около 10 мс, что действительно является десятикратным улучшением. . Но цена этого улучшения основана на том, что нужно пожертвовать пространством и потратить время на предварительный расчет. Я считаю, что если структура данных станет более сложной, повышение эффективности будет более очевидным.

Адрес исходного кода этой статьи:GitHub.com/hehe54188/море…

Наконец, я оставляю вопрос для всех: когда количество данных для поиска становится больше, например, 1000, иногда результаты поиска по дереву словаря и результаты поиска обхода несовместимы, а когда количество данных становится больше, например, 5000, то эта "проблема" будет появляться постоянно. Эта проблема не является ошибкой, но в чем проблема?

Эта статья также опубликована в моей колонке Zhihu в то же время.Автостопом по передовым технологиям, добро пожаловать на подписку

Категории