比核心库快百倍系列 - 分割文本_快速 - 2

福仔

上一个帖子, https://bbs.125.la/thread-14763101-1-1.html
上一个帖子有点问题, 比如分割("123", "456") 易语言会返回一个成员的数组, 这个是返回0个成员的数组, 属于bug
这次修复这个问题, 然后增加两个参数, 一个参数是和原来的分割文本一样, 返回指定的成员数, 另一个是预分配的成员数, 这个是用空间换时间
这次把c++的代码发出来, 有可以优化的地方还希望大佬们能优化一下, 或者提一个优化的方向
新增了一个4字节的数组类, 这个数组类只是测试用, 效率嘛肯定是比易语言数组要快, 只是很多方法都没写
等什么时候有闲时间把通用的内存类给写了之后就可以写增删成员的方法了

应该设计一个通用的内存类, 申请/释放/拷贝/重新分配内存 都在这个类里
然后其他类都继承或者内置这个内存类, 比如字符串或者数组
这样就不需要考虑分配内存的事了, 所有对象都只管往里写
有啥想法, 有能力实现的, 欢迎弄一个

[C++] 纯文本查看 复制代码

typedef LPVOID(WINAPI* PFN_Alloc)( DWORD );
typedef void(WINAPI* PFN_Free)( LPVOID );
struct PFN_CALL
{
    LPCSTR      str;            // 被分割的文本, 这个是外部传递进来的文本, 不能修改, 需要重新分配一块内存记录
    LPCSTR      subText;        // 用作分割的文本
    size_t      strLen;         // 被分割的文本的长度
    size_t      subTextLen;     // 用作分割的文本的长度
    PFN_Alloc   pfnAlloc;       // 分配内存的函数
    PFN_Free    pfnFree;        // 释放内存的函数
    LPINT*      pArr;           // 易语言的数组, 局部变量地址, *pArr是数组数据地址, 第一个成员是维数, 第二个成员是数组长度
    int         retCount;       // 要返回的成员数
    int         allocCount;     // 预分配的数组成员数, 首次分配的成员数就是这个数, 如果为0, 那就默认
};

