Ускорение работы алгоритма

Question

Для решения следующей задачи мною был составлен следующий алгоритм. На вход два аргумента - data и dictionary. В переменной data передается массив объектов вида:

  {  
      geometry: [number, number];  
      text: string;  
  }

В переменной dictionary передается массив строк - слова, которые мы умеем расшифровывать. dictionary: string[];

Чтобы получить секретное сообщение, требуется отсортировать все объекты из массива data по первой координате из поля geometry по возрастанию, а затем собрать в строку все поля text из отсортированного массива. К сожалению, сообщение закодировано на иностранном языке, а переводчик знает только слова, заданные в переменной dictionary. Поэтому если в поле text встречается слово, которого нет в массиве dictionary, сообщение невозможно расшифровать. Программа должна вернуть полученное сообщение или строку "Unreadable message"(в случае, если сообщение содержит слова, которых нет в словаре). Каким образом его можно улучшить?

 module.exports = function (inputData, inputDictionary) {
        const hashMap = {};
            inputData.sort((item1, item2) => item1.geometry[0] - item2.geometry[0]);
            inputDictionary.forEach(elem => {
                hashMap[elem] = true;
                });
            let textMessages = "";
            for(let i = 0; i < inputData.length; i++){
                if(!hashMap[inputData[i]["text"]]){
                    return "Unreadable message";
             } else {
                textMessages += inputData[i]["text"] + (i === inputData.length - 1 ? "" : " ");
               }
            }
        
            return textMessages;
          }

Answer 1

Что можно сделать, как мне кажется,

для того, чтобы понять, что сообщение не переводится не требуется предварительно что-то отсортировывать, ведь потом все равно проверяются все слова text из data в dictionary

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

какие именно числа записываются в geometry? если дискретные в небольшом диапазоне (например от 0 до 1000) то сортировку можно провести просто перемещая элементы в такой массив tmp[1001], после чего пройтись по нему и собрать расшифрованную строку
зачем вы заполняете hashMap, когда этого не требуется - вы сразу можете идти и собирать расшифрованную строку:

module.exports = function (inputData, inputDictionary) 
{
    inputData.sort((item1, item2) => item1.geometry[0] - item2.geometry[0]);
    let textMessages = "";
    for(let i = 0; i < inputData.length; i++){
        if(dictionaty[inputData[i].text] === undefined){
            return "Unreadable message";
        } else {
            textMessages += inputData[i]["text"] + (i === inputData.length - 1 ? "" : " ");
        }
    }       
    return textMessages;
}

кстати эта проверка каждый раз (i === inputData.length - 1 ? "" : " "); не нужна - лучше после цикла отрезать последний пробел в строке

БЛОГ НА HUSL

Ускорение работы алгоритма

Ответы (1 шт):