3
\$\begingroup\$

This is a follow-up to this question with bug fixes, question and code improvements from @dfhwze, @PieterWitvoet, @HenrikHansen, @t3chb0t. I am still hoping for an improved approach or algorithm rather than micro-optimizations to the code.

.Net provides String.IndexOfAny(string, char[]) but not String.IndexOfAny(string, string[]).

The existing built-in String.IndexOfAny takes an array of char and returns the lowest position of any one char from the array in a passed in string or -1 if none are found.

My extension takes a string to search s and an array of strings to find targets and returns the lowest position found of any member of targets in s or -1 if none are found.

A naive implementation (using LINQ) isn't particularly efficient:

public static int IndexOfAny1(this string s, params string[] targets) =>
    targets.Select(t => s.IndexOf(t)).Where(p => p >= 0).DefaultIfEmpty(-1).Min();

My improved implementation tracks the current candidate position and restricts future searches to be before that candidate position:

public static int IndexOfAny2(this string s, params string[] targets) => s.IndexOfAny3(StringComparison.Ordinal, targets);
public static int IndexOfAny2(this string s, StringComparison sc, params string[] targets) {
    if (targets == null || targets.Length == 0)
        return -1;

    int index = s.IndexOf(targets[0], sc);
    var sLen = s.Length;

    for (int j1 = 1; j1 < targets.Length; ++j1) {
        var target = targets[j1];
        var targetIndex = s.IndexOf(target, 0, index >= 0 ? Math.Min(sLen, index + target.Length) : sLen, sc);

        if (targetIndex >= 0 && (index == -1 || targetIndex < index)) {
            index = targetIndex;
            if (index == 0) // once you're at the beginning, can't be any less
                break;
        }
    }

    return index;
}

This runs up to two times faster.

Sample code to test the two methods:

Console.WriteLine($"IndexOfAny1 should be 8: {"foo bar baz".IndexOfAny1("barz", "baz")}");
Console.WriteLine($"IndexOfAny1 should be 0: {"aabbccddeeffgghh".IndexOfAny1("bbb", "hh", "aa")}");
Console.WriteLine($"IndexOfAny1 should be 0: {"abc".IndexOfAny1("c", "abc")}");

Console.WriteLine($"IndexOfAny2 should be 8: {"foo bar baz".IndexOfAny2("barz", "baz")}");
Console.WriteLine($"IndexOfAny2 should be 0: {"aabbccddeeffgghh".IndexOfAny2("bbb", "hh", "aa")}");
Console.WriteLine($"IndexOfAny2 should be 0: {"abc".IndexOfAny2("c", "abc")}");

Is there a better algorithm or another way to make this faster?

PS Test harness for testing random possibilities:

var r = new Random();

var sb = new StringBuilder();
for (int j1 = 0; j1 < r.Next(80,160); ++j1)
    sb.Append((char)('0'+r.Next(0, 26+52)));
var s = sb.ToString();

var listTargets = new List<string>();
for (int j1 = 0; j1 < r.Next(5, 10); ++j1)
    if (r.NextDouble() < 0.8) {
        var tLen = r.Next(4, Math.Min(s.Length - 4, 10));
        var beginPos = r.Next(0, s.Length - tLen);
        listTargets.Add(s.Substring(beginPos, tLen));
    }
    else {
        sb.Clear();
        for (int j2 = 0; j2 < r.Next(5, 10); ++j2)
            sb.Append((char)('0'+r.Next(0, 26+52)));
        listTargets.Add(sb.ToString());
    }

var targets = listTargets.ToArray();
if (s.IndexOfAny1(targets) != s.IndexOfAny2(targets))
    Console.WriteLine($"Fail on {s} containing {String.Join(",", targets)}");
\$\endgroup\$
  • 2
    \$\begingroup\$ As mentioned before, there are certainly better algorithms, but it also depends on the intended use-case. Many of the more advanced algorithms require some kind of preprocessing, which makes them slower for small inputs, but faster for larger inputs, more targets, repeated searches, and so on. What exactly are your requirements? \$\endgroup\$ – Pieter Witvoet Jul 31 at 9:12
  • \$\begingroup\$ @PieterWitvoet I would say short text, small list of targets would be typical use case: think processing lines of text from a file. Note my test harness generates 80 - 160 character strings and 5 - 10 targets of upto 10 characters, 80% found. \$\endgroup\$ – NetMage Jul 31 at 20:46
3
\$\begingroup\$

It seems that you've managed to fix the algorithm, so it does what it's supposed to do. But the concept is the same and performance isn't improved.

Still you could use some more descriptive names, and i instead of j1 (why 1?).

You could use foreach (string target in targets) { ... } instead of for (int j1;...) because you don't use the index to anything and the performance for an array is about the same for the two for-concepts.


You ask for other algorithm types that improves performance.

One concept for the algorithm - that seems to improve the performance significantly - could be the following:

public static int IndexOfAny(this string text, params string[] targets)
{
  if (string.IsNullOrEmpty(text)) return -1;
  if (targets == null || targets.Length == 0) return -1;

  for (int i = 0; i < text.Length; i++)
  {
    foreach (string target in targets)
    {
      if (i + target.Length <= text.Length && target == text.Substring(i, target.Length))
        return i;
    }
  }

  return -1;
}

Another that can improve performance even more is the following written in pseudo code - leaving it as a challenge for you to implement it in C#:

