Кто я? (пропустите, если вам не интересно)
Привет. Меня зовут Мартина. Я работал в университете, а в университете на написание статьи уходят месяцы (иногда даже годы). Вы пишете его, затем ваши коллеги проверяют его, затем компания по проверке орфографии проверяет его на английский язык, после чего вы отправляете его в журнал. В основном, они отвергают это :D или нет, но вам придется переписать большую часть вашей статьи. Итак, вы делаете... и показываете это своему коллеге и так далее. :D
Я хочу сказать, что я не привык свободно писать и публиковать статьи. Это моя первая попытка здесь, на Medium, так что, пожалуйста, потерпите меня ;)
LeetCode и его проблемы
Вчера я начал с задач на LeetCode. Дело не в том, что я программист или разработчик. В прошлом я просто занимался кодированием и недавно начал изучать машинопись.
Число Ромена в целое число
В первом задании предлагается преобразовать число Ромена в целое число.
Испытывающий? Может быть, но поскольку проблема объяснена очень четко, и нам не нужно проверять, является ли заданное число действительным римским числом, сложность этой задачи быстро уменьшается.
Понимая это, я не стал долго думать о вызове и просто начал писать код.
Мое первое решение 1: как я туда попал?
Прежде всего, я просто разбил данный номер Ромена на символы. Поскольку я не знал синтаксиса, я погуглил «разделить массив машинописных текстов» :). Google предложил мне несколько вариантов, и я выбрал тот, который показался мне наиболее привлекательным :D […romainNumber]
Следующий шаг: петля и переключатель. Обычно я знаю два варианта зацикливания: for и while. Сначала я не думал об этом много. Цикл for мне более знаком, поэтому я пошел на него. Я просто просмотрел символы числа Ромена и добавил значения вместе на основе его числового значения.
function romanToInt(s: string): number {
let answer:number = 0;
let splittedArray:Array<string> = […s];
let splittedArrayLength:number = splittedArray.length;
for (i, i<splittedArrayLength, i++) {
switch(splittedArray[i]){
case ‘I’:
answer = answer+1;
break;
case ‘V’:
answer = answer+5;
break;
case ‘X’:
answer = answer+10;
break;
case ‘L’:
answer = answer+50;
break;
case ‘C’:
answer = answer+100;
break;
case ‘D’:
answer = answer+500;
break;
case ‘M’:
answer = answer+1000;
break;
default:
break;
}
}
return answer;
};
Конечно, это решение не работает, если требуется вычитание (например, CD представляет не 100 + 500, а 500-100).
На этом этапе задача могла усложниться, но LeetCode снова облегчил нам задачу. Это ясно объясняет случаи, которые необходимо учитывать в нашем решении:
Упрощенно я просто добавил эти условия в свой код и переключился с цикла for на цикл while, потому что цикл for не позволяет пропустить шаги:
function romanToInt(s: string): number {
let answer:number = 0;
let splittedArray:Array<string> = [...s];
let splittedArrayLength:number = splittedArray.length;
let i:number = 0;
while (i<splittedArrayLength) {
switch(splittedArray[i]){
case 'I':
if(splittedArray[i+1] === 'V'){
answer = answer+4;
i = i+2;
break;
}
if(splittedArray[i+1] === 'X'){
answer = answer+9;
i = i+2;
break;
}
answer = answer+1;
i++;
break;
case 'V':
answer = answer+5;
i++;
break;
case 'X':
if(splittedArray[i+1] === 'L'){
answer = answer+40;
i = i+2;
break;
}
if(splittedArray[i+1] === 'C'){
answer = answer+90;
i = i+2;
break;
}
answer = answer+10;
i++;
break;
case 'L':
answer = answer+50;
i++;
break;
case 'C':
if(splittedArray[i+1] === 'D'){
answer = answer+400;
i = i+2;
break;
}
if(splittedArray[i+1] === 'M'){
answer = answer+900;
i = i+2;
break;
}
answer = answer+100;
i++;
break;
case 'D':
answer = answer+500;
i++;
break;
case 'M':
answer = answer+1000;
i++;
break;
default:
break;
}
}
return answer;
};
И вуаля! У нас есть первое решение. Конечно, это не самое лучшее решение, но оно работает, и мы легко можем его понять. Что меня порадовало, так это то, что это не самое худшее решение. Нажав на ссылку отправки, LeetCode выдает вам хорошую статистику:
Это решение заняло 183 мс и использовало 48,1 МБ памяти. Как видим, почти 40% других решений (на LettCode) считаются менее эффективными.
«Оптимизация» №1 (277мс, 48,1МБ)
Было уже довольно поздно, когда я закончил свое первое решение, и мне захотелось немного поспать. Тем не менее, это меня очень беспокоило. Что сделали другие люди, чтобы сделать свои решения более эффективными?
Гугл как всегда ответил на мой вопрос. Просто выполнив поиск «преобразование javascript/typescript из латинского в целое число», я нашел много решений с разными подходами.
Приняв некоторые идеи, я начал оптимизировать свое решение. Я понял две важные вещи:
- Во-первых, может быть удобно переключить символы Romain на целые числа и работать с числами, потому что числа легче сравнивать:
function numericValueOfRomanSymbol(symbol: string){
switch(symbol){
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: break;
}
}
- Во-вторых, мне не нужно пропускать итерации. Взяв, к примеру, число Ромена MCMXC, мне не нужно прибавлять 1000 + 900 + 90. Я могу сделать 1000–100, на следующей итерации я могу добавить 1000, на следующей итерации я могу вычесть 10. , а на следующей итерации добавьте 100.
function romanToInt(s: string): number {
let answer:number = 0;
let splittedArray:Array<string> = [...s];
let splittedArrayLength:number = splittedArray.length;
let i:number = 0;
for(i; i<splittedArrayLength; i++){
if(numericValueOfRomanSymbol(splittedArray[i]) >= numericValueOfRomanSymbol(splittedArray[i+1]) || i === splittedArrayLength-1){
answer = answer + numericValueOfRomanSymbol(splittedArray[i]);
}else{
answer = answer - numericValueOfRomanSymbol(splittedArray[i]);
}
}
return answer;
};
Уф, может и покороче, но читается точно не легко :( к тому же производительность у него значительно хуже:
«Оптимизация» №2 (202мс, 48,2Мб)
Показав мое «оптимизированное» решение моему парню (старшему разработчику React), он придумал несколько идей, как его улучшить:
- Во-первых, не вызывайте «numericValueOfRomanSymbol» много раз, вместо этого используйте переменные. Это не только повышает производительность, но и делает код чище.
- Во-вторых, поэкспериментируйте с функцией разделения.
- В-третьих, попробуйте использовать хэш-карту вместо переключателя при преобразовании латинских символов в целые числа.
function romanToInt(s: string): number {
let answer:number = 0;
let splittedArray:Array<string> = [...s];
let splittedArrayLength:number = splittedArray.length;
let i:number = 0;
for(i; i<splittedArrayLength; i++){
let numericValueOfTheFirstSymbol = numericValueOfRomanSymbol(splittedArray[i]);
let numericValueOfTheSecondSymbol = numericValueOfRomanSymbol(splittedArray[i+1]);
if(numericValueOfTheFirstSymbol >= numericValueOfTheSecondSymbol || i === splittedArrayLength-1){
answer = answer + numericValueOfTheFirstSymbol;
}else{
answer = answer - numericValueOfTheFirstSymbol;
}
}
return answer;
};
Определенно помогло введение переменных вместо многократного вызова одной и той же функции. Однако производительность все равно была хуже, чем в начале.
Эксперимент с функцией разделения
Есть два наблюдения, которыми я хотел бы поделиться, говоря о параметрах разделения в javascript.
- Во-первых, кажется (по крайней мере, в данном случае), что функция скобок […wordToSplit] более эффективна, чем функция разделения wordToSplit.split(‘ ’).
- Во-вторых, работать с массивом определенно эффективнее, чем без него. Несмотря на то, что возможен прямой доступ к символам в строке, это неэффективный подход.
Хэш-карта против коммутатора
Принимая во внимание идею переключения переключателя для карты хэшей, я попробовал два способа отображения оставшихся символов в целые числа:
Опция 1:
let hashMapRomanToInteger = new Map();
hashMapRomanToInteger.set('I', 1);
hashMapRomanToInteger.set('V', 5);
hashMapRomanToInteger.set('X', 10);
hashMapRomanToInteger.set('L', 50);
hashMapRomanToInteger.set('X', 10);
hashMapRomanToInteger.set('C', 100);
hashMapRomanToInteger.set('D', 500);
hashMapRomanToInteger.set('M', 1000);
Вариант 2:
const hashMapRomanToInteger ={
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
Однако оба эти варианта кажутся менее эффективными, чем исходная функция переключения.
Мое окончательное решение (124 мс, 47,4 МБ)
Окончательное и наиболее эффективное решение, которое я нашел, восходит к циклу while. Причина проста: пропуск итераций увеличивает скорость. Если в римском числе возможно вычитание, мы можем пропустить одну итерацию, добавляя вычитаемое значение непосредственно к ответу.
function numericValueOfRomanSymbol(symbol: string){
switch(symbol){
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: break;
}
}
function romanToInt(s: string): number {
let answer:number = 0;
let splittedArray:Array<string> = [...s];
let splittedArrayLength:number = splittedArray.length;
let i:number = 0;
while(i<splittedArrayLength){
let numericValueOfTheFirstSymbol = numericValueOfRomanSymbol(splittedArray[i]);
let numericValueOfTheSecondSymbol = numericValueOfRomanSymbol(splittedArray[i+1]);
if(numericValueOfTheFirstSymbol >= numericValueOfTheSecondSymbol || i === splittedArrayLength-1){
answer = answer + numericValueOfTheFirstSymbol;
i++;
}else{
answer = answer - numericValueOfTheFirstSymbol + numericValueOfTheSecondSymbol;
i = i+2;
}
}
return answer;
};
Как видите, производительность значительно лучше. Эффективнее этого решения менее 6%!
Я счастлив и иду к следующему вызову :)
PS: Есть ли у вас какие-либо идеи о том, как улучшить мое решение? Я был бы очень рад победить 100% :)
