In the Day 7 advent of code, part 2 requires two ints to be converted to strings, concatenated and then converted back into an int. This concatenation is in a 3 level deep loop.
The solution without this step runs in 40 ms Using the concatenation the runtime goes up to 46852 ms. If I replace the concatenation with a subtraction (an experiment just to replace the concatenation with a purely int based calculation) the run time only goes up to 463 ms
# int experiment
myNewResults.add( myLHS - myTerm)
# the needed string concatenation
myNewResults.add( ($myLHS & $myTerm).parseInt)There is no way to avoid the conversions and the string concatenations, but some optimizations are possible.
First, you can reduce the number of conversions from int to string as for one operand (“myTerm” in your example) you already know its string representation (encountered when parsing the input file).
Second, you can reduce the number of operations. The operators Add, Mul and Concat yields increasing values and so you can eliminate partial sums which are greater than the target value (if your algorithm allows that). This is specially useful in the case of concatenations.
Without option “-d:release”, my program runs part 1 in about 80 ms and both parts in about 3,3 seconds. With option “-d:release”, it runs part 1 in 40 ms and both parts in 550 ms.
Without the reduction of number of operations, it runs both parts in 6,8 seconds without “-d:release” and 1,2 second with “-d:release”.
So, in my case the optimization of the number of operations allows to divide the execution time by about a factor two. Compiling with option “-d:release” allows to reduce execution time by about a factor six.
Of course, performance depends also on the algorithm used to compute the possible values.
The same algorithm rewritten in Python – just to see what is possible with an interpreted language – runs in about 3 seconds. This is quite acceptable.
String conversion is very slow, did you consider implementing concatenation without it?
In my solution I use only integers without conversions:
func concat(a: var int, b: int) =
a = a * (10 ^ b.digits) + blog10 is couple times slower in release mode, but it is 20-50% faster than a loop when compiled with -d:danger flag
I didn’t think to this solution. It’s a good idea indeed.
In this problem, you don’t need to compute the number of digits as you can store it when parsing the input file. In my program, I store the whole string to avoid a conversion and storing only the number of digits saves also some time.
I tried this optimization and the program runs in about 175 ms with option “-d:release” (I avoid -d:danger as, except in rare cases, I consider that a program should run with runtime checks). The updated Python version runs in about 2,5 seconds.
Thanks for the input guys. The concatenation discussion in the Advent of Code question is of course (as @janAlkali spotted) a typical piece of Advent of Code helpful misdirection. I went with
proc multiplier(ipNum: int): int =
result = 1
var mynum=ipnum
while myNum > 0:
myNum = myNum div 10
result *= 10
myNewResults.add( myLHS * myTerm.multiplier + myTerm)which resulted in a runtime of 1504 ms :-}
There is no way to avoid the conversions and the string concatenations
There is.