IndexOfAny text targets:
    for i = 0 to len(text)-1:
        skip = len(text)
        foreach target in targets:
            target_can_skip = 0
            for k = 0 to len(target)-1:
                if target[k] <> text[i+k]:
                    target_can_skip = count how many chars that can be skipped in text before target can be a candidate again
                    break
            if k == len(target):
                return i


            skip = min(skip, target_can_skip)

        if skip > 0: 
            i = i + skip - 1

    return -1 // No match found

Besides that you may find inspiration here


Update according to VisualMelons comments:

The above implemented with string.IndexOf():

public static int IndexOfAny1(this string text, params string[] targets)
{
  if (string.IsNullOrEmpty(text)) return -1;
  if (targets == null || targets.Length == 0) return -1;

  for (int i = 0; i < text.Length; i++)
  {
    foreach (string target in targets)
    {
      if (i + target.Length <= text.Length && text.IndexOf(target, i, target.Length) == i)
        return i;
    }
  }

  return -1;
}

Notice that the count parameter must be at minimum the length of target or else it will not be found.

Test case:

  Stopwatch watch = Stopwatch.StartNew();
  IndexOfAnyDelegate[] funcs = new IndexOfAnyDelegate[]
  {
    Extensions.IndexOfAny,
    //Extensions.IndexOfAny1,
  };

    int sum = 0;

    for (int i = 0; i < 10000; i++)
    {
      foreach (var func in funcs)
      {
        sum += func("foo bar baz", "foo", "barz", "baz", " ");
        sum += func("aabbccddeeffgghh", "bbb", "hh", "aaa", "fg");
        sum += func("abcabc", "c", "abc");
        sum += func("abcabc", "x", "wer");
        sum += func("adfaææwjerqijaæsdklfjaeoirweqærqkljadfaewrwexwer", "xxxxx", "yyyyy", "zzzzz", "Aaaaaa", "x", "wer");

        //Console.WriteLine($"IndexOfAny should be 8: {func("foo bar baz", "barz", "baz", " ", "foo")}");
        //Console.WriteLine($"IndexOfAny should be 0: {func("aabbccddeeffgghh", "bbb", "hh", "aaa", "fg")}");
        //Console.WriteLine($"IndexOfAny should be 0: {func("abcabc", "c", "abc")}");
        //Console.WriteLine($"IndexOfAny should be 0: {func("abcabc", "x", "wer")}");
        //Console.WriteLine(func("adfaææwjerqijaæsdklfjaeoirweqærqkljadfaewrwexwer", "xxxxx", "yyyyy", "zzzzz", "Aaaaaa", "x", "wer"));
        //Console.WriteLine();
      }
    }
    watch.Stop();
    Console.WriteLine(sum);
    Console.WriteLine(watch.ElapsedMilliseconds);

You'll have to comment in/out as needed.


Update 2

The performance of the above pseudo code decreases (obviously) when the number of targets increases. So my analysis wasn't quite good enough. To optimize on that problem the below variant maintains an array of the next valid index per target, which minimize the number of targets that should be examined per char in the text string:

public static int IndexOfAny(this string text, params string[] targets)
{
  if (string.IsNullOrEmpty(text)) return -1;
  if (targets == null || targets.Length == 0) return -1;

  // Holds the next valid index in text per parget.
  int[] targetNextIndex = new int[targets.Length];

  for (int i = 0; i < text.Length; i++)
  {
    for (int j = 0; j < targets.Length; j++)
    {
      // If the targets next index isn't i then continue to next target
      if (targetNextIndex[j] > i)
        continue;

      string target = targets[j];
      int k = 0;

      for (; k < target.Length && i + k < text.Length; k++)
      {
        if (target[k] != text[i + k])
        {
          int nextIndex = i + 1;
          // Tries to find the next index in text where the char equals the first char in target.
          while (nextIndex < text.Length && target[0] != text[nextIndex])
          {
            nextIndex++;
          }
          // The next valid index for the target is found, so save it
          targetNextIndex[j] = nextIndex;
          break;
        }
      }

      if (k == target.Length)
      {
        return i;
      }
    }
  }

  return -1;
}
\$\endgroup\$
  • \$\begingroup\$ That middle algorithm is of course going to perform much better in some cases, but it needn't allocate anything: you can use text.IndexOf(target,i,1) == i (or something like that) instead of target == text.Substring(i, target.Length) \$\endgroup\$ – VisualMelon Jul 31 at 10:11
  • \$\begingroup\$ @VisualMelon: normally you are right, when writing something, but in this case - according to my test cases - using IndexOf() as you suggest instead of Substring() is about 10x slower. \$\endgroup\$ – Henrik Hansen Jul 31 at 10:54
  • 1
    \$\begingroup\$ Wow; glad you measured it then! Could you provide your test code in a gist or something (so I don't have to write my own), because I'm going to have to investigate why (makes no sense to me). \$\endgroup\$ – VisualMelon Jul 31 at 10:55
  • \$\begingroup\$ @VisualMelon: You are right: using StringComparison.Ordinal definitely improves performance. \$\endgroup\$ – Henrik Hansen Jul 31 at 11:10
  • 2
    \$\begingroup\$ I can't seem to find documentation for the exact behaviour of ==, but it does appear to be ordinal (ends up calling EqualsHelper here), so it probably should be Ordinal for comparison. With that change, it runs your sample on my machine in ~60ms rather than ~100ms for the SubString version (and indeed 1s for the non-ordinal version!). \$\endgroup\$ – VisualMelon Jul 31 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.