来点复杂的吧

无心人

平方根的那个已经没啥可鼓捣的了

需要目的特简单，算法特精妙的小程序

谁提一个问题

难道还要我想一个么

二进制32位的有用的运算可不好想了

gxqcn

老兄兴致高，正愁没练手的好目标。。。

可见，好的题目确实很不容易发现挖掘。

无心人

mathe

这么无聊呀.
有没有空替我优化一个关于果树问题计算的代码,那个代码由于计算太慢,已经搁置了很长时间了.
我现在需要构造一批18棵树种成17行和18行的方案(由这些方案可以继续构造19棵树种成20行以上,然后继续构造20棵树的情况.而后面部分估计数目不会很多,所以17->18变成了瓶颈).输入集是一些17棵树种成14行的方案.不过这些方案很多很多,我现在将它们等分成大概16万个文件,每个文件71个方案.然后用附件中的代码去处理(附件中给出了2个这样的文件作为测试例子).
不过现在每个文件需要一个CPU处理40分钟左右,显然太慢了.但是代码中很多地方应该可以大量优化,只是优化需要很多的耐心和时间:).如果能够将代码速度优化10倍左右,那么基本上就可行了.
代码是Linux下面的,需要gmp库
输入make编译程序以及运行程序,
编译以后就只需要输入
make run
来运行程序.

mathe

Makefile中编译finder.cpp那行命令可以添加-DNDEBUG去掉一些ASSERT的检查,从而可以加快一点运行速度

无心人

你说下文件的结构

我替你设计一个好的数据结构

mathe

附件里面是两个程序.
其中finder用来搜索结果,sfilter用来淘汰结果(不完全淘汰,同样,我还有一个速度更慢但是效率更加高的不完全淘汰程序)
而程序的输入输出都是一行由大写字母构成的串,每四个字母构成一条直线(或者说一行树),每个字母代表一棵树.
在程序finder中,函数process_one_line将处理一行输入的结果(比如这里输入应该是14行17棵数的情况,所以每行56个字母)
   这个函数第一部分将数据转化格式到line_buf[MAX_TOTAL_EDGES][NODES_PER_EDGE]; 全局变量line_count表示直线数目,比如这里初始化以后总是14.
  然后程序使用了一个LLFilter类用来过滤一些不满足平面约束条件的解. 具体来说是这样的,如果我们将14条直线中任意一条投影到无穷远,那么这条直线上4棵树变成了4个无穷远点,所以所有相交与它们的直线变成了平行线.然后我们只考虑这些平行线的约束,看看是否存在平面上的解. 对于这4组平行线,可以将其中一组投影成同横坐标平行的直线(相交于LLFilter::node_x的直线),另外一组平行于纵坐标(相交于LLFilter::node_y的直线),然后再通过伸缩横坐标或纵坐标,可以将一组变成同y=x直线平行(相交与LLFilter::node_d1的直线),而对于第四组,可以假设它们平行于直线y/k=x,其中k是待定系数).
  函数LLFilter::initFromGlobal就是使用这种方法来构造方程,首先是假设所有点的横纵坐标(这里直接使用了前两组平行关系),其中x_stat[],y_stat[]保存了每个点的横纵坐标对应的变量的索引. 另外还保存了xmc,ymc,xtc,ytc.其中xtc和ytc表示横坐标和纵坐标的总数,xmc和ymc表示其中前xmc个横坐标和前ymc个纵坐标是提供给多个点的(后面的都是一个点的横纵坐标)
   然后函数LLFilter::initFromGlobal余下部分代码是根据另外两个方向的平行线构造一些线性方程,其中这些线性方程总共使用了xtc+2*ytc个变量,前xtc个代表各个横坐标,接下去ytc个代表各个纵坐标,最后ytc个代表各个y/k.
  同时LLFilter::x_coord,LLFilter::y_coord保存了各个点横坐标和纵坐标用方程中参数的线性组合表示的方案.
