关于一个运算优化的问题

无心人

我觉得这个东西没意思了

呵呵，就128位的求2，10的对数的部分还有点意思

litaoye

问一下ls的两位,如果用2个UInt64 来做,会慢还是会快?

liangbch

我觉得不会变快。Uint64 xor 运算我不请出，但是对于vc自带的 Uint64 除法例程却性能有限，不如自己用汇编优化。

litaoye

最近又有另一个有意思的题,不过不是比速度,是比谁用的内存少!

我现在还没有过(估计跑了上百次了),因为实在不想用n^2的算法去解!大家有兴趣可以看看!

这题C#恐怕没戏了,我的c#只能跑到test10,但竟然有用java解的,没想出来是怎么干的.

http://acm.timus.ru/problem.aspx?space=1&num=1220

xenium9

C#的我也过不了：

http://acm.timus.ru/status.aspx? ... 66482&count=100

但C语言的内存可以只用513KB：

2526606 08:38:30 30 Mar 2009 xenium9 1220 C Accepted  0.421 513 KB

xenium9

http://acm.timus.ru/forum/thread ... m=1220&id=21559

那个Java牛人说：

The most important is to not create objects. So no strings, only reusable arrays of characters. And probably you are to implement reading and writing classes over byte IO that do not use object creation.

但是我用了：

BufferedStream In  = new BufferedStream(Console.OpenStandardInput (), 1);
BufferedStream Out = new BufferedStream(Console.OpenStandardOutput(), 1);

In.ReadByte();
Out.WriteByte();

还是不行，不是 Memory limit exceeded，就是 Time limit exceeded，郁闷。

无心人

xor等逻辑运算，x86都有128位的指令

litaoye

可能是Java本身内存管理的要比C#严谨，我感觉除非知道测试的部分数据，否则C#是无论如何过不了Test10的。
再牛也难。你的c程序，在AC的程序里面，用内存也算少的，确实很不错了。C++应该会多些。

光是存100000条uint，就需要400K，c#的空程序就需要300多K，这样加起来怎么也超过750了。除非有可能把输入流重新读1遍，
否则理论上就存在重大障碍。（test10 push了80000以上的记录，而没有pop一条，靠重用pop的空间应该是没戏了！

不知道哈夫曼那些压缩算法能不能用在这题上，如果有这样的可能，那还有希望。

原帖由 xenium9 于 2009-4-3 14:08 发表
http://acm.timus.ru/forum/thread ... m=1220&id=21559

那个Java牛人说：

The most important is to not create objects. So no strings, only reusable arrays of characters. And probably you  ...

xenium9

原帖由 litaoye 于 2009-4-4 00:39 发表
可能是Java本身内存管理的要比C#严谨，我感觉除非知道测试的部分数据，否则C#是无论如何过不了Test10的。

http://acm.timus.ru/status.aspx? ... 20&author=66482
C#好不容易到了Test#11，呵呵。

litaoye

原帖由 xenium9 于 2009-4-7 21:37 发表


http://acm.timus.ru/status.aspx? ... 20&author=66482
C#好不容易到了Test#11，呵呵。

恩,很厉害了!test12也是个难点。不知道我提供的读取流的程序有点用么？