可以使用内存先写入文本文件来加快写入速度吗?

huangapple go评论63阅读模式
英文:

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 &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;fstream&gt;
#include &lt;chrono&gt;
using namespace std;

int main()
{
    cout &lt;&lt; &quot;\n\n\n     Calculating all Prime Numbers up to 82,000,000&quot;;
    cout &lt;&lt; &quot;\n\n     You will have to give me exactly a minute! ...&quot;;
    cout &lt;&lt; &quot;\n\n     &quot;;
    auto start = chrono::steady_clock::now();
    ofstream myfile;
    myfile.open(&quot;Primes List.txt&quot;);
    myfile &lt;&lt; &quot;2\n&quot;;
    vector&lt;int&gt; primes;
    primes.push_back(2);
    for (int i = 3; i &lt; 82000000; i++)
    {
        bool prime = true;
        for (int j = 0; j &lt; primes.size() &amp;&amp; primes[j] * primes[j] &lt;= i; j++)
        {
            if (i % primes[j] == 0)
            {
                prime = false;
                break;
            }
        }
        if (prime)
        {
            primes.push_back(i);
            myfile &lt;&lt; i &lt;&lt; &quot;\n&quot;;
         }
     }
    auto end = chrono::steady_clock::now();
    chrono::duration&lt;double&gt; elapsed_seconds = end - start;
    myfile &lt;&lt; &quot;\n Elapsed Time: &quot; &lt;&lt; elapsed_seconds.count() &lt;&lt; &quot; seconds\n&quot;;
    cout &lt;&lt; &quot;Elapsed Time: &quot; &lt;&lt; elapsed_seconds.count() &lt;&lt; &quot; seconds\n\n\n&quot;;
    myfile.close();
    system(&quot;pause&quot;);
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} &lt;&lt; 20) {
    std::vector&lt;int&gt; 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&lt;uint64_t&gt; words(nwords);

    words[0] |= 1;
    size_t wdx = 0;
    while (wdx &lt; nwords) {
        auto b = std::countr_one(words[wdx]);
        auto p = 3 * (64 * wdx + b) + 1 + (b bitand 1);
        if (b &lt; 64 and p &lt; max) {
            primes.push_back(p);

            for (auto j = p; j &lt; max; j += 6 * p) {
                auto idx = j / 3;
                auto jdx = idx / 64;
                auto jmask = uint64_t{1} &lt;&lt; (idx % 64);
                words[jdx] |= jmask;
            }

            for (auto j = 5 * p; j &lt; max; j += 6 * p) {
                auto idx = j / 3;
                auto jdx = idx / 64;
                auto jmask = uint64_t{1} &lt;&lt; (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 &amp; (n+1);   // this gives a 1 to the left of the trailing 1&#39;s
    n--;              // this gets us just the trailing 1&#39;s that need counting
    n = (n &amp; 0x55555555) + ((n&gt;&gt;1) &amp; 0x55555555);  // 2 bit sums of 1 bit numbers
    n = (n &amp; 0x33333333) + ((n&gt;&gt;2) &amp; 0x33333333);  // 4 bit sums of 2 bit numbers
    n = (n &amp; 0x0f0f0f0f) + ((n&gt;&gt;4) &amp; 0x0f0f0f0f);  // 8 bit sums of 4 bit numbers
    n = (n &amp; 0x00ff00ff) + ((n&gt;&gt;8) &amp; 0x00ff00ff);  // 16 bit sums of 8 bit numbers
    n = (n &amp; 0x0000ffff) + ((n&gt;&gt;16) &amp; 0x0000ffff); // sum of 16 bit numbers
    return n;
}

int countr_one(uint64_t n) {
    n = ~n &amp; (n+1);
    n--;
    n = (n &amp; 0x5555555555555555ul) + ((n&gt;&gt;1) &amp; 0x5555555555555555ul);
    n = (n &amp; 0x3333333333333333ul) + ((n&gt;&gt;2) &amp; 0x3333333333333333ul);
    n = (n &amp; 0x0f0f0f0f0f0f0f0ful) + ((n&gt;&gt;4) &amp; 0x0f0f0f0f0f0f0f0ful);
    n = (n &amp; 0x00ff00ff00ff00fful) + ((n&gt;&gt;8) &amp; 0x00ff00ff00ff00fful);
    n = (n &amp; 0x0000ffff0000fffful) + ((n&gt;&gt;16) &amp; 0x0000ffff0000fffful);
    n = (n &amp; 0x00000000fffffffful) + ((n&gt;&gt;32) &amp; 0x00000000fffffffful);
    return n;
}

#endif

huangapple
  • 本文由 发表于 2023年5月7日 23:52:02
  • 转载请务必保留本文链接:https://go.coder-hub.com/76194912.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定