Michael_Lin

Michael_Lin 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑

OIer/ACMer,C/C++/Java/Js/Php/python业余开发者

个人动态

Michael_Lin 回答了问题 · 2015-11-12

解决一个关于C++的问题

请注意使用所谓的初始化器的规则
它们不是按照初始化器的位置来决定谁先初始化
而是根据变量谁在前来决定谁先初始化。

第二段代码由于mb在前,所以mb会被先初始化。
详细内容应该C++ Primer 5ed上面有的,个人的建议是不要使用互相引用来初始化

关注 5 回答 4

Michael_Lin 发布了文章 · 2015-04-12

脑补一个非有序数组的二分查找算法

原本想写Base64算法的,不过我还是想写点有趣的,而不是Base64这样没有什么思维难度的模版。在手贱在hihoCoder上看到了一个关于非有序数组的二分查找的题目,要求在非有序的数组上做线性的查找(于是就不能排序了),找到这个数组中第K大的值。做了一个下午,到晚上搞定,终于抠完几个细节。不过想的过程还是蛮棒的,这个算法是从快速排序衍生而来的,而从经典算法出发去yy,能让我们思考更多经典算法的细节,感受经典算法的那种美。

快速排序

在讲这个二分查找算法的之前我们还是先看看它的基础:快速排序算法。虽然快速排序有很多缺点:它不稳定、难理解、会被奇葩数据拿去卡,但在实践当中还是个很快很靠谱的排序算法,比Java和Python所采用的TimSort不知道高到哪里去了。我觉得作为一个IT从业者,不能理解快排就好像一个中国人没读过《论语》一样。
讲解快排的文章有很多,任何一本算法书也都不可能不讲快排。不过我这里需要特别阐述一下快排究竟在干什么。
基本的观点是,每一“趟”的快排是针对原来数据的一个区间上进行的。首先在这个区间上随意取一个值mid,然后遍历一遍这个区间,使得能够把所有数据中小于等于mid的扔到区间的左部分,大于等于mid的扔到区间的右部分。然后左右分别继续搞。这么说太抽象了,我们拿几个数据玩玩看:
假设初始的数据是34 10 23 78 56,那么如果我们取第一个34为mid,我们就要遍历一遍数组(在O(n)的时间内)变成10、23、34在左边,56、78在右边。至于10、23、34它们之间的顺序则无关紧要,不论是10、23、34还是23、34、10还是34、10、23还是别的什么都不管,反正前三个都是小于等于34的,后两个都是大于等于34的。

其实34也可能在后面一半。这点非常重要,因为这就意味着mid的值位置是不确定的,如果数据中有多个mid,它可能左右两部都有分布。实际上一趟快排结束后,我们只能保证小于mid的在左边,大于mid的在右边,至于mid在哪?不知道。

现在我放一段我的快排实现。我取mid一般是取中间那个位置,正常情况下是要随机取,而算法讲解的时候一般取第一个。

void Qsort(int l,int r){
    int mid=A[(l+r)/2];
    do{
        while (A[i]<mid) i++;
        while (A[j]>mid) j--;
        if (i<=j){
            int k=A[i];
            A[i]=A[j];
            A[j]=k;
            i++;j--;
        }
    }while (i<=j);
    if (l<j) Qsort(l,j);
    if (i<r) Qsort(i,r);
}

这段程序能保证的是,所有小于mid的都在l~j范围内,而所有大于mid的都在i到r范围内。同时j+1到i-1范围内的(至多一个,可能是零个),一定是mid。但是所有是mid的值,位置是不确定的。

非有序数组的线性查找算法

我们现在可以开始想怎么在非有序的数组里,避免全部排序整个数组,而找到某个数是第几大了。由快速排序的算法的思想出发,我们可以发现,如果一趟快排结束,那么我们每次能把小于mid的扔到区间左边,大于mid的扔到区间右边,平均来看,查找范围就缩小了一半。(当然被卡是可能的,我们只是寻求一个期望复杂度的较优。)这样一个算法能够实现,那么整体复杂度就是
要注意的是i与j之间的差。在上述的快排程序跑过一趟之后,j<i,但是我们并不确定j和i中间是否会有一个数。这个数可能有,也可能没有,必须特殊判断。最后写出来的线性查找算法如下:

int Search(int l,int r){
    if (l==r) return A[l];
    int i=l,j=r;
    int mid=A[(l+r)>>1];
    do{
        while (A[i]<mid) i++;
        while (A[j]>mid) j--;
        if (i<=j){
            int k=A[i];
            A[i]=A[j];
            A[j]=k;
            i++;j--;
        }
    }while (i<=j);
    if (j==i-2){
        if (j+1==K) return A[j+1];
    }
    if (K<=j) return Search(l,j);
    if (K>=i) return Search (i,r);
}

