织女的六把黄金尺子问题

mathe · 发表于 2014-12-16 21:47:53

我运行了下你的代码，在我机器上4分多一点

毒酒滴冻鸭 · 发表于 2014-12-17 02:38:58

mathe 发表于 2014-12-16 21:47
我运行了下你的代码，在我机器上4分多一点

可能我的compiler不好，不能尽用四核CPU的威力。。。另外我的2.9GHz CPU的确不及你的快。。。

mathe · 发表于 2014-12-17 08:20:59

编译器我是g++ -O3

liangbch · 发表于 2014-12-17 09:44:56

我的结果也出来了。搜索6把尺子，在我的笔记本电脑上用时3分钟。
我的运行环境：
CPU i7-4700HQ 2.4GH，编译器：VS 2010.

我们程序可搜1-8把尺子的方案。目前只计算了前6把尺子。下面我的程序的运行结果。

Is searching the soultion when rule count is 1
(1,)
It take 0 ms and find 1 solution
Is searching the soultion when rule count is 2
(4,)
(1,2,)
(2,)
(1,3,)
It take 0 ms and find 2 solution
Is searching the soultion when rule count is 3
(9,)
(4,6,)
(1,2,5,)
(8,)
(2,5,)
(1,3,6,)
(6,)
(4,5,)
(2,1,7,)
(7,)
(2,8,)
(3,1,5,)
(10,)
(1,7,)
(3,2,4,)
It take 0 ms and find 5 solution
Is searching the soultion when rule count is 4
(19,)
(6,8,)
(4,7,9,)
(1,2,10,5,)
(15,)
(8,10,)
(4,5,7,)
(1,2,11,6,)
(16,)
(9,10,)
(5,2,13,)
(1,3,8,6,)
(13,)
(6,12,)
(7,2,8,)
(1,3,11,5,)
(18,)
(6,14,)
(2,7,10,)
(1,4,8,3,)
(20,)
(6,8,)
(7,3,9,)
(1,4,11,2,)
(8,)
(6,14,)
(7,3,9,)
(1,4,11,2,)
(20,)
(4,14,)
(2,9,8,)
(1,5,7,3,)
(11,)
(8,10,)
(3,2,12,)
(1,6,9,4,)
(14,)
(3,13,)
(4,5,6,)
(1,7,10,2,)
(9,)
(4,14,)
(5,7,8,)
(2,1,10,6,)
(7,)
(8,10,)
(6,5,9,)
(2,1,12,4,)
(10,)
(8,9,)
(6,1,12,)
(2,3,11,4,)
(12,)
(6,13,)
(7,1,9,)
(2,3,11,4,)
(19,)
(7,11,)
(3,5,12,)
(2,4,9,1,)
(16,)
(9,10,)
(1,7,5,)
(2,4,11,3,)
(14,)
(9,11,)
(5,3,7,)
(2,4,12,1,)
(14,)
(5,10,)
(3,4,9,)
(2,6,11,1,)
(10,)
(4,12,)
(5,1,13,)
(2,7,8,3,)
(19,)
(8,12,)
(1,6,10,)
(3,2,9,4,)
(17,)
(6,10,)
(1,7,12,)
(3,2,9,4,)
(9,)
(8,12,)
(6,4,7,)
(3,2,13,1,)
(16,)
(9,11,)
(1,5,13,)
(3,4,8,2,)
(18,)
(4,10,)
(2,7,6,)
(3,5,11,1,)
(10,)
(4,14,)
(2,7,6,)
(3,5,11,1,)
(12,)
(4,14,)
(2,5,8,)
(3,6,10,1,)
(10,)
(7,12,)
(6,3,8,)
(4,1,13,2,)
(8,)
(6,11,)
(7,3,9,)
(4,1,13,2,)
(8,)
(5,15,)
(3,7,9,)
(4,2,11,1,)
(15,)
(5,7,)
(1,8,10,)
(4,2,11,3,)
(10,)
(7,11,)
(5,3,9,)
(4,2,13,1,)
(9,)
(5,12,)
(7,3,8,)
(4,2,13,1,)
(15,)
(2,18,)
(5,6,8,)
(4,3,9,1,)
(9,)
(4,16,)
(3,7,8,)
(5,1,11,2,)
(14,)
(9,11,)
(1,15,3,)
(5,2,6,4,)
(19,)
(9,11,)
(1,14,2,)
(5,3,4,6,)
(9,)
(2,16,)
(4,6,7,)
(5,3,11,1,)
(12,)
(2,16,)
(4,3,10,)
(5,6,8,1,)
(18,)
(8,11,)
(2,3,12,)
(6,1,9,4,)
(15,)
(5,14,)
(4,3,13,)
(6,2,9,1,)
(17,)
(6,10,)
(1,14,4,)
(7,2,3,8,)
(16,)
(6,12,)
(4,1,14,)
(7,2,8,3,)
(12,)
(4,13,)
(1,14,5,)
(7,3,6,2,)
(19,)
(2,16,)
(3,10,4,)
(8,1,6,5,)
(20,)
(6,12,)
(1,13,3,)
(8,2,5,4,)
(13,)
(3,14,)
(4,11,5,)
(10,2,6,1,)
(17,)
(3,13,)
(4,10,5,)
(11,1,6,2,)
It take 0 ms and find 47 solution
Is searching the soultion when rule count is 5
(34,)
(14,18,)
(5,20,8,)
(9,7,15,4,)
(1,2,10,11,6,)
(33,)
(5,22,)
(7,12,16,)
(4,9,11,10,)
(1,2,15,8,6,)
(22,)
(9,23,)
(5,15,14,)
(7,10,16,2,)
(1,3,8,13,6,)
(35,)
(16,17,)
(6,14,12,)
(10,5,8,11,)
(1,3,18,7,2,)
(30,)
(12,19,)
(2,9,15,)
(10,8,14,3,)
(1,4,16,7,6,)
(32,)
(16,18,)
(7,15,13,)
(8,11,12,2,)
(1,5,4,17,3,)
(27,)
(4,18,)
(8,16,9,)
(7,10,11,2,)
(1,5,14,12,3,)
(20,)
(4,28,)
(2,15,10,)
(11,5,13,6,)
(1,7,14,9,3,)
(23,)
(12,22,)
(6,20,7,)
(4,13,15,3,)
(1,8,2,14,5,)
(26,)
(4,25,)
(12,3,20,)
(6,10,11,7,)
(1,8,5,17,2,)
(29,)
(5,22,)
(4,14,12,)
(3,8,13,7,)
(1,9,6,17,2,)
(29,)
(6,25,)
(7,13,8,)
(3,9,14,4,)
(1,10,5,17,2,)
(32,)
(9,15,)
(8,13,14,)
(3,2,20,6,)
(1,10,7,12,4,)
(22,)
(8,19,)
(3,12,13,)
(5,4,20,6,)
(1,10,7,14,2,)
(28,)
(4,27,)
(6,13,11,)
(5,9,12,8,)
(2,1,15,7,10,)
(18,)
(10,22,)
(7,6,17,)
(9,11,14,1,)
(2,3,16,8,4,)
(32,)
(14,20,)
(1,12,17,)
(9,7,8,11,)
(2,3,18,4,6,)
(24,)
(14,20,)
(1,16,11,)
(7,6,9,10,)
(2,3,18,8,4,)
(21,)
(16,17,)
(11,7,13,)
(8,1,14,12,)
(2,3,19,6,4,)
(25,)
(9,22,)
(1,20,7,)
(10,5,8,11,)
(2,4,12,14,3,)
(27,)
(15,20,)
(11,10,13,)
(16,3,9,5,)
(2,4,18,7,1,)
(25,)
(15,17,)
(4,8,18,)
(10,1,20,3,)
(2,5,9,13,6,)
(34,)
(6,22,)
(13,4,16,)
(9,3,15,8,)
(2,5,14,10,1,)
(22,)
(6,28,)
(13,4,16,)
(9,3,15,8,)
(2,5,14,10,1,)
(26,)
(15,17,)
(3,16,11,)
(13,1,8,12,)
(2,5,18,6,4,)
(31,)
(10,18,)
(11,5,19,)
(8,4,21,1,)
(2,7,6,14,3,)
(33,)
(16,19,)
(4,20,6,)
(10,5,12,1,)
(2,7,14,8,3,)
(21,)
(1,29,)
(5,15,13,)
(9,3,19,4,)
(2,8,6,11,7,)
(35,)
(13,20,)
(4,12,14,)
(6,1,21,3,)
(2,9,8,10,5,)
(31,)
(4,20,)
(3,23,6,)
(7,8,10,9,)
(2,11,1,16,5,)
(25,)
(5,26,)
(7,10,18,)
(12,9,11,2,)
(3,1,15,8,6,)
(17,)
(5,26,)
(7,18,10,)
(12,9,11,2,)
(3,1,15,8,6,)
(28,)
(5,26,)
(10,7,18,)
(12,9,11,2,)
(3,1,15,8,6,)
(24,)
(13,22,)
(7,16,9,)
(15,5,6,8,)
(3,1,17,10,2,)
(26,)
(12,23,)
(5,15,7,)
(8,6,10,9,)
(3,1,17,11,2,)
(23,)
(11,24,)
(4,16,14,)
(12,6,7,8,)
(3,2,17,9,1,)
(33,)
(5,21,)
(2,20,12,)
(10,8,11,6,)
(3,4,9,14,1,)
(26,)
(10,19,)
(13,1,20,)
(2,6,16,9,)
(3,4,11,12,5,)
(21,)
(10,16,)
(1,24,9,)
(11,6,12,2,)
(3,4,15,8,5,)
(20,)
(10,19,)
(2,16,15,)
(8,1,13,12,)
(3,4,17,6,5,)
(29,)
(16,19,)
(5,12,15,)
(13,1,9,11,)
(3,4,18,6,2,)
(19,)
(13,16,)
(5,10,17,)
(14,9,11,1,)
(3,4,18,6,2,)
(23,)
(10,21,)
(2,9,15,)
(4,12,17,1,)
(3,5,14,6,7,)
(29,)
(8,26,)
(4,20,11,)
(10,5,17,1,)
(3,6,7,12,2,)
(30,)
(15,16,)
(2,21,12,)
(8,1,19,6,)
(3,7,4,13,5,)
(30,)
(9,17,)
(1,14,19,)
(5,6,16,2,)
(3,7,13,8,4,)
(29,)
(6,17,)
(5,16,9,)
(7,12,14,1,)
(3,8,2,18,4,)
(17,)
(6,23,)
(5,16,9,)
(7,12,14,1,)
(3,8,2,18,4,)
(21,)
(8,23,)
(1,26,7,)
(11,2,17,5,)
(3,9,6,10,4,)
(32,)
(1,23,)
(8,11,14,)
(7,2,20,6,)
(3,10,5,12,4,)
(29,)
(5,26,)
(9,6,19,)
(4,7,16,1,)
(3,10,8,12,2,)
(31,)
(7,17,)
(1,15,11,)
(5,4,19,6,)
(3,10,8,12,2,)
(17,)
(7,24,)
(1,15,11,)
(5,4,19,6,)
(3,10,8,12,2,)
(26,)
(10,24,)
(2,23,8,)
(1,6,13,9,)
(3,11,4,12,5,)
(33,)
(10,13,)
(2,22,7,)
(8,1,19,6,)
(3,11,4,12,5,)
(13,)
(10,23,)
(2,22,7,)
(8,1,19,6,)
(3,11,4,12,5,)
(30,)
(12,19,)
(9,2,23,)
(8,10,14,3,)
(4,1,15,6,7,)
(21,)
(15,19,)
(6,8,16,)
(3,7,13,12,)
(4,1,17,9,2,)
(31,)
(15,17,)
(7,11,16,)
(12,2,8,13,)
(4,1,19,6,3,)
(29,)
(13,19,)
(8,14,12,)
(16,2,9,6,)
(4,1,20,3,7,)
(23,)
(11,17,)
(1,19,13,)
(9,3,15,7,)
(4,2,8,16,5,)
(15,)
(9,23,)
(3,16,11,)
(8,5,20,1,)
(4,2,12,10,7,)
(21,)
(11,15,)
(10,9,14,)
(5,3,17,7,)
(4,2,16,12,1,)
(21,)
(11,14,)
(3,16,15,)
(5,7,10,13,)
(4,2,18,8,1,)
(20,)
(12,18,)
(3,16,15,)
(8,2,11,14,)
(4,5,17,6,1,)
(26,)
(6,25,)
(7,16,12,)
(5,3,14,10,)
(4,9,2,18,1,)
(20,)
(8,22,)
(6,11,12,)
(7,2,24,1,)
(4,10,5,13,3,)
(23,)
(9,22,)
(2,14,10,)
(3,5,20,7,)
(4,11,6,12,1,)
(28,)
(10,14,)
(8,9,16,)
(3,2,21,6,)
(4,11,7,12,1,)
(18,)
(14,15,)
(2,21,11,)
(9,10,12,4,)
(5,1,7,17,3,)
(27,)
(7,19,)
(3,14,18,)
(2,8,12,11,)
(5,1,15,9,4,)
(24,)
(2,30,)
(7,11,15,)
(4,10,13,8,)
(5,1,16,3,9,)
(24,)
(7,14,)
(4,15,16,)
(3,10,12,8,)
(5,1,17,9,2,)
(27,)
(14,16,)
(2,20,13,)
(11,4,8,9,)
(5,1,18,7,3,)
(32,)
(12,16,)
(8,13,14,)
(1,10,19,4,)
(5,2,15,3,6,)
(27,)
(11,14,)
(9,8,13,)
(3,12,19,1,)
(5,2,16,6,4,)
(22,)
(10,24,)
(8,12,11,)
(15,1,13,4,)
(5,2,19,6,3,)
(27,)
(16,18,)
(2,12,17,)
(8,3,21,1,)
(5,4,6,13,7,)
(26,)
(14,16,)
(3,17,15,)
(10,2,11,8,)
(5,4,18,6,1,)
(31,)
(13,15,)
(4,22,8,)
(10,9,14,2,)
(5,6,1,17,3,)
(28,)
(4,27,)
(14,2,17,)
(8,3,15,6,)
(5,7,13,9,1,)
(14,)
(15,17,)
(3,16,9,)
(2,4,20,7,)
(5,8,10,11,1,)
(22,)
(6,26,)
(4,13,12,)
(3,8,16,7,)
(5,9,1,18,2,)
(23,)
(7,22,)
(11,8,13,)
(6,3,24,1,)
(5,10,2,14,4,)
(24,)
(8,23,)
(10,3,19,)
(9,5,16,4,)
(6,1,11,15,2,)
(30,)
(10,22,)
(12,9,14,)
(16,2,11,4,)
(6,1,19,5,3,)
(22,)
(12,18,)
(2,14,17,)
(11,4,9,10,)
(6,1,20,5,3,)
(25,)
(15,17,)
(4,14,16,)
(10,1,12,8,)
(6,3,19,5,2,)
(31,)
(13,22,)
(3,17,9,)
(2,5,14,11,)
(6,4,8,15,1,)
(33,)
(3,23,)
(7,11,17,)
(2,13,14,5,)
(6,4,12,8,1,)
(20,)
(8,26,)
(1,17,13,)
(4,3,16,9,)
(6,5,10,12,2,)
(21,)
(2,28,)
(4,16,11,)
(1,8,15,10,)
(6,7,5,14,3,)
(32,)
(14,20,)
(1,15,11,)
(3,2,19,9,)
(6,7,10,8,4,)
(22,)
(3,29,)
(2,15,8,)
(4,12,14,5,)
(6,7,11,9,1,)
(33,)
(15,17,)
(1,24,5,)
(9,3,19,4,)
(6,8,2,11,7,)
(35,)
(5,22,)
(4,21,8,)
(1,10,13,7,)
(6,9,3,14,2,)
(30,)
(8,26,)
(5,12,11,)
(7,3,21,1,)
(6,9,4,14,2,)
(31,)
(10,22,)
(4,17,13,)
(6,3,15,5,)
(7,1,11,14,2,)
(20,)
(4,28,)
(2,21,10,)
(5,11,13,6,)
(7,1,14,3,9,)
(33,)
(13,18,)
(3,12,17,)
(11,5,9,10,)
(7,1,20,2,4,)
(29,)
(15,16,)
(5,13,17,)
(11,3,9,10,)
(7,1,20,4,2,)
(23,)
(15,20,)
(1,26,6,)
(4,12,13,5,)
(7,2,8,11,3,)
(30,)
(13,20,)
(4,22,5,)
(6,10,18,1,)
(7,2,12,3,8,)
(35,)
(16,17,)
(1,26,4,)
(10,5,13,6,)
(7,2,12,8,3,)
(12,)
(13,18,)
(5,16,6,)
(4,10,19,1,)
(7,2,15,8,3,)
(26,)
(6,18,)
(5,14,15,)
(2,9,21,1,)
(7,3,13,4,8,)
(31,)
(6,26,)
(1,16,12,)
(14,8,11,2,)
(7,3,15,5,4,)
(26,)
(14,16,)
(2,18,13,)
(11,4,8,9,)
(7,3,19,5,1,)
(21,)
(6,26,)
(2,15,14,)
(3,10,12,8,)
(7,4,5,18,1,)
(21,)
(1,28,)
(9,6,19,)
(5,13,14,3,)
(7,4,12,8,2,)
(25,)
(5,29,)
(1,22,9,)
(3,10,11,6,)
(7,8,4,14,2,)
(27,)
(11,22,)
(1,17,13,)
(3,9,16,7,)
(8,2,4,15,5,)
(19,)
(11,23,)
(1,16,15,)
(4,5,21,3,)
(8,2,12,6,7,)
(31,)
(4,17,)
(7,12,11,)
(1,13,15,5,)
(8,2,16,6,3,)
(26,)
(4,28,)
(1,20,13,)
(6,9,14,2,)
(8,3,7,12,5,)
(12,)
(13,19,)
(5,23,6,)
(10,4,16,1,)
(8,3,15,7,2,)
(31,)
(13,14,)
(3,20,9,)
(5,2,17,11,)
(8,4,6,15,1,)
(29,)
(1,24,)
(2,21,10,)
(5,13,14,3,)
(8,4,7,9,6,)
(19,)
(4,28,)
(7,11,12,)
(2,13,14,6,)
(9,1,16,5,3,)
(18,)
(4,28,)
(7,12,11,)
(2,13,14,6,)
(9,1,16,5,3,)
(23,)
(4,28,)
(11,7,12,)
(2,13,14,6,)
(9,1,16,5,3,)
(29,)
(8,26,)
(11,5,14,)
(3,12,13,7,)
(9,1,17,4,2,)
(25,)
(11,20,)
(1,17,16,)
(2,6,21,3,)
(9,4,10,5,7,)
(21,)
(15,16,)
(7,10,18,)
(2,4,23,3,)
(9,5,8,11,1,)
(32,)
(12,17,)
(8,13,10,)
(3,2,22,6,)
(9,7,4,14,1,)
(19,)
(13,15,)
(1,20,11,)
(4,3,22,5,)
(9,8,6,10,2,)
(31,)
(3,27,)
(4,15,13,)
(5,9,12,8,)
(10,1,6,16,2,)
(22,)
(14,17,)
(12,8,13,)
(2,5,23,4,)
(10,1,15,3,6,)
(25,)
(16,17,)
(8,13,14,)
(1,5,23,3,)
(10,2,7,11,4,)
(30,)
(4,29,)
(3,17,11,)
(6,8,13,5,)
(10,2,7,15,1,)
(27,)
(9,20,)
(5,6,19,)
(4,13,15,3,)
(10,2,14,7,1,)
(24,)
(6,28,)
(2,16,11,)
(5,9,17,4,)
(10,3,12,7,1,)
(27,)
(11,20,)
(6,17,12,)
(3,4,21,5,)
(10,8,1,13,2,)
(32,)
(16,17,)
(7,14,13,)
(2,4,22,3,)
(11,1,8,10,5,)
(31,)
(14,20,)
(10,9,13,)
(3,4,21,5,)
(11,1,15,2,6,)
(18,)
(8,25,)
(5,23,6,)
(4,10,16,1,)
(11,2,7,12,3,)
It take 265 ms and find 136 solution
Is searching the soultion when rule count is 6
(39,)
(15,27,)
(7,33,11,)
(13,19,22,2,)
(8,10,16,12,9,)
(3,14,6,25,4,1,)
It take 182256 ms and find 1 solution