// 不检测指针的有效性
__declspec( noinline ) int WINAPI split(PFN_CALL* call)
{
    LPSTR pStr;           // 被分割的文本, 这个是新分配的文本, 数组里的文本常用都是这个地址里的
    pStr = (LPSTR)call->pfnAlloc(call->strLen + 1);
    if ( pStr == 0 )
    {
        return 0;
    }
    if ( call->retCount < 1 )
    {
        call->retCount = 0x7fffffff;
    }
    else
    {
        // 走到这就是有限制的, 那就要预分配数组成员
        if ( call->allocCount < 1 || call->allocCount > call->retCount )
            call->allocCount = call->retCount;  // 预分配的成员数为0, 那就按返回的成员数来预分配
    }
    LPSTR pStart = pStr;
    LPCSTR pStart1 = call->str;
    while ( *pStart1 )
        *pStart++ = *pStart1++;
    *pStart = 0;
    pStart = pStr;
    
    size_t bufCount = 0;    // 预先分配这么多内存, 不够再分配
    LPINT pArr = 0;         // 最终返回的数组, 这个是易语言一维数组的格式
    size_t count = 0;       // 返回的数组成员数
    const size_t nStartData = 4;    // 起始存放数据的索引, 有两个成员是记录易语言数组的维数和成员数, 这里多分配数据保存其他
    const size_t firstIndex = nStartData - 2;
    
    LPCSTR pValue = pStr;
    LPCSTR pEnd = pStr + call->strLen;
    auto push_back = [&]()
    {
        if ( pValue == pEnd )
            return;
        if ( count + 1 > bufCount )
        {
            size_t newSize = bufCount * 2;
            if ( newSize == 0 )
            {
                // 走到这里就是首次分配内存, 需要根据用户传递的成员数来分配
                newSize = call->allocCount;     // 用户预定义的成员数, 如果为0则内部默认处理
                if ( newSize == 0 || newSize > 0x7fffffff )
                {
                    const size_t maxCount = 10000;  // 设定一个最大值, 要是首次计算的最大值超过这个值, 那就设置为这个值
                    newSize = call->strLen / call->subTextLen / 2;
                    if ( newSize > maxCount )
                        newSize = maxCount;
                    else if ( newSize < 10 )
                        newSize = call->strLen < 10 ? call->strLen : 10;
                }
            }

            // 分配易语言格式的数组内存, 数组成员数据是垃圾数据, 只写了数组维数
            size_t allocSize = newSize + nStartData + 1;
            LPINT arr = (LPINT)call->pfnAlloc(allocSize * sizeof(INT));

            if ( pArr )
            {
                allocSize = bufCount + nStartData + 1;
                for ( size_t i = nStartData; i < allocSize; i++ )
                    arr = pArr;   // 把旧的数组数据赋值到新的数组里
                call->pfnFree(pArr);
            }

            bufCount = newSize;
            pArr = arr;
        }
        size_t index = count + nStartData;
        pArr[index] = (INT)pValue;
        ++count;
    };
    while ( *pStr )
    {
        char& ch = *pStr++;
        if ( ch != call->subText[0] )
            continue;

        // 完全匹配, 需要匹配剩下的字符
        bool isContinue = false;
        for ( size_t i = 1; i < call->subTextLen; i++ )
        {
            if ( pStr[i - 1] != call->subText )
            {
                pStr += i - 1;
                isContinue = true;
                break;   // 只要有一个字符不相等, 那就不是完全匹配
            }
        }
        if ( isContinue )
            continue;

        // 走到这里就是完全匹配了, 处理下一段地址
        pStr--;
        for ( size_t i = 0; i < call->subTextLen; i++ )
            pStr = 0;    // 把分割的子文本修改成0

        push_back();
        if ( call->retCount == count )
            break;  // 成员数够了, 不继续分配了

        pStr += call->subTextLen;
        pValue = pStr;
    }
    if ( !pArr )
    {
        LPCSTR pStrStart = pEnd - call->strLen;
        // pEnd - 分割文本长度 = 被分割文本的起始地址
        // 如果上面的循环有走, 那pStr肯定是大于起始地址
        // 如果这里计算的起始地址和起始地址不相等, 那就是有分割, 0个匹配, 需要把整个文本作为一个成员
        // 如果想等, 那就是循环都没走, 传递的是空文本, 应该不会走到这
        if ( pStrStart == pStr )
            return 0;
    }

    if ( count < call->retCount )
        push_back();
    if ( !pArr )
    {
        call->pfnFree(pStart);
        return 0;
    }

    LPINT pOldArr = *call->pArr;
    
    pArr[firstIndex - 2] = (int)pOldArr;// 原来数组的地址
    pArr[firstIndex - 1] = (int)pArr;   // 分割记录的地址, 第0个成员的地址, 设置这个值是为了判断传递的数组是否是分割时记录的数组
    
    // 从这里开始就是易语言数组的格式了
    pArr[firstIndex + 0] = 1;           // 数组维数, 这个就是设置到易语言局部变量数组里的地址
    pArr[firstIndex + 1] = count;
    *call->pArr = &pArr[firstIndex];
    return count;   // 返回数组成员数
}

struct PFN_CALL_FREE
{
    PFN_Free    pfnFree;        // 释放内存的函数
    LPINT*      pArr;           // 易语言的数组, 局部变量地址, *pArr是数组数据地址, 第一个成员是维数, 第二个成员是数组长度
};

__declspec( noinline ) int WINAPI free_split(PFN_CALL_FREE* call)
{
    LPINT* pArr = call->pArr;
    LPINT arr = *pArr;
    if ( !arr )
        return 0;
    LPINT pTmp = arr - 2;
    if ( pTmp[1] != (int)pTmp )
        return 0;   // -1的位置不是记录的数组地址, 说明不是分割时记录的数组
    
    LPINT pOldArr = (LPINT)pTmp[0];
    *pArr = pOldArr;    // 把原来的数组地址赋值回去
    
    // 清理数组和文本数据
    LPSTR pStr = (LPSTR)arr[2];
    call->pfnFree(pStr);
    call->pfnFree(pTmp);
    return true;
}

