1

这是一个性能难题：我在一个Intel Celeron 1.8GHz, 3GB RAM, Ubuntu 12.04 32-bit盒子上跑步。我在, &中编写了Towers of Henoi递归解决方案。我跑了同样的路，震惊地看到以下时间：CPythonJavan = 25

业绩数字

我认为它的Java性能会比这个盒子好，Python但看起来Java比这个盒子慢几个数量级。为了中和任何代码级别的性能影响，我将代码保留为最基本的形式。以下是3个解决方案：CPython

henoi.c

#include <stdio.h>

void move(int n, char src, char intr, char dest) {
    if (n > 0) {
        move(n-1, src, dest, intr);
        printf("%c -> %c\n", src, dest);
        move(n-1, intr, src, dest);
     }
}

int main() {
    move(25, 'A', 'B', 'C');
    return 0;
}

henoi.py

def move(n, src, intr, dest):
    if n > 0:
        move(n-1, src, dest, intr)
        print '%s -> %s' % (src, dest)
        move(n-1, intr, src, dest)

move(n=25, src='A', intr='B', dest='C')

Henoi.java

public class Henoi {

    static void move(int n, char src, char intr, char dest) {
        if (n > 0) {
            move(n-1, src, dest, intr);
            System.out.println(src + " -> " + dest);
            move(n-1, intr, src, dest);
        }
    }

    public static void main(String[] args) {
        move(25, 'A', 'B', 'C');
    }
}

我正在使用gcc version 4.6.3,Python 2.7.3和Sun Java 1.6.0_24.

有人可以帮我理解上面的数字吗？？？

勘误： 很久以后我才注意到我到处都将“Hanoi”拼写为“Henoi”。对不起 ！

4

1 回答 1

1

您几乎是在专门对标准输出流的性能进行基准测试。Java 尝试尽快将所有内容刷新到标准输出。因此，通过一些额外的缓冲，我将运行时间缩短到 10 秒：

public class Henoi {

    static final PrintStream bout = new PrintStream(
                      new BufferedOutputStream( System.out ) );

    static void move(int n, char src, char intr, char dest) {
        if (n > 0) {
            move(n-1, src, dest, intr);
            bout.println(src + " -> " + dest);
            move(n-1, intr, src, dest);
        }
    }

    public static void main(String[] args) {
        move(25, 'A', 'B', 'C');
        bout.flush();
    }
}

您现在需要在程序退出之前刷新缓冲区以确保所有内容都已写入。

使这个 Java 程序变慢的另一个方面是，您为每一行创建新的 String 对象，当您已经在 C 中使用 8 位字符时，还需要将这些对象从 16 位字符转换为 8 位字节。当您避免这种情况时，您会得到性能再提升 10 倍。

public class Henoi {

    static final byte[] barr = "x -> y\n".getBytes();
    static final OutputStream bout = new BufferedOutputStream( System.out );
    static void move(int n, char src, char intr, char dest) throws IOException {
        if (n > 0) {
            move(n-1, src, dest, intr);
            barr[ 0 ] = (byte) src;
            barr[ 5 ] = (byte) dest;
            bout.write( barr, 0, barr.length );
            // System.out.println(src + " -> " + dest);
            move(n-1, intr, src, dest);
        }
    }

    public static void main(String[] args) {
        try {
            move(25, 'A', 'B', 'C');
            bout.flush();
        } catch( IOException ex ) {
            ex.printStackTrace();
        }
    }
}

它现在在我的 PC 上完成 920 毫秒（写入 RAM 磁盘），我猜再多一点 tunig（仍然有很多冗余字节数组复制）它可以在不到一半的时间内完成。相比之下，您的原始代码在相同环境（i7 4.5GHz、Windows 7 x64、Java 1.7）中几乎只用了 2 分钟。使用 Visual C++ 2010 x64 和 /Ox（所有优化）编译的未更改 C 版本需要 6.650 秒。

编辑：这是具有类似更改的 C 版本，现在需要 950 毫秒才能运行：

#include <stdio.h>

char *str;

void move(int n, char src, char intr, char dest) {
    if (n > 0) {
        move(n-1, src, dest, intr);
        str[ 0 ] = src;
        str[ 5 ] = dest;
        _fwrite_nolock( str, 7, 1, stdout );
        // printf("%c -> %c\n", src, dest);
        move(n-1, intr, src, dest);
     }
}

int main() {
    char mem[] = "x -> 5\n";
    str = mem;
    setvbuf( stdout, NULL, _IOFBF, 8192 );
    _setmode( 1 /* stdout */, 0x8000 /* _O_BINARY */ );
    move(25, 'A', 'B', 'C');
    _fflush_nolock( stdout );
    return 0;
}

该_setmode()调用避免了在 Windows ( \n-> \r\n) 上应用的换行转换，从而导致更大的输出。_fwrite_nolock与此扫描中的相同fwrite但没有锁定，并且速度大约是其两倍。

于 2013-04-21T23:52:32.480 回答