2016 9月 Algorithm，Part1 week3 作业帖

loveyomin 发表于 2016-9-26 19:51
effective java 里面建议 不要改变传入的参数，所以测试里才会有测试参数。。。points.clone()新建矩阵就 ...

嗯，知道怎么改了，但是太懒了

做的好心烦，先这样交作业求学分

还有些bug没解决。先提交下作业吧

程序里还有两个错误一直没解决。满分的同学能否给点提示？谢谢！

BruteCollinearPoints.java和FastCollinearPoints.java里各一个错误，类型相同。

Test 10: Check that data type is immutable by testing whether each method
        returns the same value, regardless of any intervening operations
  *  input8.txt
     -  failed after 12 operations involving BruteCollinearPoints
     -  first and last call to segments() returned different arrays
     -  sequence of operations was:
          BruteCollinearPoints collinear = new BruteCollinearPoints(points);
          collinear.numberOfSegments() -> 2
          collinear.numberOfSegments() -> 2
          mutate points[] array that was passed to constructor
          mutate points[] array that was passed to constructor
          collinear.numberOfSegments() -> 2
          mutate points[] array that was passed to constructor
          collinear.segments()
          mutate array returned by last call to segments()
          collinear.numberOfSegments() -> 2
          collinear.numberOfSegments() -> 2
          collinear.segments()
     -  failed on trial 1 of 100

  *  equidistant.txt
     -  failed after 9 operations involving BruteCollinearPoints
     -  first and last call to segments() returned different arrays
     -  sequence of operations was:
          BruteCollinearPoints collinear = new BruteCollinearPoints(points);
          mutate points[] array that was passed to constructor
          collinear.segments()
          collinear.numberOfSegments() -> 4
          mutate points[] array that was passed to constructor
          mutate array returned by last call to segments()
          collinear.numberOfSegments() -> 4
          mutate points[] array that was passed to constructor
          collinear.segments()
     -  failed on trial 1 of 100

==> FAILED

Test 13: Check that data type is immutable by testing whether each method
         returns the same value, regardless of any intervening operations
  *  input8.txt
     -  failed after 10 operations involving FastCollinearPoints
     -  first and last call to segments() returned different arrays
     -  sequence of operations was:
          FastCollinearPoints collinear = new FastCollinearPoints(points);
          collinear.numberOfSegments() -> 2
          collinear.segments()
          mutate points[] array that was passed to constructor
          collinear.segments()
          mutate array returned by last call to segments()
          mutate points[] array that was passed to constructor
          mutate points[] array that was passed to constructor
          collinear.numberOfSegments() -> 2
          collinear.segments()
     -  failed on trial 1 of 100

  *  equidistant.txt
     -  failed after 11 operations involving FastCollinearPoints
     -  first and last call to segments() returned different arrays
     -  sequence of operations was:
          FastCollinearPoints collinear = new FastCollinearPoints(points);
          collinear.numberOfSegments() -> 4
          collinear.numberOfSegments() -> 4
          collinear.segments()
          mutate points[] array that was passed to constructor
          collinear.segments()
          collinear.numberOfSegments() -> 4
          collinear.numberOfSegments() -> 4
          collinear.numberOfSegments() -> 4
          mutate array returned by last call to segments()
          collinear.segments()
     -  failed on trial 1 of 100

==> FAILED



补充内容 (2017-2-28 20:15):
immutable的问题后来解决了。补发下了思路。请帖子内找。

Test 2a-2g: Find collinear points among the N points on an N-by-1 grid

                                                      slopeTo()
             N    time     slopeTo()   compare()  + 2*compare()        compareTo()
-----------------------------------------------------------------------------------------------
=> passed    64   0.00        4032        4493          13018                15379         
=> passed   128   0.00       16256       17379          51014                67274         
=> passed   256   0.01       65280       67998         201276               297280         
=> passed   512   0.05      261632      268025         797682              1299407         
=> passed  1024   0.13     1047552     1062013        3171578              5688702         
=> FAILED  2048   0.47     4192256     4225115       12642486             24742743   (1.1x)
=> FAILED  4096   1.54    16773120    16847494       50468108            107245800   (1.3x)
==> 5/7 tests passed
卡了好几天了，求大神指点一下。我是用一个listArray存储在遍历过程中斜率相同的点，如果size大于3，那么然后加上参考点就是collinear。在去除多余计算的线时，对listArray排序，如果参考点和一个端点不等那么就是重复计算的，不进行存储。感觉算法上没有什么问题，不知道怎么最后就timing test failed了。

wudilaoshu 发表于 2016-12-19 16:14
Test 2a-2g: Find collinear points among the N points on an N-by-1 grid

                           ...

求教下fast的思路

我也遇到 immutable 的问题  不知道是什么原因

同immutable问题... 是指我的结果会根据输入点顺序变化而变吗？可我的输出是按端点大小排好的不会变啊

同问immuatable的问题怎么解决?

immutable的问题后来解决了。花了很长时间。跟各位分享下。
因为时间过去很久了，大致思路是，java程序的输入还是输出的array，一定要在程序内做个copy，不是仅仅copy reference，是把reference所指向的object也copy了。这样，当程序外面的array有变化的时候，不会影响程序内的数据，就是immutable的了！
这是一种所谓的best practice吧。
以上供参考