5
\$\begingroup\$

I need to search through a string array to find every occurrence of "Parameters Table", and between each "Parameters Table" and the next, get another string from a specified index (that remains constant). I have been doing this like so:

public List<string> findlistOfNames(string[] arrayToLookForNames)
{
    List<string> listOfNames = new List<string>();

    const string separator = "Parameters Table"; //This is the string I am searching for

    var cuttedWords = arrayToLookForNames.SkipWhile(x => x != separator).Skip(1);

    while (cuttedWords.Any())
    {
        var variable = cuttedWords.TakeWhile(x => x != separator).ToArray();
        cuttedWords = cuttedWords.Skip(variable.Length + 1);
        listOfNames.Add(variable[2]); //This (always index 2) needs to be added to the list
    }
    return listOfNames;
}

This works but too slowly. Is there a better way to do this?

Here is a snippet of string[] arrayToLookForNames:

Parameters Table

0

41

Baro Pressure

hPa

AFD2

recorded

Parameters Table

0

42

Baro Setting

in-hg

\$\endgroup\$
4
  • \$\begingroup\$ Can you get around it by not searching for the whole string? \$\endgroup\$
    – OmniOwl
    Commented Jun 16, 2014 at 19:44
  • \$\begingroup\$ The only way to locate variable[2] (what I'm really looking for) is to first find "Parameters Table". I may be able to search just for "Parameters" if that's any better... \$\endgroup\$ Commented Jun 16, 2014 at 19:47
  • \$\begingroup\$ What's the desired result for sample input? \$\endgroup\$ Commented Jun 16, 2014 at 19:56
  • \$\begingroup\$ EDIT: listOfNames: Baro Pressure, Baro Setting \$\endgroup\$ Commented Jun 16, 2014 at 19:57

4 Answers 4

4
\$\begingroup\$

You are chaining methods deeper and deeper, so the longer the loop runs, the slower it gets.

You start out with cuttedWords as the expression arrayToLookForNames.SkipWhile(x => x != separator).Skip(1). Every time that you use cuttedWords it will evaluate that expression again, and every method that you chain into it will also be evaluated from there on.

After one iteration in the loop cuttedWords is (assuming that the record length is 7):

arrayToLookForNames.SkipWhile(x => x != separator).Skip(1).Skip(7)

After ten iterations it's:

arrayToLookForNames.SkipWhile(x => x != separator).Skip(1).Skip(7).Skip(7).Skip(7).Skip(7).Skip(7).Skip(7).Skip(7).Skip(7).Skip(7)

If you just keep track of how many items to skip instead of chaining expressions, it will get faster:

public List<string> findlistOfNames(string[] arrayToLookForNames)
{
    List<string> listOfNames = new List<string>();
    const string separator = "Parameters Table"; //This is the string I am searching for
    int skip = 0;
    while (arrayToLookForNames[skip] != separator) {
      skip++;
    }
    skip++;
    while (skip < arrayToLookForNames.Length)
    {
        string[] variable = arrayToLookForNames.Skip(skip).TakeWhile(x => x != separator).ToArray();
        skip += variable.Length + 1;
        listOfNames.Add(variable[2]); //This (always index 2) needs to be added to the list
    }
    return listOfNames;
}
\$\endgroup\$
1
  • \$\begingroup\$ This might be exactly what I'm looking for! I couldn't figure out why it was getting slower each iteration. \$\endgroup\$ Commented Jun 17, 2014 at 12:26
5
\$\begingroup\$

Perhaps the best way to solve this problem is to not have it in the first place. If you are in control of the code that produce this array of string, probably from a text file or a similar input, you could produce a tree of values instead right from the start. That way, instead of trying to find specific values through a text search, you could simply find the nodes in the tree that you need, for instance the "Parameters Table" node, and then dive into each parameters from there. This would look a little bit like this:

<root node>
    A
        B1
        C1
    A
        B2
        C2

If you are not in control of this code, then you have no other choice than to search through the entire list. Marcin Juraszek did propose a pretty good solution for this. Another way to do this search, which would also be a little bit faster would be this:

public static class EnumerableExtensions
{
    private class SearchResults
    {
        public List<String> Values = new List<string>();
        public int SkipCounter = -1;
    }

    public static List<string> FindAllSubItems(this IEnumerable<string> source, string keyword, int distance)
    {
        return source.Aggregate(
            new SearchResults(),
            (sr, v) =>
            {
                if (v.Equals(keyword))
                {
                    sr.SkipCounter = distance;
                }

                if (sr.SkipCounter == 0)
                {
                    sr.Values.Add(v);
                }

                --sr.SkipCounter;

                return sr;
            },
            sr => sr.Values
        );
    }
}

Which can be used like so:

var someList = new string[] {"A", "B1", "C1", "A", "B2", "C2" };
someList.FindAllSubItems("A", 1); // returns { "B1", "B2" }

The idea around this solution is to make sure that only one pass through the list will ever happen. This is an O(n) solution, as opposed to Juraszek's one which is an O(n + m) solution where n is the amount of inputs and m is the amount of matching keys. This solution also adds a safety around keys that does not have at least distance elements. For now, it simply skips it, but it is trivial to check for the value of SkipCounter before resting it if an exception needs to be thrown.

Once we find a match for our first parameter, we set a skip counter based on a distance parameter. We then proceed on decrementing the counter until it reaches zero. If the counter reaches zero, we have a found an item at distance items of the parameter so we save it. If it never reaches zero it means that we are looking for an item further than there is in the list. Providing a negative distance to this algorithm will never yield any results as it is a forward only algorithm. When the final value is returned, we simply trash the counter and only keep the values we saved in our temporary SearchResults object.

EDIT

As requested in the comment, the question author is wondering how to trigger updates to a progress bar in a solution like this. Since this code is using LINQ which works wonders with yield return, you can simply call it like this:

var items = someList
    .Select((x, i) => { UpdateMyProgressBarForIndex(i); return x; })
    .FindAllSubItems(...);

As you expect, the lambda specified in the select block will be called for each element in the list. But because of how LINQ methods are designed (using yield return), this will happen as the aggregate method process them. This is because the list of items that Select returns is built only as new items are requested by the bottom most foreach loop which runs inside the Aggregate method. Basically, you will see this behavior:

Initialize aggregate seed
foreach items in the list
Select's lambda for item (x)
Aggregate lambda for item(x)
when done
extract final values from the seed
\$\endgroup\$
5
  • \$\begingroup\$ My solution is not O(n log(n)). Second pass goes only through m indexes (m - number of separators found) and uses indexer access on array, which is O(1). It makes the solution O(n+m). \$\endgroup\$ Commented Jun 16, 2014 at 20:57
  • \$\begingroup\$ True, I did corrected the post to match accordingly. \$\endgroup\$ Commented Jun 16, 2014 at 21:36
  • \$\begingroup\$ @EtienneMaheu Thank you, this looks great. I should have expanded on my question, though. See, within the while loop (see my OP) I was calling methods, updating a progress bar, etc (I should have included this). Basically, I need the functionality of being able to "do" things once each section (strings between "Parameters Table") is found. Is there any way to maintain this functionality using your solution? \$\endgroup\$ Commented Jun 17, 2014 at 12:22
  • 1
    \$\begingroup\$ I've added details in the solution about how to integrate with it. \$\endgroup\$ Commented Jun 19, 2014 at 14:21
  • \$\begingroup\$ @EtienneMaheu Just noticed this now but it will still be useful, thanks! \$\endgroup\$ Commented Jun 25, 2014 at 15:16
2
\$\begingroup\$

A lot of these solutions seems overly complex. Here is one way of doing it:

public static List<string> FindNames(string[] input, string key, int toSkip)
{
    var names = new List<string>();
    for (var i = 0; i < input.Length; i++)
    {
        if (input[i] == key)
        {
            i += toSkip;
            names.Add(input[i]);
        }
    }

    return names;
}

However, you can generalise your data structures. I think the key insight is that you're not searching through an array, you're searching through a sequence.

The IEnumerator<T> interface then makes it easy to express the solution.

public static IEnumerable<string> FindNames(IEnumerable<string> input, string key, int toSkip)
{
    using (var enumerator = input.GetEnumerator())
    {
        while (enumerator.MoveNext())
        {
            if (enumerator.Current != key)
            {
                continue;
            }

            for (var i = 0; i < toSkip; i++)
            {
                enumerator.MoveNext();
            }

            yield return enumerator.Current;
        }
    }
}

One benefit of this solution is that you don't need all the strings in memory at once. For instance, you could use this method on the contents of a file, without the entire file in memory:

foreach (var name in FindNames(File.ReadLines(fileName), "Parameters Table", 3))
{
    ProcessName(name);
}
\$\endgroup\$
0
\$\begingroup\$
public static List<string> findlistOfNames(string[] arrayToLookForNames)
{
    var indexes = arrayToLookForNames.Select((x, i) => new { x, i })
                                     .Where(x => x.x == "Parameters Table")
                                     .Select(x => x.i)
                                     .ToArray();

    return indexes.Select(i => arrayToLookForNames[i + 3]).ToList();
}

Description

First LINQ query search through the source collection and gets indexes of your separator ("Parameters Table"). When it's done, the second query selects items under separatorIndex + 3 index.

\$\endgroup\$
7
  • \$\begingroup\$ I will try this out, thanks. Within my while loop, I also had a counter variable that I would send to update a progress bar on a UI. Is there an easy way to maintain that functionality with your solution? \$\endgroup\$ Commented Jun 16, 2014 at 20:14
  • 1
    \$\begingroup\$ If I could ask a BIG favor of you....I have to use similar code elsewhere in my program, would you mind describing what your solution does/how it works? \$\endgroup\$ Commented Jun 16, 2014 at 20:24
  • \$\begingroup\$ Why are you doing this in two passes? Take a look at my Aggregate solution which builds from your idea and uses only one pass to do its job. \$\endgroup\$ Commented Jun 16, 2014 at 20:54
  • \$\begingroup\$ @EtienneMaheu Because it's much more readable. And because second pass uses indexer access, which is O(1), performance will be pretty the same. \$\endgroup\$ Commented Jun 16, 2014 at 20:56
  • \$\begingroup\$ @user2340818 I've added some explanation. Hope it's enough, because the overall idea is really simple, I don't see any point in further explanations. \$\endgroup\$ Commented Jun 16, 2014 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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