问题标签 [in-place]

我正在研究航空电子操作系统（线程层），我正在寻找关于以下（简化）要求的最佳解决方案：“等待[各种对象]的线程按优先级顺序排队。对于相同的优先级，线程是也按 FIFO 顺序排队”。

[各种对象] 例如信号量。

我认为我可以使用经典链表构建这样的等待列表，这使得插入/排序相对快速和容易，并且完全符合预期的使用情况（一个线程一次进入等待状态）。但是我正在研究一个裸机目标并且我没有任何 libc 支持，因此我没有 malloc（这对于链表非常有用！）。

对于按优先级排序线程，我通常使用非常有效的二进制堆（http://en.wikipedia.org/wiki/Binary_heap），但这里不能使用它，因为不能以这种方式管理“FIFO 顺序”。

当然，我可以使用更经典的排序算法来做到这一点，但它们通常很耗时，即使是一次插入也是如此，因为每次插入时可能会移动很多数组元素。

所以我想知道是否存在合适的算法......也许是一种改进的二进制堆？......或者“静态”链表？......或者最好的东西是与链表相关的分配器算法？... .

有关信息： - 线程总数限制为 128，因此内存需求始终是有限的，并且可以在编译时知道/保留。- 我的数量或 RAM 有限，所以我几乎无法构建这样一个按 FIFO 上的优先级排序的二进制堆（自然按到达时间排序）......</p>

我真的很感激关于这个问题的任何想法和新的看法。

谢谢 ！

我想编写一种方法来修剪字符串末尾的字符。这很简单：

我宁愿这是一种就地方法。天真的方法，

抛出错误“无法更改 self 的值：self = trim(amount)”。

编写这种就地方法的正确方法是什么？我需要手动设置字符串的属性吗？如果是这样，我如何访问它们？

我有一个用于图形搜索的基于数组的二进制堆（尽管目的无关紧要）。
（索引 0 处的项目是堆的顶部。）

每隔一段时间，堆顶部的项目满足我正在寻找的标准，因此我将其弹出并保存以备后用。
目前，我只是将这些找到的项目放在一个单独的数组中并将它们返回给用户。

但是，我想知道：有什么有效的方法可以让我将项目保持在原始数组的前面，通过某种方式简单地以某种方式重新调整堆的“活动”部分的边界（即，移动起始边界一个元素的活动部分）并继续直到我完成？
天真地这样做会破坏堆的结构。

我想以就地方式从集合中删除元素。考虑以下代码段：

http://play.golang.org/p/1nL6Il2Gf1

令人惊讶的结果是：final a [1 3 5 7 9 10 10 10 10 10]

我想知道如何做到这一点。我很确定接收器需要是指向Ints. 但这会使代码有些混乱（*xs可能在任何地方都添加括号），但更重要的是它会产生相同的结果。

这是第 2 轮亚马逊面试问题。将给定的二叉搜索树转换为预购和后购链表，并且必须进行这种转换。

我正在经历一些编码练习，并且遇到了一个问题来实现统一目录路径的功能。

例子：

• 输入：/dir1/dir2/../dir3/file.txt

• 输出：/dir1/dir3/file.txt

我们可以使用堆栈以 O(n) 的时间/空间复杂度来解决这个问题。但是我们不想使用额外的空间。

我们如何以 O(1) 的空间复杂度解决这个问题？我正在为就地解决方案而苦苦挣扎。

我正在 Swift 中创建一个简单的选择排序。在我的排序方法中，调用用于交换数组内值的方法时出现错误。

交换方法：

谢谢您的帮助！:)

我正在尝试“就地”修改一个 numpy 数组。我有兴趣在原地重新排列数组（而不是返回：重新排列数组的版本）。

这是一个示例代码：

赋值 ar=arr[[1,0]] 打破了“arr”与传递给函数“modar”的原始数组的对应关系。您可以通过注释/取消注释该行来确认这一点。当然，这是因为必须创建一个新数组。

我如何告诉 python 新数组仍然对应于“arr”？

简单地说，我怎样才能让“modar”重新排列阵列“就地”？

好的..我修改了该代码并将“modarr”替换为：

例程“test2”仍然从“modar”获得一个未修改的数组。

我知道关于“就地”算法的含义还有其他问题，但我的问题有点不同。我知道这意味着算法会更改原始输入数据，而不是为输出分配新空间。但我不确定辅助内存是否重要。即：

• 如果算法分配一些额外的内存来计算结果
• 如果一个算法有一个非常量的递归调用，它们占用了堆栈上的额外空间

我尝试研究更严格的编程主题，因为我意识到那里有许多我一无所知的范例。我关注了 SICP 和计算机科学基础等书籍。我现在正在以一种正式的、面向证明的方式学习算法。当我学习 Quicksort 时，我意识到我不知道如何用函数式语言来实现它。这是一种就地排序算法，但我如何在没有变异的情况下实现这一点超出了我的范围。

也许有一个简单的答案，我还不知道很多实际和理论概念。但我读到函数式语言是基于 lambda 演算的，它的功能相当于图灵机。我在 Haskell 中找到了一个实现，但我不知道 monads，希望我最终能学会。

那么你能用尽可能简单的术语解释一下这是怎么可能的吗？lambda演算本身有变异的概念吗？不要太苛刻，因为我不太了解 lambda 演算，只是在 Scheme 中编程。一个是或否的答案加上一点解释就足够了。