在Python中查找最小或最大值的索引

Question

我有一个如下所示的结构：

>>> items
[([[0, 1], [2, 20]], 'zz', ''), ([[1, 3], [5, 29], [50, 500]], 'a', 'b')]

每个元组中的第一个项是一系列范围，我想制作一个生成器，按照起始索引升序提供这些范围。由于范围列表已经按其起始索引排序，因此此操作很简单：只需要完成排序合并即可。我希望以良好的计算效率来做到这一点，因此我的想法是通过弹出具有范围列表中最小起始索引的元组列表的前面，从而隐式跟踪我的合并状态。我可以使用min()获得[0,1]，但我该如何获取它的索引？我有这个：

[ min (items[i][0]) for i in range(len(items)) ]

这让我得到了每个列表的第一个项目，然后可以一些如何进行 min()，但是当任何一个列表变为空时它就会失败，并且不清楚如何获取索引以便使用 pop()，而不必在列表中查找它。

总结一下：想要构建生成器，为我返回：

([0,1], 'zz', '')
([1,3], 'a', 'b')
([2,20], 'zz', '')
([5,29], 'a', 'b')
([50,500], 'a', 'b')

甚至更有效率的是，我只需要这些数据：

[0, 1, 0, 1, 1]

（我想要取前一项的元组索引）

- Steven Lu

---

我为之前的一个回答编写了一个 mergeiter 函数；我使用 enumerate() 添加索引。 - Martijn Pieters

@MartijnPieters 在 Python 方面我还是比较新手，一开始对你的 mergeiter 函数有些困惑。但在查看了其他答案后，你的方法显然是正确的。然而，这是唯一一个没有作为答案发布的方法... - Steven Lu

对于标题中的问题，可以参考以下链接：python - Getting the index of the returned max or min item using max()/min() on a list - Stack Overflow。 - user202729

Answer 1

 from operator import itemgetter
 index, element = max(enumerate(items), key=itemgetter(1))

返回items中最大元素的索引和元素本身。

- MatthieuBizien

---

好的，假设我想要进一步深入（比如说我想按照第一个索引的某个部分进行排序），我需要使用 lambda 吗？请把我的“无用的东西”考虑在内，作为我想要让它变得非常复杂的理由 :) - Steven Lu

我会在最后一个评论中回答我的问题，我认为深入挖掘的方法是使用lambda。 - Steven Lu

为了避免导入，可以使用以下代码来获取最大的元素及其索引：max(enumerate(items), key=lambda x: x[1])。 - stillanoob

这总是比另一种解决方案更差，参见基准测试。Lambda 可能会更慢。 - user202729

Answer 2

这种方法可以找到可迭代对象中最大元素的索引，而且不需要任何外部导入：

def argmax(iterable):
    return max(enumerate(iterable), key=lambda x: x[1])[0]

- 1''

---

只有非循环解决方案才能在单次扫描中同时给出最大值和最大值的索引！ - gaborous

这里有一个相关的方法，基于反转元组词典序排序 - max(enumerate(l), key=lambda t: list(reversed(t)))。与原始方法不同的是，当最大值出现多次时，它会给出最后一个索引（在某些情况下更有用）。 - yoniLavi

Answer 3

找到列表中最大值的索引：

def argmax(lst):
  return lst.index(max(lst))

如果lst中存在重复的最大值，这将返回找到的第一个最大值的索引。

- stupidsven

---

这样做还会对列表进行两次迭代，所以不要这样做。 - mrexodia

@mrexodia 对于两次迭代列表的方式有什么问题吗？只是效率不高吗？这种实现方法潜在的速度比基于enumerate的方法要快得多，因为后者为每个元素分配了一对堆上的空间。这种解决方案也比其他解决方案更简短、更易于理解，所以可以认为是更加Pythonic的。但是，如果要比较的项很耗费时间，它可能会更慢，而且它不能用于一般的可迭代对象。 - benrg

Answer 4

另一种获取argmax的方法是：

