Блог

Я только что прошел онлайн-тест по программированию, и этот вопрос действительно беспокоил меня. Мое решение было правильным, но было отклонено из-за неоптимизации. Вопрос заключается в следующем:

Напишите функцию combineTheGivenNumber , принимающую два аргумента:

1. numArray : число []
2. num : число

Функция должна проверять все пары конкатенации, которые могут привести к получению числа, равного num и возвращать их количество.

Например. если numArray = [1, 212, 12, 12] amp; num = 1212, то мы будем иметь возвращаемое значение из 3 combineTheGivenNumber

Пары выглядят следующим образом:

1. numArray[0] numArray[1]
2. numArray[2] numArray[3]
3. numArray[3] numArray[2]

Функция, которую я написал для этой цели, выглядит следующим образом:

 function combineTheGivenNumber(numArray, num) {
  //convert all numbers to strings for easy concatenation
  numArray = numArray.map(e => e '');
  //also convert the `hay` to string for easy comparison
  num = num '';
  let pairCounts = 0;
  
  // itereate over the array to get pairs
  numArray.forEach((e,i) => {
    numArray.forEach((f,j) => {
    if(i!==j amp;amp; num === (e f)) {
        pairCounts  ;
       }
    });
  });
  
  return pairCounts;
}

console.log('Test 1: ', combineTheGivenNumber([1,212,12,12],1212)); 

console.log('Test 2: ', combineTheGivenNumber([4,21,42,1],421));  

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

Исключение строки из числа в строку приведет к значительному увеличению скорости, но я не уверен, как в противном случае проверить наличие конкатенированных чисел.

Исключение строки из числа в строку значительно повысит скорость

Нет, этого не произойдет.

Во-первых, вы нигде не преобразуете строки в числа, но, что более важно, упражнение требует конкатенации, поэтому работа со строками — это именно то, что вы должны делать. Понятия не имею, почему они даже передают числа. У вас уже все в порядке, выполняя преобразование только один раз для каждого ввода числа, а не каждый раз, когда вы формируете пару. И последнее, но не менее важное: отказ от преобразования не будет значительным улучшением.

Чтобы добиться значительного улучшения, вы должны использовать лучший алгоритм. @derpirscher прав в своем комментарии: «[Это] вложенный цикл, проверяющий каждую возможную комбинацию, которая достигает ограничения по времени. Например, для вашего примера, когда внешний цикл указывает на 212 то, что вам не нужно выполнять какие-либо проверки, потому что независимо от того, что вы объединяете 212 , это никогда не может привести к 1212 «.

Поэтому используйте

 let pairCounts = 0;
numArray.forEach((e,i) => {
  if (num.startsWith(e)) {
//^^^^^^^^^^^^^^^^^^^^^^
    numArray.forEach((f,j) => {
      if (i !== j amp;amp; num === e f) {
        pairCounts  ;
      }
    });
  }
});
 

Вы можете сделать то же самое с суффиксами, но становится сложнее исключить конкатенацию с самим собой.

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

 function combineTheGivenNumber(numArray, num) {
  const strings = new Map();
  for (const num of numArray) {
    const str = String(num);
    strings.set(str, 1   (strings.get(str) ?? 0));
  }
  const whole = String(num);
  
  let pairCounts = 0;
  for (const [prefix, pCount] of strings) {
    if (!whole.startsWith(prefix))
      continue;
    const suffix = whole.slice(prefix.length);
    if (strings.has(suffix)) {
      let sCount = strings.get(suffix);
      if (suffix == prefix) sCount--; // no self-concatenation
      pairCounts  = pCount*sCount;
    }
  }
  return pairCounts;
}
 

(правильная обработка дубликатов немного затруднена)

Мне нравится ваш подход к раннему переходу к строкам. Я могу предложить пару простых оптимизаций.

Вам нужны только числа, которые являются допустимыми «первыми частями», и те, которые являются допустимыми «вторыми частями»

Вы можете использовать javascript .startsWith и .endsWith протестировать эти условия. Все остальные строки можно выбросить.

Длина строк должна составлять длину желаемого ответа

Предположим, что ваша целевая строка имеет длину 8 цифр. Если у вас есть 2 допустимых 3-значных «первых части», то вам нужно только знать, сколько у вас допустимых 5-значных «вторых частей». Предположим, у вас их 9. Эти первые части могут объединяться только со вторыми частями и давать вам 2 * 9 = 18 допустимых пар.

На самом деле вам не нужно хранить струны!

Меня поразило, что если вы знаете, что у вас есть 2 действительных 3-значных «первых части», вам не нужно сохранять эти фактические строки. Знание того, что они являются действительными 2-значными первыми частями, — это все, что вам нужно знать.

