0
\$\begingroup\$

I have a dictionary iteration that uses a for-each comparisment in order to find multiple equalities in a string (fileline).

    //
    //  reads fileLine
    //
    public void readLine(string fileline)
    {
        //// turn fileline into desired format
        fileline = fileline.ToLower();
        fileline = fileline.Trim(StaticData.secondLvlSeperation);

        lineElements = fileline.Split(firstLvlSeperation, StringSplitOptions.None);

        if (lineElements.Length > 2)
        {
            alert = createAlert(systemname, diagnoseClass);
            //  == matched sequences when iterating through dictionary on each line new == //
            WordReader.fileLine = fileline;
            WordReader.matched = new HashSet<string>();
            WordReader.iterationCounter = 0;
            WordReader.lineLength = lineElements.Length;
        }
        else
        {
            return;
        }

        foreach (string lineElement in lineElements)
        {
            string trimmed = lineElement.Trim(); 
            WordReader.dictionaryIteration(trimmed);
        }

        checkAndAddAlert(alert);
        GC.Collect();
    }

dictionaryIteration below works as followed:

  • There is a dictionary StaticData.keywords<string, string> coming from a file that is loaded at start of Form.

  • The dictionary key is a string that holds a keyword which functions as an alert which could (or could not) be found in a file.

  • The dictionary value is a string that holds a value which is given to the keyword: ('critical', 'error' or 'informatic')

<k,v> example could be:

"mengbed1 connected" - 'informatic' (full sequence match in fileline)

or

"failed,insert,msstraat4" - 'error' (wildcard, multiple instances required in fileline)

Keywords in table

  1. Iterator 'hits' same number as fileline.length
  2. Possibly the match-sequence formed is equal to one of the keys, key-match is found. Key is bound to alert
  3. IF NO matched are found, we are possibly dealing with a wildcard-key
  4. Fileline must contain -ALL- desired matched words coming from wildcard key in order to connect wildcard key to alert
  5. No match of either sides means unknown alert

.

using System.Collections.Generic;
using System.Linq;

namespace Logdog.Processors.Readers
{
    class WordReader
    {
        public static HashSet<string> matched;
        public static string fileLine;
        public static int lineLength;
        public static int iterationCounter = 0;


        //
        //  searches for match sequences in dictionary 
        //
        public static void dictionaryIteration(string wordToCheck)
        {
            iterationCounter++;

            //// match-forming in order to maintain right match sequence after 'hitting' filelength
            foreach (KeyValuePair<string, string> entry in StaticData.keywords.Where(ek => !ek.Key.Contains(',')))
            {
                string keyword = entry.Key;

                string[] keywords = keyword.Split();

                foreach (string keywordpart in keyword.Split())
                {
                    if (keywordpart.Equals(wordToCheck))
                    {
                        matched.Add(keywordpart);
                    }

                }
            }

            //// at the end of the line
            if (iterationCounter.Equals(lineLength))
            {
                compareMatchedSeq();
            } 

            //// when no equality found at all
            if (Linereader.alert.alertType == null)
            {
                Linereader.alert.alertType = "Unknown";
                Linereader.alert.alertKeyword = "Undefined";
            }

        }

        //
        //  compares the match sequence with dictionary elements
        //
        private static void compareMatchedSeq()
        {
            string matchedSeqRegular = string.Join(" ", matched);

            // first check on direct match equality
            KeyValuePair<string, string> matchedEntry = StaticData.keywords.FirstOrDefault(k => k.Key.Equals(matchedSeqRegular));

            if (matchedEntry.Key != null)
            {
                Linereader.alert.alertKeyword = matchedEntry.Key;
                Linereader.alert.alertType = matchedEntry.Value;
            }
            // if none found, this would mean this sequence is a wildcard type of key 
            else
            {
                int matchCounter = 0;

                foreach (KeyValuePair<string, string> wildCardEntry in StaticData.keywords.Where(ek => ek.Key.Contains(',')))
                {
                    string[] keywordParts = wildCardEntry.Key.Split(',');

                    // check if all required matches are qualified
                    for (int i = 0; i < keywordParts.Length; i++)
                    {
                        if (fileLine.Contains(keywordParts[i]))
                        {
                            matchCounter++;
                        }
                    }

                    // when all matched 
                    if (matchCounter.Equals(keywordParts.Length))
                    {
                        Linereader.alert.alertKeyword = wildCardEntry.Key;
                        Linereader.alert.alertType = wildCardEntry.Value;
                        break;
                    }
                }
            }
        }
    }
}

I have the idea that I may make too many for-each loops, (inc. the LINQ usage as well) but when trying other ways around the methods no longer work as desired so this is why I am asking this community if I indeed do have too many loops.

\$\endgroup\$
  • 1
    \$\begingroup\$ How are fileLine and StaticData.keywords declared? Can you show some sample data? It is difficult to understand what you are doing. \$\endgroup\$ – Olivier Jacot-Descombes Nov 15 '17 at 14:52
  • \$\begingroup\$ Happens in other class, I can add this \$\endgroup\$ – MwBakker Nov 15 '17 at 14:56
  • 1
    \$\begingroup\$ The point is that the data structure used for those determine if you can use fast lookups or need slow loops. With the right collection types, you can eliminate loops. So, it is essential to know how they are declared. \$\endgroup\$ – Olivier Jacot-Descombes Nov 15 '17 at 15:00
  • \$\begingroup\$ The dictionary StaticData.keywords comes from a file at formload(); \$\endgroup\$ – MwBakker Nov 15 '17 at 15:08
  • 1
    \$\begingroup\$ Please post the complete class, not just parts of it. There's lot more wrong with it the this, e.g. everything being static. \$\endgroup\$ – t3chb0t Nov 15 '17 at 16:25