最后调用LLFilter::linear_reduce()进行消元.
    首先reduce_x尽量消去所有的横坐标,然后只保留那些仅使用了y和y/k形式变量的方程.
    其次reduce_y尽量消去那些变量y,留下一些仅仅使用y/k形式变量的方程,对于这些方程其中1/k是公因子我们可以扔掉,所以得到了一些关于纵坐标的线性组合,由此可以将一些纵坐标用其它点的纵坐标的线性组合替换.
         其中reduce_cols会进行消元并且将那些可以用其它的线性组合表示的y/k消掉
    而replace_y_by_y2会将这些线性组合中的公因子1/k去除,然后将对应的y坐标直接对应的变量也消除.
   同样类似有函数reduce_y2,它通过尽量消除变量y/k,留下一下仅仅使用y形式变量的方程,得到一些关于纵坐标的线性组合,然后同样替换掉一些变量.
   最后simplify_col()函数只是仅仅调整了一下这些余下的参数的编号(很多变量被消元了)
其次是函数LLFilter::checkValid()用来判断是否出现矛盾,其标准很简单,就是前xmc个横坐标必须全部相互不同,而后面的xtc-xmc个变量相互之间可以相等,但是它们也不能同前xmc个相等(不然都不是果树问题的解),同样对于纵坐标也有类似的判断.

当然上面的判断方法通过不代表必然有解,所以程序使用了将所有不同直线作为无穷远直线的组合判断结果. 只要其中一个判断结果无解,那么必然无解.反之,就存在一个可能的候选结果需要进一步判断.

然后回到程序process_one_line的最后面,调用了一个递归函数search,这个函数的目的就是每次在前面的一个方案中间在添加一条直线(这条直线必然经过最后一个点,也就是先添加的点). 同样我们首先需要判断没有三点共线出现在两个不同直线上之类的简单判断,然后有到了调用LLFilter来过滤的情况.
   为了仅可能提高效率,这里每次递归下去,我们都将原先的LLFilter复制一份,然后通过函数
          LLFilter::addOneEdge 又添加了关于这一条新的边的信息,最次化简并判断是否无解.
所以所有的这些LLFilter构成了一个二维数组
  LLFilter gFilter[FILTER_COUNT][INIT_EDGES];
而其中FILTER_COUNT是递归可能达到的最大深度的一个上界.
INIT_EDGES是所有被当成无穷远直线的直线数目,也就是输入方案的直线数目(比如这里是14)

mathe

而再找到一个候选结果后,在函数output_cur中(输出一个结果),
又会调用一个以前的归一化代码NESET::normalize将结果归一化(这个可以保证两个同构的解会有相同的输出)
这个有利于下一步判断时可以将这些同构的解预先删除.
这个部分由于最后输出,现在应该不是优化考虑的重点.

无心人

只看到极端复杂， 呵呵
有否能转化成一个小矩阵，按照矩阵运算处理的思路

比如按18个字母的18 * 14的矩阵
以0, 1表示

mathe

而另外一个文件sfilter.cpp构成了一个专门用于过滤数据的程序.
上面搜索过程的程序中也包含了一部分过滤数据用的代码,但是程序中只使用了线性关系,而这个代码将使用非线性关系,所以代码过滤效率更加高,但是速度更加慢.
同样函数process_one_line处理一个数据,程序开始将字符串数据转化到line_buf中,然后再次转化格式到数组e_to_n[][],n_to_e[][]中,这个数组会对于给定两条边,给出它们的交点,对于给定两个点,给出过它们的线(不存在结果为-1)
然后后面是一个循环,for(i=0;i<line_count;i++)就是选择不同的点,准备将它投影成无穷远直线.
  而这个循环的开头是个二重循环,来选择两个比较合适的方向作为横坐标和纵坐标的方向.
然后利用这个方案调用函数solve_problem来判断是否是非法的种树问题.
而这个解题方案我过去也介绍过.
在函数solve_problem里面首先将这些直线转化成一些多元二次方程组保存在一个ssolver类中.
然后调用ssolver::simplify来对方程组进行化简和ssolver::isValid来判断是否非法.
其中关键部分为ssolver::simplify,我觉得这部分代码效率不够高,而提高这部分效率对整体速度非常重要.
ssolver结构中由于处理的是多元二次方程组,首先_n代表变量的数目(其中常数1也看成一个变量,标号为0)
而所有方程表示成一个矩阵,矩阵每一列代表一个二次项,也就是对应两个变量的乘积,所以_n个变量最多有(_n+1)_n/2个列.
columnid[v1][v2]给出了对于变量v1,v2,二次项v1*v2所对应的项. column_info[col][0]和column_info[col][1]给出了给定的列,其对应二次项中两个变量的编号.