如何对2000000数据量的二维数组排序?

Question

题目如下:文件x中的数据格式为：
A段|B段|（如：8613570282030|460000210732030|）数据量：
2000000要求：
1、将文件中的数据以A段为排序字段进行排序，并输出到文件A
 如:8613570282031|460000210732033
    8613570282032|460000210732032
    8613570282033|460000210732031
2、将文件中的数据以B段为排序字段进行排序，并输出到文件B
 如:8613570282033|460000210732031
    8613570282032|460000210732032
    8613570282031|4600002107320333、需计算两次排序处理过程所需要的时间（如数据装载时间、排序时间），以毫秒为单位/*----------------------------------------------------------------------*/
    
    我想用java来实现这个问题,考虑到如此盘大的数据量,如何提高排序效率,以及如何给数组分配内存成了很大一个问题,java中没有指针的概念,所以不能用二维指针数组.
    那么如何从文件x中读出这些数据并放在内存进行排序呢?
    java有提供这样一个排序函数Arrays.sort();这个函数的排序算法是不是快速排序?
    还有如何计算这个装载时间和排序时间(我的java学的很浅=.=)
    最好大侠们能给些代码示例一下.谢谢!

Answer 1

嗯，如此庞大的数据量，我想是不是可以借助DBMS来处理？用java直接处理内存恐怕不够用。
先把数据导入表中，加了索引的表查询排序速度还是比较快的，同时最耗时的地方就是这个导入过程，如果DBMS本身有导入命令最好直接使用。

Answer 2

2000000数据对机器性能是一个很大的考验。楼主可以首先把文本数据进行解析，分解成“A段|B段”的形式存放在一个一维数组中。
存储后数组中的数据格式类似于{"A1|B1","A2|B2","A3|B3",..."An|Bn"}1、将文件中的数据以A段为排序字段进行排序
楼主可以直接调用Arrays.sort(Object[] a)进行排序，然后输出排序结果至文本文件中；2、将文件中的数据以B段为排序字段进行排序
楼主自定义一个Comparator实现类（BComparator，具体实现可以参考String的内部类CaseInsensitiveComparator源码），按照自己想要的逻辑，对“A段|B段”这种数据截取“B段”比较，然后调用Arrays.sort(Object[] a, Comparator c)方法进行排序，然后输出排序结果至文本文件中；不过，这种方法中间会做数组的复制，对内存要求很高。建议楼主最好使用数据库进行操作。

Answer 3

/*以下是我写的一段测试代码,调用Arrays.sort(Object[] a,, Comparator c)进行排序,不知道这个排序方法能不能对这2000000条数据进行排序?!效率如何?!还有一个问题就
是:Arrays.sort*(Object[] a,, Comparator c)能不能对字符串数组进行排序?*/import java.util.*;
public class test {
public static void main(String[] arg)throws Exception {
int ary[][]={{2,5},{6,9},{3,6},{5,3}};//测试数据
                    //读入数据部分
sorttype s=new sorttype("A");//按A段排序
Arrays.sort(ary,s);//对二维数组排序
//创建写入对象
                  //writetofile file = new writetofile();
for(int[] a:ary) {
for(int i:a) 
    System.out.print(i+"|");//测试输出
                                //请问这里如何获取排序后的数据data写入到文件A中
                                //方法file.write(data);
System.out.println();

  }
 }
}//排序方法类
class sorttype implements Comparator<int[]>{
private String ss;
    private int ind=0;
    public sorttype(String s){
     if(s=="A")ss="0";//按A段排序
    else if(s=="B")ss="1";//按B段排序
    else ss="0";
}
    
    public int compare(int a[], int b[]) {
     int r;
        if(a[Integer.parseInt(ss.substring(ind,ind+1))]>b[Integer.parseInt(ss.substring(ind,ind+1))])
         r=1;
        else if(a[Integer.parseInt(ss.substring(ind,ind+1))]<b[Integer.parseInt(ss.substring(ind,ind+1))])
            r=-1;
        else r=0;
        ind++;
        if(ind>=ss.length()) ind=0;
        return r;
   }
}

Answer 4

2000000  数组new出来就堆栈溢出了

Answer 5

但是我不想用到数据库来完成呀.
现在的问题是Arrays.sort*(Object[] a,, Comparator c)能不能直接对字符串数组进行排序?

Answer 6

给你一个基于文件的实现，前提是你的数据必须为定长数据
类似这样的格式
8613570282030|460000210732030   这里假定A段长度都是13，B段长度都是15，行结束标志为\r\n，则每行长度固定为31package webuilder.tools.list;import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.AbstractList;
import java.util.List;
import java.util.RandomAccess;/**
 * 把二进制文件映射成List，用于大数据量的List操作<br>
 * 要求文件中的数据是定长的byte数组，文件总长度是byte数组长度的整倍数
 * 
 * @author Li Jian
 * 
 */
public class RandomAccessFileList extends AbstractList<Object> implements List<Object>,
RandomAccess { private int blockSize; private int listSize; private String fileName; private RandomAccessFile file; /**
 * 
 * @param fileName
 * @param blockSize
 *            每一个数据项占用的字节数
 */
public RandomAccessFileList(String fileName, int blockSize) {
super();
// TODO 自动生成构造函数存根
this.blockSize = blockSize;
this.fileName = fileName;
} public void open() throws IOException {
File f = new File(fileName);
if (!f.exists())
f.createNewFile();
int fileLength = (int) f.length(); listSize = fileLength / blockSize; file = new RandomAccessFile(f, "rw");
} public void close() throws IOException {
file.close();
} @Override
public Object get(int index) {
// TODO 自动生成方法存根
rangeCheck(index); try {
file.seek(index * blockSize);
byte[] buf = new byte[blockSize];
file.read(buf);
return buf;
} catch (IOException e) {
// TODO 自动生成 catch 块
throw new RuntimeException(e);
}
} @Override
public Object set(int index, Object element) {
// TODO 自动生成方法存根
rangeCheck(index);
Object oldValue = get(index);
byte[] buf = (byte[]) element;
try {
file.seek(index * blockSize);
file.write(buf);
} catch (IOException e) {
throw new RuntimeException(e);
}
return oldValue;
} @Override
public boolean add(Object e) {
// TODO 自动生成方法存根
int newLength = (listSize + 1) * blockSize;
try {
file.setLength(newLength);
listSize++;
set(listSize - 1, e);
return true;
} catch (IOException e1) {
throw new RuntimeException(e1);
}
} @Override
public int size() {
// TODO 自动生成方法存根
return listSize;
} private void rangeCheck(int index) {
if (index >= listSize)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + listSize);
}
}

Answer 7

//实际的排序代码
String fileName = ".....";  // 存储数据的文件名 RandomAccessFileList list = new RandomAccessFileList(fileName, 31); // 31为行的长度
list.open();
// 这是根据字段B的排序
Collections.sort(list, new Comparator<Object>() { public int compare(Object o1, Object o2) {
// TODO 自动生成方法存根
byte[] buf1 = (byte[]) o1;
byte[] buf2 = (byte[]) o2;
String s1 = new String(buf1, 14, 13);
String s2 = new String(buf2, 14, 13);
                                // 注释中是根据字段A的排序
// String s1 = new String(buf1, 14, 13);
// String s2 = new String(buf2, 14, 13);
return s1.compareTo(s2);
}
});
list.close();

Answer 8

// 根据字段A的排序应该是这样 :)String s1 = new String(buf1, 0, 13);
String s2 = new String(buf2, 0, 13);