我拿了一个用algorithm库提供的sort函数做的O(NlogN)排序程序做对拍,在N=106的情况下,不开O2速度快一倍,开了O2快30%左右,效率提升还是很显著的。

查看原文

赞 0 收藏 2 评论 2

Michael_Lin 发布了文章 · 2015-03-25

Java Servlet实现文件上传

文件上传可以说是Web应用中很常用的一块,前几天打算研究一下HTML5提供的FileReader API,并且用Tomcat作为后端来实验大文件的上传(只是学校的课程作业必须用Java写,都不允许使用最好的编程语言php>.<)。可Java Servlet与php这种喜闻乐见的Web码农语言不同,并没有提供一个很简单的处理文件上传的API,所以还捣鼓了蛮久,也对一般的文件上传的HTML控件和实现原理稍微有了一点了解。

对面宿舍的一位同学说我很久没更了不太好,于是我就写一篇,谢谢他的提醒。

首先,我们都知道最常见的HTML的文件上传控件是喜闻乐见的<input type="file">,但一定要搭配form的属性enctype="multipart/form-data",服务器上要有一个接收上传的cgi或者别的什么,既然我们用java写,就叫uploadServlet。于是有了一个如下的常见的上传表单。

<form action="uploadServlet" enctype="multipart/form-data" method="POST">
    <input name="password" type="password" />
    <input name="File1" type="file" />
    <input type="submit" value="Upload" />
</form>

然后我们在后端处理。由于Java Servlet的API是没有提供什么$_FILES数组这样傻瓜式的文件操控方式,我们必须自己处理request。我们不妨先把收到的request输出到文件当中,看看Servlet会收到什么,再想想怎么处理。放这样一个servlet的代码:

import javax.servlet.*;
import javax.servlet.http.*;
import java.io.*;

public class UploadServlet extends HttpServlet{
    @Override
    public void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException{
        response.setContentType("text/plain;charset=utf-8");
        PrintWriter writer=response.getWriter();
        InputStream in=request.getInputStream();
        File f = new File("/tmp/upload");
        //把文件存到/tmp/upload
        FileOutputStream fout = new FileOutputStream(f);
        byte[] b=new byte[1024];
        int n=0;
        while ((n=in.read(b))!=-1){
            fout.write(b,0,n);
        }
        fout.close();
        in.close();
        writer.println("Finished uploading files!");
        writer.close();
    }
}

有了Servlet就拖出去跑一跑。这里我的表单不仅会发送文件,还会发送一个密码域。如果我随便发一个文本文件,那么我得到了这样的结果。
upload请求数据用gedit打开的upload请求数据图片
多上传几次还会发现那一堆横杠开头的数字会变动。这下不好玩了,虽然我们可以看到我们上传的数据,但要解析它有点过于复杂了。这个请求是依据RFC1867来写的,虽然有标准可依,但我们这么懒怎么会去依照标准写一个解析器呢?

于是我们需要请出Apache开发的文件上传处理库Commons FileUpload。这个网站提供了最新版的下载链接和基本的使用指南。文档讲得过于全面了,而我们一般不需要那么多功能,够用就好。翻了几篇教程,写出来了一个简单的文件上传接收代码。

javaimport javax.servlet.*;
import javax.servlet.http.*;
import java.io.*;
import java.util.*;
import org.apache.commons.fileupload.*;
import org.apache.commons.fileupload.servlet.*;
import org.apache.commons.fileupload.disk.*;

首先需要多装载三个库,以及一个java.util.List,因为到时候处理的时候,Commons FileUpload会把搞成一个List返回回来,我们需要接收这个List并处理解析它。

public class UploadServlet extends HttpServlet{
    private String filepath;
    private String temppath;
    private String buf;
    public void init(ServletConfig config) throws ServletException{
        super.init(config);
        ServletContext context=getServletContext();
        filepath=context.getRealPath("/"+config.getInitParameter("filepath"));
        temppath=context.getRealPath("/"+config.getInitParameter("temppath"));
    }

为了方便维护,我把保存上传文件的目录用Init Parameter的方式写到web.xml里面去,然后在这个地方读出来。我们需要一个保存上传文件的目录和一个用来做缓存的临时目录。如果你接收上传文件之后不打算保存而是直接拿去处理,也没有问题,但是一定要有一个缓存目录,在后面有用。

接下来是真正激动人心的处理上传的代码了。我懒得写doGet了所以就只有一个doPost。