Итак, давайте создадим массив, содержащий:

   How many valid 1-digit first parts do we have?,
  How many valid 2-digit first parts do we have?,
  How many valid 3-digit first parts do we have?,
  etc.
 

И аналогично массив, содержащий количество допустимых 1-значных вторых частей и т.д.

X первые части и Y вторые части могут быть объединены X * Y способами

За исключением случаев, когда части имеют одинаковую длину, и в этом случае мы повторно используем один и тот же список, и поэтому это просто X * (Y-1).

Таким образом, нам не только не нужно сохранять строки, но нам нужно только выполнить умножение соответствующих элементов массивов.

5 1-символьных первых частей и 7 3-символьных вторых частей = 5 * 7 = 35 пар

6 2-символьных первых частей и 4 2-символьных вторых части = 6 * (4-1) = 18 пар

и т. д

Так что это становится чрезвычайно просто. Один проход по струнам, подсчитывая совпадения «первой части» и «второй части» каждой длины. Это можно сделать с помощью an if и a соответствующего элемента массива.

Затем один проход по длинам, который будет очень быстрым, так как массив длин будет намного короче массива фактических строк.

 function combineTheGivenNumber(numArray, num) {
  const sElements = numArray.map(e => ""   e);
  const sTarget = ""   num;
  const targetLength = sTarget.length
  const startsByLen = (new Array(targetLength)).fill(0);
  const endsByLen = (new Array(targetLength)).fill(0);

  sElements.forEach(sElement => {
    if (sTarget.startsWith(sElement)) {
      startsByLen[sElement.length]  
    }
    if (sTarget.endsWith(sElement)) {
      endsByLen[sElement.length]  
    }
  })
  // We can now throw away the strings. We have two separate arrays:
  // startsByLen[1] is the count of strings (without attempting to remove duplicates) which are the first character of the required answer
  // startsByLen[2] similarly the count of strings which are the first 2 characters of the required answer
  // etc.
  // and endsByLen[1] is the count of strings which are the last character ...
  // and endsByLen[2] is the count of strings which are the last 2 characters, etc.

  let pairCounts = 0;

  for (let firstElementLength = 1; firstElementLength < targetLength; firstElementLength  ) {
    const secondElementLength = targetLength - firstElementLength;
    if (firstElementLength === secondElementLength) {
      pairCounts  = startsByLen[firstElementLength] * (endsByLen[secondElementLength] - 1)
    } else {
      pairCounts  = startsByLen[firstElementLength] * endsByLen[secondElementLength]
    }
  }

  return pairCounts;
}

console.log('Test 1: ', combineTheGivenNumber([1, 212, 12, 12], 1212));
console.log('Test 2: ', combineTheGivenNumber([4, 21, 42, 1], 421)); 

В зависимости от настроек, нарезка целых чисел может быть немного быстрее

Хотя, в конце концов, это не удается

Кроме того, при тестировании на более высоких значениях N предыдущий ответ взорвался в jsfiddle. Возможно, ошибка памяти.