复制代码

liangbch · 发表于 2014-12-17 09:46:05

这是我编写的代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
/* 说明：
我们定义尺子编号为i,(i>=0), 尺子i总是有i+1段。
我们首先搜索编号最大的尺子，然后搜索编号次小的尺子，最后搜索编号为0的尺子，在本程序尺子编号用rule_idx来表示
*/
#define MAX_RULES_COUNT 8 //最多可搜索8把尺子
#define MAX_SEG_COUNT 120 //最多可覆盖120种不同的长度
int g_used[MAX_SEG_COUNT+1]; //used[i]=1表示长度i可被尺子测量
int g_maxSegArr[]={1,4,10,20,35,56,84,120}; //maxSegArr[i]表示尺子i可测量的不同长度的总数
int g_result[MAX_RULES_COUNT][MAX_RULES_COUNT]; // result[i][j]表示尺子i第j+1段的长度
int g_count;
void output_result( int rule_count)
{
int i,j;
for(i=0;i<rule_count;i++)
{
printf("(");
for(j=0;j<=i;j++)
printf("%d,",g_result[i][j]);
printf(")\n");
}
printf("\n");
g_count++;
}
int check(int rule_idx, int deep, int *pNewSegCount, int newSegs[] )
{
int i,c,sum;
for (c=0,sum=0,i=deep-1;i>=0;i--)
{
sum += g_result[rule_idx][i];
if ( g_used[sum] )
return 0;
g_used[sum]=1;
newSegs[c++]=sum;
*pNewSegCount=c;
}
return 1;
}
//deep: 表示将要确定尺子第deep+1段的长度
void new_mark(int rule_count,int seg_count,int rule_idx, int deep)
{
int i,j,mid,flag,sum,new_used_count;
int new_used[MAX_SEG_COUNT+1];
mid=rule_idx/2; //第rule_idx+1把尺子中间段的编号
for (sum=0,i=0;i<deep;i++)
sum += g_result[rule_idx][i];
for (i=1;i<=seg_count;i++)
{
if ( g_used[i])
continue;
if ( i + sum > seg_count)
break;
if ( deep==mid+1 && i< g_result[rule_idx][rule_idx-deep] )
continue; //消除重复的结果
g_result[rule_idx][deep]=i;
flag=check(rule_idx,deep+1,&new_used_count,new_used);
if (flag )
{
if ( rule_idx==0)
output_result(rule_count);
if ( deep==rule_idx)
new_mark(rule_count,seg_count,rule_idx-1,0);
else
new_mark(rule_count,seg_count,rule_idx,deep+1);
}
for ( j=0;j<new_used_count;j++)
g_used[new_used[j]]=0;
}
}
void search(int n)
{
DWORD t;
printf("\nIs searching the soultion when rule count is %d\n",n);
t=::GetTickCount();
g_count=0;memset(g_result,0,sizeof(g_result));
new_mark(n,g_maxSegArr[n-1],n-1,0);
t=::GetTickCount()-t;
printf("It take %d ms and find %d solution\n",t,g_count);
}
int main(int argc, char* argv[])
{
int i;
for (i=1;i<=6;i++ ) search(i);
return 0;
}

