logo标签列表

从元组列表中获取最小值和最大值

pythonpython-3.xlistsortingtuples
4
我有一个元组列表，对应于一些点的(x,y)坐标（可以是8个到数百个点）:
mylist = [(x0,y0), (x1,y1), ..., (xn,yn)]

我希望获取x和y坐标的最小值和最大值（无论它们是什么，最小的x等等）。这是为了优化比例尺以将点绘制到矩形区域中。
所以我有两个解决方案：
1.第一种解决方案：创建两个具有坐标[foo[0] for foo in mylist]的列表，以及相同的foo[1]。然后我可以轻松地获取最小值和最大值。但我必须创建这些列表（为了不做两次理解，一次用于最小值，一次用于最大值）。
2.第二种解决方案：两次排序列表，一次按第一个坐标排序，然后按第二个坐标排序，并每次获取第一个和最后一个值。内存使用较少，但需要排序。
哪种解决方案是最佳的？
2
请用客观的术语解释您所说的“最佳”是什么意思。 - TylerH
最好的答案是能够解决问题的答案。尝试一个解决方案可以为该解决方案提供洞见。此外，重构是编程的重要组成部分。在尝试解决问题时，您会更多地了解问题，而在编写实现时，您会更多地了解特定的实现。另外，正如前面的评论所说，这取决于您的需求。对于特定用例而言被认为最佳的解决方案可能实际上在其他情况下甚至大多数情况下都是适得其反的。不要过早地进行优化。考虑Big-O算法。但通常从一个算法开始会带给您更好的答案。 - SherylHohman
5个回答
6

您可以使用itemgetter()函数与max一起使用，我认为这比lambda更高效。请参考此答案。

from operator import itemgetter
max_x = max(mylist,key=itemgetter(0))[0]
是的，我想要取得最高分。 - Devang Hingu
1
然后使用这个 max(students_dict.iteritems(), key=itemgetter(1))[0]。 - Mihai Alexandru-Ionut
好的，请让我检查一下。 - Devang Hingu
1
@MihaiAlexandru-Ionut 我在我的机器上使用了你的 timeit 分析答案，对于大小为 3 百万或 30 萬的元组列表，你的代码平均需要 1.3s，有趣的是，它在 Google Colab 上对于大小为 3 百万或 30 萬的元组列表平均只需要 750ms。是的，使用 lambda 的 max 要慢得多，itemgetter 与 max 相比要快得多。 - Ch3steR
1
@MihaiAlexandru-Ionut 再次编辑我的答案，你的代码片段在我的机器上平均需要 750ms。 - Ch3steR
显示剩余5条评论
5
你可以在这里使用 zip。
In [1]: a=[(1,2),(3,4),(5,6)]

In [2]: x,y=zip(*a)

In [3]: x
Out[3]: (1, 3, 5)

In [4]: y
Out[4]: (2, 4, 6)

In [5]: min(x),max(x)
Out[5]: (1, 5)  #1 in min and 5 is max in x

In [6]: min(y),max(y)
Out[6]: (2, 6)   #2 is min and 5 is max in y

在谷歌Colab上进行timeit分析。
%timeit minmax(z) #ch3ster's answer
1 loop, best of 3: 546 ms per loop

%timeit  minmax1(z) #CDJB's answer
1 loop, best of 3: 1.22 s per loop

%timeit minmax2(z) #Mihai Alexandru-Ionut's answer
1 loop, best of 3: 749 ms per loop

%timeit minmax3(z) #Yevhen Kuzmovych's answer
1 loop, best of 3: 1.59 s per loop

编辑： 如果我们在这里使用set，仍然可以减少执行时间。

In [24]: def minmax(a):
    ...:     x=set()
    ...:     y=set()
    ...:     for i,j in a:
    ...:         x.add(i)
    ...:         y.add(j)
    ...:     return max(x),min(x),max(y),min(y)

一个包含3百万或30万个元素的元组列表用于基准测试。

z=[(randint(0,10),randint(0,10)) for _ in range(3000000)]

timeit 是 Python 3.7 和 Windows 10 中进行性能分析的工具。

