Уменьшите сложность сопоставления элементов двух массивов - PullRequest
Новая
       97

Уменьшите сложность сопоставления элементов двух массивов

1 голос
/ 09 мая 2020

Я написал код, который извлекает заголовки столбцов (первую строку на листе) из листа Google и сравнивает их с массивом объектов. Каждый объект в массиве объектов имеет 3 свойства: «вопрос», «ответ» и «категория». Код сравнивает заголовок каждого столбца со свойством «вопрос» для каждого объекта в массиве.

Если они похожи, он должен добавить индекс столбца в качестве ключа к некоторому словарю и установить его value как массив, содержащий ответ и категорию этого вопроса. Не нужно много объяснять, почему я это делаю, но вкратце я построил этот logi c, чтобы иметь возможность оценивать ответы соискателей на некоторые вопросы (следовательно, связав индекс вопроса с правильным ответом и с его категорией). Вот код: 

 for (i = 0; i<columnHeaders[0].length; i++){
    for (j=0; j<questionsObjects.length; j++){
      //Get the current question and convert it to lower case
      question = questionsObjects[j].question.toString().toLowerCase(); 

      //Get column header, remove any spaces and new lines from it, and convert it to lower case
      columnHeader = columnHeaders[0][i].toString().toLowerCase();


      if (isStringSimilar(columnHeader, question)){

        //Link the column index to its corresponding question object
        var catAndAnswer = []; 
        catAndAnswer.push (questionsObjects[j].category.toLowerCase()); 
        catAndAnswer.push (questionsObjects[j].rightAnswer.toLowerCase()); 

        columnsQuestionsDictionary[i] = catAndAnswer; 
      } else {
        SpreadsheetApp.getActive().getSheetByName("log").appendRow(["no", columnHeader, question]); 
      }
    }
  }

Код работает хорошо, моя единственная проблема - сложность, она очень высока. В некоторых случаях для выполнения этого метода требуется почти 6 минут (в этом случае у меня было около 40 столбцов и 7 объектов вопросов)! Чтобы отделить вложенные циклы, я подумал о том, чтобы объединить значения вопросов (всех объектов в массиве объектов вопросов) в одну строку, в которой каждому вопросу предшествует его индекс в массиве объектов.

Например: 

  var str = ""; 

  for (j=0; j<questionsObjects.length; j++){

    str = str + j + questionsObjects[j].question.toString.toLowerCase();

  }

Затем я могу иметь еще один отдельный l oop через заголовки столбцов, извлекать каждый заголовок в строку, а затем использовать метод регулярного выражения exec для сопоставления этот заголовок в длинной строке вопросов (str), и если он будет найден, я получу его индекс в str, а затем вычтите из него 1, чтобы узнать его индекс в массиве объектов. Однако оказалось, что сложность сопоставления регулярного выражения составляет O (N), где N - длина строки, в которой мы ищем (str в этом примере), учитывая, что это будет внутри столбцов l oop, I видим, что мы все еще получаем высокую сложность, которая может от go до O (N ^ 2).

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

1 Ответ

1 голос
/ 10 мая 2020

Хорошо, поэтому я использовал способ, предложенный Ниной Шхольц в комментариях, и переместил columnHeader = columnHeaders[0][i].toString().toLowerCase(); во внешний l oop вместо внутреннего, поскольку он нужен только в внешний.

Время, необходимое для запуска кода, было сокращено с ~ 295 секунд до ~ 208 секунд, что хорошо.

Я также попытался изменить порядок циклов, сделав внешний l oop внутренним, а внутренний - внешним, и обновил использование i и j соответственно. Я сделал это, потому что всегда рекомендуется иметь внешний l oop с меньшим количеством итераций, а внутренний - с большим количеством итераций (согласно этому resource ), а в моем случае l oop, который повторяет Ожидается, что массив объектов over questions всегда будет иметь количество итераций <= остальные l oop. </p>

Это потому, что если мы хотим вычислить сложность 2 вложенных циклов, это будет (ixj) + i, где i и j представляют количество итераций внешнего и внутреннего циклов соответственно. Изменение порядка циклов не повлияет на часть умножения (ixj), но повлияет на часть сложения. Так что всегда лучше, чтобы внешнее количество итераций было меньше внутренних.

После этого окончательное время пробега стало ~ 202 секунды.

Конечно, поскольку теперь циклы переключаются, я переместил эту строку на внутренний l oop: columnHeader = columnHeaders[0][i].toString().toLowerCase();, но в то же время я переместил этот question = questionsObjects[j].question.toString().toLowerCase(); под внешний l oop потому что он нужен только там.

...