我有一个文件,其中包含一行:
1 , 1 2 , 1 3 6 , 4 ,...
在此表示中,空格分隔整数和逗号。 这个字符串太大了,我无法使用 RandomAccessFile.readLine() 读取它(需要近 4 Gb)。这样我创建了一个缓冲区,它可以包含 10 个整数。我的任务是对字符串中的所有整数进行排序。
你能帮忙吗?
编辑
@奥斯卡雷耶斯
我需要将一些整数序列写入文件,然后从中读取。其实我不知道,该怎么做。我是新手。所以我决定用chars来写整数,整数之间的分隔符是“,”,序列之间的分隔符是“\n\r”。所以我创造了一个读取它的怪物:
public BinaryRow getFilledBuffer(String filePath, long offset) throws IOException{
mainFile = new RandomAccessFile(filePath, "r");
if (mainFile.length() == 0){
return new BinaryRow();
}
StringBuilder str = new StringBuilder();
mainFile.seek(mainFile.length()-4); //that is "\n" symbol
char chN = mainFile.readChar();
mainFile.seek(offset);
int i = 0;
char nextChar = mainFile.readChar();
while (i < 11 && nextChar != chN){
str.append(nextChar);
if (nextChar == ','){
i++;
if (i == 10){
break;
}
}
nextChar = mainFile.readChar();
}
if (nextChar == chN){
position = -1;
}else{
position = mainFile.getFilePointer();
}
BinaryRow br = new BinaryRow();
StringBuilder temp = new StringBuilder();
for (int j = 0; j < str.length(); j++){
if ((str.charAt(j) != ',')){
temp.append(str.charAt(j));
if (j == str.length() - 1){
br.add(Integer.parseInt(temp.toString()));
}
}else{
br.add(Integer.parseInt(temp.toString()));
temp.delete(0, temp.length());
}
}
mainFile.close();
return br;
}
如果你能建议怎么做,请去做 =)
最佳答案
这正是原点QuickSort当时没有足够的 RAM 在内存中排序,所以他们的程序是将部分结果存储在磁盘中。
所以你可以做的是:
- 选择一个支点。
- 按顺序读取您的文件并将低于基准的数据存储在 temp_file_1 中,将大于或等于基准的数据存储在 temp_file_2 中
- 在 temp_file_1 中重复该过程并将结果附加到 result_file
- 对 temp_file_2 重复该过程并将结果附加到 result_file
当零件足够小时(像2直接交换它们足够在内存中排序)
这样您就可以分块排序并将部分结果存储在临时文件中,您将得到一个包含排序结果的最终文件。
编辑 我告诉过你可以进行快速排序。
看来您毕竟需要一些额外的空间来存放临时文件。
这就是我所做的。
我创建了一个 40 MB 的文件,其中数字以逗号分隔。
我将其命名为输入
:
input http://img200.imageshack.us/img200/5129/capturadepantalla201003t.png
输入为 40mb
在排序过程中,会创建包含“大于”、“小于”值桶的 tmp 文件,排序完成后,这些值将发送到名为(猜猜是什么)output
processing http://img200.imageshack.us/img200/1672/capturadepantalla201003y.png
使用部分结果创建临时文件
最后,所有 tmp 文件都被删除,结果以正确排序的数字序列保存在文件“输出”中:
output http://img203.imageshack.us/img203/5950/capturadepantalla201003w.png
最后创建了文件“output”,注意它也是 40 mb
这是完整的程序。
import java.io.*;
import java.util.*;
public class FileQuickSort {
static final int MAX_SIZE = 1024*1024*16; // 16 megabytes in this sample, the more memory your program has, less disk writing will be used.
public static void main( String [] args ) throws IOException {
fileQuickSort( new File("input"), new File("output"));
System.out.println();
}
//
static void fileQuickSort( File inputFile, File outputFile ) throws IOException {
Scanner scanner = new Scanner( new BufferedInputStream( new FileInputStream( inputFile ), MAX_SIZE));
scanner.useDelimiter(",");
if( inputFile.length() > MAX_SIZE && scanner.hasNextInt()) {
System.out.print("-");
// put them in two buckets...
File lowerFile = File.createTempFile("quicksort-","-lower.tmp",new File("."));
File greaterFile = File.createTempFile("quicksort-","-greater.tmp", new File("."));
PrintStream lower = createPrintStream(lowerFile);
PrintStream greater = createPrintStream(greaterFile);
PrintStream target = null;
int pivot = scanner.nextInt();
// Read the file and put the values greater than in a file
// and the values lower than in other
while( scanner.hasNextInt() ){
int current = scanner.nextInt();
if( current < pivot ){
target = lower;
} else {
target = greater;
}
target.printf("%d,",current);
}
// avoid dropping the pivot
greater.printf("%d,",pivot);
// close the stream before reading them again
scanner.close();
lower.close();
greater.close();
// sort each part
fileQuickSort( lowerFile , outputFile );
lowerFile.delete();
fileQuickSort( greaterFile , outputFile);
greaterFile.delete();
// And you're done.
} else {
// Else , if you have enough RAM to process it
//
System.out.print(".");
List<Integer> smallFileIntegers = new ArrayList<Integer>();
// Read it
while( scanner.hasNextInt() ){
smallFileIntegers.add( scanner.nextInt() );
}
scanner.close();
// Sort them in memory
Collections.sort( smallFileIntegers );
PrintStream out = createPrintStream( outputFile);
for( int i : smallFileIntegers ) {
out.printf("%d,",i);
}
out.close();
// And your're done
}
}
private static PrintStream createPrintStream( File file ) throws IOException {
boolean append = true;
return new PrintStream( new BufferedOutputStream( new FileOutputStream( file, append )));
}
}
文件的格式是number,number,number,number
您当前的格式是:n u m b e r , n u m b , b e r
要解决这个问题,您只需要全部阅读并跳过空白即可。
为此添加另一个问题。
关于java - 在Java中对一个大文件进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2382820/