(C#) 提高自定义getBetweenAll的速度

Question

我用 c# 编写了一个自定义扩展方法，它是对扩展方法 string[] getBetweenAll(string source, string startstring, string endstring);

的改进

最初这个扩展方法找到了两个字符串之间的所有子字符串，例如：

string source = "<1><2><3><4>";
source.getBetweenAll("<", ">");
//output: string[] {"1", "2", "3", "4"}

但是如果你在开头又出现了 <，它就会介于那个和整个字符串之间

string source = "<<1><2><3><4>";
source.getBetweenAll("<", ">");
//output: string[] {"<1><2><3><4"}

所以我重写了它以使其更准确，并从“>”向后搜索以找到第一次出现的“<”

现在我开始工作了，但这里的问题是它太慢了，因为搜索方法会跳回每个字符每次出现的整个字符串。你知道我怎样才能提高这个功能的速度吗？还是不可能？

这是目前为止的全部代码http://pastebin.com/JEZmyfSG 我在代码需要提高速度的地方添加了评论

public static List<int> IndexOfAll(this string main, string searchString)
{
    List<int> ret = new List<int>();
    int len = searchString.Length;
    int start = -len;
    while (true)
    {
        start = main.IndexOf(searchString, start + len);
        if (start == -1)
        {
            break;
        }
        else
        {
            ret.Add(start);
        }
    }
    return ret;
}

public static string[] getBetweenAll(this string main, string strstart, string strend, bool preserve = false)
{
    List<string> results = new List<string>();
    List<int> ends = main.IndexOfAll(strend);
    foreach (int end in ends)
    {
        int start = main.previousIndexOf(strstart, end);  //This is where it has to search the whole source string every time
        results.Add(main.Substring(start, end - start) + (preserve ? strend : string.Empty));
    }
    return results.ToArray();
}

//This is the slow function (depends on main.Length)
public static int previousIndexOf(this string main, string find, int offset)
{
    int wtf = main.Length ;
    int x = main.LastIndexOf(find, wtf);
    while (x > offset)
    {
        x = main.LastIndexOf(find, wtf);
        wtf -= 1;
    }
    return x;
}

我想还有另一种方法 PreviousIndexOf(string, int searchfrom);会提高速度.. 像 IndexOf() 除了向后和提供的起始偏移量

Answer 1

我写了一个简单的方法，比你的快四倍（但到目前为止没有 preserve 参数）：

public static string[] getBetweenAll2(this string main, string strstart, string strend, bool preserve = false)
{
    List<string> results = new List<string>();

    int lenStart = strstart.Length;

    int indexStart = 0;
    while (true)
    {
        indexStart = main.IndexOf(strstart, indexStart);
        if (indexStart < 0)
            break;

        int indexEnd = main.IndexOf(strend, indexStart);

        if (indexEnd < 0)
            break;

        results.Add(main.Substring(indexStart+ lenStart, indexEnd- indexStart- lenStart));
        indexStart = indexEnd;
    }
    return results.ToArray();
}

这会为您提供字符串 <1><2><3><4>

中的数字 1、2、3 和 4

这是你想要的吗？

[编辑]

查找嵌套的东西：

public static string[] getBetweenAll2(this string main, string strstart, string strend, bool preserve = false)
{
    List<string> results = new List<string>();

    int lenStart = strstart.Length; 
    int lenEnd = strend.Length;

    int index = 0;

    Stack<int> starPos = new Stack<int>();

    while (true)
    {
        int indexStart = main.IndexOf(strstart, index);
        int indexEnd = main.IndexOf(strend, index);

        if (indexStart != -1 && indexStart < indexEnd)
        {
            index = indexStart + lenStart;
            starPos.Push(index);
        }
        else if (indexEnd != -1 && (indexEnd < indexStart || indexStart == -1))
        {
            if (starPos.Count == 1)
            {
                int startOfInterst = starPos.Pop();
                results.Add(main.Substring(startOfInterst, indexEnd - startOfInterst));
            } else if(starPos.Count>0)
            {
                starPos.Pop();
            }
            index = indexEnd + lenEnd;
        }
        else
        {
            break;
        }
    }
    return results.ToArray();
}

Answer 2

使用堆栈来完成。一旦看到打开令牌，就开始向 stack 添加字符。一旦您看到关闭令牌 - 从您的堆栈中弹出所有内容，这将是您感兴趣的角色。

现在，一旦您实现了基本案例，就可以使用递归对其进行改进。如果您在关闭令牌之前看到另一个打开令牌 - 开始将字符收集到新堆栈，直到您看到关闭令牌。

这会给您带来 O(N) 的复杂度，因为您只需要传递所有内容一次。

如果您在打开令牌之前看到关闭令牌，您也需要处理这种情况，但是从您的问题中不清楚程序应该做什么。

Answer 3

我发现这符合我的要求，但方式不同！一个执行 PreviousIndexOf(string source, string token, int offset) 的函数对于其他东西仍然会非常感激！

public static List<string> GetBetweenAll(this string main, string start, string finish, bool preserve = false,  int index = 0)
{
    List<string> matches = new List<string>();
    Match gbMatch = new Regex(Regex.Escape(start) + "(.+?)" + Regex.Escape(finish)).Match(main, index);
    while (gbMatch.Success)
    {
        matches.Add((preserve ? start : string.Empty) + gbMatch.Groups[1].Value + (preserve ? finish : string.Empty));
        gbMatch = gbMatch.NextMatch();
    }
    return matches;
}
public static string[] getBetweenAllBackwards(this string main, string strstart, string strend, bool preserve = false)
{
    List<string> all = Reverse(main).GetBetweenAll(Reverse(strend), Reverse(strstart), preserve);
    for (int i = 0; i < all.Count; i++)
    {
        all[i] = Reverse(all[i]);
    }
    return all.ToArray();
}
public static string Reverse(string s)
{
    char[] charArray = s.ToCharArray();
    Array.Reverse(charArray);
    return new string(charArray);
}

Answer 4

作为原来的GetBetweenAll，我们可以使用正则表达式。为了仅匹配封闭字符串的最短 "inner" 出现，我们必须对起始字符串使用负前瞻，并对内容使用非贪婪量词。

public static string[] getBetweenAll(this string main, 
    string strstart, string strend, bool preserve = false)
{
    List<string> results = new List<string>();

    string regularExpressionString = string.Format("{0}(((?!{0}).)+?){1}", 
        Regex.Escape(strstart), Regex.Escape(strend));
    Regex regularExpression = new Regex(regularExpressionString, RegexOptions.IgnoreCase);

    var matches = regularExpression.Matches(main);

    foreach (Match match in matches)
    {
        if (preserve)
        {
            results.Add(match.Value);
        }
        else
        {
            results.Add(match.Groups[1].Value);
        }
    }

    return results.ToArray();
}

(C#) 提高自定义getBetweenAll的速度

(C#) Improving speed of custom getBetweenAll

c#

string

performance

indexof