- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我正在处理一个排序项目,我已经到了主要瓶颈是读取数据的地步。使用 cin
对从 stdin 读入的 100,000,000 个整数进行排序需要我的程序大约 20 秒。和 std::ios::sync_with_stdio(false);
但事实证明,其中 10 秒用于读取数据进行排序。我们确实知道我们将读入多少整数(计数位于我们需要排序的文件的顶部)。
我怎样才能让它更快?我知道这是可能的,因为上学期的一个学生能够在 3 秒多一点的时间内完成计数排序(这基本上是纯粹的阅读时间)。
程序只是提供了一个文件的内容,其中包含由换行符分隔的整数,例如 $ ./program < numstosort.txt
谢谢
相关代码如下:
std::ios::sync_with_stdio(false);
int max;
cin >> max;
short num;
short* a = new short[max];
int n = 0;
while(cin >> num) {
a[n] = num;
n++;
}
最佳答案
假设 Linux/POSIX 在商品硬件上运行,这将尽可能快地将您的数据存入内存。请注意,由于您显然不允许使用编译器优化,因此 C++ IO 不会成为读取数据的最快方式。正如其他人指出的那样,如果不进行优化,C++ 代码将无法尽可能快地运行。
鉴于重定向的文件已经作为stdin
/STDIN_FILENO
打开,使用低级系统调用/C 风格的IO。这将不需要进行优化,因为它会尽可能快地运行:
struct stat sb;
int rc = ::fstat( STDIN_FILENO, &sb );
// use C-style calloc() to get memory that's been
// set to zero as calloc() is often optimized to be
// faster than a new followed by a memset().
char *data = (char *)::calloc( 1, sb.st_size + 1 );
size_t totalRead = 0UL;
while ( totalRead < sb.st_size )
{
ssize_t bytesRead = ::read( STDIN_FILENO,
data + totalRead, sb.st_size - totalRead );
if ( bytesRead <= 0 )
{
break;
}
totalRead += bytesRead;
}
// data is now in memory - start processing it
该代码会将您的数据作为一个长的 C 风格字符串读入内存。缺少编译器优化一点也不重要,因为它几乎都是裸机系统调用。
使用 fstat()
获取文件大小允许一次分配所有需要的内存 - 无需 realloc()
或复制数据。
您需要添加一些错误检查,更强大的代码版本将检查以确保从 fstat()
返回的数据实际上是一个具有实际大小的常规文件,而不是“cat 的无用使用”,例如 cat filename | YourProgram
,因为在那种情况下 fstat()
调用不会返回有用的文件大小。您需要在调用后检查 struct stat
的 sb.st_mode
字段,以查看 stdin
流的真正含义:
::fstat( STDIN_FILENO, &sb );
...
if ( S_ISREG( sb.st_mode ) )
{
// regular file...
}
(对于真正的高性能系统,确保您正在读取数据的内存页面实际上映射到您的进程地址空间中可能很重要。如果数据到达速度快于内核的内存管理,性能确实会停滞系统可以为数据转储到的页面创建虚拟到物理的映射。)
为了尽可能快地处理一个大文件,您需要使用多线程,一个线程读取数据并提供一个或多个数据处理线程,这样您就可以在完成读取之前开始处理数据。
编辑:解析数据。
同样,阻止编译器优化可能会使 C++ 操作的开销比 C 风格的处理慢。基于这个假设,简单的东西可能运行得更快。
假设数据是按上述方式读入的 C 风格字符串,这在非优化二进制文件中可能会工作得更快:
char *next;
long count = ::strtol( data, &next, 0 );
long *values = new long[ count ];
for ( long ii = 0; ii < count; ii++ )
{
values[ ii ] = ::strtol( next, &next, 0 );
}
这也是非常脆弱的。它依赖于 strtol()
skipping over leading whitespace ,这意味着如果数值之间除了空格之外还有其他任何内容,它将失败。它还依赖于值的初始计数是否正确。再次 - 如果那不是真的,该代码将失败。因为它可以在检查错误之前替换 next
的值,所以如果它因为错误的数据而偏离轨道,它将无可救药地丢失。
但在不允许编译器优化的情况下,它应该尽可能快。
这就是不允许编译器优化的疯狂之处。您可以编写简单、健壮的 C++ 代码来完成您的所有处理,利用一个好的优化编译器,并且可能运行得几乎和我发布的代码一样快——它没有错误检查,如果被喂食,将会以意想不到的和未定义的方式严重失败意外数据。
关于c++ - 从标准输入 C++ 读取数百万整数的最快方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40473560/
什么是更快的安卓? Color.rgb(184, 134, 011); 或 Color.parseColor("#234181"); 还是别的什么? 答案:最快的似乎是: int mycolor =
没错, 基本上我需要计算出从服务器到最终用户的最短路线。我有 2 台服务器 - 一台在英国,一台在美国。 我需要根据最终用户的位置确定从哪个服务器加载内容。 我最初想使用 fsock/curl/fgc
我正在阅读固定宽度整数类型 ( cpp reference) 并遇到int_fast8_t、int_fast16_t、int_fast32_t 和 int_least8_t 类型,int_least1
Closed. This question is opinion-based。它当前不接受答案。 想改善这个问题吗?更新问题,以便editing this post用事实和引用来回答。 6年前关闭。
我有大量目录,我想尽快读取所有文件。我的意思是,不是 DirectoryInfo.GetFiles 快,而是“get-clusters-from-disk-low-level”快。 当然,.NET 2
我尝试寻找最小的可被1到n整除的数字,现在我正在寻求有关进一步压缩/使我的解决方案更有效的方法的建议。如果也有O(1)解决方案,那将非常酷。 def get_smallest_number(n):
有很多不同的方法可以在驱动程序之间选择元素。我想知道哪一个最快且最适合 native 应用程序(iOS 和 Android)。 Appium Driver 类有: findElementByAcces
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于 Stack Overflow 来说是偏离主题的,
让矩阵 A 说 A = magic(100);。我见过两种计算矩阵 A 的所有元素之和的方法。 sumOfA = sum(sum(A)); 或者 sumOfA = sum(A(:)); 其中一个比另一
我想为玩具车在没有障碍物的平面 (2d) 上规划一条路线。玩具车应该从点 (p1x,p1y) 移动到 (p2x,p2y)(又名狄利克雷边界条件)。此外,玩具车在起点的速度是(v1x,v1y),终点处要
假设有 n 个 3 维对象(多面体)。最快的方法是计算所有对象的交集O(n^2)? 现在,我正在使用一个基本上强制 T(n) 等于 n ^ 2 的库: for each object: // ther
关闭。这个问题需要 details or clarity 。它目前不接受答案。 想改进这个问题吗? 添加细节并通过 editing this post 澄清问题。 关闭 5 年前。 Improve
在 c: 上,我有数以万计的 *.foobar 文件。它们在各种各样的地方(即子目录)。这些文件的大小大约为 1 - 64 kb,并且是纯文本。 我有一个 class Foobar(string fi
我的基本问题是有多个线程做一些事情,其中一些需要比其他线程更多的时间(20 倍甚至更多),他们需要的时间只取决于起始值,但不能从起始值预测单独他们需要多少时间。为了减少更快线程的空闲时间,我想通过
好的,我有一个疑问: select distinct(a) from mytable where b in (0,3) 什么会更快,上面的还是 select distinct(a) from myta
问题简介: 我正在开发一个生态生理模型,我使用了一个名为 S 的引用类列表。存储模型需要输入/输出的每个对象(例如气象、生理参数等)。 此列表包含 5 个对象(请参见下面的示例): - 两个数据帧,S
我有一个正在工作的问题陈述,但我仍然想知道更高效、更快,更重要的是正确设计来处理下面提到的场景。 我有一个 POJO 类 class A { String s; Double d; } 我正在
关闭。这个问题需要更多focused .它目前不接受答案。 想改进这个问题吗? 更新问题,使其只关注一个问题 editing this post . 关闭 3 年前。 Improve this q
关于 LLVM 如何优化代码,关于 SO 以及整个网络都有一些非常好的描述。但这些都无法回答我的具体问题。 在 Xcode 中,项目和目标设置中有各种代码优化选项。我理解在开发过程中不需要优化,但为什
我正在用 C# 开发一个服务器项目,在收到 TCP 消息后,它会被解析并存储在一个精确大小的 byte[] 中。 (不是固定长度的缓冲区,而是存储所有数据的绝对长度的字节[]。) 现在为了阅读这个 b
我是一名优秀的程序员,十分优秀!