复杂的heapq惰性合并(最小化使用的空间)

文章/答案/技术大牛

发布

1回答

python、python-3.x

给定一个有序列表列表，我希望生成一个有序的输出列表。这很简单： nums : List[List[int]] h = heapq.merge(nums) 但是，我也希望使用内部列表的索引来标记输出的每个元素。= heapq.merge(*map(lambda l: map(lambda x: (x,l[0]), l[1]), enumerate(nums))) 但我担心我可能已经失去了理想的空间复杂性保证；我如何知道(转换后的

浏览 20提问于2020-04-13得票数 0

2回答

python中heapq.merge的时间复杂度是多少？

python、time-complexity、heapq

我听说heapq.merge函数是专门用来合并2个有序数组的？时间复杂度是O(n)吗？如果不是，它是什么?为什么？还有它的空间复杂性是什么。我正在解决用两个指针合并两个排序数组的问题，并且可以达到O(n)时间复杂度和O(n)空间复杂度。

浏览 51提问于2019-02-18得票数 5

3回答

在线性空间中存储成对和

arrays、algorithm、sorting、big-o、asymptotic-complexity

如果我们有两个大小为n的数组，并且希望对它们的和进行排序，那么简单的方法就是将它们的和存储在O(n^2)空间中，并按O(n^2 logn)时间对其进行排序。假设我们有相同的运行时间O(n^2 logn)，我们如何将和存储在O(n)的线性空间中？我想我们并不打算存储所有的和，因为它们的n^2元素不适合n个空间，而且我们只是按排序顺序打印所有的内容，这是否意味着我们必须动态地存储这些项呢？有小费吗？ (这是作业问题)

浏览 4提问于2015-04-29得票数 10

回答已采纳

1回答

Python分割错误？

python、python-2.7、mergesort

在我开始之前，下面是代码：import heapq return heapq.mergeassert sortediterator == sorted(randomiterator) if __name__ == '__ma

浏览 2提问于2013-10-01得票数 12

3回答

实现外部合并排序

python、sorting

我正在努力学习Python，并正在使用ints输入文件进行外部合并排序。我正在使用heapq.merge，我的代码几乎可以工作，但它似乎是将我的行排序为字符串而不是it。此外，我是否正确地认为这将允许我排序一个比内存更大的文件(给定足够的磁盘空间)from itertools import islice #converts

浏览 6提问于2015-05-27得票数 0

回答已采纳

5回答

堆q库中函数的时间复杂度是多少？

python、heap

我的问题来自下面的leetcode解决方案，我不明白为什么是O(k+(n-k)log(k))。补充:也许复杂性不是这样的，事实上我不知道heappush()和heappop()的时间复杂性def findKthLargest(self, nums, k): for num in nums: for _ in xra

浏览 3提问于2016-08-06得票数 66

回答已采纳

1回答

为什么有堆O (V )而不是(V+ E)的Dijkstra的空间复杂性？

python、dijkstra、space-complexity

关于具有最小堆(优先级队列)的Dijkstra， [(1, 5), (2, 3)], [(4, 4), (dist[start] = 0 # pop current shortest distance node if new_dist < dis

浏览 6提问于2022-06-01得票数 0

6回答

如何合并k个排序列表？

python、arrays、list、sorting、merge

results.append(list2.pop(0)) results.extend(list2)这是将2个排序列表合并为1的标准算法。但是，如何将多个排序列表合并为1呢？

浏览 0提问于2018-10-15得票数 0

回答已采纳

2回答

合并预先排序的文件，而无需将所有内容读取到内存中

python

我有一个日志文件列表，其中每个文件中的每一行都有一个时间戳，并且这些行在每个文件中按升序预先排序。不同的文件可以有重叠的时间范围，我的目标是将它们混合到一个大文件中，按时间戳排序。在排序中可能会有联系，在这种情况下，我希望下一行来自输入列表中第一个列出的任何文件。我见过如何使用fileinput (请参阅)来完成此操作的示例，但这似乎是将所有文件读取到内存中。由于我的文件很大，这将是一个问题。因为我的文件是预先排序的</em

浏览 0提问于2012-09-17得票数 2

回答已采纳

1回答

索引优先级队列是否确实加快了dijkstra的速度？

algorithm、data-structures、graph、graph-algorithm、dijkstra

“懒惰”dijkstra的最短路径算法的渐近时间复杂度为O(Elog(V))，它使用规则优先级队列而不是索引堆。这意味着会有重复的节点，算法必须跳过这些节点，但是不管如何处理。解决这个问题的一个解决方案是使用索引优先级队列，但我对它在实际生活中和使用大O时是否真的比惰性版本更快感到困惑，因为懒惰版本仍然跳过算法中的重复节点。通过一些研究，我还发现索引dijkstra比惰性实现的O(

浏览 1提问于2021-08-29得票数 2

回答已采纳

1回答

在简单的惰性seq上的doseq用完了堆空间

clojure、lazy-sequences

在工作中对一些Clojure代码进行压力测试时，我注意到它在迭代大型数据集时耗尽了堆空间。我最终设法将问题追溯到Clojure的doseq函数和惰性序列的实现的组合。这是通过耗尽可用堆空间使Clojure崩溃的最小代码片段：doseq的文档清楚地表明它不保留惰性序列的头部，所以我预计上面代码

浏览 2提问于2012-08-13得票数 2

3回答

Python heapq与排序的复杂性和性能

python、performance、sorting、heap、complexity-theory

我对python (使用v3.x语法)比较陌生，希望能注意到heapq与sorted的复杂性和性能。我已经为贪婪的“查找最佳作业计划”算法实现了一个基于heapq的解决方案。但后来我了解了将'sorted‘与operator.itemgetter()和reverse=True一起使用的可能性。不幸的是，我找不到任何关于'sorted‘vs. heapq的预期<

浏览 0提问于2014-07-10得票数 14

1回答

在Python中查找Kth最大元素的总体复杂性

python、algorithm、heap、time-complexity、heapsort

我当时正在解决这个leetcode问题，使用heapq模块找到了一个很棒的解决方案，这个函数的运行时间非常短。5, [10, 122, 2, 3, 3, 4, 5, 5, 10, 12, 23, 18, 17, 15, 100, 101])但是我很难理解整个算法的时间复杂度这是我的分析，如果我错了，请纠正我！时间复杂性：结果=列表(islice(it，n)) -> O(n) heapq<

浏览 2提问于2015-11-11得票数 1

回答已采纳

1回答

我想知道这段代码的总体时间复杂度！下面的代码对数组进行排序

arrays、python-3.x、time-complexity

我使用堆函数对数组进行排序。import heapq print ("The array: ", arr)heapArray = arrheapq.heapify(heapArray) sortedArray.appen

浏览 9提问于2022-06-08得票数 -1

1回答

空间复杂性与辅助空间复杂性

algorithm、sorting、space-complexity

例如，合并排序、堆排序和插入排序的辅助空间为O(1)，而合并排序、插入排序、堆排序的空间复杂性为O(n)。那么，如果有人问我合并排序、堆排序或插入排序的空间复杂度是多少，那么我该怎么告诉他们O(1)或O(n)呢？另外，在选择排序的情况下，我看到它的空间复杂度是O(1)，它是辅助空间。那么，是否有可能使

浏览 0提问于2018-06-26得票数 2

回答已采纳

1回答

用最小堆数据结构实现列到列包含的单程算法

python、pandas、dataframe、data-structures、heap

我正试图用Python实现以下算法，虽然我已经成功地实现了相同的结果，但我的处理时间确实很慢。该算法的作者声称，他的性能至少比我所经历的要快几倍。关于我处理的数据库的一些细节： IND：列对，例如，A列和B列，其中A列中的所有

浏览 1提问于2019-02-11得票数 1

1回答

如何获得字典中的多个最小/largest值？

python、python-2.7、sorting、dictionary

就像我使用以下脚本创建字典一样：for z in df.index: s = df.loc[z, 'rv'] r_lst.setdefault(float(z),[]).append(float(r_value)) 4508.28: [0.217036381157

浏览 0提问于2018-10-15得票数 2

回答已采纳

7回答

合并排序时间和空间复杂度

algorithm、time-complexity、mergesort、space-complexity

让我们以合并排序的实现为例if (r <= l) return;mergesort(a, l, m); ------------(1)merge(a, l, m, r); 这种合并排序的时间复杂度是O(( b)这种合并排序的空间复

浏览 0提问于2012-04-26得票数 46

回答已采纳

1回答

推入堆时出现不可排序类型错误

python-3.x、tuples、heap、heapq

我有N个链接列表的列表，我试图根据它们的值合并它们，使用堆。由于heapq在堆中使用元组中的第一个值进行排序，所以我编写了以下代码： print(nodeList) 这很好，并在元组的第一个值上创建了一个排序堆。然而，当我试图在这个堆上推送更多的元素时，它会给我一个无序

浏览 6提问于2022-04-24得票数 0

回答已采纳

3回答

在python3中使用heapq模块合并k排序列表

python、data-structures、linked-list、python-3.7、heapq

问题：-合并k个排序列表。但问题是python解释器正在引发一个错误：因此，我想

浏览 21提问于2021-05-02得票数 0

点击加载更多