1w фрагментов данных, мозаичный массив в древовидную структуру

JavaScript

1w фрагментов данных было потеряно в фоновом режиме

После тысяч вычислений я до сих пор не убежал, фон действительно выбрасывает на фронтенд десятки тысяч данных за раз. Ну, к счастью, это не 10w. Таким образом, фон возвращает эту структуру:

const flatArr = [
  { id: '001', name: '节点1' },
  { id: '0011', parentId: '001', name: '节点1-1' },
  { id: '00111', parentId: '0011', name: '节点1-1-1' },
  { id: '002', name: '节点2' },
]

Как видите, на самом деле это тайловый массив, наше требование — отображать такие данные вElement-uiВ каскадном селекторе он получает следующую древовидную структуру:

let options = [
  {
    value: 'zhinan',
    label: '指南',
    children: [
      {
        value: 'shejiyuanze',
        label: '设计原则',
        children: [
          { value: 'yizhi', label: '一致' },
          { value: 'fankui', label: '反馈'}
        ],
      }
    ]
  }
]

Хороший парень, разве это не требует от меня преобразования мозаичного массива в древовидную структуру!

Операция лютая как тигр, а рекурсия пишется без слов.

рекурсивный путь

carbon.png

Готово, код лаконичен, мысль ясна, как только запустится, что? Страница застряла,console.time()Расчет, на расчет нужной нам древовидной структуры ушло около 18 секунд.

Я задумался над собой, это десятки тысяч кусков данных, каждый раз, когда я рекурсивно ищу дочерние узлы родительского узла снизу вверх, мне нужно один раз пройтись по массиву, что, конечно, требует много времени! Более того, время расчета явно привело к зависанию страницы.Этот метод определенно нежелателен.Итак, есть ли лучшее решение?

нерекурсивный

carbon.pngУмное приложение здесьОбъекты содержат ссылкиХарактеристики каждый раз, когда идентификатор текущего узла используется в качестве ключа, справочная информация соответствующего узла сохраняется, а информация о дочерних элементах objMap обновляется каждый раз при обходе массива, так что все узлы и дочерние узлы сохраняется в objMap. Самое главное, что нам нужно толькоперебирать массив,Временная сложность O (n). Таким образом, время расчета составляет всего 60 мс!

Суммировать

  • рекурсивный путь: каждый раз, когда вы рекурсивно находите дочерние узлы текущего узла, вам нужно снова пройти массив, и временная сложностьO(nlogn)
  • нерекурсивный: найти дочерние узлы от корневого узла вниз, сохранить информацию о каждом узле и его дочерних узлах через карту, дочерние узлы сохраняют ссылку на карте, дочерние узлы каждого узла можно найти на карте по идентификатору, время сложноO(n)

Давайте посмотрим на сравнительную таблицу:

image.png

Из приведенной выше тенденции временной сложности видно, что по мере увеличения объема данных, когда данные становятся все больше и больше, время, необходимое для рекурсивного алгоритма, будет намного больше, чем для нерекурсивного алгоритма. Поэтому, когда количество данных невелико, рекурсивный алгоритм имеет определенные преимущества, но когда данные в определенной степени велики, недостаток рекурсивного подхода будет становиться все более и более очевидным, и нерекурсивный алгоритм будет намного эффективнее. Быстрее!

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

Категории