In [25]: timeit minmax(z) #Ch3steR's set answer.
384 ms ± 26.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [44]: timeit minmax1(z) #Ch3steR's zip answer.
626 ms ± 3.28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [39]: timeit minmax2(z) #CDJB's answer max with lambda
1.18 s ± 25.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [40]: timeit minmax3(z) #Mihai Alexandru-Ionut's answer max with itemgetter
739 ms ± 42.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [41]: timeit minmax4(z) #Yevhen Kuzmovych's answer with updating max and min while iterating
1.97 s ± 42.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Ch3steR的设定答案 < Ch3steR的压缩答案 < Mihai Alexandru-Ionut的使用itemgetter的最大值和最小值 < CDJB的使用lambda的最大值和最小值 < Yevhen Kuzmovych的在迭代时更新最大值和最小值的答案

当 0<= x,y <=1000000 时 用于基准测试的列表。

x=[(randint(0,1000000),randint(0,1000000)) for _ in range(3000000)]
< p >使用 timeit 进行分析。

In [48]: timeit minmax(x) #Ch3steR's set answer.
1.75 s ± 92.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [49]: timeit minmax1(x) #Ch3steR's zip answer.
753 ms ± 31.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [51]: timeit minmax2(x) #CDJB's answer max with lambda
1.29 s ± 115 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [52]: timeit minmax3(x) #Mihai Alexandru-Ionut's answer max with itemgetter
794 ms ± 35.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [53]: timeit minmax4(x) #Yevhen Kuzmovych's answer with updating max and min while iterating
2.3 s ± 164 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

注意：

当0< x,y <10时，Ch3steR的方案是高效的，但当0< x,y <1000000时，它的平均时间为1.7秒。

我强烈建议在0< x,y < 1000000时使用Ch3steR的zip方案或Mihai Alexandru-Ionut的max和min with itemgetter方案。

很棒的分析！你能试试我的解决方案吗？ :) - Yevhen Kuzmovych
@YevhenKuzmovych 我敢打赌你的不是最优的。 - jimifiki
@jimifiki 完全同意，只是想知道更糟或更好多少。此时，这更多是Python实现规范而不是算法本身的问题。 - Yevhen Kuzmovych
@Yevhen Kuzmovych，我会添加对你的代码的分析。现在我正在上课，一旦回到宿舍，我会确保添加它。 - Ch3steR
2
@Ch3steR 你很棒。 - Yevhen Kuzmovych
显示剩余3条评论
2
这里有另一个解决方案：
max_x, max_y = min_x, min_y = mylist[0]
for x, y in mylist:
    max_x = max(max_x, x)
    max_y = max(max_y, y)
    min_x = min(min_x, x)
    min_y = min(min_y, y)
1

欢迎来到SO!

希望这可以帮助你。

我建议你选择option1。您可以通过以下步骤进一步优化您的方法：

  • 步骤1：一次解析整个列表，以获取x_min和y_min。复杂度为O(N)
  • 步骤2：仅存储具有x_min和y_min元组的索引（节省了50％以上的空间）。复杂度为O(N)。

如果您只想查找最小值或最大值，请勿对这么大的列表进行排序。排序可能需要的复杂度是O(N*N) 到 O(NlogN)。

你的回答有点令人困惑。你所说的“parse”，是指“遍历”/“循环”吗？虽然“超过50%的空间被节省下来”是正确的，但最好说空间复杂度是常数 = O(1)，而不是O(n)。而且，O(NlogN)比O(N*N)更好/更快/更小，所以你可能是指“从O(NlogN)到O(N*N)”。 - Yevhen Kuzmovych
@YevhenKuzmovych - 是的和是的。 - sam
1
您可以使用 min() 和 max() 函数，并加上 key 参数。要获得所需结果，您可以使用以下代码：
max_y = max(mylist, key=lambda x: x[1])[1]
min_y = min(mylist, key=lambda x: x[1])[1]
max_x = max(mylist, key=lambda x: x[0])[0]
min_x = min(mylist, key=lambda x: x[0])[0]
2
很棒的解决方案，但是max和min会返回一个元组，所以你需要在之后取相应的元素。 - Yevhen Kuzmovych
@YevhenKuzmovych 哎呀，谢谢 :) - CDJB
这会对元组进行4次迭代，而不是所需的1次（但由于C实现，这可能仍然非常快）。 - Chris_Rands
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接