原題：SHPATH 题意很简单，但是因为测试数据非常庞大，非常容易超时。推荐使用Dijkstra+BinaryHeap的算法，不过我的程序是没有通过的，Python写的代码光是读取数据就要用8s，并且即使读取结束，也总会运行时错误。 在tutorial组的题目中有一个Turtle’s Shortest Path TSHPATH，题目完全一样，测试数据也一样，除了时间限制很宽松，可以用来测试程序是否正确。 我后来编写了C版本的Dijkstra+BinaryHeap的代码，却总是WA，而用我自己特地生成的随机数据进行测试结果却完全正确（对比了问牛人要来的代码运行的结果）。 下面是我的代码，如果有牛人路过，希望能指出其中的错误： Python版（我记得有些许小错误，因为某些数据和C版本不一致），C版本 gengraph测试数据生成脚本，不过可能会产生孤点。
Tag Archives: C
在SpiderMonkey中产生可调用的对象
2008年10月3日 – 5:25 下午
我应该对标题做一个更详细的解释：用C语言在SpiderMonkey中产生一个在JavaScript中可以当成函数被调用的对象，换句话说，就是一个非Function的对象，在JavaScript中可以被当成Function进行调用。例如，我有一个Hash对象，当我在var h = new Hash()之后，可以直接调用h(key)，h并非一个函数对象，却可以以这种函数调用的方式来获取键key对应的值。 首先，必须要在创建这个Hash类的结构时，将JSClass中的”call”字段设置为相应的函数，如下： static JSBool call_hash(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval){ /* here the obj refers to the global object, not the callee itself */ *rval = JSVAL_NULL; return JS_TRUE; } static JSClass hash_class = { “Hash”, JSCLASS_HAS_PRIVATE, JS_PropertyStub, JS_PropertyStub, JS_PropertyStub, JS_PropertyStub, JS_EnumerateStub, JS_ResolveStub, JS_ConvertStub, finalize_hash, 0, 0, [...]
提领类型双关的指针将破坏强重叠规则
2008年07月18日 – 11:54 上午
最近复习C/C++，今日用APR编写了一个生产/消费模型的小程序。结果出现了这样一个奇怪的警告：“提领类型双关的指针将破坏强重叠规则”，让我大惑不解，特此和大家讨论一下。 我用的是gcc 版本 4.2.3 (Ubuntu 4.2.3-2ubuntu7) 线程模型：posix。出现警告的这段是这样的： apr_queue_t *queue = (apr_queue_t *) data; int *d = NULL; while(1){ apr_queue_pop(queue, (void **)(&d)); // －－ 此处为出现警告的地方。 printf(“Consumed: %d\n”, *d); } 虽然可以运行无误，但该警告还是让我比较无奈，最后我改成了如下： apr_queue_t *queue = (apr_queue_t *) data; int *d = NULL; void *c = NULL; while(1){ apr_queue_pop(queue, &c); d = (int *)c; printf(“Consumed: %d\n”, *d); } 因为很久没有写C，在这里，我的问题是： [...]
TCMalloc：线程缓存的Malloc
2008年01月2日 – 8:29 下午
作者：Sanjay Ghemawat, Paul Menage 原文 翻译：ShiningRay 动机 TCMalloc要比glibc 2.3的malloc（可以从一个叫作ptmalloc2的独立库获得）和其他我测试过的malloc都快。ptmalloc在一台2.8GHz的P4机器上（对于小对象）执行一次malloc及free大约需要300纳秒。而TCMalloc的版本同样的操作大约只需要50纳秒。malloc版本的速度是至关重要的，因为如果malloc不够快，应用程序的作者就很有可能在malloc之上写一个自己的自由列表。这就可能导致额外的代码复杂度，以及更多的内存占用――除非作者本身非常仔细地划分自由列表的大小并经常从自由列表中清除空闲的对象。 TCMalloc也减少了多线程程序中的锁争用情况。对于小对象，几乎已经达到了零争用。对于大对象，TCMalloc尝试使用粒度较好和有效的自旋锁。ptmalloc同样是通过使用每线程各自的场地来减少锁争用，但是ptmalloc2使用每线程场地有一个很大的问题。在ptmalloc2中，内存可能会从一个场地移动到另一个。这有可能导致大量空间被浪费。例如，在一个Google的应用中，第一阶段可能会为其URL标准化的数据结构分配大约300MB内存。当第一阶段结束后，第二阶段将从同样的地址空间开始。如果第二个阶段被安排到了一个与第一阶段什?用的场地不同的场地，这个阶段不会复用任何第一阶段留下的的内存，并会给地址空间添加另外一个300MB。类似的内存爆炸问题也可以在其他的应用中看到。 TCMalloc的另一个好处是小对象的空间最优表现形式。例如，分配N个8字节对象可能要使用大约8N * 1.01字节的空间。即，多用百分之一的空间。而ptmalloc2中每个对象都使用了一个四字节的头，（我认为）并将最终的尺寸规整为8字节的倍数，最后使用了16N字节。 使用 要使用TCMalloc，只要将tcmalloc通过“-ltcmalloc”链接器标志接入你的应用即可。 你也可以通过使用LD_PRELOAD在不是你自己编译的应用中使用tcmalloc： $ LD_PRELOAD=”/usr/lib/libtcmalloc.so” LD_PRELOAD比较讨巧，我们也不十分推荐这种用法。 TCMalloc还包含了一个堆检查器以及一个堆测量器。 如果你更想链接不包含堆测量器和检查器的TCMalloc版本（比如可能为了减少静态二进制文件的大小），你可以接入libtcmalloc_minimal。 概览 TCMalloc给每个线程分配了一个线程局部缓存。小分配可以直接由线程局部缓存来满足。需要的话，会将对象从中央数据结构移动到线程局部缓存中，同时定期的垃圾收集将用于把内存从线程局部缓存迁移回中央数据结构中。 TCMalloc将尺寸小于<= 32K的对象（“小”对象）和大对象区分开来。大对象直接使用页级分配器（一个页是一个4K的对齐内存区域）从中央堆直接分配。即，一个大对象总是页对齐的并占据了整数个数的页。 连续的一些页面可以被分割为一系列小对象，而他们的大小都相同。例如，一个连续的页面（4K）可以被划分为32个128字节的对象。 小对象的分配 每个小对象的大小都会被映射到170个可分配的尺寸类别中的一个。例如，在分配961到1024字节时，都会归整为1024字节。尺寸类别这样隔开：较小的尺寸相差8字节，较大的尺寸相差16字节，再大一点的尺寸差32字节，如此类推。最大的间隔（对于尺寸 >= ~2K的）是256字节。 一个线程缓存对每个尺寸类都包含了一个自由对象的单向链表。 当分配一个小对象时： 我们将其大小映射到对应的尺寸类中。 查找当前线程的线程缓存中相应的自由列表。 如果自由列表不空，那么从移除列表的第一个对象并返回它。当按照这个快速通道时，TCMalloc不会获取任何锁。这就可以极大提高分配的速度，因为锁/解锁操作在一个2.8GHz Xeon上大约需要100纳秒的时间。 如果自由列表为空： 从该尺寸类别的中央自由列表（中央自由列表是被所有线程共享的）取得一连串对象。 将他们放入线程局部的自由列表。 将新获取的对象中的一个返回给应用程序。 如果中央自由列表也为空：(1) 我们从中央页分配器分配了一连串页面。(2) 将他们分割成该尺寸类的一系列对象。(4) 像前面一样，将部分对象移入线程局部的自由列表中。 大对象的分配 一个大对象的尺寸(> 32K)会被除以一个页面尺寸（4K）并取整（大于结果的最小整数），同时是由中央页面堆来处理的。中央页面堆又是一个自由列表的阵列。对于i < 256而言，第k个条目是一个由k个页面组成的自由列表。第256个条目则是一个包含了长度>= 256个页面的自由列表： k个页面的一次分配通过在第k个自由列表中查找来完成。如果该自由列表为空，那么我们则在下一个自由列表中查找，如此继续。最终，如果必要的话，我们将在最后一个自由列表中查找。如果这个动作也失败了，我们将向系统获取内存（使用sbrk、mmap或者通过在/dev/mem中进行映射）。 如果k个页面的一次分配行为由连续的长度> k的页面满足了，剩下的连续页面将被重新插回到页面堆的对应的自由列表中。 跨度（Span） TCMalloc管理的堆由一系列页面组成。连续的页面由一个“跨度”（Span）对象来表示。一个跨度可以是已被分配或者是自由的。如果是自由的，跨度则会是一个页面堆链表中的一个条目。如果已被分配，它会是一个已经被传递给应用程序的大对象，或者是一个已经被分割成一系列小对象的一个页面。如果是被分割成小对象的，对象的尺寸类别会被记录在跨度中。 [...]
JavaScript = C + Lisp
2006年04月3日 – 7:31 上午
作者： William Taysom 原文地址：http://www.jadetower.org/muses/archives/000307.html 翻译：ShiningRay 我在过去的几周内一直在写JavaScript代码——使用我们的对话框系统来个性化Mozilla。假设你要求：“嘿，电脑，我要教你如何在Amazon.com上找书。首先你象这样进入Amazon，然后在这里输入你要的书的名字。点击“Go”然后……”我的困难在于对Mozilla编码使我的对话框系统可以“看”浏览器中正在进行什么然后自己可以执行这些动作。 由于Mozilla中较高的层次是用JavaScript实现的。所以我一直在废寝忘食研究它（我的Rhino book里面全是我做的书签）我写的越多，我越觉得它像Lisp。 考虑以下代码： semanticAccepter = acceptOnlyIf( acceptNot(emptyTextAccepter), scriptFilter, acceptAny( textAccepter, linkAccepter, formRelatedElementAccepter, linkImageAccepter)); usefulContentOfThePage = new SemTree(semanticAccepter); 这里SemTree是一个对象，它允许你从一个HTML DOM 树中选出某些你感兴趣的节点，去掉那些你不感兴趣的节点。（根本上说，这是一个TreeWalker 类的包装器。）若要建立一个 SemTree ，你要给出一个接受器。一个接受器只是一个判断给定节点是否能被接受的一个函数： function emptyTextAccepter(n) { return (n instanceof Text) && n.data.match(/^\s*$/); } 一旦有了一些基本的接受器和筛选器，很容易就可以定义组合筛选器──一种将筛选器以特殊形式组合起来的函数： function acceptAny() { var disjuncts = arguments; return function(n) { for (var i = 0; [...]
嵌入JavaScript引擎梗概教程
2006年04月2日 – 4:58 下午
嵌入JavaScript引擎 梗概教程 作者：Brendan Eich 2000年2月21日 翻译：ShiningRay @ NirvanaStudio 如何启动VM并执行一个脚本 如果不使用任何错误检查这样： JS_起头的返回指针的函数会返回空（null） JS_起头的返回布尔值的函数会返回假（false） （错误照例会被保存在一个JSBool变量ok中）。 JSRuntime *rt; JSContext *cx; JSObject *global; JSClass global_class = { "global",0, JS_PropertyStub,JS_PropertyStub,JS_PropertyStub,JS_PropertyStub, JS_EnumerateStub,JS_ResolveStub,JS_ConvertStub,JS_FinalizeStub }; /* * 你必须有：You always need: * 每个进程一个运行时（runtime）, * 每个线程一个上下文（context）， * 每个上下文有一个全局对象（global）, * 标准类（如Date）。 */ rt = JS_NewRuntime(0×100000); cx = JS_NewContext(rt, 0×1000); global = JS_NewObject(cx, &global_class, NULL, NULL); JS_InitStandardClasses(cx, [...]
