你好,游客 登录 注册 搜索
背景:
阅读新闻

C++高性能转换大小写算法

[日期:2017-12-30] 来源:Linux社区  作者:oloroso [字体: ]

简述

有一个需求,是需要将URL中的query参数的key全部转换为小写或者大写,键值对的数量有点多,但全部都是英文字母,无需考虑非字母的情况。
实现比较快的做法是使用STL或C标准库中的转换接口,如下:

#include <string> 
#include <cctype> 
#include <algorithm>

// 字符串中的大写字符转小写
std::string strtolower(std::string s)
{
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    return s;
}

// 字符串中的小写字符转大写
std::string strtoupper(std::string s)
{
    transform(s.begin(), s.end(), s.begin(), ::toupper);
    return s;
}

这个方法虽然很好,但是效率不是很高。
分析了一下ascii码的码值,发现大小写字母的ascii码之间是有规律的。

原理

英文字母的ASCII码值表示如下

对比一下其二进制形式

从对比的结果可以看出,大写字母与小写字母的差别仅是一个比特位的不同
因为它们的这个规律,可以写出下面的转换函数(如果输入不是字母,转出的结果会有错误)
可以查看数字0-9的ascii码值,可以看出它们的第6位都是0,所以转为小写的算法不会影响数字的值。
转小写算法中受到影响的,只有ascii码二进制表示中第六位为0的部分。其中非字母部分如下表

#include <iostream>
#include <string>
#include <stdint.h>
// 更优化
std::string strtoupper(std::string s)
{
    if(s.empty()){return s;}
    size_t len = s.size() + 1;
    size_t alignlen = len + 8 - (len % 8);
    s.resize(alignlen);
    size_t ec = alignlen / 8;
    uint64_t* p8 = (uint64_t*)s.data();
    for(size_t i=0;i<ec;++i){
        p8[i] &= 0xDFDFDFDFDFDFDFDF;
    }
    s.resize(len-1);
    return s;
}

// 未做进一步优化
std::string strtolower(std::string s)
{
    size_t len = s.size();
    size_t ec = len /8;
    uint64_t* p8 = (uint64_t*)s.data();
    for(size_t i=0;i<ec;++i){
        p8[i] |= 0x2020202020202020;
    }
    uint8_t* p1 = (uint8_t*)(p8 + ec);
    len %= 8;
    for(size_t i=0;i<len;++i){
        p1[i] |= 0x20;
    }
    return s;
}

性能测试

测试代码如下:

int main()
{
    //std::cout << "Hello, world!\n";
    for(size_t i=0;i<1000000;++i){
    std::string s = strtoupper("qwertyuiopasdfghjklzxcvbnm````````QWERTYUIOPASDFGHJKLZXCVBNM");
    //std::cout<<s<<std::endl;
    s = strtolower("qwertyuiopasdfghjklzxcvbnm\t\t\t\t\t\t\t\tQWERTYUIOPASDFGHJKLZXCVBNM");
    //std::cout<<s<<std::endl;
    }
    return 0;
}

--编译时候请勿优化,否则可能被优化掉!--
测试结果如下:
使用STL算法结果如下

time ./teststl
./teststl  7.88s user 0.03s system 100% cpu 7.904 total

自写代码测试结果如下

time ./test
./test  0.93s user 0.00s system 99% cpu 0.928 total

可以看到,其性能有差异。(应用场景有限)

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-12/149966.htm

linux
相关资讯       C++转换大小 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款