Optimize query

dnks

New member
Joined
Mar 14, 2020
Messages
4
Programming Experience
3-5
Can some one optimize below query
C#:
public string FindString(long findnumber)
{
    var numbers = Enumerable.Range(1, 10);
    var data = numbers.Select(number => new { number = number});
    var val = data.FirstOrDefault(d => d.number == findnumber);
    return val.ToString();
}
 
Last edited by a moderator:

jmcilhinney

C# Forum Moderator
Staff member
Joined
Apr 23, 2011
Messages
2,725
Location
Sydney, Australia
Programming Experience
10+
How about, instead of posting "here's my code, fix it", you provide a full and clear explanation of what you're trying to achieve, how you're trying to achieve it (you've got that part covered), what happens when you try and how that differs from your expectations? What that code actually does seems pointless so optimising it would appear to involve getting rid of most of it. Can you explain why that wouldn't be the case?
 

dnks

New member
Joined
Mar 14, 2020
Messages
4
Programming Experience
3-5
How about, instead of posting "here's my code, fix it", you provide a full and clear explanation of what you're trying to achieve, how you're trying to achieve it (you've got that part covered), what happens when you try and how that differs from your expectations? What that code actually does seems pointless so optimising it would appear to involve getting rid of most of it. Can you explain why that wouldn't be the case?

Thank you for response

below is my question in interview
How can you make search faster below query ? You cannot just return numberToFind.ToString()

C#:
public string FindStringEquivalent(long numberToFind)
{
    var numbers = Enumerable.Range(1, int.MaxValue);
    var data = numbers.Select(number => new { number, numberstring = number.ToString() });
    return data.FirstOrDefault(d => d.number == numberToFind).numberstring;
}

Please reply me i am curious to know answer
 

jmcilhinney

C# Forum Moderator
Staff member
Joined
Apr 23, 2011
Messages
2,725
Location
Sydney, Australia
Programming Experience
10+
I have now formatted your code for readability twice. You either didn't see or ignored the notification from the first time. Please be sure to format all code snippets as unformatted code is much harder to read, largely because of the lack of indenting.

As for the question, I'm not sure exactly how much you're allowed to change but there are two options that stand out.

First, this line doesn't make sense:
C#:
return data.FirstOrDefault(d => d.number == numberToFind).numberstring;
The whole point of calling FirstOrDefault is that you're allowing for the fact that there could be no match, but that code immediately accesses a member of the result, which seems to assume that there always will be a match. Either there will always be a match or there might not be. The fact that the input is a long and the search list is all type int suggests that there might not, which seems like the very first thing that should be checked and null returned if the input is too big to match. If the assumption is that, despite being a long, the input will never be bigger than int.MaxValue, the call should be First rather than FirstOrDefault.

Apart from that, the obvious optimisation seems to be to perform a binary search. Arrays and List<T> objects have their own BinarySearch methods but you wouldn't want to realise an item for every possible positive integer before searching. You could implement your own binary search as it is a fairly simple algorithm.
 

Skydiver

Well-known member
Joined
Apr 6, 2019
Messages
1,029
Location
Virginia Beach, VA
Programming Experience
10+
Seeing that the range to be searched is hard coded, and the result is a string version of the number only if the number is within the range, why even search? Just check the limits and return appropriately. In pseudo code:
C#:
string FindString(long needle)
    IF (needle is less or equal than max AND needle is greater or equal min) THEN
       RETURN needle.ToString()
    Handle error when not in range
 

jmcilhinney

C# Forum Moderator
Staff member
Joined
Apr 23, 2011
Messages
2,725
Location
Sydney, Australia
Programming Experience
10+
Seeing that the range to be searched is hard coded, and the result is a string version of the number only if the number is within the range, why even search? Just check the limits and return appropriately. In pseudo code:
C#:
string FindString(long needle)
    IF (needle is less or equal than max AND needle is greater or equal min) THEN
       RETURN needle.ToString()
    Handle error when not in range
Post #3 says that it is an interview question and that that's a no-no. Obviously, it's a very contrived problem but many are that are intended to demonstrate a specific principle without additional noise.
 

Skydiver

Well-known member
Joined
Apr 6, 2019
Messages
1,029
Location
Virginia Beach, VA
Programming Experience
10+
Interesting... but all those extra memory allocations to create the anonymous object and the string version of the value within is expensive. To speed up that query with the most impact, minimize the allocations.

As for using binary search, the rule of thumb is that the speed gain is only worth the effort when you have more than 100 items. Prior to that, the cost of sorting and then searching is to prohibitive, and so it's better to just do a linear search.
 

Skydiver

Well-known member
Joined
Apr 6, 2019
Messages
1,029
Location
Virginia Beach, VA
Programming Experience
10+
C#:
try
{
    return Enumerable.Range(Convert.ToInt32(numberToFind), 1)
        .ToString();
}
catch (OverflowException)
{
    throw new NullReferenceException();
}
O(1) now instead of O( n ) solution.
 

Sheepings

Senior Programmer
Joined
Sep 5, 2018
Messages
939
Location
UK
Programming Experience
10+
It's a trick question.

public string FindStringEquivalent(long numberToFind)
You wouldn't be using the return type of string if you're dealing with returning a number for a start.
val.ToString();
So you wouldn't need to call to string() if the type was right in the first place.

If your enumerable range is between 1 , 10, then you wouldn't need to use long
FindString(long findnumber)
Everything is wrong with the question, and the code, and its a bad example to test someone with because It kinda doesn't make sense.

Anyway... if you know your element range is between 1, 10, that means that the indexes of the Enumerable type will start from 0 and that means 1 will be at the index of 0. So you could simply minus 1 from the number you want to find, like so :
C#:
        public static string FindString(short findnumber)
        {
            return Enumerable.Range(1, 10).ElementAt(findnumber - 1).ToString();
        }
This code took 2ms to execute. While the following code took 3.7ms to execute :
C#:
        public static string FindString(short findnumber)
        {
            return ((short)Enumerable.Range(1, 10).Take(findnumber).ElementAt(findnumber - 1)).ToString();
        }
This variation takes the number to find from the elements position minus one of the number to find.

While this variation loops with an enumerable step, which moved through the Enumerable Range of numbers, and checks if the number in the range was found. And this only took 1ms :
C#:
        public static string FindString(short findnumber)
        {
            using (IEnumerator<int> number = Enumerable.Range(1, 10).GetEnumerator())
            {
                while (number.MoveNext())
                    if (number.Current.Equals(findnumber))
                        return number.Current.ToString();
            }
            return null;
        }
This variation is the same as the one above except its using a traditional foreach iteration of the Enumerable Range. This also took exactly 1ms :
C#:
        public static string FindString(short findnumber)
        {
            foreach (int numeber in Enumerable.Range(1, 10))
                if (numeber.Equals(findnumber))
                    return numeber.ToString();
            return null;
        }
In all examples, this is all pointless unless you wanted to know the index of the position of the number in the Enumerable Range. But since that's not the question at hand, this should answer your question. Does it not?

But if you did want the index of where the number can be found in the Enumerable Range instead, you can do this which executes at 1ms also :
C#:
        public static string FindString(short findnumber)
        {
            int index = 0;
            foreach (int number in Enumerable.Range(1, 10))
            {
                if (number.Equals(findnumber))
                    return index.ToString();
                        index++;
            }
            return null;
        }
If you wanted both, the number of the index in the Enumerable Range and the number itself, if it can be found, you need to change your return type to something like this :
C#:
        public static int[] FindString(int findnumber)
        {
            int index = 0;
            foreach (int number in Enumerable.Range(1, 10))
            {
                if (number.Equals(findnumber))
                    return new int[] { index, number };
                        index++;
            }
            return null;
        }
Note, your calling code would be : int[] x = FindString(8); and x[0] will contain the index and x[1] will contain your number. Your result looking like int[2] => {[0] 7, [1] 8}

But its a pointless test, and redundantly silly.
 

Sheepings

Senior Programmer
Joined
Sep 5, 2018
Messages
939
Location
UK
Programming Experience
10+
annnnnd ... Here comes @Skydiver with some improvements and @jmcilhinney with some welcomed criticism, no doubt. :LOL:
 

Skydiver

Well-known member
Joined
Apr 6, 2019
Messages
1,029
Location
Virginia Beach, VA
Programming Experience
10+
See my post #9: Since Enumerable.Range() lets you set the initial number, why not just start at the number that is being sought instead of looping multiple times until you get to that number.

And yes, I agree, this is a silly interview question.
 

Sheepings

Senior Programmer
Joined
Sep 5, 2018
Messages
939
Location
UK
Programming Experience
10+
Just for the fun of finding other ways to do it, other than what you just said and already said, we can do it like this just because we can and because its fun to write variations of code. :)
 

Skydiver

Well-known member
Joined
Apr 6, 2019
Messages
1,029
Location
Virginia Beach, VA
Programming Experience
10+
below is my question in interview
How can you make search faster below query ? You cannot just return numberToFind.ToString()

C#:
public string FindStringEquivalent(long numberToFind)
{
    var numbers = Enumerable.Range(1, int.MaxValue);
    var data = numbers.Select(number => new { number, numberstring = number.ToString() });
    return data.FirstOrDefault(d => d.number == numberToFind).numberstring;
}
I just realized... This is simpler than it really is and completely complies with the requirement I highighted above.
C#:
public string FindStringEquivalent(long numberToFind)
{
    checked
    {
        return Convert.ToString((int) numberToFind, 10);
    }
}
I don't use numberToFind.ToString().

Or
C#:
public string FindStringEquivalent(long numberToFind)
{
    checked
    {
        return (((int) numberToFind) + 0).ToString();
    }
}
 

Sheepings

Senior Programmer
Joined
Sep 5, 2018
Messages
939
Location
UK
Programming Experience
10+
Another way in Linq, which isn't the quickest by any stretch, but using skip in Linq is worth it, especially if you wanted to iterate a very large range, you can go directly to the number you are looking for by doing the following :
C#:
        public static int Find_Number (int number)
        {
            return Enumerable.Range(1, 10).Skip(number -1).Select(x => x).Where(n => n.Equals(number)).First();
        }
Skip all numbers minus the one before, and then select it where the number may be in that range. You'd be wise wrapping this in a try catch too, or just use .FirstOrDefault(); instead of First();. (y)
 

Skydiver

Well-known member
Joined
Apr 6, 2019
Messages
1,029
Location
Virginia Beach, VA
Programming Experience
10+
An obfuscated way to get the string without searching...

C#:
public string FindStringEquivalent(long numberToFind)
{
    checked
    {
        return GetDigits((int) numberToFind)
            .Reverse()
            .Aggregate("", (s, d) => s += d);
    }
   
    IEnumerable<char> GetDigits(int n)
    {
        if (n == 0)
            yield return '0';

        bool negative = n < 0;
        if (negative)
            n *= -1;

        while(n != 0)
        {
            yield return (char)((n % 10) + '0');
            n /= 10;
        }

        if (negative)
            yield return '-';
    }
}
 
Top Bottom