快速多替换成字符串 [英] Fast multi-replacement into string

问题描述

我有类似下面的字符串：

  {A} jahshs {B} {jwuw c}里wuqjwhaha {D} {É} {F} JSJ {G}
 

和我需要一个不同的字符串替换每个 {X} 。问题就来了，因为这个过程将围绕1000次/秒重复，所以我需要一个优化/快速的方式来做到这一点。

你知道吗？升压更换？提升格式？等等。

解决方案

1. preallocate所有缓冲区

   ...




2. 利润

呵呵，没有垃圾邮件。示例code的<击> 5 10分钟。

好吧这里有云：还 住在Coliru

 的#include＆LT;串GT;
＃包括LT＆;＆sstream GT;
＃包括LT＆;升压/实用/ string_ref.hpp＆GT;模板＆LT; typename的范围和GT;
INT扩大（范围常量和放大器; / *键* /）
{
    返回兰特（）％42; //用键（一定要保持苗条这里）待办事项查找值
}＃包括LT＆;＆iostream的GT;
诠释的main（）
{
    静态常量的std ::字符串msg_template ={A} jahshs {B} {jwuw c}里wuqjwhaha {D} {É} {F} JSJ {G} \\ n;    的std :: ostringstream建设者;
    。builder.str（）准备金（1024）; //预留足够的空间，并不重要，因为我们反正重用    用于（为size_t迭代= 1UL＆L​​T;＆LT; 14;迭代; --iterations）
    {
        builder.str（）;
        的std :: ostreambuf_iterator＆LT;＆烧焦GT;出（制造商）;        为（自动F（msg_template.begin（）），L（msg_template.end（））;！F =升;）
        {
            开关（* F）
            {
                案件 '{' ：
                    {
                        自动S = ++ F;
                        为size_t N = 0;                        而（F = L＆安培;！＆安培;！* F ='}'）
                            ++楼+ N;                        //关键的是[S，F现
                        建设者＆LT;＆LT;扩大（升压:: string_ref（安培; * S，N））;                        如果（F！= 1）
                            ++ F; //跳过}
                    }
                    打破;
                默认：
                    *总分++ = *˚F++;
            }
        }
        //让它慢，取消注释：
        //性病::法院LT＆;＆LT; builder.str（）;
    }
}
 

<击>这个运行在〜0.239s我的系统上。 那约68K扩展/秒的
哎呀。在发布建立它确实4000000扩展/秒。在 Col​​iru达到近100万扩张/秒 。

改进的余地：

• 您可以prevalidate输入


• 如果您知道参数键总是1个字母，那么你可以简单地用字符替换string_ref，并通过不循环的'} 。


• 您可以precalculate参数的indicecs和跳跃前进。这里的好处是不那么某些（顺序内存访问是在一些处理器非常好，天真的做法可能会更快）

I have a string like the following:

{A}jahshs{b}jwuw{c}wuqjwhaha{d}{e}{f}jsj{g}

And I need to replace every {x} with a different string. The problem comes because this process will be repeated around 1000 times/second, so I need a optimized/fast way to do it.

Any idea? Boost replace? Boost format? Etc..

解决方案

1. preallocate all buffers

   ....

2. profit

Oh, and don't spam. Sample code in 5 10 minutes.

Okay here goes: also Live On Coliru

#include <string>
#include <sstream>
#include <boost/utility/string_ref.hpp>

template <typename Range>
int expand(Range const& /*key*/)
{
    return rand()%42; // todo lookup value with key (be sure to stay lean here)
}

#include <iostream>
int main()
{
    static const std::string msg_template = "{A}jahshs{b}jwuw{c}wuqjwhaha{d}{e}{f}jsj{g}\n";

    std::ostringstream builder;
    builder.str().reserve(1024); // reserve ample room, not crucial since we reuse it anyways

    for (size_t iterations = 1ul << 14; iterations; --iterations)
    {
        builder.str("");
        std::ostreambuf_iterator<char> out(builder);

        for(auto f(msg_template.begin()), l(msg_template.end()); f != l;)
        {
            switch(*f)
            {
                case '{' : 
                    {
                        auto s = ++f;
                        size_t n = 0;

                        while (f!=l && *f != '}')
                            ++f, ++n;

                        // key is [s,f] now
                        builder << expand(boost::string_ref(&*s, n));

                        if (f!=l)
                            ++f; // skip '}'
                    }
                    break;
                default:
                    *out++ = *f++;
            }
        }
        // to make it slow, uncomment:
        // std::cout << builder.str();
    }
}

This runs in ~0.239s on my system. Thats about 68k expansions/second. Oops. In release build it does 4 million expansions/second. On Coliru it reaches almost 1 million expansions/second.

Room for improvement:

• you can prevalidate the input
• if you know the parameter keys are always 1 letter, then you can simply by replacing the string_ref with the char, and by not looping for the '}'.
• you can precalculate the indicecs of arguments and jump ahead. The benefit here is not so certain (sequential memory access is very good on some processors and the naive approach may be faster)

这篇关于快速多替换成字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！