如何根据嵌套列表中内部列表的第一个元素获取所有最小元素? [英] How to get all the minimum elements according to its first element of the inside list in a nested list?

问题描述

简单地说！有这个列表说LST = [[12,1],[23,2],[16,3],[12,4],[14,5]]，我想根据它的内部列表的第一个元素获取此列表的所有最小元素.因此，对于上面的示例，答案将是[12,1]和[12,4]. python中有什么典型的方法吗? 预先谢谢你.

Simply put! there is this list say LST = [[12,1],[23,2],[16,3],[12,4],[14,5]] and i want to get all the minimum elements of this list according to its first element of the inside list. So for the above example the answer would be [12,1] and [12,4]. Is there any typical way in python of doing this? Thanking you in advance.

推荐答案

紧凑的单遍解决方案需要对列表进行排序-从技术上来说，对于N个长列表来说，这是O(N log N)，但是Python的排序是如此之好，并且如此多的序列恰好发生"在其中具有嵌入顺序(timsort巧妙地利用它来加快执行速度)，因此基于排序的解决方案有时在现实世界中具有令人惊讶的良好性能.

A compact single-pass solution requires sorting the list -- that's technically O(N log N) for an N-long list, but Python's sort is so good, and so many sequences "just happen" to have some embedded order in them (which timsort cleverly exploits to go faster), that sorting-based solutions sometimes have surprisingly good performance in the real world.

这是需要2.6或更高版本的解决方案:

Here's a solution requiring 2.6 or better:

import itertools
import operator
f = operator.itemgetter(0)

def minima(lol):
  return list(next(itertools.groupby(sorted(lol, key=f), key=f))[1])

要了解这种方法，从内而外"看会有所帮助.

To understand this approach, looking "from the inside, outwards" helps.

f(即operator.itemgetter(0))是一个键函数，用于排序其参数的第一项，而operator.itemgetter的主要目的是轻松，紧凑地构建此类函数.

f, i.e., operator.itemgetter(0), is a key-function that picks the first item of its argument for ordering purposes -- the very purpose of operator.itemgetter is to easily and compactly build such functions.

sorted(lol, key=f)返回列表lol的排序副本，按增加的第一项排序.如果您省略key=f，则排序后的副本将按字典顺序排序，因此 也将按递增第一项的顺序排列，但仅用作主键"-相同的项目反过来，第一个子项目将按照第二个子项目的值进行排序，依此类推-当 with 和key=f一起使用时，您可以保证保留各项目之间的原始顺序具有相同的第一个子项目.您没有指定所需的行为(在您的示例中，这两种行为恰好产生相同的结果，因此我们无法与该示例区分开)，这就是为什么我会仔细地详细说明这两种可能性，以便您选择.

sorted(lol, key=f) therefore returns a sorted copy of the list-of-lists lol, ordered by increasing first item. If you omit the key=f the sorted copy will be ordered lexicographically, so it will also be in order of increasing first item, but that acts only as the "primary key" -- items with the same first sub-item will in turn be sorted among them by the values of their second sub-items, and so forth -- while with the key=f you're guaranteed to preserve the original order among items with the same first sub-item. You don't specify which behavior you require (and in your example the two behaviors happen to produce the same result, so we cannot distinguish from that example) which is why I'm carefully detailing both possibilities so you can choose.

itertools.groupby(sorted(lol, key=f), key=f)执行作为操作核心的分组"任务:根据sorted提供的序列)中产生 groups >订购标准.也就是说，当您调用以该项目作为参数的f时，一个具有所有相邻项目的组彼此之间产生相同的值，然后一个具有所有相邻项目的组与第一组具有不同值的组(但彼此之间相同)，等等. groupby尊重它作为参数的序列的顺序，这就是为什么我们必须首先对lol进行排序的原因(而groupby的这种行为使得它在序列的顺序确实重要的许多情况下非常有用)

itertools.groupby(sorted(lol, key=f), key=f) performs the "grouping" task that is the heart of the operation: it yields groups from the sequence (in this case, the sequence sorted provides) based on the key ordering criteria. That is, a group with all adjacent items producing the same value among themselves when you call f with the item as an argument, then a group with all adjacent item producing a different value from the first group (but same among themselves), and so forth. groupby respect the ordering of the sequence it takes as its argument, which is why we had to sort the lol first (and this behavior of groupby makes it very useful in many cases in which the sequence's ordering does matter).

groupby所得到的每个结果yield是一对k, g:键k是该组中每个项目的f(i)结果，一个迭代器g会产生该项目中的每个项目.按顺序排列的组.

Each result yielded by groupby is a pair k, g: a key k which is the result of f(i) on each item in the group, an iterator g which yields each item in the group in sequence.

给定迭代器的内置next(此解决方案中唯一需要Python 2.6的位)将产生其下一项-特别是在调用新生成的迭代器(以及每个当然，的生成器是，以及groupby的结果).在早期的Python版本中，它必须为groupby(...).next()(因为next只是迭代器的一种方法，而不是内置的)，自2.6起不推荐使用.

The next built-in (the only bit in this solution which requires Python 2.6) given an iterator produces its next item -- in particular, the first item when called on a fresh, newly made iterator (and, every generator of course is an iterator, as is groupby's result). In earlier Python versions, it would have to be groupby(...).next() (since next was only a method of iterators, not a built-in), which is deprecated since 2.6.

因此，总而言之，我们的next(...)的结果正好是对k, g，其中k是第一个子项目的最小值(即排序后的第一个)，而g是迭代器分组中的项目.

So, summarizing, the result of our next(...) is exactly the pair k, g where k is the minimum (i.e., first after sorting) value for the first sub-item, and g is an iterator for the group's items.

因此，使用[1]我们只选择迭代器，因此我们有一个迭代器仅生成所需的子项.

So, with that [1] we pick just the iterator, so we have an iterator yielding just the subitems we want.

由于我们需要一个列表，而不是一个迭代器(根据您的规范)，因此最外面的list(...)调用完成了该工作.

Since we want a list, not an iterator (per your specs), the outermost list(...) call completes the job.

在性能方面，所有这些都值得吗?不在您给出的小例子列表上-minima实际上比@Kenny的答案中的任何一个都要慢(其中第一个两次通过"解决方案更快).我只是认为有必要针对可能遇到的 next 序列处理问题牢记想法，在这种情况下，典型输入的细节可能会大不相同(更长的列表，更小的最小值，输入中的部分排序， & c，&c;-).

Is all of this worth it, performance-wise? Not on the tiny example list you give -- minima is actually slower than either code in @Kenny's answer (of which the first, "two-pass" solution is speedier). I just think it's worth keeping the ideas in mind for the next sequence processing problem you may encounter, where the details of typical inputs may be quite different (longer lists, rarer minima, partial ordering in the input, &c, &c;-).

这篇关于如何根据嵌套列表中内部列表的第一个元素获取所有最小元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！