3

Помогите оптимизировать код так, чтобы он быстрее выполнялся

var res = 0
var (c) = readLine()!!.split(' ').map(String::toInt)
val num = arrayListOf<Int>()
while (c != 0) {
    num.add(c % 10)
    c /= 10 
}
for (i in num) {
    if (i % 3 == 0) {
        res += i
    }
}
print(res)
insolor
  • 49,104
Makar Makar
  • 39
  • 3
    А что он должен делать? – Эникейщик Dec 16 '19 at 14:00
  • Из целого числа находит сумму цифр кратных 3 – Makar Makar Dec 16 '19 at 14:04
  • var (c) = readLine()!!.split(' ').map(String::toInt) зачем тут эта конструкция? Если у вас несколько чисел на входе, то всё что после readLine()!! бессмысленно, потому что вы берёте только первую из них и выкидываете всё остальное – IR42 Dec 16 '19 at 15:44

2 Answers2

3

Надо все делать в 1-м цикле, примерно так:

while (c != 0) {
    if(((c % 10) % 3)==0)
      res+=(c%10)
    c /= 10 
}

Update

А если такой вариант (смесь моего варианта и @Эникейщик)?

Экономия на операции деление по модулю, которая по сути является операцией:

c%10=(c-(c/10)*10)

а поскольку операция деления один раз уже делается то есть экономия на 1-й операции деления.

while (c != 0) {
    a=c/10
    when (c-10*a) {
       3 -> res = res + 3
       6 -> res = res + 6
       9 -> res = res + 9
    }   
    c=a
 }
Barmaley
  • 81,300
  • Проверил. Если сначала замерять мой вариант, а потом ваш, то ваш быстрее (~15%)ю. А если сначала замерять ваш, а потом мой, то быстрее мой (~30%). – Эникейщик Dec 16 '19 at 15:49
  • Я недавно как раз где-то увидел этот небольшой хак, чтобы два раза на одно и то же не делить, но уже успел забыть о нем :) – Эникейщик Dec 16 '19 at 19:09
  • Ну с when и хардкодингом суммирования - тоже неплохой ход :) – Barmaley Dec 17 '19 at 10:51
2

Предлагаю такой вариант:

var res = 0
var c = readLine()!!.split(' ').map(String::toInt)
while (c!= 0) {
    when (c % 10) {
        3 -> res = res + 3
        6 -> res = res + 6
        9 -> res = res + 9
    }
    c= c/ 10
}
print(res)

Минус цикл, минус массив, сокращение количества делений с остатком (более дорогая операция, чем сравнение).

Прогнал оба способа (ваш и мой) на числах от 1 до 10 и до 100 млн. Мой способ быстрее в 3-4 раза. Код для сравнения:

import kotlin.system.measureTimeMillis

fun mineFun(num: Int): Int {
    var numTemp = num
    var res = 0

    while (numTemp != 0) {
        when (numTemp % 10) {
            3 -> res = res + 3
            6 -> res = res + 6
            9 -> res = res + 9
        }
        numTemp = numTemp / 10
    }
    return res
}

fun notMineFun(num: Int): Int {
    var c = num
    var res = 0
    val numArray = arrayListOf<Int>()
    while (c != 0) {
        numArray.add(c % 10)
        c /= 10
    }
    for (i in numArray) {
        if (i % 3 == 0) {
            res += i
        }
    }
    return res
}

fun main() {
    val limit = 10_000_000
    var x = 0
    val t1 = measureTimeMillis {
        for (n in 1..limit) {
            x = mineFun(n)
        }
    }

    val t2 = measureTimeMillis {
        for (n in 1..limit) {
            x = notMineFun(n)
        }
    }

    println(t1)
    println(t2)
}
Эникейщик
  • 26,625