def argmax(lst):
    return max(range(len(lst)), key=lst.__getitem__)

- yoniLavi

Answer 5

这个可以正常工作：

by_index = ([sub_index, list_index] for list_index, list_item in
             enumerate(items) for sub_index in list_item[0])
[item[1] for item in sorted(by_index)]

提供：

[0, 1, 0, 1, 1]

详细来说，这个生成器：

by_index = ([sub_index, list_index] for list_index, list_item in
             enumerate(items) for sub_index in list_item[0])
list(by_index)    
[[[0, 1], 0], [[2, 20], 0], [[1, 3], 1], [[5, 29], 1], [[50, 500], 1]]

所需的仅是排序并获取所需的索引：

[item[1] for item in sorted(by_index)]

- Mike Müller

---

我认为在这里排序是完全不必要的，即使它可能不会使运行时间变得可怕或其他什么。只需要一个最小操作。 - Steven Lu

Python的排序非常高效（http://en.wikipedia.org/wiki/Timsort）。归并排序也被使用。如果我理解你的意思正确，你想对所有索引应用“min”函数。取出最小值并重复此过程，直到列表被消耗完？我的一些测试表明，对于较大的列表和已经有序的项目，排序更快。 - Mike Müller

嗯，你可能是对的。毕竟有不止一个最小值操作。 - Steven Lu

在看到你的解决方案并更好地理解你的需求后，我更新了我的解决方案。现在它只有两行。尝试用大数据集计时与你的解决方案比较一下。 - Mike Müller

哦，我喜欢这个！这段代码看起来更适合通过虚拟机进行优化。我毫不怀疑它会更高效。谢谢。 - Steven Lu

这个答案比我的好，因为它不会出现min尝试索引空列表的情况。时间复杂度可能是O(n log n)，而我的是O(n^2)。可以通过避免使用enumerate来进一步改进。 - Steven Lu

Answer 6

最简单和最有效的方式（O（n））

arg_max, maximum = max(list(enumerate(nums)), key=lambda x: x[1])  # Returns both the maximum element and it's index 

- Yoni Kremer

Answer 7

所以，这是一个快速简便的方法，可以帮助您获得更高效的版本：

a = []
count = 0
for i in items:
    for x in i[0]:
        #place a list with the index next to it in list a for sorting
        a.append((x,count))
#continually grabs the smallest list and returns the index it was in
sort = [a.pop(a.index(min(a)))[1] for i in range(len(a))]

这是与您的物品一起展示它工作的代码：

>>> items = [([[0, 1], [2, 20]], 'zz', ''), ([[1, 3], [5, 29], [50, 500]], 'a', 'b')]
>>> a = []
>>> count = 0
>>> for i in items:
...     for x in i[0]:
...             a.append((x,count))
...     count += 1
... 
>>> sort = [a.pop(a.index(min(a)))[1] for i in range(len(a))]
>>> sort
[0, 1, 0, 1, 1]

- Ryan Saxe

---

我试图避免重新查找，这就是 a.index(min(a)) 的作用。index 是一种搜索... - Steven Lu

哦，好的。那个列表推导式对于几乎任何数组都是一个快速排序器！无论是列表、嵌套列表等等，它基本上适用于任何东西，我只需要添加[1]。虽然如果你不想查找如何进行排序，这个想法有点难以理解... - Ryan Saxe

根据你的解释，我认为我的代码很适合它。因为如果你读了注释，我的代码会跟踪哪个列表在哪个元组中！之所以有a.index是因为你需要这样做才能使用a.pop。难道我理解错了吗？ - Ryan Saxe

是的，它只需要知道哪个项中第一个项目的最小值是元组中的哪个（那些是两个列表），这样它就可以将其删除。然后下一次重复。它不需要使用包含两个列表的索引。 - Steven Lu

嗯。是的。我认为建立那个a列表来弹出其中的东西并没有意义。在整个集合中查找最大值是没有意义的。应该是在每个元组的下一个项目之间查找最大值。请参阅我的自我回答，了解我希望采取的方向。希望这会让它更清晰明了。 - Steven Lu

