通过python中的元组列表中元组的第一个元素索引元素的最快方法

Question

list_ = [(1, 'a'), (2, 'b'), (3, 'c')] 
item1 = 1 
item2 = 'c' 
#hypothetical: 
assert list_.index_by_first_value(item1) == 0 
assert list_.index_by_second_value(item2) == 2 

在python中模拟index_by_first/second_value方法的最快方法是什么？

如果你不明白发生了什么;如果你有一个元组列表（如list_中所包含的那样），那么如何找到一个元组索引，并将元组的第一个/第二个值作为要索引的元素？

---

我最好的猜测是这样的：

[i[0] for i in list_].index(item1) 
[i[1] for i in list_].index(item2) 

但我希望看到你们能想出什么用。有任何想法吗？

Answer 1

编辑：只是开个玩笑。随着列表的增长，看起来像手动for循环花费的时间更少。更新以通过小次郎的方法生成随机列表：

只是在维护列表时对您的信息进行一些计时测试。保留列表形式与字典的好处是可以扩展包含任意长度的元组。

import timeit 
from operator import itemgetter 
import random 

list_= [('a', i) for i in range(10)] 
random.shuffle(list_) 

def a(): 
    return [i[1] for i in list_].index(1) 

def b(): 
    return zip(*list_)[1].index(1) 

def c(): 
    return map(itemgetter(1), list_).index(1) 

def d(): 
    for index, value in enumerate(list_): 
     if 1 == value[1]: 
      return index 

随着timeit：

C:\Users\Jesse\Desktop>python -m timeit -s "import test" "test.a()" 
1000000 loops, best of 3: 1.21 usec per loop 

C:\Users\Jesse\Desktop>python -m timeit -s "import test" "test.b()" 
1000000 loops, best of 3: 1.2 usec per loop 

C:\Users\Jesse\Desktop>python -m timeit -s "import test" "test.c()" 
1000000 loops, best of 3: 1.45 usec per loop 

C:\Users\Jesse\Desktop>python -m timeit -s "import test" "test.d()" 
1000000 loops, best of 3: 0.922 usec per loop 

Answer 2

搜索列表是O（n）。将其转换为字典，然后查找需要O（1）。

>>> list_ = [(1, 'a'), (2, 'b'), (3, 'c')] 
>>> dict(list_) 
{1: 'a', 2: 'b', 3: 'c'} 
>>> dict((k, v) for v, k in list_) 
{'a': 1, 'c': 3, 'b': 2} 

如果你想在原来的指数，你可以枚举它：

>>> dict((kv[0], (i, kv[1])) for i, kv in enumerate(list_)) 
{1: (0, 'a'), 2: (1, 'b'), 3: (2, 'c')} 

>> dict((kv[1], (i, kv[0])) for i, kv in enumerate(list_)) 
{'a': (0, 1), 'c': (2, 3), 'b': (1, 2)} 

Answer 3

起初，我沿着the same lines as Nick T想。如果元组数（N）很短，那么你的方法就没有问题。但是当然，线性搜索是O（N）。随着元组数量的增加，时间直接随着它增加。你可以得到O（1）查找时间用字典的每个元组的第零元素映射到其索引：

{el[0]:idx for idx,el in enumerate(list_)} 

但列表转换为一个字典的成本可能太高了！下面是我的结果：

>>> from timeit import timeit as t 
>>> t('[i[0] for i in list_].index(1)', "import random;list_=[(i,'a') for i in range(10)]; random.shuffle(list_)") 
1.45 
>>> t('[i[0] for i in list_].index(1)', "import random;list_=[(i,'a') for i in range(100)]; random.shuffle(list_)") 
7.415766954421997 
>>> t('{el[0]:idx for idx,el in enumerate(list_)}[1]', "import random;list_=[(i,'a') for i in range(10)]; random.shuffle(list_)") 
2.1753010749816895 
>>> t('{el[0]:idx for idx,el in enumerate(list_)}[1]', "import random;list_=[(i,'a') for i in range(100)]; random.shuffle(list_)") 
15.062835216522217 

因此名单到字典转换是杀害我们从具有O（1）查找得到任何好处。但是，仅仅证明字典是真快，如果我们能避免做一次以上的转换：

>>> t('dict_[1]', "import random;list_=[(i,'a') for i in range(10)];random.shuffle(list_);dict_={el[0]:idx for idx,el in enumerate(list_)}") 
0.050583839416503906 
>>> t('dict_[1]', "import random;list_=[(i,'a') for i in range(100)];random.shuffle(list_);dict_={el[0]:idx for idx,el in enumerate(list_)}") 
0.05001211166381836 
>>> t('dict_[1]', "import random;list_=[(i,'a') for i in range(1000)];random.shuffle(list_);dict_={el[0]:idx for idx,el in enumerate(list_)}") 
0.050894975662231445 

