获取接近列表末尾的元素索引

Question

我有一个包含 objects 的排序列表，我想获取最后一个值的第一个索引（使用 get_val 方法）的列表。我写了这个函数，但我想知道是否有任何方法可以进一步优化它？

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

编辑：列表不包含数字，它包含对象。

Answer 1

一般回答

我们从头到尾扫描列表

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

特例：值是连续的（即没有间隙）： [1, 1, 2, 2, 2] 是可能的，[1, 1, 2, 3, 2] 不是。

我们从头到尾扫描列表，

我们可以反转列表，但我们也可以不反转它：

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

Answer 2

这快了约 33%（对于给定的数据）：

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

通过将参数 get_val 函数更改为属性名称，您可以获得另外 ~15% 的 speepdup：

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')

以相反的顺序分析以确保 RAM 操作不支持优化版本：

    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)

获取接近列表末尾的元素索引

Getting index of element close to end of list

python

indexing

optimization

list