__declspec( noinline ) int WINAPI free_split1(PFN_Free pfnFree, LPINT* pArr)
{
    LPINT arr = *pArr;
    if ( !arr )
        return 0;
    LPINT pTmp = arr - 2;
    if ( pTmp[1] != (int)pTmp )
        return 0;   // -1的位置不是记录的数组地址, 说明不是分割时记录的数组

    LPINT pOldArr = (LPINT)pTmp[0];
    *pArr = pOldArr;    // 把原来的数组地址赋值回去

    // 清理数组和文本数据
    LPSTR pStr = (LPSTR)arr[2];
    pfnFree(pStr);
    pfnFree(pTmp);
    return true;
}

下面这个是分割1的代码, 分割1需要改进, 目前分割1的效率比不上第一种分割
但是在c++里使用 vector的话, 会比第一种快.....

[C++] 纯文本查看 复制代码

typedef void( WINAPI* PFN_Insert )( LPCSTR, LPVOID pArg );
struct PFN_CALL1
{
    LPSTR       pStr;           // 被分割的文本, 这个是新分配的文本, 数组里的文本常用都是这个地址里的
    LPCSTR      subText;        // 用作分割的文本
    size_t      strLen;         // 被分割的文本的长度
    size_t      subTextLen;     // 用作分割的文本的长度
    PFN_Insert  pfnInsert;      // 把分割得到的地址传递出去, 让外部存放地址
    LPVOID      pArg;           // 传递给pfnInsert的参数
};
__declspec( noinline ) int WINAPI split1(PFN_CALL1* call)
{
    LPSTR pStr = call->pStr;
    LPSTR pStart = pStr;

    size_t bufCount = 0;    // 预先分配这么多内存, 不够再分配
    size_t count = 0;       // 返回的数组成员数
    const size_t nStartData = 4;    // 起始存放数据的索引, 有两个成员是记录易语言数组的维数和成员数, 这里多分配数据保存其他
    const size_t firstIndex = nStartData - 2;

    LPCSTR pValue = pStr;
    LPCSTR pEnd = pStr + call->strLen;

    while ( *pStr )
    {
        char& ch = *pStr++;
        if ( ch != call->subText[0] )
            continue;

        // 完全匹配, 需要匹配剩下的字符
        bool isContinue = false;
        for ( size_t i = 1; i < call->subTextLen; i++ )
        {
            if ( pStr[i - 1] != call->subText )
            {
                pStr += i - 1;
                isContinue = true;
                break;   // 只要有一个字符不相等, 那就不是完全匹配
            }
        }
        if ( isContinue )
            continue;

        // 走到这里就是完全匹配了, 处理下一段地址
        pStr--;
        for ( size_t i = 0; i < call->subTextLen; i++ )
            pStr = 0;    // 把分割的子文本修改成0

        ++count;
        call->pfnInsert(pValue, call->pArg);

        pStr += call->subTextLen;
        pValue = pStr;
    }
    

    LPCSTR pStrStart = pEnd - call->strLen;
    // pEnd - 分割文本长度 = 被分割文本的起始地址
    // 如果上面的循环有走, 那pStr肯定是大于起始地址
    // 如果这里计算的起始地址和起始地址不相等, 那就是有分割, 0个匹配, 需要把整个文本作为一个成员
    // 如果想等, 那就是循环都没走, 传递的是空文本, 应该不会走到这
    if ( pStrStart == pStr )
        return 0;
    
    if ( pValue != pEnd )
    {
        ++count;
        call->pfnInsert(pValue, call->pArg);
    }
    
    return count;   // 返回数组成员数
}

忘了上传源码....... 不要在意这些细节.....
高效命令处理.e (79.37 KB, 下载次数: 369)

2023-3-21 21:59 上传

点击文件名下载附件

jylt531971998

赞！！！！！！！！！！！！！！

不想解释太多

的郭德纲的风格

鸿运

        感谢你的支持，精易有你更精彩

prospect

只有一个数值没有分隔符时应该返回1的，结果返回了0

renzhanxin

v支持开源~！感谢分享

myogoo

感谢分享！！！！

lovevike1

前已经想到的优化有一个地方

wolfpack

赞！！！！！！！！！！！！！！

肥智

学习一下看看