Насколько я тестировал как со случайными, так и с созданными вручную значениями, мое решение остается в силе. Это основано на наблюдении, что если X, Y объединены == Z, то следующее должно быть истинным:
Z - Y == X * 10^(floor(log10(Y)) 1)
пример этого:
1212 - 12 = 1200
12 * 10^(floor((log10(12)) 1) = 12 * 10^(1 1) = 12 * 100 = 1200

Теперь, теоретически, это должно быть быстрее, чем манипулирование строками. И на многих других языках это, скорее всего, так и было бы. Однако в Javascript, как я только что узнал, ситуация немного сложнее. Javascript делает некоторые странные вещи с кастингом, которые я еще не понял. Короче говоря, когда я попытался сохранить числа (и их количество) на карте, код стал значительно медленнее, что привело к тому, что любые возможные выгоды от этих махинаций с логарифмами испарились. Кроме того, хранение их в пользовательской структуре данных не гарантировано будет быстрее, так как вам нужно ее создать и т.д. Также это было бы довольно много работы.

В нынешнем виде это логарифмическое сравнение выполняется в ~ 8 раз быстрее в случае без совпадений (или всего с несколькими), поскольку квадратичный коэффициент еще не введен. Пока возможное количество постфиксов не слишком велико, оно будет превосходить линейное решение. К сожалению, он по-прежнему носит квадратичный характер, а точка разрыва зависит от общего количества строк, а также от их длины.

Так что, если вы ищете иголку в стоге сена — например, вы ищете несколько пар в огромной куче чисел, это может помочь. В другом случае поиска большого количества совпадений это не поможет. Аналогично, если входной массив был отсортирован, вы могли бы использовать двоичный поиск, чтобы повысить критическую точку.

В конце концов, если вам не удастся выяснить, как хранить целые числа на карте (или в какой-либо ее пользовательской реализации) таким образом, чтобы это полностью не снижало производительность, линейное решение предыдущего ответа будет быстрее. Это все равно может быть полезно даже при снижении производительности, если ваши вычисления будут занимать много памяти. Хранение чисел занимает меньше места, чем хранение строк.

 var log10 = Math.log(10)
function log10floored(num) {
     return Math.floor(Math.log(num) / log10)
}
function combineTheGivenNumber(numArray, num) {
      count = 0
      for (var i=0; i!=numArray.length; i  ) {
        let portion = num - numArray[i]
        let removedPart = Math.pow(10, log10floored(numArray[i]))
        if (portion % (removedPart * 10) == 0) {
          for (var j=0; j!=numArray.length; j  ) {
                    
                        if (j != i amp;amp; portion / (removedPart * 10) == numArray[j] ) {
                    count  = 1
             }
           }  
         }  
        }
      return count
      
      }
 //The previous solution, that I used for timing, comparison and check purposes 
 function combineTheGivenNumber2(numArray, num) {
  const strings = new Map();
  for (const num of numArray) {
    const str = String(num);
    strings.set(str, 1   (strings.get(str) ?? 0));
  }
  const whole = String(num);
  
  let pairCounts = 0;
  for (const [prefix, pCount] of strings) {
    if (!whole.startsWith(prefix))
      continue;
    const suffix = whole.slice(prefix.length);
    if (strings.has(suffix)) {
      let sCount = strings.get(suffix);
      if (suffix == prefix) sCount--; // no self-concatenation
      pairCounts  = pCount*sCount;
    }
  }
  return pairCounts;
}
var myArray = []
for (let i =0; i!= 10000000; i  ) {
    myArray.push(Math.floor(Math.random() * 1000000))
}
var a = new Date()
t1 = a.getTime()
console.log('Test 1: ', combineTheGivenNumber(myArray,15285656)); 
var b = new Date()
t2 = b.getTime()
console.log('Test 2: ', combineTheGivenNumber2(myArray,15285656)); 
var c = new Date()
t3 = c.getTime()

console.log('Test1 time: ', t2 - t1)
console.log('test2 time: ', t3 - t2)
 

Небольшое обновление

До тех пор, пока вы готовы снизить производительность при настройке и согласиться на увеличение производительности в ~ 2 раза, может помочь использование простой таблицы «хеширования».(Таблицы хеширования хороши и аккуратны, это простая таблица поиска по модулю. Хотя принцип похож.)

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

 function combineTheGivenNumber(numArray, num) {
  count = 0
  let size = 1000000
  numTable = new Array(size)
  for (var i=0; i!=numArray.length; i  ) {
    let idx = numArray[i] % size
    if (numTable[idx] == undefined) {
        numTable[idx] = [numArray[i]]
    } else {
      numTable[idx].push(numArray[i])
    }       
  }
  for (var i=0; i!=numArray.length; i  ) {
    let portion = num - numArray[i]
    let removedPart = Math.pow(10, log10floored(numArray[i]))
    if (portion % (removedPart * 10) == 0) {
      if (numTable[portion / (removedPart * 10) % size] != undefined) {
        let a = numTable[portion / (removedPart * 10) % size]
        for (var j=0; j!=a.length; j  ) {

          if (j != i amp;amp; portion / (removedPart * 10) == a[j] ) {
              count  = 1
           }
         }  
       }  
      }
    }
  return count
  
  }
 

Вот упрощенный и частично оптимизированный подход с 2 циклами:

 // let's optimise 'combineTheGivenNumber', where
// a=array of numbers AND n=number to match
const ctgn = (a, n) => {
  // convert our given number to a string using `toString` for clarity
  // this isn't entirely necessary but means we can use strict equality later
  const ns = n.toString();
  
  // reduce is an efficient mechanism to return a value based on an array, giving us
  // _=[accumulator], na=[array number] and i=[index]
  return a.reduce((_, na, i) => {
    // convert our 'array number' to an 'array number string' for later concatenation
    const nas = na.toString();
    
    // iterate back over our array of numbers ... we're using an optimised/reverse loop
    for (let ii = a.length - 1; ii >= 0; ii--) {
      // skip the current array number
      if (i === ii) continue;
      
      // string   number === string, which lets us strictly compare our 'number to match'
      // if there's a match we increment the accumulator
      if (a[ii]   nas === ns)   _;  
    }
    
    // we're done
    return _;
  }, 0);
}