1
\$\begingroup\$

You are using the dictionary StaticData.keywords in a wrong way. I assume (since we still not have your declaration) that it is declared as

public static class StaticData
{
    public static Dictionary<string, string> keywords = new Dictionary<string, string>();
}

The dictionary is implemented as hash table. Hash tables have a near constant lookup time. I.e., it makes no difference whether it contains 20 entries or 20,000 entries. The lookup time is the same. The Big O notation is often used to describe this behavior. For a constant lookup time, this is O(1).

If, however, you loop through the dictionary, you have a linear access time, denoted as O(n). I.e., It takes 1000 times more time to lookup 20,000 than 20 entries.

Therefore, try to eliminate dictionary iterations. This not easy, as you have multiple key parts per entry and probably the same key part can occur in several entries.

Therefore, you need a multi-dictionary that can contain several entries per key (I'll be using the key parts, i.e. the keywords, as separate keys in the dictionary). There is no such collection in the .NET library; however, you can easily create one by combining a Dictionary<K,V> with a List<T>

public class MultiDictionary<TKey, TValue> : Dictionary<TKey, List<TValue>>
{
    public void Add(TKey key, TValue value)
    {
        if (TryGetValue(key, out List<TValue> valueList)) {
            valueList.Add(value);
        } else {
            Add(key, new List<TValue> { value });
        }
    }
}

You also need a class that can store alert entries appropriately:

/// <summary>Initializes a new instance of the AlertEntry class.</summary>
/// <param name="keywordsString">The keywords string, e.g. "failed,insert,msstraat4".</param>
/// <param name="alertType">Type of the alert. e.g. "informatic".</param>
public class AlertEntry
{
    public AlertEntry(string keywordsString, string alertType)
    {
        Keywords = keywordsString.ToLower().Split(',');
        AlertType = alertType;
    }

    public string[] Keywords { get; } // This is storing the key parts of your key.
    public string AlertType { get; }
}

Now, change the type of the keywords dictionary to

public static class StaticData
{
    public static MultiDictionary<string, AlertEntry> AlertEntries { get; } =
        new MultiDictionary<string, AlertEntry>();
}

Add alert entries like this (it's the same for full match keys or wildcard keys):

var alertEntry = new AlertEntry("failed,insert,msstraat4", "error");
foreach (string key in alertEntry.Keywords) {
    StaticData.AlertEntries.Add(key, alertEntry);
}

And finally, find matching sequence like this

private static void CompareMatchedSeq()
{
    string matchedSeqRegular = String.Join(" ", matched);

    // Fast lookup, no iteration (not even hidden inside FirstOrDefault)!
    if (StaticData.AlertEntries.TryGetValue(matchedSeqRegular,
                                            out List<AlertEntry> matchedEntries)) {
        AlertEntry matchedEntry = matchedEntries[0]; // Assumes matched entries
                                                     // only contain one entry.
        Linereader.alert.alertKeyword = matchedEntry.Keywords[0];
        Linereader.alert.alertType = matchedEntry.AlertType;
    } else {
        // If none found, this would mean this sequence is a wildcard type key.
        string[] fileLineKeys = ExtractKeywordPartsFromFileLine(); // TODO: Implement it!
        // Lookup by first fileLine key (could take any other). Again no iteration!
        if (StaticData.AlertEntries.TryGetValue(fileLineKeys[0],
                                                out List<AlertEntry> entries)) {
            // Find best matching entry, i.e. the one with the most keys matching.
            foreach (var wildCardEntry in entries.OrderByDescending(e => e.Keywords.Length)) {
                if (wildCardEntry.Keywords.All(k => fileLineKeys.Contains(k))) {
                    // When all matched.
                    Linereader.alert.alertKeyword = String.Join(",", wildCardEntry.Keywords);
                    Linereader.alert.alertType = wildCardEntry.AlertType;
                    break;
                }
            }
        }
    }
}

There are other issues. I will not address all of them. One is the naming. There are Naming Guidelines for C# and other .NET languages. And remove this GC.Collect();! The garabge collector does the things right by itself.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for this answer and I really appreciate the effort. However I do not understand what you mean with "multiple keys per entry" this is not the case. There is one entry containing one key, with only one value. No more is possible. I will add an image to my question \$\endgroup\$ – MwBakker Nov 15 '17 at 18:21
  • \$\begingroup\$ I mean in "failed,insert,msstraat4" - 'error' there are 3 keywords ("failed", "insert" and "msstraat4") belonging to one alert type ("error"), which together form one alert entry. In Dictionary<K,V> terms they are keys and "error" is the value. \$\endgroup\$ – Olivier Jacot-Descombes Nov 15 '17 at 18:24
  • \$\begingroup\$ In my implementation I am using the 3 key parts as 3 different keys in the dictionary. Therfore your key is converted into 3 dictionary keys to enable fast lookup and to avoid looping through the dictionary entries. \$\endgroup\$ – Olivier Jacot-Descombes Nov 15 '17 at 18:36
  • \$\begingroup\$ What other issues than naming? I know about the naming, I do this on purpose since I am the only one working on this, and it was a BlueJ thing in my college (where it started all) \$\endgroup\$ – MwBakker Nov 15 '17 at 18:48
  • 1
    \$\begingroup\$ @OlivierJacot-Descombes What is the reason for creating a MultiDictionary class with it's own Add method? Why not just use Dictionary<TKey, TValue> ? \$\endgroup\$ – Brad M Nov 15 '17 at 20:33

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.