3

我想知道我们如何从以下 PseudoCode 编写 Java 代码

 foreach file F in file directory D
        foreach int I in file F
               sort all I from each file

基本上这是外部排序算法的一部分,所以这些文件包含排序整数列表,我想从每个文件中读取第一个并对其进行排序,然后输出到另一个文件,然后从每个文件移动到下一个整数再次,直到所有整数都完全排序。
问题是,据我了解,每个文件都需要一个阅读器,所以如果我们有N个文件,那是否意味着我们需要N个文件阅读器?

======更新=======

我想知道它看起来像这样吗?如果我错过任何东西或任何其他更好的方法,请纠正我。

int numOfFiles = 10;
Scanner [] scanners = new Scanner[numOfFiles];
try{
    //reader all the files
    for(int i = 0 ; i < numOfFiles; i++){
        scanners[i] = new Scanner(new BufferedReader(
            new FileReader("file"+i+".txt");
    }
}
catch(FileNotFoundException fnfe){

}
4

5 回答 5

1

问题是,据我了解,每个文件都需要一个阅读器,所以如果我们有 N 个文件,那是否意味着我们需要 N 个文件阅读器?

是的,这是正确的——除非你想要么必须返回数据,要么将每个文件的整个返回到内存中。其中任何一个都可以让您一次只打开一个文件 - 但这很可能不适合您想要做的事情。

操作系统通常只允许您一次打开一定数量的文件。如果您尝试从大量文件中创建单个排序的结果集,您可能需要考虑一次对其中的几个进行操作,从而生成更大的中间文件。在最简单的情况下,这只会一次对两个文件进行排序,例如

input1 + input2 => tmp-a1
input3 + input4 => tmp-a2
input5 + input6 => tmp-a3
input7 + input8 => tmp-a4

tmp-a1 + tmp-a2 => tmp-b1
tmp-a3 + tmp-a4 => tmp-b2

tmp-b1 + tmp-b2 => result
于 2012-11-19T06:47:09.210 回答
0

是的,我们必须有 N 个文件阅读器才能阅读 N 个文件。

为了迭代一个目录中的所有文件,一个一个地读取文件,并将它们存储在一个List中。然后再次对该列表进行排序以获得您的输出。

于 2012-11-19T06:52:28.210 回答
0

只是呈现代码,而不是回答“需要 N 个文件阅读器?” :)

使用 org.apache.commons.io:

//get line iterators :
Collection<File> files = FileUtils.listFiles(/* TODO : filter conf */);
List<LineIterator> iters = new ArrayList<LineIterator>();
for(File file : files) {
  iters.add(FileUtils.lineIterator(file, "UTF-8"));
}

//collect a line from each file
List<String> numbers = new ArrayList<String>();
for(LineIterator li : iters) {
  numbers.add(li.nextLine());
}

//sort
//Arrays.sort(numbers/*will fail*/);//  :)
于 2012-11-19T07:31:10.667 回答
0

我最近在我的 ds 类中学到了一种称为多相合并排序的方法,您可以在其中以运行的形式遍历文件(运行是排序的序列)。有 n 个源和一个目的地。

这种多相方法的要点是必须保持没有文件(给定一组文件)空闲。它显着减少了迭代。它是通过采用等于文件数量的顺序的斐波那契序列来完成的。因此,如果有 5 个文件,我将采用顺序 5 的 fib 序列:[1,1,2,4,8],它表示您将从每个文件中取出并放置它们的运行次数,从对应于runs = 1的文件中,其中一个将是目标。

简而言之:

  1. 根据 fib 序列将文件分发到运行中。[这意味着整个数据集都在一个文件中。如果不是这种情况,您可以随时创建原位运行,您可能希望添加虚拟运行以适应序列]
  2. 将每个文件的前 n 次运行放入缓冲区,对它们进行排序(首选插入)并将它们转储到 ONE 文件中。该 ONE 文件再次被斐波那契数列选中。
  3. 运行到一个点,您只需一次运行即可获得一个文件。

这是一篇巧妙地解释了多相概念的论文。ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/76/543/CS-TR-76-543.pdf

http://en.wikipedia.org/wiki/Polyphase_merge_sort更好地解释了算法

于 2012-11-19T08:24:14.933 回答
-2

是的,您需要 N 个文件阅读器。

public void workOnFiles(){

    File []D = new File("directoryName").listFiles(); //D.length should equal to N.

    for(File F:D){

        doSortingForEachFile(F);//do sorting part here. The same reader cannot open same file here again.

    }
}

public void doSortingForEachFile(File f){
    try{
        ArrayList<Integer> list=new ArrayList<Integer>();
        Scanner s=new Scanner(f);
        while(s.hasNextInt()){//store ints inside the file.
            list.add(s.nextInt());
        }
        s.close();//once closed, cannot open again.
        Collections.sort(list);//this method will sort the ArrayList of int.
        //...write numbers inside list to another file...
    }catch(Exception e){}
}
于 2012-11-19T06:48:30.657 回答