     @Override
    public void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException{
        response.setContentType("text/plain;charset=utf-8");
        PrintWriter writer=response.getWriter();
        int count=0;
        try{
            DiskFileItemFactory diskFactory = new DiskFileItemFactory();
            diskFactory.setSizeThreshold(4 *1024 );
            diskFactory.setRepository(new File(temppath));

这里我们开了一个diskFactory,就是FileUpload所需要使用的缓存,当内存存不下上传的文件的时候,它会自动写入缓存目录。通过setSizeThreshold方法可以设置内存的使用上限,也就是当内存用了这么多却还存不下,就开始写缓存。显然这个值很大程度上会决定这个Servlet的效率。

    ServletFileUpload upload = new ServletFileUpload(diskFactory);
    upload.setSizeMax(4 * 1024 * 1024);
    List fileItems = upload.parseRequest(request);
    Iterator iter = fileItems.iterator();

这里我们就真正建了一个ServletFileUpload的实例upload来处理文件的上传。可以设置上传文件的最大大小。然后把request对象直接交给upload来解析,它会返回一个一个List,这个List的每一项实际上是一个FileItem对象,后面就要用迭代器处理这个列表。

    while (iter.hasNext()){
        FileItem item = (FileItem) iter.next();
        if (item.isFormField()){
            writer.println(item.getFieldName()+" : "+item.getString());
        }

要注意的是ServletFileUpload也会处理非文件的信息,可以用isFormField方法来检查,然后将信息获取出来。但这在这里不是重点,只是必须要处理掉而已。

        else{
            String filename = item.getName();
            filename = filename.substring(
            filename.lastIndexOf("\\")+1,filename.length());
            File uploadFile = new File(filepath+"/"+filename);
            item.write(uploadFile);
            writer.println("Get file:"+ filename);
            writer.println(" filetype: "+item.getContentType());
            count++;
        }
        }
    } catch (Exception e){
        e.printStackTrace();
    }
    writer.println("Finished uploading files!");
    writer.close();
}
}

处理文件的代码就这么点,如果还要说什么的话,就是每个文件的FileItem对象不仅可以用write方法来直接写到什么文件里面去,也可以用getInputStream方法得到一个输入流来解析,或者用get方法直接读到一个byte数组里面去。可以说这个库提供了一个很方便的方法解析上传的文件。

最后提一下,Apache Commons是一个Java增强库,提供了大量的优质Java资源库,涉及很多开发领域。如果不出意外,应该我会在近期写一篇关于JavaScript FileReader的blog,敬请期待。

参考的文章:
Servlet实现基本文件上传
在Servlet中使用开源fileupload包实现文件上传功能

查看原文

赞 4 收藏 15 评论 2

Michael_Lin 关注了问题 · 2015-02-20

解决印象笔记地图集 使用的是什么地图API

看上去有点像矢量图,现在貌似就Google 提供矢量图额,但是看上去也不像是 Google 地图。

另外请问下,现在 Android 和IOS 还有 Google Maps 的 API 吗? 现在 google.com 的不是被禁用了嘛?

关注 4 回答 3

Michael_Lin 赞了回答 · 2015-01-30

Windows下的cmd替代工具?

三个答案都没提到 PowerShell,你们是故意的么。PowerShell 就是 cmd 的代替品,cmd 还留着一方面可能也是出于向下兼容,另一方面就是 PowerShell 出来那么多年了知道的人却不多… 另外 cmd 交互上 Windows 10 有改进。

关注 84 回答 26

Michael_Lin 关注了标签 · 2014-08-31

apache

Apache是世界使用排名第一的Web服务器软件。它可以运行在几乎所有广泛使用的计算机平台上,由于其跨平台和安全性被广泛使用,是最流行的Web服务器端软件之一。它快速、可靠并且可通过简单的API扩充,将Perl/Python等解释器编译到服务器中。

关注 1714

Michael_Lin 关注了标签 · 2014-08-31

django

Django是一个开放源代码的Web应用框架,由Python写成。采用了MVC的软件设计模式,即模型M,视图V和控制器C。它最初是被开发来用于管理劳伦斯出版集团旗下的一些以新闻内容为主的网站的。并于2005年7月在BSD许可证下发布。这套框架是以比利时的吉普赛爵士吉他手Django Reinhardt来命名的。

