1

Всем привет!

Прошу помощи в понимании как правильно оценить и, самое главное, уменьшить сложность алгоритма.

Проблема - тормозит анимация интерфейса на React при обращении к базе на одном из легаси проектов. При анализе обнаружил большую задержку при отрисовке полученных данных в таблицу.

В выделенном комментариями куске делается сначала .map, внутри ещё один .map, внутри еще .find, да еще и несколько indexOf. Сложность алгоритма, если я правильно понимаю, точно не меньше O(n^2) (а скорее всего больше).

В сети полно информации про определении сложности алгоритмов, но понятной информации по уменьшению этой самой сложности я не нашел. Каким образом можно оптимизировать данный алгоритм? Какие вообще существуют принципы уменьшения сложности?

Заранее спасибо за любую помощь!

                <Table className="YearShedule" striped bordered size="sm">
                  <tbody>

// НАЧАЛО АЛГОРИТМА
                    {monthOrder.map((mName) => (
                      <tr className="YS_row" key={monthOrder.indexOf(mName)}>
                        <td>{monthRusName[mName]}</td>

                        {daysOfMonth.map((d) => {
                          let day_params = this.state.plc.shedule.base.days.find(
                            (el) => el.date == monthOrder.indexOf(mName) + 1 + ':' + d
                          )

                          let ind = this.state.plc.shedule.base.days.indexOf(day_params)
//КОНЕЦ АЛГОРИТМА

                          return day_params ? (
                            <DayShedule
                              key={d}
                              day_params={day_params}
                              title_mn={monthRusName[mName]}
                              title_d={d}
                              changeShedule={(val) => (this.state.plc.shedule.base.days[ind] = val)}
                            />
                          ) : (
                            <td key={d}>
                              <b>{d}</b>
                              <br />
                              &nbsp;
                              <br />
                              &nbsp;
                            </td>
                          )
                        })}
                      </tr>
                    ))}
                  </tbody>
                </Table>
1
  • Вы бы пример данных привели и что у вас this.state.plc.shedule.base.days ну и что требуется сделать. А по уменьшению сложности - надо придумать алгоритм который не будет делать IndexOf. Например заранее пробежаться по массивам (или в том же проходе) и сделать из них словари вроде dict={mName1: first_index1, mName2:...} и тогда брать по словарю уже dict[mName]
    – Mike
    30 ноя 2021 в 10:50

1 ответ 1

1

Боже. Приведу исправленный кусок Вашего кода

{monthOrder.map((mName, i) => (
                  <tr className="YS_row" key={i}>
                    <td>{monthRusName[mName]}</td>

                    {daysOfMonth.map((d) => {
                      let ind = this.state.plc.shedule.base.days.findIndex(
                        (el) => el.date == i + 1 + ':' + d
                      )

                      let day_params = this.state.plc.shedule.base.days[ind]
//КОНЕЦ АЛГОРИТМА

                      return day_params ? (
2
  • спасибо. Таким образом мы избавились от лишних IndexOf. А как быть с остальными вложенными циклами? Правильно ли я понимаю, что основная нагрузка именно из-за них? 30 ноя 2021 в 12:29
  • скорее всего нагрузка из-за перерисовок
    – Sanya H
    30 ноя 2021 в 18:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.