Sunday 28 September 2008

排序算法的实际应用

上次在研究算法的时候详细的介绍了快速排序。
今天有个朋友托我将一些域名排序,按域名长度进行排序。
我看了轨迹至少有300多万行,处理出的结果(txt文件)多大将近100M.
数据量好大啊。
下面是程序清单。核心算法还是复用上次研究过的排序算法。由于数据量巨大,内存会溢出,所以基本解决解决方式是先将文件分段成多个小文件,再分别排序,最后合并到一个文件,删除那些小文件。这对性能造成了影响。所以我直接全部在内存中运算。

五个文件。
Compare.java接口 定义比较排序方式的接口
StringCompare.java Compare的实现类 比如我们这是以域名长度为排序结果
QuickSortVector.java 快速排序算法
GetFile.java 负责文件的输入输出
Main.java主函数入口


——————————————————————————
package sort;

interface Compare {
boolean lessThan(Object sou, Object des);
boolean lessThanOrEqual(Object sou, Object des);
}


——————————————————————
package sort;

public class StringCompare implements Compare
{

public boolean lessThan(Object sou, Object des)
{
return ((String)sou).length()-((String)des).length()<0;
}

public boolean lessThanOrEqual(Object sou, Object des)
{

return((String)sou).length()-((String)des).length()<=0;
}

}
————————————————————————————————
package sort;

import java.util.Vector;

public class QuickSortVector extends Vector{
private Compare compare;
public QuickSortVector(Compare com){
this.compare=com;
}
public void sort(){
quickSort(0,size()-1);
}
public void quickSort(int left,int right){
if(right<=left)
return ;
else{
Object pivot=elementAt(right);
int leftPtr=partition(left,right,pivot);
quickSort(left,leftPtr-1);
quickSort(leftPtr+1,right);
}
}
public int partition(int left,int right,Object pivot){

int leftPtr=left-1;
int rightPtr=right;
while(true){

while(compare.lessThan(elementAt(++leftPtr), pivot)){}
while(rightPtr>0&&compare.lessThan(pivot, elementAt(--rightPtr))){}
if(leftPtr<rightPtr)
swap(leftPtr,rightPtr);
else break;
}
swap(leftPtr,right);
return leftPtr;
}
public void swap(int left,int right)
{
Object temp=elementAt(left);
setElementAt(elementAt(right), left);
setElementAt(temp, right);



}
}
————————————————————————————————————
package sort;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class GetFile
{
private File file;
private File newFile;
private QuickSortVector qsv;
BufferedReader br=null;
BufferedWriter bw=null;
public GetFile(String file,String newFile,QuickSortVector qsv)
{
this.file=new File(file);
this.newFile=new File(newFile);
this.qsv=qsv;

}
public void process(File dir)
{

if (dir.isDirectory())
{
File[] dirs = dir.listFiles();

for (File temp : dirs)
{
if (temp.isDirectory())
{
process(temp);
} else if (temp.isFile())
{
try
{

getQSV(temp);

} catch (IOException e)
{

e.printStackTrace();
}

}
}

} else
{
try
{
getQSV(dir);
} catch (IOException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}
}

}
public BufferedReader getReader(File file)
{
BufferedReader br=null;
try
{
br=new BufferedReader(new FileReader(file));
} catch (FileNotFoundException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}
return br;
}
public BufferedWriter getWriter(File file)
{
BufferedWriter bw=null;

try
{
bw=new BufferedWriter(new FileWriter(file));
} catch (IOException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}

return bw;
}
public QuickSortVector getQSV(File file) throws IOException
{
br=getReader(file);


String temp=null;
while((temp=br.readLine())!=null)
{
qsv.addElement(temp);
}
br.close();
qsv.sort();
bw=getWriter(new File(this.newFile.getPath()+File.separator+file.getName()));

for(Object cc:qsv)
{
try
{
System.out.println((String)cc);
bw.write((String)cc+"\n");
} catch (IOException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}
}
try
{
bw.close();
} catch (IOException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}

return qsv;
}

}
————————————————————————————————————————
package sort;

import java.io.File;
import java.io.IOException;

public class Main
{
// private qsv;

public static void main(String[] args)
{
Compare compare=new StringCompare();
QuickSortVector qsv=new QuickSortVector(compare);
GetFile getFile=new GetFile("D:/sort","D:/sort/result",qsv);
getFile.process(new File("D:/sort"));
[code=Java][/code]


}

}