[HomeWork] Algorithms, Part I (week 2)

这次练习难度不大，主要是有两个 可以参考的代码  ResizingArrayStack.java ；LinkedStack.java； 没思路的时候可以看看。
deque 可以用两个带sentinel node 双向链表搞定，这个在cs61b前几周里讲过。。。
RandomizedQueue 我一开始还是用双向链表去搞。。。发现不好randomize，但我就是想用双向链表，插入、删除多方便啊。。。于是把链表的数据直接复制到一个item[] 数组里，然后借用shuffle()函数，心里想肯定能成，结果一提交就傻逼了。。。timing挂了一大半。即使再写一个private 定位链表的函数也不管用。。。  其实这种方法虽然麻烦，但也是可以的，我其他的test 都过了，timing 死也过不了。最后还是用数组来搞，终于搞完了。。。其实搞完了，心里也是虚的，虽然代码都是自己写的，总觉得不踏实。。。哎!

我第三个subset.java程序这样写的，顺利通过auto-grader了。但在Eclipse上运行不起来，显示“Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0”.
如果我把第一行改成int k = StdIn.readInt(); 那样Eclipse就能运行了（但要用ctrl+D终止程序接受输入），但却过不了auto-grader 3个tests. 有人能解释下怎么回事吗？

最后再问下，command line argument和standard input到底什么区别？之前一直以为一回事，请高手详细解释给我这个小白听下呀，多谢啦。

过了一周再回过头来看写的代码，已经记不得哪些是重点了。感觉Randomized queue在弹出式有点问题，不过还是过了。

iPhD 发表于 2015-7-1 02:37
我第三个subset.java程序这样写的，顺利通过auto-grader了。但在Eclipse上运行不起来，显示“Exception i ...

我用drJava写的，也是有问题，在输入时无法停止。同求解。

拖延症啊。。又要due了。。

先贴作业：

我发现这课喜欢考一些他没好好讲过的，但是默认你会的/默认你自己会去他那本红宝书上找的。
week2感觉就是把amortized analysis, randomised analysis, I/O纠缠在一起考了。

Deque，randomizedQueue怎么实现都好说；探讨三个问题：
1. dequeue()为何是O(1)
2. I/O
3. bonus point
今天写了一天，实在没力气了。。。先睡了，明天起来再填坑。。。

enirinth 发表于 2015-7-13 22:36
先贴作业：

1. dequeue()的效率为何是O(1)randomizedQueue用resizing array实现。每一次的dequeue()都会随机在[front, back)区间中generate一个随机数，然后删去这个数。
删去了之后，形成一个空位；但是此时不能移动元素把空填住：因为amortized running time的要求是O(1), 所以只在resizing这样的“稀疏”时刻允许大规模移动元素；不能每次都移动。
那么只能检查generate的这个数在不在以前的空里，如果不幸命中空位，只能再重新生成，那我得重新生成多少次呢？会不会次数太多不是O(1)了呢？
randomized analysis:
假设[front,back)区间长度是N，其中有M个空，那么命中空位的概率为p = M/N
只需要1次就成功删除的概率为: 1 - p
2次：(1 - p)p
3次：(1 - p)p^2
i次： (1 - p)p^(i-1)
那么每次dequeue()需要操作次数的期望就是S = 1*(1 - p) + 2*(1 - p)p+ 3*(1 - p)^2 + ... + i*(1 - p)p^(i-1) + ...
S = (1 - p) (1 + 2p + 3p^2 + 4p^3 + ... )
   = (n -> 无穷) (1 - p^n)/(1 - p) - np^n
   = 1/(1 - p)
由于randomizedQueue的array整体的size ≥ N(front,back这个区间的长度)；
一共有N - M个数，N - M ≤ 0.25 * size就会resize了，所以一定有
N － M ≥ 0.25 * size ≥ 0.25 * N
从而p ＝ M/N ≤ 0.75
故S = 1 / (1 - p) ≤ 4
也就是说，虽然我每次都有可能生成一个随机数数刚好命中空位，但数学期望是我在4次以内能命中一个非空位，使得dequeue()成功进行；
从而dequeue()期望上是O(1)的。

