问题标签 [in-place]

所以快速排序的空间效率是O(log(n))。这是维护调用堆栈所需的空间。

现在，根据Quicksort 上的维基百科页面，这符合就地算法，因为该算法只是交换输入数据结构中的元素。

然而，根据此页面，O(log n) 的空间效率使快速排序无法到位，因为它的空间效率大于 O(1)。根据这个定义，任何空间效率大于 O(1) 的算法都不是就地的。所以我假设这意味着所有递归算法都没有按定义到位？

所以很明显这里有两种不同的就地定义。维基百科并不总是一个完全可靠的来源，所以我咨询了我的一位教授。

我的教授同意第二个定义。他说 Quicksort 没有到位。即使数据保留在输入数组中，堆栈所需的额外空间也会使其不合格。我的教授写了一本关于算法的流行书，所以我非常尊重他的意见，但这个答案对我来说似乎并不正确。

我认为就地的属性是相当字面的。数据保持不变。它不会脱离其原始数据结构。对我来说，这个定义更有用，因为它意味着您可以使用指针执行算法，而不是要求您复制数据。这似乎是算法的一个有价值的属性，并且配得上“就地”的名称。

list.sort()对列表进行排序并替换原始列表，而sorted(list)返回列表的排序副本，而不更改原始列表。

• 什么时候优先于另一个？
• 哪个更有效率？多少？
• 列表执行后是否可以恢复为未排序状态list.sort()？

我已将此报告为pandas issues上的一个问题。与此同时，我在这里发布这个希望节省其他人的时间，以防他们遇到类似的问题。

在分析需要优化的进程时，我发现重命名列未就地提高 x120 的性能（执行时间）。分析表明这与垃圾收集有关（见下文）。

此外，通过避免 dropna 方法恢复了预期的性能。

以下简短示例演示了一个因子 x12：

就地=真

100 个循环，3 个循环中的最佳：每个循环 15.6 毫秒

第一个输出行%%prun：

ncalls tottime percall cumtime percall filename:lineno(function)

就地=假

1000 次循环，3 次中的最佳：每个循环 1.24 毫秒

避免dropna

通过避免使用以下dropna方法可以恢复预期的性能：

1000 个循环，3 个循环中的最佳：每个循环 865 µs

1000 个循环，3 个循环中的最佳：每个循环 902 µs

我正在尝试使用 fileinput 模块对文件进行就地编辑，但它似乎不想工作。

我正在使用的代码：

修改了备份参数，因为我认为它可能会修复错误，但它没有。该文件在我运行此命令之前不存在（我已经检查了一百次），之后也不存在。我正在我的主目录中创建文件，所以应该没有错误。

这是完整的错误：

我想另一个问题是，我如何检查原始的投诉.db 是否在文件中的某个位置打开而不知道它可能在哪里打开。如果是这样，我可以从代码中的任何位置随意关闭它吗？

我不能执行 f.close ，因为此时代码中不会定义 f 。我试过 os.close(complaint_db) （complaint_db 是一个保存数据库位置的通用变量）。它不起作用，因为它需要一个 int，所以我现在有点迷路了。

我最近一直在处理一些代码，这些代码需要我将数组中的元素向左、向右、向上和向下移动（取决于索引i）。我的第一个想法是尝试这样的事情：

但是，当我以这种方式进行布局时，第 1 列被复制到第 2 列，第 2 列被复制到第 3 列，第 3 列被复制到……这并不是数据的转移，而是第一列覆盖了左边的所有内容。

但是，如果我翻转索引，

一切正常，向左或向右移动。我怀疑编译器在第二种情况下检测到连续内存的就地更新，因此它会“在后台”制作一个临时副本以避免覆盖问题，但这只是我的猜测。谁能更详细地解释为什么这种转变以一种方式而不是另一种方式起作用？

I'm trying to write a quicksort for my own edification. I'm using the pseudocode on wikipedia as a guide. My code works. It seems like it should run in O(n log n) time. I tried actually timing my code to check the complexity (i.e., when I double the input size, does the run time increase by approximately n log n), but I'm still not sure.

My code seems pretty simple. I do the sort in-place. Other implementations I've seen use a partition function, which I don't have. This makes me think that I've implemented some other sorting algorithm. Is this a quicksort algorithm?

Second version based on Dukeling's response.

我正在使用 primefaces<p:inplace />并<p:editor />在我的项目中模拟内联编辑。问题是当我完成编辑时，就地显示了html代码。 问题图片：

我想要的是这样的东西，<h:outputtext escape="false">但是<p:inplace/> 当我搜索时，我发现了一些关于 averriding InplaceRendered 的东西，我是初学者，我真的不知道该怎么做。任何人都可以向我解释如何？认为。

当内存分析以下测试时，感兴趣的行上只有一个（相对）小分配（可能是缓冲结果以添加完整列），因此我认为这是一个就地操作，其中乘法的每个结果组件被直接添加到目标矩阵 A 的对应元素。

然而，在更复杂的情况下（例如，在循环之前有其他操作的循环中），此行创建了一个完整的临时（大小为 A）用于

我想知道为什么会这样。在大规模设置中，这可能决定 Matlab 是否出现内存不足。可能是我高估了 JIT，它甚至没有在测试用例中进行就地操作；或者正如我所希望的，也有一些技巧可以推动 JIT 就地执行更复杂的代码。

编辑：

简单的测试用例：

复杂的测试用例：

（如果你想知道，这里：R= N= 29008）

复杂代码：

尽管有内存分析器输出，我可以看到htop内存使用量在第 244 行期间出现峰值，其大小W约为 6GB。

htop在第 244 行：

htop第 244 行之后：

假设我有一个列表：

就地（双重强调）替换所有出现的4with的最有效和最简单的pythonic方法是44什么？

我也很好奇为什么没有standard办法做到这一点（特别是当strings有一个非就地 replace方法时）？

我已经为合并排序编写了一个程序，该程序工作正常，直到合并时它没有正确合并

例如示例：

mergesort.in: // 所有数字都是一个数组，不使用临时数组进行排序

• 2 //-->这是数组编号
• 5 //-->这是数组（下一行）长度
• 4 6 98 8 24
• 8 //-->这是数组（下一行）长度
• 12 14 89 21 4 7 9 41

合并排序。输出：

• 4 6 8 24 98
• 4 7 9 12 14 21 41 89

我不明白如何使用 mergeArray 函数进行就地合并排序