Django的主要目标是使得开发复杂的、数据库驱动的网站变得简单。Django注重组件的重用性和“可插拔性”,敏捷开发和DRY法则(Don't Repeat Yourself)。在Django中Python被普遍使用,甚至包括配置文件和数据模型。

关注 4679

Michael_Lin 赞了回答 · 2014-08-24

关于js的闭包

一般来讲,js的所有函数都是闭包,但是匿名函数可以在其它函数内部创建,而且可以访问到外层的局部变量,相对来讲功能比较强一点。然而这两种函数都一样,return可有可无。如果一个函数没有return,那它的返回值默认是undefined

关注 6 回答 8

Michael_Lin 发布了文章 · 2014-06-24

有向图欧拉回路的快速算法(POJ 2230题解)

高考考完开始进行算法竞赛的康复训练(好吧其实是从零开始直接学,过完高三什么都忘了T T),在POJ上做了一些水题。今天做到这道欧拉回路,很有感触,因为第一次学这个算法的时候并没有学透,今天再做才发现原来求欧拉回路的算法有这么精妙。

先讲题意吧,原文链接:http://poj.org/problem?id=2230。大意是给你一个无向图,要求找一条路径,走过每一条边恰好两次,且每次走的方向不同。很容易就能想到把这图转化为有向图求欧拉回路。题目保证一定能找到从1点出发回到1点的答案。

现在的关键就是求这个回路了,一个朴素的想法就是直接DFS,每次经过一条边就删除它,回退的时候再还原。如果经过了原图边数恰好两倍就找到了一个答案。但这个算法实在太慢,直接TLE。

现在我们考虑搜索的过程:如果不还原一个点所遍历的边,那么当这个点去掉所有边之后,再去掉这个点,剩下的图是什么?先上图,这是题目所给的样例的草图:
还没遍历时的图像
然后从1开始,我们丧心病狂一点,直接把1就搞掉不碰与1无关的边,反正遍历的顺序是不确定的,这么做未尝不可。那么就变成了这样:
删除1和相关的边的情况
我们看到,剩下的还是一个欧拉回路。我们可以猜想,一个欧拉回路,删掉一个点,仍然是一个欧拉回路。这个结论其实非常容易证明,随便想想就明白这是对的。进一步研究,会发现一个更普遍的结论:从一个欧拉回路中拖走一个小欧拉回路,结果也是一个欧拉回路。这个性质也很明显,而且前一个结论是后一个结论的推论。由这个结论,我们可以考虑,有公共点的两个欧拉回路其实是可以拼接的。于是下面这个搜索算法就很好理解了:

void DFS(int now)
{
    for (int p=G.Head[now];p;p=G.Pre[p])
    {
        if (!G.Vis[p])
        {
            G.Vis[p]=1;
            DFS(G.V[p]);
        }
    }
    printf("%d\n",now);
}

G是图,我用了一个邻接表,G.Vis是标记这条边是否走过。如果一条边还没走过,就标记然后走下去,关键在如果一个点已经走完了怎么办:直接输出。每次从v出发回到v,就是扒走了一个回路,根据栈的性质,这样得到的顺序其实是相反的。不过由于这题的图中边是成对出现,所以没关系,倒过来也是可以的。输出的过程就是把一个个欧拉回路拼在一起。对于无向图,通过拼接也可以得到欧拉回路,不过相对于这个算法要复杂不少。最后提供Gitcafe代码链接,如有需要参考请看:https://gitcafe.com/linmx0130/OJCode/blob/master/POJ/P2230/main.cpp

查看原文

赞 0 收藏 1 评论 0

Michael_Lin 赞了回答 · 2014-06-24

说一下在win和linux下开发PHP的区别、感受、内心想法。望点评

首先要分清楚“开发时用的操作系统”和“开发环境的操作系统”的区别。前者是你运行IDE,编辑器,查邮件,和团队沟通时使用的操作系统,而后者是你开发过程中运行代码用的操作系统,我的观点是后者一定不能是windows,而前者随意。 两者可以是同一个linux,可以是一台windows或mac,另一台里面的linux虚拟机,也可以是两台物理机器都ok,放弃使用windows作为开发环境是很对的,但这不意味着你就必须得用linux桌面。

另外关于编译的吐槽,如果你开发的系统对php的版本、模块并不特别挑剔的话,几乎所有发行版都有编译好的php二进制包。当然,学会自己编译更好,所谓的“Linux基本功”其实不外乎文件/文本操作和源码编译/安装两大块。比起微软的那套东西,linux下可能你上手装第一台机器要半天,但熟练以后装100台机器也就只要半天。windows你上手可能只要一小时,但装100台机器一周都不一定能搞定,还要给微软缴100份授权,呵呵

关注 7 回答 11

认证与成就

  • 获得 23 次点赞
  • 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2014-04-26
个人主页被 963 人浏览