我正在实现几个数据结构和一个我要使用的原语如下:我有一个内存块A [N](它有一个可变长度,但我的示例需要100)并且在这个块中,有一个较小的部分C长度为K(比方说30),我想移动而不使用任何额外的内存.
另外的困难是,A"包裹",即C可以从A [80]开始,然后C的前20个元素是元素A [80..100],最后10个元素是元素A [ 0..10].此外,目标范围还可以以任何可能的方式"包裹"并与C重叠.另外,我不想使用超过一定数量的额外内存,一切都应该到位.此外,既不在目标范围内也不在源范围内的A部分可能包含重要的内容,因此也不能使用.所以一个案例如下:
A看起来像这样:
| 456789ABCDEF0123456789AB | ----- | 0123 |
应该转变为:
| 89AB | ----- | 0123456789ABCDEF01234567 |
只是将它委托给一个库或者使用库中的另一个数据结构不是一个选项,我想自己理解这个问题.在第一眼看来,我认为它可能不是微不足道的,但是一旦你区分了一些案例,它就会变得清晰,但现在我遇到了严重的麻烦.当然,如果它们不重叠或不包装,则存在微不足道的情况,但至少如果两者同时发生,则会变得混乱.您可以从一个空闲位置开始移动属于那里的部件,然后在其他地方创建另一个自由部件,并且很难跟踪您可以使用哪些部件.
也许我完全错过了一些东西,但即使是我的特殊情况,如果目标范围没有换行也有近100行(虽然它的一半是断言和注释)我可以更新它以便它也处理一般情况下一些额外的索引计算,但如果有人有一个优雅而简短的解决方案,我将不胜感激.直觉上我认为这应该是微不足道的,但我还没有看到最好的解决方案.
注意:有趣的情况当然是,如果C几乎和A一样大.如果| C | <N/2,这是微不足道的.
编辑:使用超过一定数量的额外标志/索引计数作为额外的内存,我想尽可能避免这种情况.
编辑:有些人想看我的代码.我的问题相当抽象,所以我不想发布它,但也许有人会看到如何改进它.这很糟糕,它只适用于目标从头开始(但是,可以很容易地改变)并且非常长的情况,但是它在O(n)中没有额外的存储器的情况下完成工作.
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
void move_part(int* A, size_t N, size_t target, size_t source, size_t size, int show_steps)
{
assert(source + size <= N);
assert(target + size <= N);
if (show_steps) {
printf("Moving size %d from %d to %d.\n", size, source, target);
}
memmove(A + target, …我打算在Haskell中编写一个小玩具编译器,以获得一种非常简单的语言,以加强我的Haskell技能,并设计一种新语言.我仍然在考虑一些一般性的决定,其中一个最大的开放点是如何进行集成测试.我有以下要求:
我还有以下可选要求:
我试图找到满足我需求的东西,但到目前为止我还没有成功.我考虑的替代方案如下:
我不确定我应该选择哪个选项,我仍然希望我错过了一个很好的解决方案.您是否知道如何创建满足我所有要求的集成测试？
自最新的 Rails 版本以来，ActiveRecord::MigrationContext#new似乎采用了一个名为 的新参数schema_migration。但我不知道要经过什么以及从哪里得到它。
我找不到任何相关信息。我用谷歌搜索了一个小时，MigrationContext我发现的所有示例都引用了旧的 Rails 版本。MigrationContext 类似乎根本没有记录。从源代码中我也无法弄清楚要传递什么。
一些背景：我正在尝试测试一些更危险的迁移。我找到了很多教程，看起来很简单，我就跟着做了。但是准备测试数据库状态以便我可以应用迁移的代码当前不起作用。遗憾的是，所有教程都使用较旧的 Rails 版本，并且由于参数数量错误而失败：
ActiveRecord::MigrationContext.new(migrations_paths)
在Ruby中,如果我有两个Regexp,我有可能创建另一个这样的正则表达式:
a = /\d+/ # Matches digits
b = /\s+/ # Matches whitespaces
c = Regexp.union(a, b) # Matches sequences that consist only of digits or only of whitespaces
我想在Scala中做同样的事情,但我没有发现我怎么能做到这一点.请注意,我不是要求语法来创建像(\d+)|(\s+)前面示例中那样的字符类联合,我真的在寻找从两个给定的Regexp创建新Regexp的可能性.
实际上,最后,我不会只为两个正则表达式而是大量表示.我不关心分组或任何东西,我只想知道一个String是否与给定的Regexp列表中的一个匹配.我可以在循环中检查所有这些,但这样效率太低,这就是为什么我需要一个Regexp来检查联合.
我在为Ruby编写C++扩展时遇到的一个问题是,即使用户做了愚蠢的事情,也要确保它真正安全.他应该获得例外,但绝不会是SegFault.具体问题如下:我的C++类有一个非平凡的构造函数.然后我使用Rice API来包装我的C++类.如果用户在他的Ruby代码中重新定义了initialize(),则会覆盖Rice创建的initialize()函数,并且既不分配也不初始化该对象.一个玩具示例可能如下:
class Person {
public:
Person(const string& name): m_name (name) {}
const string& name() const { return m_name; }
private:
string m_name;
}
然后我像这样创建Ruby类:
define_class<Person>("Person")
.define_constructor(Constructor<Person, const string&>(), Arg("name"))
.define_method("name", &Person::name);
然后,以下Ruby代码会导致Segfault
require 'MyExtension'
class Person
def initialize
end
end
p = Person.new
puts p.name
我会很高兴有两种可能:禁止以某种方式覆盖Ruby中的初始化函数或检入C++,如果Object已正确分配,如果没有,则抛出异常.
我曾经直接使用Ruby C API然后很容易.我刚刚在allocate()函数和initialize方法中分配了一个由Null指针和一个设置为false的标志组成的虚拟对象,我分配了真实对象并将标志设置为true.在每个方法中,我检查了该标志并引发异常,如果它是假的.但是,我用Ruby C API编写了许多愚蠢的重复代码,我首先必须包装我的C++类,以便它们可以从C访问,然后包装和解包Ruby类型等,另外我必须检查这个愚蠢的标志每一种方法,所以我迁移到赖斯,这真的很好,我很高兴.
但是,在Rice中,程序员只能提供一个在rice创建的initialize()函数中调用的构造函数,而allocate()函数是预定义的,什么都不做.我不认为有一种简单的方法可以改变这个或以"官方"方式提供自己的分配功能.当然,我仍然可以使用C API来定义分配函数,所以我试图以某种方式混合C API和Rice,但后来我真的很讨厌,我得到了奇怪的SegFaults并且它真的很难看,所以我放弃了这个想法.
这里有没有人有赖斯的经验,或者有谁知道如何安全吗？
有没有办法为嵌套monad实现bind？我想要的是以下签名:
(>>>=) :: (Monad m, Monad n) => m (n a) -> (a -> m (n b)) -> m (n b)
它看起来应该是一项微不足道的任务,但我不知何故无法绕过它.在我的程序中,我将这种模式用于monad的几种不同组合,对于每种组合,我都可以实现它.但对于一般情况,我只是不明白.
编辑:似乎在一般情况下不可能.但在某些特殊情况下肯定是可能的.例如,如果内在的Monad是一个Maybe.因为我想要使用的所有Monads都可以使用,所以有额外的限制似乎对我来说很好.所以我稍微改变了一下这个问题:
我需要对n进行哪些额外限制,以便可以进行以下操作？
(>>>=) :: (Monad m, Monad n, ?? n) => m (n a) -> (a -> m (n b)) -> m (n b)
我想出了一个晦涩的排序算法，鉴于它如此简单，它一定是以前发明和命名的，所以我想知道它叫什么。
它有一个非常罕见的约束：它仅适用于具有从0to n-1（或等效键）键的输入。这是一个非常强的约束，使其在实践中毫无用处，但也许我们可以构建一些让它有用的人为设置。该算法基本上将特定位置的元素与其最终位置交换，直到数组排序为止。伪代码：
def obscure_sort(array):
sorted_until = 1
while true
if key(array[0]) != 0:
# Swap the element at position 0 to its final position.
swap(array, 0, key(array[0]))
else:
# Find the next element that isn't in its final position.
while key(array[sorted_until]) == sorted_until:
sorted_until++
# If we happen to reach the end, we're done.
if sorted_until == array.length:
return
# Swap the newfound first unsorted element to position 0
swap(array, 0, sorted_until)
该算法实际上运行在O(n). 看到这一点并不完全是微不足道的，除非有人真的感兴趣，否则我将省略分析。 …
我目前正在Haskell中编写一个编译器作为玩具项目,我有一个函数可以使用签名进行状态转换:
transform :: (Exp -> m Exp) -> Exp -> m Exp
这允许我在其上实现以下类型的操作:
但不知何故,即使这一定非常简单,我仍然坚持创建一个基于上述变换方法的无状态映射函数,该方法具有以下特征:
map :: (Exp -> Exp) -> Exp -> Exp
我宁愿不再对如何遍历地图中的子项进行相同的逻辑,而是在变换之上实现它.