在.NET 4.0+中,类SortedSet<T>有一个名为的方法GetViewBetween(l, r),它返回树部件上的接口视图,其中包含指定的两个之间的所有值.鉴于它SortedSet<T>是作为红黑树实现的,我自然希望它能够及时运行O(log N).C++中的类似方法是std::set::lower_bound/upper_boundJava TreeSet.headSet/tailSet,它们是对数的.
然而,事实并非如此.以下代码在32秒内运行,而等效O(log N)版本GetViewBetween将使该代码在1-2秒内运行.
var s = new SortedSet<int>();
int n = 100000;
var rand = new Random(1000000007);
int sum = 0;
for (int i = 0; i < n; ++i) {
s.Add(rand.Next());
if (rand.Next() % 2 == 0) {
int l = rand.Next(int.MaxValue / 2 - 10);
int r = l + rand.Next(int.MaxValue / 2 - 10);
var t = s.GetViewBetween(l, …我经常想在文本内部发表一些评论,这些评论与讨论的主题没有太大关系.通常为了这个目的我使用quotation环境,因为它左边有大的缩进.注释可以很大,可以包括公式,代码清单,嵌套引用等.
如何创建quotation环境以在其所有内容的左侧绘制一条长垂直线？您通常可以使用实际引号在Web上找到此样式.
谷歌找到了一个解决方案:
\begin{flushleft}
\hbox{%
\vrule\hspace{.5em}\parbox{.9\textwidth}%
{Lorem ipsum dolor sit amet, consectetur adipiscing elit. Morbi id hendrerit
nunc. Sed scelerisque lacus vitae erat eleifend eleifend. Donec eros mi, placerat
in porta eleifend, placerat a urna. Pellentesque venenatis neque non turpis
convallis vehicula. Aliquam aliquet ultricies tincidunt.}}
\end{flushleft}
但它不能处理文本内部的代码清单等.
感谢您的意见.对不起,如果我的英语不够容易理解.
我以某种方式将我的项目带到了一个状态,在这个状态下,Visual Studio 2013无法用一个荒谬的错误编译它:
类型'System.Collections.Generic.Dictionary`2'在未引用的程序集中定义.您必须添加对程序集'System.Collections,Version = 4.0.0.0,Culture = neutral,PublicKeyToken = b03f5f7f11d50a3a'的引用.
首先,没有这样的组装,它不存在.其次,Dictionary<TKey, TValue>定义在mscorlib.dll,当然默认引用.Resharper(有自己的代码分析引擎)报告解决方案应该正常编译.
我不知道地球上会发生什么,因为我的最新变化与所谓的错误地方毫无关系.该行引用了一些标准的LINQ函数(GroupBy和ToDictionary),它可以工作数月而不需要任何更改.不幸的是,我无法创建任何MRE:显然,这个错误只出现在我的巨大解决方案的上下文中,并且只有在可能无关的地方进行了一些特定的更改.
这是我尝试过的,它不起作用:
有没有人见过这样的怪癖？
有一个名为treap的数据结构:这是一个随机二进制搜索树,它也是随机生成的所谓"优先级"的堆.
这种结构存在一种变体,其中键是隐式的,它们不存储在树中,但我们将树中节点的有序索引视为此节点的键.我们需要在每个节点中存储子树的大小而不是密钥.这种技术使我们能够像某种数组一样思考treap,它在O(log N)时间内支持大量操作:子数组的插入,删除,恢复,间隔的变化等等.
我对这种结构有点了解,但没有那么多.我试图谷歌它,但我发现很多关于treap本身的文章,但没有关于这个"隐含的treap"/"索引列表".我甚至不知道它的名字,因为我的母语不是英语,我听过的讲座使用的是结构的本土术语,而不是英文原始术语.这个原生术语可以直接用英语翻译为"隐式键上的Treap"或"隐式键上的笛卡尔树".
任何人都能指出我关于这个结构的文章或告诉我它的原始名称吗？谢谢.
PS对不起,如果我的英语不够容易理解.
UPD:关于我正在寻找的结构的一些额外解释.
考虑使用随机选择的优先级和密钥的常用treap,它们是存储在树中的实际用户数据.然后让我们假设我们在每个节点中都存储了一些其他用户信息,而键只是搜索键.下一步是计算和维护每个节点中的子树大小:我们必须在每次合并/拆分/添加/删除后更新此参数,但它允许我们在O(log N)中查找树的第K个元素时间.
当我们在每个节点中有子树大小时,我们可以抛弃键并想象treap表示inorder遍历中的用户数据数组.可以从子树大小容易地计算每个元素的数组索引.现在我们可以添加/删除数组中间的元素或拆分此数组 - 所有这些都在O(log N)时间内完成.
我们也可以进行"多重"操作 - 例如,为我们的"数组"的所有元素添加一个常量值.为了实现这一点,我们必须延迟此操作,在每个节点中添加一个参数,该参数表示延迟常量,必须"稍后"添加到此节点的子阵列的所有元素,并将更改"推"到必要.向子阵列添加常量或绘制(标记)子阵列可以通过这种方式延迟,因为反转子阵列(此处节点中的延迟信息位"子阵列必须反转"),依此类推.
UPD2:这是代码片段 - 我发现的一小部分信息.不要注意西里尔语:)单词"снеявнымключом"的意思是直接翻译"with implicit key".
在非线性算术和未解释的函数中,莱昂纳多德莫拉表示这种qfnra-nlsat策略尚未与Z3的其余部分完全整合.我认为情况在两年内发生了变化,但显然整合还不是很完整.
在下面的示例中,我将数据类型纯粹用于"软件工程"目的:将数据组织到记录中.即使没有未解释的功能,Z3仍然无法给我一个解决方案:
(declare-datatypes () (
(Point (point (point-x Real) (point-y Real)))
(Line (line (line-a Real) (line-b Real) (line-c Real)))))
(define-fun point-line-subst ((p Point) (l Line)) Real
(+ (* (line-a l) (point-x p)) (* (line-b l) (point-y p)) (line-c l)))
(declare-const p Point)
(declare-const l Line)
(assert (> (point-y p) 20.0))
(assert (= 0.0 (point-line-subst p l)))
(check-sat-using qfnra-nlsat)
(get-model)
> unknown
(model
)
但是,如果我手动内联所有函数,Z3会立即找到一个模型:
(declare-const x Real)
(declare-const y Real)
(declare-const a Real)
(declare-const b Real) …