1
\$\begingroup\$

Follow-Up question

.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. Essentially it is the char equivalent of my naive definition.

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) {
    int? curAns = null;
    foreach (var target in targets) {
        var posAns = s.IndexOf(target, 0, curAns.HasValue ? curAns.Value + target.Length : s.Length);

        if (posAns >= 0 && (!curAns.HasValue || posAns < curAns)) {
            curAns = posAns;
            if (curAns == 0) // once you're at the beginning, can't be any less
                break;
        }
    }

    return curAns ?? -1;
}

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($"IndexOfAny2 should be 8: {"foo bar baz".IndexOfAny2("barz", "baz")}");
Console.WriteLine($"IndexOfAny2 should be 0: {"aabbccddeeffgghh".IndexOfAny2("bbb", "hh", "aa")}");

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\$
  • 3
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Simon Forsberg Jul 30 at 19:17
5
\$\begingroup\$

Review

  • Don't use abbreviated variable names s, curAns and posAns; use self describing names: value, index and targetIndex instead.
  • The nullable int could be replaced with -1. This reads cleaner and allows you to bypass the final ?? operator in curAns ?? -1.
  • You can optimize the count curAns.Value + target.Length with adding -1 because we don't care about finding another match on the currently best found index.
  • You should exit early if no targets are specified

Refactored

public static int IndexOfAny2(this string value, params string[] targets)
{
    var index = -1;
    if (targets == null || targets.Length == 0) return index;

    foreach (var target in targets)
    {
        var targetIndex = value.IndexOf(target, 0, 
            index > -1 ? index + target.Length - 1 : value.Length);

        if (targetIndex >= 0 && (index == -1 || targetIndex < index))
        {
            index = targetIndex;
            if (index == 0)
            {
                break;
            }
        }
    }

    return index;
}
\$\endgroup\$
  • \$\begingroup\$ Nice, but not really helpful to my question. BTW, I don't find value any more compelling than s. Perhaps its leaks from my database knowledge, but I think using -1 to mean index has no value yet is bad practice - don't use magic values when coding. If I were designing it today, IndexOf would return an int? instead. \$\endgroup\$ – NetMage Jul 29 at 21:24
  • \$\begingroup\$ Why avoid the most well known magic number (index = -1) to use it anyway at return time? \$\endgroup\$ – dfhwze Jul 30 at 16:00
  • \$\begingroup\$ Just a matter of style or preference I guess. \$\endgroup\$ – NetMage Jul 30 at 16:11
  • \$\begingroup\$ I improved my IndexOfAny2 based on your comments and added at bottom of question. Thanks for the improvements, though still not getting at the root of my question. \$\endgroup\$ – NetMage Jul 30 at 18:53
1
\$\begingroup\$
  • "abc".IndexOfAny2("c", "abc") fails with an ArgumentOutOfRangeException, because IndexOf requires startIndex + count to not exceed the length of the string.
  • For a tiny improvement, make curAns a normal integer and initialize it with s.Length. After the necessary changes, you'll end up with fewer checks inside the foreach loop.

Most time is spent in string.IndexOf however, so for more substantial improvements you'll want to investigate more optimized (and more complex) algorithms such as Rabin-Karp, Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick, etc.

\$\endgroup\$
  • \$\begingroup\$ I would assume based on the reference source that String.IndexOf being a C intrinsic is either using a direct x64 instruction or is implementing a high speed optimized algorithm already (it calls the kernel32 FindNLSString function). However, this did lead me to add StringComparison.Ordinal to my IndexOf call, which added some speed. \$\endgroup\$ – NetMage Jul 30 at 15:57
  • \$\begingroup\$ Added a bug fix version of the bottom of my question, thanks for the bug report. I like your s.Length suggestion as the code looks nice but in practice it runs fractionally slower even with fewer tests. \$\endgroup\$ – NetMage Jul 30 at 19:01
  • \$\begingroup\$ @NetMage: As far as I could find, IndexOf is doing a 'naive' search. Good point about StringComparison.Ordinal, but it depends on what behavior you need. For example, a culture-specific comparison can match "é" against "é" (which is "e\u0301" - an 'e' followed by a combining accent), an ordinal comparison won't. I'd make it a parameter instead of hard-coding it. \$\endgroup\$ – Pieter Witvoet Jul 30 at 19:37
  • \$\begingroup\$ I did so, but of course, I can't put the improved code anywhere in a way I would like. I may ask another question with working code... BTW, I am not sure that the .Net Core usage matches the .Net Framework call to the kernel function. \$\endgroup\$ – NetMage Jul 30 at 19:46
  • \$\begingroup\$ I'd assume that if FindNLSString was using a better algorithm, they would've ported it to .Net Core, given how much they're focusing on performance, but without access to the actual source there's no way to be sure. \$\endgroup\$ – Pieter Witvoet Jul 30 at 19:58

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.