Answer 4

@Nick牛逼

我觉得有些浪费时间枚举列表，然后将其转换为一个字典，所以即使是字典的O（1）查找，首先创建字典的成本太高，无法将其视为大型列表的可行选项。

这是我用来确定它的测试：

import time 
l = [(i, chr(i)) for i in range(1000000)] 
def test1(): 
    t1 = time.time() 
    ([i[0] for i in l].index(10872)) 
    t2 = time.time() 
    return t2 - t1 

def test2(): 
    t1 = time.time() 
    (dict((kv[0], (i, kv[1])) for i, kv in enumerate(l))[10872][0]) 
    t2 = time.time() 
    return t2 - t1 

def test3(): 
    sum1 = [] 
    sum2 = [] 
    for i in range(1000): 
     sum1.append(test1()) 
     sum2.append(test2()) 
    print(sum(sum1)/1000) 
    print(sum(sum2)/1000) 

test3() 

编辑：哈哈小次郎，你打我吧！

Answer 5

什么是最快的？这取决于您需要使用它的次数，以及是否能够从一开始就创建索引字典。

正如其他人所提到的，一旦拥有它，字典就会快得多，但将列表转换为字典会代价高昂。我将要展示我在计算机上获得的内容，以便我可以比较数字。下面是我的了：

>>> import timeit 
>>> timeit.timeit('mydict = {val[0]:(ind, val[1]) for ind, val in enumerate(mylist)}', 'mylist = [(i, "a") for i in range(1000)]') 
200.36049539601527 

出人意料的是，这是显著比它慢甚至创造摆在首位名单：

>>> timeit.timeit('mylist = [(i, "a") for i in range(1000)]') 
70.15259253453814 

那么，如何与此相比，在事先创建字典地点？

>>> timeit.timeit('mydict = {i:("a", i) for i in range(1000)}') 
90.78464277950229 

显然，这并不总是可能的，因为你并不总是一个创建列表，但我想这包括用于比较。

初始化摘要：

• 创建列表 - 70.15
• 创建字典 - 90.78
• 索引现有列表 - 70.15 + 200.36 = 270.51

所以现在，假设你有一个列表或字典已经建立，需要多长时间？

>>> timeit.timeit('[i[0] for i in mylist].index(random.randint(0,999))', 'import random; mylist = [(i, "a") for i in range(1000)]') 
68.15473008213394 

然而，这将创建一个新的临时列表中的每个时间，所以让我们来看看击穿

>>> timeit.timeit('indexed = [i[0] for i in mylist]', 'import random; mylist = [(i, "a") for i in range(1000)];') 
55.86422327528999 
>>> timeit.timeit('indexed.index(random.randint(0,999))', 'import random; mylist = [(i, "a") for i in range(1000)]; indexed = [i[0] for i in mylist]') 
12.302146224677017 

55.86 + 12.30 = 68.16，这与68.15之前的结果给了我们一致的。现在，词典：

>>> timeit.timeit('mydict[random.randint(0,999)]', 'import random; mylist = [(i, "a") for i in range(1000)]; mydict = {val[0]:(ind, val[1]) for ind, val in enumerate(mylist)}') 
1.5201382921450204 

当然，在每一种情况下我使用random.randint让我们的时间，要因素出来：

>>> timeit.timeit('random.randint(0,999)', 'import random') 
1.4206546251180043 

所以现在使用索引摘要：

• 使用列表 - （68.16-1.42）= 66.74第一次，（12.30-1.42）= 10.88之后
• 使用词典 - （1.52-1.42）= 0.10，每次

现在让我们弄清楚为使字典变得更有用，需要多少次访问。首先，对于时间的公式作为访问次数的一个函数：

• 列表 - 55.86 + 10.88x
• 词典 - 200.36 + 0.10x
• 初始词典 - 20.63 + 0.10x

基于这些公式，如果您需要至少访问14次字典，字典会变得更快。如果你可以从开始而不是列表创建一个字典，那么创建一个字典而不是一个列表的额外开销就会超过开销的偏移量来创建一个只包含元组中第一个值的列表。

那么哪个最快？这取决于您需要使用它的次数，以及是否能够从一开始就创建索引字典。

注意：我正在使用Python 2.7.5。 Python 3.x中的计时可能非常不同，并且在不同的机器上也可能会有所不同。我很想知道别人会在他们的机器上拿出什么。

所有时间都在几秒钟内，但计时为一百万次。因此，单个运行几微秒内的数字是相同的。