[公开课] [Princeton] Algorithms, Part II (week 1)

交下作业……感谢skenan给我的巨大帮助

交作业 这style与我所学大不相同啊

交作业。。。

先交作业吧。。。
虽然还有个小bug

landuostorm 发表于 2014-4-1 21:32
交作业 这style与我所学大不相同啊

请问一下你是用什么data structure存放synsets的？
我是用了一个ST<String, Bag<Integer>>存放noun 和对应的ids
然后再用了一个resizing array String[] 存放id和相应的nouns
这样就能从noun查找到ids，然后SAP里面的ancestors的id返回来也能找到nouns。
一个time test没过

我新手一个，感觉这样好麻烦。
所以想跟大家交流一下，你们用的是什么样的data structure

rsun 发表于 2014-4-11 14:46
请问一下你是用什么data structure存放synsets的？
我是用了一个ST存放noun 和对应的ids
然后再用了一个 ...

我的id to synsets 和 synsets to id 都是用了ST

landuostorm 发表于 2014-4-11 18:51
我的id to synsets 和 synsets to id 都是用了ST

这么说来我的time没过是其他的原因了。。。我再找找

不对，也有可能是rezising的时候超时了。。。我换ST试试

rsun 发表于 2014-4-11 19:18
这么说来我的time没过是其他的原因了。。。我再找找

不对，也有可能是rezising的时候超时了。。。我换 ...

嗯，有可能，resizing 和 searching 都是O(n)复杂度

rsun 发表于 2014-4-11 19:18
这么说来我的time没过是其他的原因了。。。我再找找

不对，也有可能是rezising的时候超时了。。。我换 ...

全局变量声明一个Array[]，大小未知

我在读文件的时候把<ID, nouns>放到了一个TreeMap<Integer,String>里面（临时的），
读完以后知道了V的大小，Array = new String[V]，
然后for遍历临时的TreeMap，把string放到对应的Array里面，

这样以后查找的时候都是O(1)

grassgigi 发表于 2014-3-25 12:06
交作业

我最后一个timing 没过，想了半天也没有优化的办法了，请问大神们有没有针对outcast有什么优化？

我的思路就是暴力遍历：
d[i] = dis[i,1]+dis[i,2]+...+dis[i,N]
dis的时间复杂度也是在SAP里面确定的，但是SAP的timing 我过了。。。

Timing Outcast
*-----------------------------------------------------------
Running 1 total tests.

3.34 seconds to build WordNet

Computing time to find outcasts. Total time must not exceed 5 seconds.


    filename       N     time
-----------------------------
   outcast4.txt    4     0.42
   outcast5.txt    5     0.17
  outcast5a.txt    5     0.10
   outcast5.txt    5     0.08
   outcast7.txt    7     0.16
   outcast8.txt    8     0.24
  outcast8a.txt    8     0.26
  outcast8b.txt    8     0.18
  outcast8c.txt    8     0.19
   outcast9.txt    9     0.24
  outcast9a.txt    9     0.28
  outcast10.txt   10     0.32
outcast10a.txt   10     0.22
  outcast11.txt   11     0.32
  outcast12.txt   12     0.31
outcast12a.txt   12     0.33
  outcast20.txt   20     0.95
  outcast29.txt   29     2.13
=> FAILED, total elapsed time: 6.87

Total: 0/1 tests passed!