这是我最近发文时候，发现审核总是有点慢的，引起的思考。下面内容仅代表个人想法，如果冒犯，CSDN不能打我哈
前言
我们言归正传，开始我们的算法思考。修改后重发为啥审核时间减短
你有没有感受过，文章写好时候，看到待审核的焦虑。频繁的刷新，想要早点给可爱的人看看。可是怎么刷都不动，难受至极！你有没有发现过，当你修改已经发好文章时，它的审核速度又突然加快了。神奇哎！满心欢喜的点开文章，想象着自己有着破万的浏览量，多么美妙的白日梦。
现在我们来认真思考下，为啥CSDN它审核这么慢？ 你发可能是涉及羞羞的文字，你是坏孩子。 你发可能文字超过了10万字，文章太长了。我发出了疑问，你能不能看完这么多字。 更有可能你半夜发了一篇文章，人家工作人员不上班，打烊了。等次日早晨吧。
那它是怎么审核呢，要是人工一个字一个字审核，恐怕，是大哥也要疯了！我觉得吧，在弘扬社会主义核心价值观的前提下，它要刷选哪些是值的发的，要是你坏孩子，那可不好的。比如，数据分析看看，你文章有多少不雅文字，图片是否合格，你转发的链接是否有诱导因素等等。敲黑板了，主要看中你是好孩子！
我们言归正传，开始我们的算法思考。
既然你写的文字就相当于在插入字符，那么是不是就相当于在一个很大容量空间里面插入一个数组，这个数组依次排开，然后组成你的文章，那么它的插入算法就是关键所在了。插入结束，我们是不是还要检索相关【不当】字符，这又是不是一个算法。 设想，我们假如我们使用链表插入，那是不是很长很长一条直线了，到时候查询时候，所有空间都遍历一遍，这个时间消耗是不是很大。要是我们使用二叉树来左右插入，是不是就保持两边都有子树，那么在查询的时候是不是只要看该字符值的大小，来确定在那个半边，最起码节省一半时间。对吧！ 下面我们实现下代码 链表插入并查询
public interface Map
void add(K key, V value);
boolean contains(K key);
V get(K key);
void set(K key, V newValue);
V remove(K key);
int getSize();
boolean isEmpty();
}
下面对创建LinkedListMap，实现对【重点字符】的查询 我这里使用的《傲慢与偏见》英文版书籍，里面有十二万字 我们查找出现 pride 和 prejudice 的频次作为我们的关键字
public class LinkedListMap
private class Node{
public K key;
public V value;
public Node next;
public Node(K key, V value, Node next){
this.key = key;
this.value = value;
this.next = next;
}
public Node(K key){
this(key, null, null);
}
public Node(){
this(null, null, null);
}
@Override
public String toString(){
return key.toString() + " : " + value.toString();
}
}
private Node dummyHead;
private int size;
public LinkedListMap(){
dummyHead = new Node();
size = 0;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
private Node getNode(K key){
Node cur = dummyHead.next;
while(cur != null){
if(cur.key.equals(key))
return cur;
cur = cur.next;
}
return null;
}
@Override
public boolean contains(K key){
return getNode(key) != null;
}
@Override
public V get(K key){
Node node = getNode(key);
return node == null ? null : node.value;
}
@Override
public void add(K key, V value){
Node node = getNode(key);
if(node == null){
dummyHead.next = new Node(key, value, dummyHead.next);
size ++;
}
else
node.value = value;
}
@Override
public void set(K key, V newValue){
Node node = getNode(key);
if(node == null)
throw new IllegalArgumentException(key + " doesn't exist!");
node.value = newValue;
}
@Override
public V remove(K key){
Node prev = dummyHead;
while(prev.next != null){
if(prev.next.key.equals(key))
break;
prev = prev.next;
}
if(prev.next != null){
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size --;
return delNode.value;
}
return null;
}
public static void main(String[] args){
System.out.println("Pride and Prejudice");
ArrayList
if(FileOperation.readFile("pride-and-prejudice.txt", words)){
System.out.println("Total words: " + words.size());
LinkedListMap
for(String word: words) {
if (map.contains(word))
map.set(word, map.get(word) + 1);
else
map.add(word, 1);
}
System.out.println("Total different words: " + map.getSize());
System.out.println("Frequency of PRIDE: " + map.get("pride"));
System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
}
}
}
输出结果
Pride and Prejudice
Total words: 125901
Total different words: 6530
Frequency of PRIDE: 53
Frequency of PREJUDICE: 11
ok很完美，确实可以 我们再看看BSTMap
public class BSTMap
private class Node{
public K key;
public V value;
public Node left, right;
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
}
}
private Node root;
private int size;
public BSTMap(){
root = null;
size = 0;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
// 向二分搜索树中添加新的元素(key, value)
@Override
public void add(K key, V value){
root = add(root, key, value);
}
// 向以node为根的二分搜索树中插入元素(key, value)，递归算法
// 返回插入新节点后二分搜索树的根
private Node add(Node node, K key, V value){
if(node == null){
size ++;
return new Node(key, value);
}
if(key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if(key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
node.value = value;
return node;
}
// 返回以node为根节点的二分搜索树中，key所在的节点
private Node getNode(Node node, K key){
if(node == null)
return null;
if(key.compareTo(node.key) == 0)
return node;
else if(key.compareTo(node.key) < 0)
return getNode(node.left, key);
else // if(key.compareTo(node.key) > 0
return getNode(node.right, key);
}
@Override
public boolean contains(K key){
return getNode(root, key) != null;
}
@Override
public V get(K key){
Node node = getNode(root, key);
return node == null ? null : node.value;
}
@Override
public void set(K key, V newValue){
Node node = getNode(root, key);
if(node == null)
throw new IllegalArgumentException(key + " doesn't exist!");
node.value = newValue;
}
// 返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node){
if(node.left == null)
return node;
return minimum(node.left);
}
}
public static void main(String[] args){
System.out.println("Pride and Prejudice");
ArrayList
if(FileOperation.readFile("pride-and-prejudice.txt", words)){
System.out.println("Total words: " + words.size());
BSTMap
for(String word: words) {
if (map.contains(word))
map.set(word, map.get(word) + 1);
else
map.add(word, 1);
}
System.out.println("Total different words: " + map.getSize());
System.out.println("Frequency of PRIDE: " + map.get("pride"));
System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
}
}
}
Pride and Prejudice
Total words: 125901
Total different words: 6530
Frequency of PRIDE: 53
Frequency of PREJUDICE: 11
对比链表的，两个结果一样，达到预期效果 我们现在看下时间消耗
public class TestMapMain {
private static double testMap(Map
long startTime = System.nanoTime();
System.out.println(filename);
ArrayList
if(FileOperation.readFile(filename, words)) {
System.out.println("Total words: " + words.size());
for (String word : words){
if(map.contains(word))
map.set(word, map.get(word) + 1);
else
map.add(word, 1);
}
System.out.println("Total different words: " + map.getSize());
System.out.println("Frequency of PRIDE: " + map.get("pride"));
System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
String filename = "pride-and-prejudice.txt";
BSTMap
double time1 = testMap(bstMap, filename);
System.out.println("BST Map: " + time1 + " s");
System.out.println();
LinkedListMap
double time2 = testMap(linkedListMap, filename);
System.out.println("Linked List Map: " + time2 + " s");
System.out.println();
}
}
输出结果
pride-and-prejudice.txt
Total words: 125901
Total different words: 6530
Frequency of PRIDE: 53
Frequency of PREJUDICE: 11
BST Map: 0.2790993 s
pride-and-prejudice.txt
Total words: 125901
Total different words: 6530
Frequency of PRIDE: 53
Frequency of PREJUDICE: 11
Linked List Map: 14.0617589 s
看看耗时，可想而知了，那么你想到了嘛。没错真相只有一个字数太多，以后少发一点。
修改后重发为啥审核时间减短
下面接着思考，为啥我们对已经发表过的文章修改，很快就能审核通过 不知道大伙有没有想到 【菲波那契数列】 f(n) = f(n - 1) + f(n - 2) ，f(1)=1，f(0)=0。 要是 f(4) = f(3)+f(2) = f(2)+f(1)+f(1)+f(0) = f(1)+f(0)+f(1)+f(1)+f(0) = 3 看到没，这里出现很多的重复项，你的文章也是一样的道理，要是系统在重新在审核插入要多麻烦事，相信大伙都看出来了，用动态规划了吧，以此来减少时间差。 下面我们看下代码的对比。
递归求斐波那契数列
public class Solution1 {
private int num = 0;
public int fib( int n ){
num ++;
if( n == 0 )
return 0;
if( n == 1 )
return 1;
return fib(n-1) + fib(n-2);
}
public int getNum(){
return num;
}
public static void main(String[] args) {
int n = 42;
Solution1 solution = new Solution1();
long startTime = System.currentTimeMillis();
int res = solution.fib(n);
long endTime = System.currentTimeMillis();
System.out.println("fib(" + n + ") = " + res);
System.out.println("time : " + (endTime - startTime) + " ms");
System.out.println("run function fib() " + solution.getNum() + " times.");
}
}
这里计算的42值，就花了很长时间
结果输出
fib(42) = 267914296
time : 2214 ms
run function fib() 866988873 times.
我们再看动态规划
public class Solution2 {
private int num = 0;
public int fib(int n){
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return fib(n, memo);
}
private int fib(int n, int[] memo){
num ++;
if(n == 0)
return 0;
if(n == 1)
return 1;
if(memo[n] == -1)
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
public int getNum(){
return num;
}
public static void main(String[] args) {
//int n = 42;
int n = 1000; // 注意: 我们使用n = 1000只是为了测试性能, 实际上会溢出
// 斐波那契额数列是以指数速度上涨的
Solution2 solution = new Solution2();
long startTime = System.currentTimeMillis();
int res = solution.fib(n);
long endTime = System.currentTimeMillis();
System.out.println("fib(" + n + ") = " + res);
System.out.println("time : " + (endTime - startTime) + " ms");
System.out.println("run function fib() " + solution.getNum() + " times.");
}
}
这个差距呀
输出结果
fib(1000) = 1556111435
time : 0 ms
run function fib() 1999 times.
看到了吧，再次提交修改的文章审核时间大幅度减短是有原因的，要是你觉得不对，可能是你比较优秀，CSDN直接看中你多人。 这是我对审核的一点小小的思考，当然人家的算法更厉害，不可能像我这样说，时间优化肯定还要更完善。 文章至此，仅代表个人想法，要是不小心冒犯了，我会虚心接受点评的。