英文:
Can I speed up my text file writing by using memory first?
问题
以下是您的C++代码的中文翻译:
这是我的C++代码
我正在尝试提高它的运行速度,如果可能的话。
如何将数据写入内存,然后在最后将整个文件转储到“Primes List.txt”?
如果您能提供任何帮助,我将不胜感激。
#include <vector>
#include <iostream>
#include <fstream>
#include <chrono>
using namespace std;
int main()
{
cout << "\n\n\n 计算所有素数,直到8200万";
cout << "\n\n 你需要给我一分钟时间! ...";
cout << "\n\n ";
auto start = chrono::steady_clock::now();
ofstream myfile;
myfile.open("Primes List.txt");
myfile << "2\n";
vector<int> primes;
primes.push_back(2);
for (int i = 3; i < 82000000; i++)
{
bool prime = true;
for (int j = 0; j < primes.size() && primes[j] * primes[j] <= i; j++)
{
if (i % primes[j] == 0)
{
prime = false;
break;
}
}
if (prime)
{
primes.push_back(i);
myfile << i << "\n";
}
}
auto end = chrono::steady_clock::now();
chrono::duration<double> elapsed_seconds = end - start;
myfile << "\n 经过时间:" << elapsed_seconds.count() << " 秒\n";
cout << "经过时间:" << elapsed_seconds.count() << " 秒\n\n\n";
myfile.close();
system("pause");
return 0;
}
希望这个翻译对您有所帮助。如果您有任何其他问题,请随时提出。
英文:
Here is my code in C++
I am trying to speed it up if possible.
How do I write to memory then dump the whole file to "Primes List.txt" at the end?
Thanks if you can help at all.
#include <vector>
#include <iostream>
#include <fstream>
#include <chrono>
using namespace std;
int main()
{
cout << "\n\n\n Calculating all Prime Numbers up to 82,000,000";
cout << "\n\n You will have to give me exactly a minute! ...";
cout << "\n\n ";
auto start = chrono::steady_clock::now();
ofstream myfile;
myfile.open("Primes List.txt");
myfile << "2\n";
vector<int> primes;
primes.push_back(2);
for (int i = 3; i < 82000000; i++)
{
bool prime = true;
for (int j = 0; j < primes.size() && primes[j] * primes[j] <= i; j++)
{
if (i % primes[j] == 0)
{
prime = false;
break;
}
}
if (prime)
{
primes.push_back(i);
myfile << i << "\n";
}
}
auto end = chrono::steady_clock::now();
chrono::duration<double> elapsed_seconds = end - start;
myfile << "\n Elapsed Time: " << elapsed_seconds.count() << " seconds\n";
cout << "Elapsed Time: " << elapsed_seconds.count() << " seconds\n\n\n";
myfile.close();
system("pause");
return 0;
}
I'm running this on quite a beast of a PC and would expect it to run faster.
答案1
得分: 1
以下是您提供的代码的中文翻译:
正如多位评论者所指出的,第一个问题是加速素数生成。以下代码1)使用位图进行筛法,大大减少了所需的内存,并且2)仅检查+/-1 mod 6
的数字。
这是我所知道的最快的筛法算法。在我的机器上,它仅花了108毫秒来覆盖到8200万。对奇数进行筛法花费了180毫秒,而我没有足够的耐心来测量传统的筛法算法。
示例代码
auto sieve_mod6_prime_seq(int max = int{1} << 20) {
std::vector<int> primes;
primes.push_back(2);
primes.push_back(3);
auto max_index = max / 3;
auto bits_per = sizeof(uint64_t) * CHAR_BIT;
auto nwords = (bits_per + max_index - 1) / bits_per;
std::vector<uint64_t> words(nwords);
words[0] |= 1;
size_t wdx = 0;
while (wdx < nwords) {
auto b = std::countr_one(words[wdx]);
auto p = 3 * (64 * wdx + b) + 1 + (b bitand 1);
if (b < 64 and p < max) {
primes.push_back(p);
for (auto j = p; j < max; j += 6 * p) {
auto idx = j / 3;
auto jdx = idx / 64;
auto jmask = uint64_t{1} << (idx % 64);
words[jdx] |= jmask;
}
for (auto j = 5 * p; j < max; j += 6 * p) {
auto idx = j / 3;
auto jdx = idx / 64;
auto jmask = uint64_t{1} << (idx % 64);
words[jdx] |= jmask;
}
}
else {
++wdx;
}
}
return primes;
}
对于没有std::countr_one
可用的C++
版本,以下是一个实现。
// 如果我们使用gcc或clang,则使用编译器内置函数。
#if defined(__GNUC__) || defined(__clang__)
int countr_one(unsigned int n) {
return ~n == 0 ? (sizeof(unsigned int) * CHAR_BIT) : __builtin_ctz(~n);
}
int countr_one(unsigned long int n) {
return ~n == 0 ? (sizeof(unsigned long int) * CHAR_BIT) : __builtin_ctzl(~n);
}
int countr_one(unsigned long long int n) {
return ~n == 0 ? (sizeof(unsigned long long int) * CHAR_BIT) : __builtin_ctzll(~n);
}
// 否则,采用符合标准的实现
#else
int countr_one(uint32_t n) {
n = ~n & (n+1);
n--;
n = (n & 0x55555555) + ((n>>1) & 0x55555555);
n = (n & 0x33333333) + ((n>>2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n>>4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n>>8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n>>16) & 0x0000ffff);
return n;
}
int countr_one(uint64_t n) {
n = ~n & (n+1);
n--;
n = (n & 0x5555555555555555ul) + ((n>>1) & 0x5555555555555555ul);
n = (n & 0x3333333333333333ul) + ((n>>2) & 0x3333333333333333ul);
n = (n & 0x0f0f0f0f0f0f0f0ful) + ((n>>4) & 0x0f0f0f0f0f0f0f0ful);
n = (n & 0x00ff00ff00ff00fful) + ((n>>8) & 0x00ff00ff00ff00fful);
n = (n & 0x0000ffff0000fffful) + ((n>>16) & 0x0000ffff0000fffful);
n = (n & 0x00000000fffffffful) + ((n>>32) & 0x00000000fffffffful);
return n;
}
#endif
希望这些翻译对您有所帮助。如果您有任何其他问题或需要进一步的翻译,请告诉我。
英文:
As multiple commenters noted, the first issue is to speed up the prime generation. The following code 1) uses a bitmap for the sieve which greatly reduces the required memory and 2) only checks numbers that are +/-1 mod 6
.
This is fastest sieve algorithm of which I know. On my machine it only took 108ms to cover up to 82M. Sieving the odds was 180ms and I didn't have enough patience to measure the canonical sieve algorithm.
Sample Code
auto sieve_mod6_prime_seq(int max = int{1} << 20) {
std::vector<int> primes;
primes.push_back(2);
primes.push_back(3);
auto max_index = max / 3;
auto bits_per = sizeof(uint64_t) * CHAR_BIT;
auto nwords = (bits_per + max_index - 1) / bits_per;
std::vector<uint64_t> words(nwords);
words[0] |= 1;
size_t wdx = 0;
while (wdx < nwords) {
auto b = std::countr_one(words[wdx]);
auto p = 3 * (64 * wdx + b) + 1 + (b bitand 1);
if (b < 64 and p < max) {
primes.push_back(p);
for (auto j = p; j < max; j += 6 * p) {
auto idx = j / 3;
auto jdx = idx / 64;
auto jmask = uint64_t{1} << (idx % 64);
words[jdx] |= jmask;
}
for (auto j = 5 * p; j < max; j += 6 * p) {
auto idx = j / 3;
auto jdx = idx / 64;
auto jmask = uint64_t{1} << (idx % 64);
words[jdx] |= jmask;
}
}
else {
++wdx;
}
}
return primes;
}
For C++
versions without std::countr_one
available, here is an implementation.
// If we are using gcc or clang, using the compiler builtin.
#if defined(__GNUC__) || defined(__clang__)
int countr_one(unsigned int n) {
return ~n == 0 ? (sizeof(unsigned int) * CHAR_BIT) : __builtin_ctz(~n);
}
int countr_one(unsigned long int n) {
return ~n == 0 ? (sizeof(unsigned long int) * CHAR_BIT) : __builtin_ctzl(~n);
}
int countr_one(unsigned long long int n) {
return ~n == 0 ? (sizeof(unsigned long long int) * CHAR_BIT) : __builtin_ctzll(~n);
}
// Otherwise, a standards compliant implementation
#else
int countr_one(uint32_t n) {
n = ~n & (n+1); // this gives a 1 to the left of the trailing 1's
n--; // this gets us just the trailing 1's that need counting
n = (n & 0x55555555) + ((n>>1) & 0x55555555); // 2 bit sums of 1 bit numbers
n = (n & 0x33333333) + ((n>>2) & 0x33333333); // 4 bit sums of 2 bit numbers
n = (n & 0x0f0f0f0f) + ((n>>4) & 0x0f0f0f0f); // 8 bit sums of 4 bit numbers
n = (n & 0x00ff00ff) + ((n>>8) & 0x00ff00ff); // 16 bit sums of 8 bit numbers
n = (n & 0x0000ffff) + ((n>>16) & 0x0000ffff); // sum of 16 bit numbers
return n;
}
int countr_one(uint64_t n) {
n = ~n & (n+1);
n--;
n = (n & 0x5555555555555555ul) + ((n>>1) & 0x5555555555555555ul);
n = (n & 0x3333333333333333ul) + ((n>>2) & 0x3333333333333333ul);
n = (n & 0x0f0f0f0f0f0f0f0ful) + ((n>>4) & 0x0f0f0f0f0f0f0f0ful);
n = (n & 0x00ff00ff00ff00fful) + ((n>>8) & 0x00ff00ff00ff00fful);
n = (n & 0x0000ffff0000fffful) + ((n>>16) & 0x0000ffff0000fffful);
n = (n & 0x00000000fffffffful) + ((n>>32) & 0x00000000fffffffful);
return n;
}
#endif
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论