Can this implementation of Damm algorithm be optimized?
Nestor via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Thu Feb 9 13:29:22 PST 2017
On Thursday, 9 February 2017 at 20:46:06 UTC, Daniel Kozak wrote:
> Maybe you can try use static array instead of dynamic
> static immutable ubyte[10][10] QG10Matrix = ...
I shaved it to this to discard unneccessary time-consuming
functions:
static immutable ubyte[10][10] QG10Matrix = [
[0,3,1,7,5,9,8,6,4,2],[7,0,9,2,1,5,4,8,6,3],
[4,2,0,6,8,7,1,3,5,9],[1,7,5,0,9,8,3,4,2,6],
[6,1,2,3,0,4,5,9,7,8],[3,6,7,4,2,0,9,5,8,1],
[5,8,6,9,7,2,0,1,3,4],[8,9,4,5,3,6,2,0,1,7],
[9,4,3,8,6,1,7,2,0,5],[2,5,8,1,4,3,6,7,9,0],
];
static immutable string number =
"0123456789012345678901234567890123456789012345678901234567890123456789";
static int charToInt(char chr) {
return ((chr >= '0') || (chr <= '9')) ? cast(int)(chr - '0') :
-1;
}
ubyte checkDigit(string str) {
ubyte tmpdigit;
foreach(chr; str) tmpdigit =
QG10Matrix[tmpdigit][charToInt(chr)];
return tmpdigit;
}
void main() {
auto digit = checkDigit(number);
}
I even tried making checkDigit static, but surprisingly this
increased average execution time by 1ms.
Anyway, the previopus version (modified to benefit from a little
optimization too) is almost as performant, even though it
includes multiplication and sum:
static immutable char[] QG10Matrix =
"03175986427092154863420687135917509834266123045978" ~
"36742095815869720134894536201794386172052581436790";
static immutable string number =
"0123456789012345678901234567890123456789012345678901234567890123456789";
static int charToInt(char chr) {
return ((chr >= '0') || (chr <= '9')) ? cast(int)(chr - '0') :
-1;
}
char checkDigit(string str) {
char tmpdigit = '0';
foreach(chr; str) tmpdigit =
QG10Matrix[charToInt(chr) + (charToInt(tmpdigit) * 10)];
return tmpdigit;
}
void main() {
auto digit = checkDigit(number);
}
I compiled both with -inline -noboundscheck -release and the
multidimensional array version does perform 1ms faster for a
couple hundred runs, but I expected the difference to be much
more noticeable.
Any idea of what might be happening here?
More information about the Digitalmars-d-learn
mailing list