我试图理解外部合并排序算法是如何工作的(我看到了相同问题的一些答案,但没有找到我需要的东西).我正在阅读Jeffrey McConnell撰写的"分析算法"一书,我正在尝试实现那里描述的算法.
例如,我有输入数据:3,5,1,2,4,6,9,8,7,我只能将4个数字加载到内存中.
我的第一步是读取4个数字块的输入文件,在内存中对它们进行排序,然后将一个写入文件A,然后写入文件B.
我有:
A:[1,2,3,5][7]
B:[4,6,8,9]
现在我的问题是,如果它们不适合内存,我如何将这些文件中的块合并到较大的文件中呢？杰弗里麦康奈尔写道,我需要阅读半块并将它们合并到下一个文件C和D.
但我得错了序列:
C:[1,2,4,6,3,8,5,9]
D:[7]
有人可以提供分步说明的例子吗？
PS:我理解如何通过读取文件来合并数字,但是如何使用内存缓冲区来减少I/O操作呢？
这个问题看似简单,但我无法理解它背后的真正工作.我知道人们会说,分解成512 Megs块并将它们排序,就像使用Map reduce一样使用Merge Sort.
所以这是我的实际问题:
假设我将文件分成512 Megs块,然后发送到不同的主机进行排序.假设这些机器使用了Merge Sort.现在说,我有2000台机器每个排序2000,512兆块.现在当我合并它们时,它是如何工作的？尺寸不会继续增加吗？例如,合并两个512兆的将产生1024Megs,这是我的RAM的大小,那么这将如何工作？任何机器都不能将超过512兆块的块与另一块块合并,因为那么大小> 1 GB.
在合并结束时我将能够将两个0.5 TB的块与另一个0.5 TB的块合并.虚拟内存的概念是否会在这里发挥作用？
我在这里澄清我的基础知识,我希望我正确地问这个非常重要的问题(正确).另外,谁应该做这个合并(排序后)？我的机器或那些2000机器中的一些？
我有一个非常大的文本文件(45GB).文本文件的每一行包含两个空格分隔的64位无符号整数,如下所示.
4624996948753406865 10214715013130414417
4305027007407867230 4569406367070518418
10817905656952544704 3697712211731468838 ......
我想读取文件并对数字执行一些操作.
void process_data(string str)
{
vector<string> arr;
boost::split(arr, str, boost::is_any_of(" \n"));
do_some_operation(arr);
}
int main()
{
unsigned long long int read_bytes = 45 * 1024 *1024;
const char* fname = "input.txt";
ifstream fin(fname, ios::in);
char* memblock;
while(!fin.eof())
{
memblock = new char[read_bytes];
fin.read(memblock, read_bytes);
string str(memblock);
process_data(str);
delete [] memblock;
}
return 0;
}
我对c ++比较陌生.当我运行此代码时,我遇到了这些问题.
由于以字节读取文件,有时块的最后一行对应于原始文件中的未完成行("4624996948753406865 10214"而不是主文件的实际字符串"4624996948753406865 10214715013130414417").
这段代码运行得非常慢.在具有6GB RAM的64位Intel Core i7 920系统中运行一个块操作需要大约6秒.是否有任何可用于改善运行时的优化技术？
是否有必要在boost分割功能中包含"\n"和空白字符？
我已经阅读了关于C++中的mmap文件,但我不确定这是否是正确的方法.如果是,请附上一些链接.
我正在从Elmasri和Navathe的作者，第5版的数据库系统基础一书中研究数据库，并且几乎在第15章开始时，他们都使用合并排序简要地解释了外部排序。他们将算法分为两个阶段：
1）排序：他们使用下一个符号：
在此阶段中，我们将尽可能多的块放入数据文件中，使用任何内部排序算法对它们进行排序，并将它们写入为临时排序的子文件。我们在文件的其余块中重复此操作，因此我们将获得更多排序的子文件。这些子文件被它们称为“部分”，它们的数量是：
nr =？b / nb？。
符号？？表示上限功能。此阶段的I / O成本为2b，因为我们需要一次读取每个块（b次访问）。然后，要保存所有部分，我们还需要进行b访问。
2）合并：他们说类似的话（我用我的解释重写了它，以使其更清楚）：
生成的部分（有序子文件）以一遍或多遍混合。每次通过时，将在内存中保留一个输出块，以放置混合结果，其余部分用作输入块，最大可达nb-1，并且每个块一次放置一个块有序部分，目的是将它们混合。当输入块少于部分时，需要多次通过。另外，由于每个部分可以具有一个以上的块，因此将每个遍细分为迭代，每个迭代中都放置了每个部分的块。
数字dm必须等于（nb-1）和nr之间的最小值。如果我们将对数的底数放在（）之间，而其对数放在??之间，则通过的次数为：
？log（dm）？nr ??。
我感到困惑的部分是，他们说这一阶段的成本是
2b *？log（dm）？nr ??，
所以他们基本上是在暗示，在每遍中，我们只需要读取一次每个块并将其写入一次，但是我不确定这是否正确。我怀疑可能需要更多访问权限。
因此，该算法的总成本为2b + 2b *？log（dm）？nr ??。
= 2b（1 +？log（dm）？nr ??）
实际上，他们不是这样说的，而是：“通常，对数以dm为底，表示访问的块数的表达式如下：”
（2 * b）+（2 *（b *（log（dm）？nr？））），
基本上是一样的
例如，假设我们有一个10个块的文件，每个块3条记录。内存（缓冲池）中的可用空间为4个块。让我们用||分隔文件的块
29,11,27 || 22,1,20 || 7,30,26 || 9,8,21 || 13,24,15 || 23,4,28 || 17,12,10 || 5,3,6 || 16,19,2 || 25,14,18
导致分选阶段的部分“ nr”的数量为“ …
我有一个文件,它由一行组成:
1 , 1 2 , 1 3 6 , 4 ,...
在此表示中,空格分隔整数和逗号.这个字符串是如此巨大,我无法用RandomAccessFile.readLine()读取它(几乎需要4 Gb).这样我就创建了一个缓冲区,它可以包含10个整数.我的任务是对字符串中的所有整数进行排序.
能否请你帮忙？
编辑
@Oscar Reyes
我需要将一些整数序列写入文件然后从中读取.其实我不知道,怎么做.我是新手.所以我决定使用字符来编写整数,整数之间的分隔符是",",序列之间的分隔符是"\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 == …什么是高效稳定的外部排序算法实现(用c编写)？
我有char*一个文件数组.我工作的公司将数据存储在平面文件中.有时数据会被排序,但有时却不是.我想对文件中的数据进行排序.
现在我可以从头开始编写代码来执行此操作.有没有更简单的方法？
当然,就地排序将是最佳选择.我正在处理大文件并且内存很少.但我会考虑所有选择.
所有字符串都是相同的长度.
这是一些示例数据:
the data is of fixed length
the Data is of fixed length
thIS data is of fixed lengt
这将代表三条长度为28的记录.该应用程序知道长度.每条记录以CRLF(\r\n)结束,但这种情况无关紧要.
外部排序的主要原因是数据可能比我们拥有的主内存大.但是,我们现在正在使用虚拟内存,虚拟内存将负责主内存和磁盘之间的交换.为什么我们需要有外部排序呢？
假设您在磁盘上有一个包含 n 个对象的大型集合，每个对象都有一个可变大小的字符串。使用纯字符串比较为这些对象建立索引的有效方法的常见做法是什么。由于大小和 I/O 的原因，将整个字符串存储在索引上从长远来看是令人望而却步的，但由于磁盘具有高延迟，仅存储引用也不是一个好主意。
我一直在考虑使用类似 B 树的设计并尝试使用这种方法，但找不到任何数据库实现。事实上，很难找到主要数据库如何实现字符串索引（它可能会迷失在 SQL 级信息的大量结果中。）
蒂亚！
编辑：将标题从“有效外部排序和搜索具有大字符串的存储对象”更改为“有效存储字符串的外部索引”。
我有一个包含大量数据的文件，我想对它进行排序，以便在任何给定时间仅将一部分数据保存在内存中。
我注意到合并排序在外部排序中很流行，但是我想知道是否可以使用堆（最小或最大）来完成。基本上，我的目标是在100个项目的列表中获得前10个项目（使用任意数字），同时在内存中保存的项目绝不超过10个。
我最了解堆，并了解堆数据将按适当的顺序排列，从中可以将其最后一部分作为解决方案，但我不知道如何在没有I / O的情况下进行处理。每一个freakin项目。
有想法吗？
谢谢！：D
在线排序算法和外部排序算法有什么区别？它们是相同的还是不同的？