至于resizing，它只发生在一些稀疏的时刻，amortized analysis中的averaging method很容易得出连续M个dequeue()平均下来一定是O(1)的；
那么如果dequeue(),enqueue()交替混杂的进行，如何判断平均用时呢？
- accounting method; CS 61B这门课分析resizing hash table的时候详细讲了这个方法，此处从略；它依旧可以证明我随机的进行dequeue()和enqueue()操作时，最后得出的平均时间还是O(1)；

2. I/O
input stream最重要的特点就是你不能反复的读取它，读到了某个位置之后，再readString()就一定是在这个位置之后了；
这门课提供的StdIn实际上主要用的是java.util.Scanner；
作业不让用util里的类，让你用StdIn，其实后者也用到了util，多么讽刺....
用Scanner的好处是，我可以直接readAll()，存一个String（而不是String[], 因为数组长度是O(N)的，违反了bonus test的要求）；然后就是String的算法了，Scanner里面提供了很多很直白的函数；
既然不让用，那我们就免不了while (!StdIn.isEmpty()) 这个循环了

3. bonus point: randomizedQueue的最大长度始终≤k,而不是N

我最开始的想法是如果知道了k和N，那么读每个数的时候就知道他进randomizedQueue 的概率了；
但问题是input stream读完之前，我不可能知道N是多少；而input stream读完之后，每个数都按自己应有的概率enqueue了;
所以解决问题的方法就是：N是动态的；每读一个数，N++，然后对之前的概率分配进行调整；
以1,2,3,4,5 ; k = 3, N =5 为例：
在queue长度达到k之前，照单全收；所以queue长度达到k时里面的元素是:1, 2 ,3
这时候从input stream里面读到4，一共读了4个数，N变成了4;
由于queue的长度不能超过k，超过1个也不行，所以我要先从1，2，3里面随机洗出一张牌，再把4放进去；保证queue的长度一直是k；
由于dequeue()是随机的，所以(1,2,4),(1,3,4),(2,3,4)都是等概的；
问题是没有(1,2,3); 所以有一定概率我不要4从而得出(1,2,3)。这个概率是多少呢？
也就是从N个数里面挑k个数，没有某一个数的概率 = C_{N - 1}k / C_Nk = (N - k) / N
此时k = 3, N =  4，(1,2,3)的概率就是1/4了；
下一步，读到5，N = 5; 又要面临是否要把5弄进去的抉择，此时的(N - k) / N = 2/5; 也就是说不要5的概率是2/5.
由此保证了每个(a,b,c)的permutation一定是等概的。

这个算法的思路在于：
每次决定要不要一个新数加进来的时候，我都可以保证：如果加进来，然后我可以把包含它的所有组合洗的等概；那么我只要保证不加他进来的总概率（或加他进来的总概率）是对的即可；
这个不加进来的概率就是(N - k) / N （加进来的概率是k / N）

1. public static void main(String[] args) {
   
2.   int k = Integer.parseInt(args[0]);
   
3.   RandomizedQueue<String> randomStrQue = new RandomizedQueue<String>();
   
4.   double N = 1.0;
   
5.   while (!StdIn.isEmpty()) {
   
6.      String s = StdIn.readString();
   
7.      if (k == 0) {
   
8.         break;
   
9.      } else if (randomStrQue.size() < k) {   //  长度到k之前照单全收
   
10.          randomStrQue.enqueue(s);
    
11.      } else if (StdRandom.uniform() > ((N - k) / N)) {  //  按(N - k)/N的概率决定要这个新数之后，才先洗出来一张，然后把他加进去
    
12.          randomStrQue.dequeue();
    
13.          randomStrQue.enqueue(s);
    
14.      }
    
15.      N++;
    
16.   }
    
17.   while (!randomStrQue.isEmpty()) {
    
18.      System.out.println(randomStrQue.dequeue());
    
19.   }

复制代码

enirinth 发表于 2015-7-14 12:05
1. dequeue()的效率为何是O(1)randomizedQueue用resizing array实现。每一次的dequeue()都会随机在[front ...

ORZ!!!真心佩服，

看着简单 结果也是提交了好几次才通过所有测试

小的现在看书看到一个不会的地方 希望各位大神给个解答哈，
为什么在binary heap 里面，when a key is smaller than a child， we need to exchange key in parent with key in larger child instead of small child？  
因为是自己看书没跟着一起上课， 小的实在找不到讲heap sort 的帖子了， 希望鹳狸猿大人不要删帖