повышение производительности кодообразования

Question

сегодня я слышал об этом сайте, называемом codility, где пользователь может дать различные тесты для проверки производительности своего кода.

Когда я начинал, они представили мне с этим испытанием образца,

Описание задачи Маленькая лягушка хочет, чтобы добраться до другой стороны дороги . Лягушка в настоящее время находится в положении X и хочет получить до положение, большее или равное Y. Маленькая лягушка всегда прыгает на фиксированное расстояние , D. Подсчитайте минимальное количество прыжков, которые должна выполнить лягушка , чтобы достичь его цель.

Написать функцию: class Solution { public int solution(int X, int Y, int D); } , что, учитывая три целых числа X, Y и D, возвращает минимальное количество прыжков с позиции X в положение, равное или большее, чем Y.

Например, дано:
X = 10
Y = 85
D = 30 функция должна возвращать 3, , потому что лягушки будут расположены следующим образом:

после первого прыжка, в положении 10 + 30 = 40

после второго прыжка, в положении 10 + 30 + 30 = 70

после третьего прыжка, в положении 30 + 10 + 30 + 30 = 100

Предположим, что: X, Y и D представляют собой целые числа в диапазоне

[1..1,000,000,000]; X ≤ Y. Сложность: ожидаемое наихудшее время

сложность O (1); ожидаемая наихудшая пространственная сложность - O (1).

Вопрос был довольно прямо вперед, и он взял меня, как 2 минуты, чтобы написать решение, которое следующий,

class Solution { 
    public int solution(int X, int Y, int D) { 

     int p = 0; 
     while (X < Y){ 
      p++; 
      X = X + D; 
     } 
    return p; 
    } 
} 

Однако результат теста показывает, что производительность моего кода просто 20% и я забил только 55%,

Вот ссылка на результат, https://codility.com/demo/results/demo66WP2H-K25/

Это был такой простой код, где я только что использовал одиночный цикл while, как это могло быть сделано намного быстрее?

Answer 1

Основные математике:

X + nD >= Y 
nD >= Y - X 
n >= (Y - X)/D 

Минимальное значение п будет являться результатом округления до разделения (Y - X) через D.

Большой анализ вывода для этой операции:

• Сложность: O (1). Это различие, разделение и сгонять
• Пессимистический пространство сложность O (1): вы можете иметь больше максимум 3 переменные:
  • разница для Y - X, давайте назначим это в Z.
  • Разделите между Z на D, давайте присвойте это в E.
  • Округление E вверх, давайте назначим его в R (из результата).

Answer 2

class Solution { 
    public int solution(int x, int y, int d) { 
     // write your code in Java SE 8 
     System.out.println("this is a debug message"+(y-x)%d); 
     if((y-x)%d == 0) 
      return ((y-x)/d); 
     else 
      return (((y-x)/d)+1); 
    } 
} 

Answer 3

JavaScript решение 100/100

function solution (x,y,d) { 
    if ((y-x) % d === 0) { 
     return (y-x)/d; 
    } else { 
     return Math.ceil((y-x)/d); 
    } 
} 

Answer 4

Вот Scala решение:

def solution(X: Int, Y: Int, D: Int): Int = { 

    //divide distance (Y-X) with fixed jump distance. If there is reminder then add 1 to result to 
    // cover that part with one jump 

    val jumps = (Y-X)/D + (if(((Y-X) % D) >0) 1 else 0) 

    jumps 

    } 

Производительность: https://codility.com/demo/results/trainingTQS547-ZQW/

Answer 5

C# получил 100 из 10 0 баллов

using System; 
// you can also use other imports, for example: 
// using System.Collections.Generic; 

// you can write to stdout for debugging purposes, e.g. 
// Console.WriteLine("this is a debug message"); 

class Solution { 
    public int solution(int X, int Y, int D) { 

     int Len= Y-X; 
     if (Len%D==0) 
     { 
      return Len/D; 
     } 
     else 
     { 
      return (Len/D)+1; 
     } 
    } 
} 

Answer 6

class Solution { 
    public int solution(int x, int y, int d) { 
    return (y - x + d - 1)/d; 
    } 
} 

Answer 7

Java (одна линия), Корректность 100%, производительность 100%, целевая забьет 100%

// you can also use imports, for example: 
// import java.util.*; 

// you can write to stdout for debugging purposes, e.g. 
// System.out.println("this is a debug message"); 

class Solution { 
    public int solution(int X, int Y, int D) { 
     return (int) Math.ceil((double) (Y - X)/(double) D); 
    } 
}