Getting index of element close to end of list-CodePudding

I have a sorted list containing objects, and I would like to get the first index of the last value (which is retrieved by using the get_val method) of the list. I wrote this function but I was wondering if there is any way to optimize this even more?

def index_last_value(tbl, get_val=lambda obj:obj):
    tbl_len, prev_v = len(tbl), get_val(tbl[-1])
    for i,v in enumerate(reversed(tbl)):
        v = get_val(v)
        if v == prev_v:
            index = tbl_len-i-1
        if v != prev_v or i 1 == tbl_len:
            return index
        prev_v = v

class MyObject:
    def __init__(self, v):
        self.v = v

tbl_1 = list(map(MyObject, [1,1]))
tbl_2 = list(map(MyObject, [1,1,2,2,2]))
index_last_value(tbl_1, get_val=lambda obj:obj.v)  # -> 0
index_last_value(tbl_2, get_val=lambda obj:obj.v)  # -> 2

EDIT: The list doesn't contain numbers, it contains objects.

CodePudding user response：

This is ~33% faster (for the data given):

def index_last_value2(tbl, get_val=lambda obj:obj):
    prev_v = get_val(tbl[-1])
    for i in range(len(tbl) - 2, -1, -1):
        if get_val(tbl[i]) != prev_v:
            return i   1
    return 0

You could get another ~15% of speepdup by changing argument get_val function into name of attribute:

def index_last_value3(tbl, val_name):
    prev_v = tbl[-1].__dict__[val_name]
    for i in range(len(tbl) - 2, -1, -1):
        if tbl[i].__dict__[val_name] != prev_v:
            return i   1
    return 0
index_last_value3(tbl_1, val_name='v')
index_last_value3(tbl_2, val_name='v')

Profiling in reverse order to make sure RAM operations do not favor optimized versions:

    44      1001       2682.0      2.7      3.8      for _ in range(1000):
    45      1000       6420.0      6.4      9.1          index_last_value3(tbl_1, val_name='v')
    46      1000       7857.0      7.9     11.1          index_last_value3(tbl_2, val_name='v')
    47      1001       2745.0      2.7      3.9      for _ in range(1000):
    48      1000       7676.0      7.7     10.9          index_last_value2(tbl_1, get_val=lambda obj: obj.v)
    49      1000      10370.0     10.4     14.7          index_last_value2(tbl_2, get_val=lambda obj:obj.v)
    50      1001       2670.0      2.7      3.8      for _ in range(1000):
    51      1000      12083.0     12.1     17.1          index_last_value(tbl_1, get_val=lambda obj: obj.v)
    52      1000      18007.0     18.0     25.5          index_last_value(tbl_2, get_val=lambda obj: obj.v)

CodePudding user response：

General answer

We scan the list from its beginning to its end

def index_last_value(tbl, get_val=lambda obj:obj):
    lastv = get_val(tbl[-1])
    for i,v in enumerate(tbl):
        if get_val(v) == lastv:
            return i

Special case : the values are contiguous (ie. there is no gap) : [1, 1, 2, 2, 2] is possible, [1, 1, 2, 3, 2] is not.

We scan the list from end to its beginning,

We could reverse the list but we can also do without reversing it:

def index_last_value(tbl, get_val=lambda obj:obj):
    len_tbl = len(tbl)
    if len_tbl == 1:
        return 0
    lastv = get_val(tbl[-1])
    for i,v in enumerate(tbl[-2::-1]):
        if get_val(v) != lastv:
            return len_tbl - i - 1
    return 0