5
\$\begingroup\$

I implemented a search function like this:

private static void GetResults(ref ObservableCollection<string> resultTitles, ref string[] query, ref ObservableCollection<int> weight)
{
    int position = -1;

    foreach (string[] r in SearchKeys.Keys)
    {
        position++;
        foreach (string s in query)
        {
            int m = r.Length/2;
            int min = r[m][0] < s[0] ? m : 0;
            int max = r[m][0] <= s[0] ? r.Length : m+1;

            for (int i = min; i < max; i++)
            {
                weight.Add(0);

                if (r[i] == s)
                {
                    if (weight[position] == 0)
                    {
                        resultTitles.Add(r[0]);
                    }
                    weight[position]++;

                }   // end if
            }   // end foreach(s)
        }   // end foreach(t)
    }   // end foreach(r)
}

In the main program, the use inputs a query, the program splits the query at the spaces, and passes the query and two empty ObservableCollections to this function.

SearchKeys.Keys is implemented like this:

public static string[][] Keys = { Array1, Array2, Array3 };

The arrays are implemented like this:

private static string[] Array1 = { "Title", "val1", "val2", "val3", "val4", "val5", "val6" };

As always, all comments are welcome; particularly, I am interested in which ways could this code's performance be improved. The data in SearchKeys is sorted, of course.

This is a previous version of my code, which may also be of interest. This version should run about twice as slow as the above, according to my estimates:

private void getResults(ref ObservableCollection<string> tmp, ref string[] query, ref ObservableCollection<int> weight)
{
    int position = -1;

    foreach (string[] r in SearchKeys.Keys)
    {
        position++;
        foreach (string t in r)
        {
            weight.Add(0);

            foreach (string s in query)
            {
                if (t == s)
                {
                    if (weight[position] == 0)
                    {
                        tmp.Add(r[0]);
                    }
                    weight[position]++;

                }   // end if
            }   // end foreach(s)
        }   // end foreach(t)
    }   // end foreach(r)
}

This is how I call this function:

static void Main(string[] args)
{
    ObservableCollection<int> weight = new ObservableCollection<int>();
    ObservableCollection<string> resultTitles = new ObservableCollection<string>();
    string[] query = Console.ReadLine().Split(' ');

    GetResults(ref resultTitles, ref query, ref weight);
    StableSort(ref resultTitles, ref weight);

    foreach (string s in resultTitles)
        Console.WriteLine(resultTitles.IndexOf(s)+": "+s);
}

This is StableSort (see Stable Sort in C#):

static void StableSort(ref ObservableCollection<string> values, ref ObservableCollection<int> weights)
{
    while(weights.Contains(0))
    {
        weights.Remove(0);
    }

    if (values == null) { throw new ArgumentNullException("values"); }
    if (weights == null) { throw new ArgumentNullException("weights"); }

    if (values.Count != weights.Count) { throw new ArgumentOutOfRangeException("collections count not equal", (Exception)null); }

    ObservableCollection<string> localValues = new ObservableCollection<string>();
    ObservableCollection<int> localWeights = new ObservableCollection<int>();

    int index = -1;
    var weightsWithIndex = weights.Select(p => new { Value = p, Index = ++index }).OrderByDescending(p => p.Value);

    foreach (var w in weightsWithIndex)
    {
        localWeights.Add(w.Value);
        localValues.Add(values[w.Index]);
    }

    values = localValues;
    weights = localWeights;
}
\$\endgroup\$

3 Answers 3

4
\$\begingroup\$

Focusing on

foreach (string[] r in SearchKeys.Keys)
{
    position++;
    foreach (string s in query)
    {
        int m = r.Length/2;
        int min = r[m][0] < s[0] ? m : 0;
        int max = r[m][0] <= s[0] ? r.Length : m+1;  

r.Length won't change by iterating over query nor does r[m][0]

foreach (string[] r in SearchKeys.Keys)
{
    position++;
    int length = r.Length;
    int middleOfArray = length / 2;
    Char firstKeyItemCharacter = r[middleOfArray][0];
    foreach (string s in query)
    {
        int min = firstKeyItemCharacter < s[0] ? middleOfArray : 0;
        int max = firstKeyItemCharacter <= s[0] ? length : middleOfArray + 1;

instead of adding to weight for each iteration of the most inner loop, add it at the most outer loop.

Because you remove all entries of weight where the entry == 0 in the StableSort() method, we can do this here using the Where() method. Btw. by first removing the "0" entries the check for weights == null will be senseless.

private static void GetResults(ref ObservableCollection<string> resultTitles, ref string[] query, ref ObservableCollection<int> weight)
{
    int position = -1;
    IList<int> currentWeights = new List<int>();
    foreach (string[] r in SearchKeys.Keys)
    {
        currentWeights.Add(0);
        position++;
        int length = r.Length;
        int middleOfArray = length / 2;
        Char firstKeyItemCharacter = r[middleOfArray][0];
        foreach (string s in query)
        {
            int min = firstKeyItemCharacter < s[0] ? middleOfArray : 0;
            int max = firstKeyItemCharacter <= s[0] ? length : middleOfArray + 1;

            for (int i = min; i < max; i++)
            {
                if (r[i] == s)
                {
                    if (currentWeights[position] == 0)
                    {
                        resultTitles.Add(r[0]);
                    }
                    currentWeights[position]++;
                }
            }
        }
    }
    weight = new ObservableCollection<int>(currentWeights.Where(x => x > 0));
}
\$\endgroup\$
6
\$\begingroup\$

You're doing a good job at indenting your code, well done! But then why would you need these?

            }   // end if
        }   // end foreach(s)
    }   // end foreach(t)
}   // end foreach(r)

Now, the signature:

private static void GetResults(ref ObservableCollection<string> resultTitles, ref string[] query, ref ObservableCollection<int> weight)

"void GetResults"... "void Get". And then the two ref parameters...

and passes the query and two empty ObservableCollections to this function.

query doesn't need to be passed by reference, doesn't need to be specifically an array, and if I had to use ref parameters I'd put it first in the signature:

private static void GetResults(IEnumerable<string> query, ref ObservableCollection<string> resultTitles, ref ObservableCollection<int> weight)

Now, the method doesn't care that our collections are observable - it only needs to know it's some kind of ICollection<T>... but there's a smell there nonetheless: passing ref parameters instead of returning a collection, doesn't feel quite natural.

I believe, because it's a private method, that whatever you're passing in as weight could be promoted to a private field if it's used anywhere else in the class, or moved to the GetResults scope where it's used.

\$\endgroup\$
0
6
\$\begingroup\$

I hate to pick on names, but I really dislike single letter variable names.

foreach (string[] r in SearchKeys.Keys)

How about string[] keys instead? Maybe you can think of something better.

And again here

foreach (string t in r)

Will you remember what that means 6 weeks from now? 6 months? 6 years? No. You won't. It's often been said that the hardest thing in computer science and programming is naming things. It's true. It is the hardest thing, but it's also the most important. It's been my experience that the easy way is never the right way. You took the easy way out here, when you should be coding like the programmer who touches the code next is a violent psychopath who knows where you live.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @Hosch250 that's because you just wrote it. I promise you that all those single letter variables look like jibberish to me now, and will to you in 6 months. I know you want help with the algorithm, but please remember that we're all volunteering our time. If you want to make your code more efficient, first you need to make it clean so others can grasp the code without a second thought. \$\endgroup\$
    – RubberDuck
    Dec 21, 2014 at 5:40

Your Answer

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