复制代码

liangbch · 发表于 2014-12-17 11:02:22

我觉得上楼的58-62行是瓶颈。它需要检查很多次。改用链接来存储尚未可被尺子度量的数应该可加快搜索过程。晚上下班后重写一版，看看速度能否提高。

if ( g_used[i])
continue;
if ( i + sum > seg_count)
break;

复制代码

liangbch · 发表于 2014-12-17 22:23:06

不打算编写新版了。
刚刚测试了下3个程序的在我的电脑 (I7-4700HQ Vs2010) 运行时间，12#，22#和28#，仅仅测试一次。
12# 代码应该是没有消除对称的代码，运行时间为7分35秒
22# 代码的运行时间为5分34秒
28# 代码的的运行时间为2分35秒

liangbch · 发表于 2014-12-18 08:19:46

本楼是讨论汇编优化的，不喜欢汇编的人请忽略本楼。
在28#的代码中，“if ( g_used [ i ] ) continue” 这句是用来查找一个值为0的元素，这使我立即想起c运行时刻函数strlen,这个函数也是用来查找值为0的元素，不过其数组是char型而不是整型。如果将这段代码改为调用strlen函数，效果如何呢？说干就干，于是我又写了一版调用函数strlen的版本。另外，我有加了2个strlen函数的汇编的版本。源代码是来自于丹麦的Anger Fog。下面是调用strlen函数的版本。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
/* 说明：
我们定义尺子编号为i,(i>=0), 尺子i总是有i+1段。
我们首先搜索编号最大的尺子，然后搜索编号次小的尺子，最后搜索编号为0的尺子，在本程序尺子编号用rule_idx来表示
*/
#define MAX_RULES_COUNT 8 //最多可搜索8把尺子
#define MAX_SEG_COUNT 120 //最多可覆盖120种不同的长度
char g_used[MAX_SEG_COUNT+2]; //used[i]=1表示长度i可被尺子测量
int g_maxSegArr[]={1,4,10,20,35,56,84,120}; //maxSegArr[i]表示尺子i可测量的不同长度的总数
int g_result[MAX_RULES_COUNT][MAX_RULES_COUNT]; // result[i][j]表示尺子i第j+1段的长度
int g_count;
// The asm code is from Anger Fog "optimization_manuals"
_declspec(naked)
int anger_strlen( char *s )
{
__asm
{
push ebx
mov ecx, [esp+8] ; get pointer to string
mov eax, ecx ; copy pointer
and ecx, 3 ; lower 2 bits of address, check alignment
jz L2 ; string is aligned by 4. Go to loop
and eax, -4 ; align pointer by 4
mov ebx, [eax] ; read from nearest preceding boundary
shl ecx, 3 ; mul by 8 = displacement in bits
mov edx, -1
shl edx, cl ; make byte mask
not edx ; mask = 0FFH for false bytes
or ebx, edx ; mask out false bytes
; check first four bytes for zero
lea ecx, [ebx-01010101H] ; subtract 1 from each byte
not ebx ; invert all bytes
and ecx, ebx ; and these two
and ecx, 80808080H ; test all sign bits
jnz L3 ; zero-byte found
; Main loop, read 4 bytes aligned
L1: add eax, 4 ; increment pointer by 4
L2: mov ebx, [eax] ; read 4 bytes of string
lea ecx, [ebx-01010101H] ; subtract 1 from each byte
not ebx ; invert all bytes
and ecx, ebx ; and these two
and ecx, 80808080H ; test all sign bits
jz L1 ; no zero bytes, continue loop
L3: bsf ecx, ecx ; find right-most 1-bit
shr ecx, 3 ; divide by 8 = byte index
sub eax, [esp+8] ; subtract start address
add eax, ecx ; add index to byte
pop ebx
ret
}
}
// The asm code is from Anger Fog "optimization_manuals"
_declspec(naked)
int anger_strlen_sse2( char *s )
{
__asm
{
mov eax, [esp+4] ; get pointer to string
mov ecx, eax ; copy pointer
pxor xmm0, xmm0 ; set to zero
and ecx, 15 ; lower 4 bits indicate misalignment
and eax, -16 ; align pointer by 16
movdqa xmm1, [eax] ; read from nearest preceding boundary
pcmpeqb xmm1, xmm0 ; compare 16 bytes with zero
pmovmskb edx, xmm1 ; get one bit for each byte result
shr edx, cl ; shift out false bits
shl edx, cl ; shift back again
bsf edx, edx ; find first 1-bit
jnz L2 ; found
; Main loop, search 16 bytes at a time
L1: add eax, 16 ; increment pointer by 16
movdqa xmm1, [eax] ; read 16 bytes aligned
pcmpeqb xmm1, xmm0 ; compare 16 bytes with zero
pmovmskb edx, xmm1 ; get one bit for each byte result
bsf edx, edx ; find first 1-bit
jz L1 ; loop if not found
L2: ; Zero-byte found. Compute string length
sub eax, [esp+4] ; subtract start address
add eax, edx ; add byte index
ret
}
}
void output_result( int rule_count)
{
int i,j;
for(i=0;i<rule_count;i++)
{
printf("(");
for(j=0;j<=i;j++)
printf("%d,",g_result[i][j]);
printf(")\n");
}
printf("\n");
g_count++;
}
int check(int rule_idx, int deep, int *pNewSegCount, int newSegs[] )
{
int i,c,sum;
for (c=0,sum=0,i=deep-1;i>=0;i--)
{
sum += g_result[rule_idx][i];
if ( g_used[sum] )
return 0;
g_used[sum]=32;
newSegs[c++]=sum;
*pNewSegCount=c;
}
return 1;
}
//deep: 表示将要确定尺子第deep+1段的长度
void new_mark(int rule_count,int seg_count,int rule_idx, int deep)
{
int i,j,mid,flag,sum,new_used_count;
int new_used[MAX_SEG_COUNT+1];
mid=rule_idx/2; //第rule_idx+1把尺子中间段的编号
for (sum=0,i=0;i<deep;i++)
sum += g_result[rule_idx][i];
for (i=1;i<=seg_count;i++)
{
//i+= strlen(g_used+i);
//i+= anger_strlen(g_used+i);
i+= anger_strlen_sse2(g_used+i);
if ( i + sum > seg_count)
break;
if ( deep==mid+1 && i< g_result[rule_idx][rule_idx-deep] )
continue; //消除重复的结果
g_result[rule_idx][deep]=i;
flag=check(rule_idx,deep+1,&new_used_count,new_used);
if (flag )
{
if ( rule_idx==0)
output_result(rule_count);
if ( deep==rule_idx)
new_mark(rule_count,seg_count,rule_idx-1,0);
else
new_mark(rule_count,seg_count,rule_idx,deep+1);
}
for ( j=0;j<new_used_count;j++)
g_used[new_used[j]]=0;
}
}
void search(int n)
{
DWORD t;
printf("\nIs searching the soultion when rule count is %d\n",n);
t=::GetTickCount();
g_count=0;memset(g_result,0,sizeof(g_result));
new_mark(n,g_maxSegArr[n-1],n-1,0);
t=::GetTickCount()-t;
printf("It take %d ms and find %d solution\n",t,g_count);
}
//int main(int argc, char* argv[])
//{
// int i;
// for (i=1;i<=6;i++ ) search(i);
// return 0;
//}

复制代码

liangbch · 发表于 2014-12-18 08:30:42

效果？
效果不是很明显，调用3种strlen函数的版本的速度区别不大，在忽略误差的情况下，与原始版本差不多，可能的原因有
1. 这段代码不是热点。
2. 值为0的元素相对比较多，函数strlen查找的长度较小；
3. g_used[ i ]的地址在绝大部分情况下不是4字节对齐。汇编版本难以施展其威力。
我们不应怀疑汇编函数的意义。在字符串长度相对较长的情况下，在字符串地址是4字节对齐的情况下。汇编版本的strlen应该具有很大的优势。

zeroieme · 发表于 2014-12-18 18:14:05

渣机器渣代码跑了半小时……
于是，我想能否转成跳舞链的01矩阵

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 织女的六把黄金尺子问题

点评

点评