小编cid*_*ole的帖子

我正在使用一个SplHeap来保存树的图形节点,该树的节点边缘将从叶子遍历到根.为此,我预先计算节点的"扇入"并将它们放入堆中,这样我就可以始终检索具有最小扇入(0)的节点.

在访问节点之后,我将其后继节点的扇入减少1.显然,需要重新计算堆,因为后续节点现在位于错误的位置.我已经尝试了recoverFromCorruption(),但它没有做任何事情并且保持堆的顺序错误(fanIn在较小的前面有较大停留的节点fanIn).

作为一种解决方法,我现在在每次访问后创建一个新堆,每次都达到完整的O(N*log(N))排序.

但是,应该可以对更改的堆条目进行堆上操作,直到它位于O(log(N))中的正确位置.

API for SplHeap没有提到上堆(或删除任意元素 - 然后可以重新添加).我可以以某种方式派生类SplHeap来执行此操作,还是必须从头开始创建纯PHP堆？

编辑:代码示例:

class VoteGraph {
    private $nodes = array();

    private function calculateFanIn() { /* ... */ }

    // ...

    private function calculateWeights() {
        $this->calculateFanIn();
        $fnodes = new GraphNodeHeap(); // heap by fan-in ascending (leaves are first)

        foreach($this->nodes as $n) {
            // omitted: filter loops
            $fnodes->insert($n);
        }

        // traversal from leaves to root
        while($fnodes->valid()) {
            $node = $fnodes->extract(); // fetch a …

为了尝试MappedByteBuffer(Java中的内存映射文件),我编写了一个简单的wc -l(文本文件行计数)演示:

int wordCount(String fileName) throws IOException {
    FileChannel fc = new RandomAccessFile(new File(fileName), "r").getChannel();
    MappedByteBuffer mem = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());

    int nlines = 0;
    byte newline = '\n';

    for(long i = 0; i < fc.size(); i++) {
        if(mem.get() == newline)
            nlines += 1;
    }

    return nlines;
}

我在大约15 MB(15008641字节)和100k行的文件上尝试了这个.在我的笔记本电脑上,它需要13.8 sec.为什么这么慢？

完整的类代码在这里:http://pastebin.com/t8PLRGMa

作为参考,我在C中写了相同的想法:http://pastebin.com/hXnDvZm6

它运行大约28毫秒,或490 times faster.

出于好奇,我还使用与Java中基本相同的算法和API编写了Scala版本.它运行10 times faster,这表明肯定有一些奇怪的事情发生.

更新:该文件由操作系统缓存,因此不会涉及磁盘加载时间.

我想使用内存映射来随机访问可能不适合RAM的较大文件.这就是为什么我不只是使用BufferedReader.