Just to be clear: your proposed solution is still the fastest one. I was just looking for reasons for the speed-up.

What do you mean? "Reason for the speed up" as in how I did it, or why?

I originally also had a solution with no if that would use an intermediate table with i % 2 as index, but the performance boost was negligible. So I was interested which of the parts you left out brought the extra performance. At the moment, it looks like the enumerate plays the most important role.

It's hard to say, considering you have to have i % 2 and enumerate or an equivalent zip.

I modified your solution to include just an unnecessary enumerate like such:

Oh... does not work to well :D

Press CTRL-k

or preindent with 4 spaces

@classmethod
def calculate_peil_crooked(cls, input_):
    """Calculate the check digit using Luhn's algorithm"""
    sum_ = 0
    for i, (digit, lut) in enumerate(zip(
            reversed(input_),
            itertools.cycle([cls.SUM_DOUBLE_MOD10_LUT,
                             cls.SUM_MOD10_LUT]))):
        sum_ = lut[sum_][digit]
    return cls.CHECK_DIGIT_LUT[sum_]

Thanks.

This lead to the performance loss I mentioned below your answer.

That's just going to waste CPU cycles and so is OFC slower. If you add a i % 2 it's going to be slower too. Since you're wasting CPU cycles it's not accurate to measure, unless you're measuring against other things that have the same wasted cycles. Give me 2 mins and I'll have some code.

def luhn_peil_list(cls, input_):
    sum_ = 0
    for i, digit in enumerate(reversed(input_)):
        if i % 2:
            sum_ = cls.SUM_MOD10_LUT[sum_][digit]
        else:
            sum_ = cls.SUM_DOUBLE_MOD10_LUT[sum_][digit]
    return cls.CHECK_DIGIT_LUT[sum_]


def luhn_peil_without_if(cls, input_):
    tables = [cls.SUM_DOUBLE_MOD10_LUT, cls.SUM_MOD10_LUT]
    sum_ = 0
    for i, digit in enumerate(reversed(input_)):
        sum_ = tables[i % 2][sum_][digit]
    return cls.CHECK_DIGIT_LUT[sum_]

LuhnPeilList 0.281
LuhnPeilWithoutIf 0.254
LuhnPeilWithoutIfEnumerate 0.29
Luhn 0.212

This shows that removing the if leads to a 0.027 speedup. Changing from enumerate to zip however is slower than with the speedup. So enumerate is faster.

Given that I don't know a way to get between LuhnPeilWithoutIf and Luhn that is only one 'step' (change) then it's hard to accurately say what is causing the performance increase or decrease.

But on the whole we know that Luhn is faster, we know that's because we've gotten rid of the if but we don't know what part of the change from i % 2 to zip(..., cycle(...)) makes it faster.

Given that the enumerate is faster.

luhn_peil_without_if is basically exactly what I came up with to get rid of the if. The only difference was that tables was defined as class variable and not in the method.

calculate_lut_overkill == Luhn in the timings?

@AlexV Yes, sorry didn't rename that one

Yeah formatting doesn't work on multi-line messages. :/

Learned so much things about the chat today ;-)

Actually I think I've figured out the step, one sec

def luhn_peil_list(cls, input_):
    sum_ = 0
    for i, digit in enumerate(reversed(input_)):
        if i % 2:
            sum_ = cls.SUM_MOD10_LUT[sum_][digit]
        else:
            sum_ = cls.SUM_DOUBLE_MOD10_LUT[sum_][digit]
    return cls.CHECK_DIGIT_LUT[sum_]


def luhn_peil_without_if(cls, input_):
    tables = [cls.SUM_DOUBLE_MOD10_LUT, cls.SUM_MOD10_LUT]
    sum_ = 0
    for i, digit in enumerate(reversed(input_)):
        sum_ = tables[i % 2][sum_][digit]
    return cls.CHECK_DIGIT_LUT[sum_]

LuhnPeilList 0.279
LuhnPeilWithoutIf 0.252
LuhnPeilWithoutIfEnumerate 0.288
LuhnPeilWithoutIfMod 0.23
LuhnPeilWithoutIfModEnumerate 0.208
Luhn 0.213

The difference between LuhnPeilWithoutIfMod and LuhnPeilWithoutIfModEnumerate is that table[i] is slow in Python, but fast in C. The speed increase outweighs the speed increase enumerate has over zip.

luhn_peil_without_if_mod_enumerate would basically be the implementation of what you mentioned in your answer at "It doesn't matter too much whether you build the list with [] * len(input_) or [...]", correct?

Yes, it is actually the same as LuhnPeilAltTables.

They fluctuate from about 0.205 - 0.215. But they are roughly the same

Now I'm wondering why building the whole list would be as fast as a generator/iterator I assume itertools.cycle to be. The itertools.cycle C implementation looks quite straightforward (for C code) and required auxiliary storage should be minimal. I will have to check for larger inputs. But that's a question for another day.

Anyway, your analysis was pretty interesting. It would be great if some of this would find it's way into the answer. I will have to check how to award a bounty to an existing answer. You have definitely earned it!

@AlexV I can't imagine they're too different. The loop for building the list is in C and iterating over both is in C. If we'd manually built tables with tables.append() then performance would be terrible.