Answer 8

还有另一种选择：

max(zip(lst, range(len(lst))))[0]

这似乎是最快的，连同

max(range(len(lst)), key=lst.__getitem__)

- Mi chael

---

目前你的回答不够清晰。请编辑并添加更多细节，以帮助其他人理解它如何回答所提出的问题。你可以在帮助中心找到有关如何撰写好答案的更多信息。 - Community

Answer 9

如果你不试图利用内部范围列表已排序的事实，那么这很容易。

sorted(sum([ [(rng,) + i[1:] for rng in i[0]] for i in items ], []), lambda i: i[0][0])

看起来你想要一个返回最小值索引的函数

def min_idx(l, key=lambda x: x):
    min_i, min_key = None, float('inf')
    for i, v in enumerate(l):
        key_v = key(v)
        if key_v < min_key:
            mini_i = i
            min_key = key_v
    return min_i

def merge_items(items):
    res = []
    while True:
        i = min_idx(items, key=lambda i: i[0][0][0])
        item = items[i]
        res.append((item[0][0],) + item[1:])
    return res

- Phil Reinhold

Answer 10

我不确定发生了什么，但我认为每个人都有点偏离正确方向。我会归咎于我没有很好地解释我要解决的问题。无论如何，这是我已经得到的进展：

items[min(range(len(items)), key = lambda x: items[x][0][0])][0].pop(0)

这让我完成了大部分工作，但还需要处理的是当一个列表已经用尽时的情况。一旦处理好了，将其放入循环中并在其中进行yield就可以轻松地将其变成生成器，而且希望不需要太多的工作就可以将其改进为在生成器上执行高效的排序合并。

>>> items[min(range(len(items)), key = lambda x: items[x][0][0])][0].pop(0)
[0, 1]
>>> items[min(range(len(items)), key = lambda x: items[x][0][0])][0].pop(0)
[1, 3]
>>> items[min(range(len(items)), key = lambda x: items[x][0][0])][0].pop(0)
[2, 20]
>>> items[min(range(len(items)), key = lambda x: items[x][0][0])][0].pop(0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
IndexError: list index out of range

更新：

将仍然有效的项目的适当子集组装到要进行min操作的对象中是关键。

def next_value_in_sections(sections):                 
    while 1:                                          
        idxs = []                                     
        for i, x in enumerate(sections):              
            if x[0]:                                  
                idxs.append(i)                        
        print idxs                                    
        if not idxs:                                  
            break                                     
        j = min(idxs, key=lambda x: sections[x][0][0])
        yield (sections[j][0].pop(0), j)              

items = [([[0, 1], [2, 20]], 'zz', ''),               
         ([[1, 3], [5, 29], [50, 500]], 'a', 'b')]    
x = next_value_in_sections(items)                     
for i in x:                                           
    print i                                           

已执行：

$ python test.py  
[0, 1]
([0, 1], 0)
[0, 1]
([1, 3], 1)
[0, 1]
([2, 20], 0)
[1]
([5, 29], 1)
[1]
([50, 500], 1)
[]

我注意到这个还有改进的空间，每次迭代都会重建idxs列表。它并不需要这样做，但是这样做并不能提高渐进界。当然，我们必须想知道是否真的关心性能，无论使用lambda是否是一个好主意，尽管我真的看不到除了拆开min之外还有其他的解决方案，那只是一种走向疯狂的行为。

- Steven Lu

---

这可能是一个有点繁琐的交易，但为什么不将其放在try和except中，然后您只需在except中找出哪个列表为空，然后就可以得到剩下的内容了！ - Ryan Saxe

是的，考虑到我甚至避免排序和组装更多列表，因此为此引入异常似乎太过头了，因为我认为这些都是不必要的。看起来异常可以很好地与生成器作为输入列表兼容。这很好。不过我想我已经有了解决方案。一旦测试完成，我会编辑答案。 - Steven Lu