Блог

Главная - Вопросы по программированию - Временная сложность итерации по массиву и объекту

Временная сложность итерации по массиву и объекту

#javascript #arrays #object #big-o

Вопрос:

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

 const students = 
  [ { name: "John",   tags: [ 'tag1', 'tag2' ] } 
  , { name: "Leslie", tags: [ 'tag1' ]         } 
  , { name: "Mark",   tags: [ 'tag', 'tag2' ]  }
  ]

Прямо сейчас, чтобы найти студентов с одинаковыми тегами, я перебираю массив объектов и массив тегов для каждого студента, который равен O(n) в квадрате.

 const filterByTag = (filter) => {
  let result = [];
  initialStudents.map((student) => {
    student.tags.map((tag) => {
      if (tag.includes(filter)) {
        result.push(student);
      }
    });
  });
  return resu<
};

Как я могу уменьшить временную сложность? Я думал о создании объекта с тегами name ->, а затем просмотреть его, но, похоже, это тот же O(n) в квадрате.

Комментарии:

1. Вы почти всегда можете уменьшить временную сложность, используя карту ключей/значений/словарь для поиска. Кроме того, не используйте map as forEach .

2. Я пытался, но, похоже, мне придется пройти через каждое значение ключа и через каждое значение (массив), и в любом случае это O(n) в квадрате

3. Взгляните на структуру данных Trie или «Дерево префиксов», чтобы создать индекс.

Ответ №1:

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

  • каждый студент
  • каждый тег внутри каждого ученика
  • каждый символ внутри каждой строки тега (абстрагируется за .includes )

Это требует значительной вычислительной сложности, которую вы уже реализуете довольно разумно.

Но вы можете сделать код немного лучше и уменьшить немного ненужных накладных расходов. Не используйте .map для побочных эффектов-для побочных эффектов, используйте forEach или for..of . Но лучший подход здесь состоял бы в том, чтобы использовать .filter для построения нового массива объектов учащихся в зависимости от того, какие из них проходят тест, поскольку вы, вероятно, хотите отправить только одного учащегося, когда он соответствует, а не этого учащегося для каждого соответствующего тега.

 const filterByTag = (filter) => {
    return initialStudents.filter(student => 
        student.tags.some(
            tag => tag.includes(filter)
        )
    );
};

(Используйте только .map , когда вы используете результат вызова в качестве нового массива — например const mappedArray = originalArray.map(... )

Метки: