10
\$\begingroup\$

The challenge requires the program to receive data from the console and use binary search to find if a term is contained in a set of other terms. I've unit-tested the solution below, but according to the grader, my solution is too slow (i.e. the logic is "correct" but inefficient). The grader returns 30 seconds of execution time presumably for very large input (which I can't access).

Where's the bottleneck (or, how can I make this faster?)

The input consists of two lines:

  • Input line 1 contains the number of data, followed by the actual data, already sorted.
    Example: 5 1 5 8 12 13 represents a five-element list 1 5 8 12 13.
  • Input line 2 contains the number of search terms, followed by the search terms.
    Example: 5 8 1 23 1 11 represents five search terms: 8, 1, 23, 1, 11.
  • Output for the example above: 2 0 -1 0 -1
    Explanation: search term 8 is found at actual data location 2, 1 is found at 0, 23 is not found (returns -1), 1 is found at 0, 11 is not found (-1)

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

namespace BinarySearch
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Launcher().Run(args);
        }
    }

public class Launcher
{
    public void Run(string[] args)
    {
        var input = Console.ReadLine().Split(' ').Select(n => Convert.ToInt64(n)).ToArray();
        var numData = (int)input[0];
        // attempt to make console reading faster...
        //var data = input.Skip(1).Take((int) (numData)).ToArray();
        // attempt to make console reading faster...            
        //var data = new ArraySegment<long>(input, 1, numData).ToArray();
        var data = new List<long>(input).GetRange(1, numData).ToArray();

        var searchTerms = Console.ReadLine().Split(' ').Select(n => Convert.ToInt64(n)).ToArray();
        var numSearchTerms = (int)searchTerms[0];
        // attempt to make console reading faster...
        //var search = searchTerms.Skip(1).Take((int)(numSearchTerms)).ToArray();
        // attempt to make console reading faster...
        //var search = new ArraySegment<long>(searchTerms, 1, numSearchTerms).ToArray();
        var search = new List<long>(searchTerms).GetRange(1, numSearchTerms).ToArray();

        Console.WriteLine(BinarySearchSetup(data, search));
    }

    public string BinarySearchSetup(long[] data, long[] searchTerms)
    {
        var resultString = "";

        var lowerBound = 0;
        var upperBound = data.Length - 1;

        for (var i = 0; i < searchTerms.Length; i++)
            resultString += BinarySearch(data, lowerBound, upperBound, searchTerms[i]) + " ";

        return resultString.Trim();
    }

    public long BinarySearch(long[] data, long low, long high, long key)
    {
        if (high < low)
            return -1;

        var mid = low + (high - low) / 2;

        if (key == data[mid])
            return mid;

        else if (key < data[mid])
            return BinarySearch(data, low, mid - 1, key);

        else
            return BinarySearch(data, mid + 1, high, key);
    }
}
}
\$\endgroup\$
  • \$\begingroup\$ So, if the problem is actually with the output reporting code, it's unfair to get poor marks. Benchmark the search only (disable output) to see how performant the search is. More important than absolute time is the $log n$ way in which it grows. \$\endgroup\$ – JDługosz Jun 25 '16 at 12:07
12
\$\begingroup\$

If the number of search terms becomes large, it would be better to use a StringBuilder. Otherwise, a new string (which is growing) will be allocated for each iteration.

I would consider caching results:

public string BinarySearchSetup(long[] data, long[] searchTerms)
{
    var lowerBound = 0;
    var upperBound = data.Length - 1;

    var cache = new Dictionary<long, long>();
    var resultBuilder = new StringBuilder();
    for (var i = 0; i < searchTerms.Length; i++)
    {
        var searchTerm = searchTerms[i];
        long result;
        if (!cache.TryGetValue(searchTerm, out result))
        {
            result = BinarySearch(data, lowerBound, upperBound, searchTerm);
            cache.Add(searchTerm, result);
        }
        resultBuilder.Append(result);
        resultBuilder.Append(" ");
    }
    return resultBuilder.ToString();
}

If you have a really large list and multiple cores, you also could try to parallelize the search, e.g. using Parallel.For in combination with a ConcurrentDictionary for caching:

public string BinarySearchSetup(long[] data, long[] searchTerms)
{
    var lowerBound = 0;
    var upperBound = data.Length - 1;

    var cache = new ConcurrentDictionary<long, long>();
    var resultArray = new long[searchTerms.Length];
    Parallel.For(0, searchTerms.Length, i =>
    {
        var searchTerm = searchTerms[i];
        long result;
        if (!cache.TryGetValue(searchTerm, out result))
        {
            result = BinarySearch(data, lowerBound, upperBound, searchTerm);
            cache.TryAdd(searchTerm, result);
        }
        resultArray[i] = result;
    });
    return string.Join(" ", resultArray);
}
\$\endgroup\$
  • \$\begingroup\$ I used StringBuilder to fix the += time hog. Much thanks! \$\endgroup\$ – brntsllvn Jun 24 '16 at 19:38
  • 5
    \$\begingroup\$ Your parallel approach is broken. You're not necessarily writing the results in the correct order and you're not appending the space atomically. Don't blindly convert serial for-loops to Parallel.For. \$\endgroup\$ – Johnbot Jun 24 '16 at 19:41
  • \$\begingroup\$ @Johnbot: You are right... stupid mistake. I fixed it by using an array that preserves the order. \$\endgroup\$ – JanDotNet Jun 24 '16 at 20:01
11
\$\begingroup\$

An alternative to using a StringBuilder is using LINQ with string.Join(). It's about as fast and is more concise and readable.

public string BinarySearchSetup(long[] data, long[] searchTerms)
{
    var resultString = "";

    var lowerBound = 0;
    var upperBound = data.Length - 1;
    var results = searchTerms.Select(x => BinarySearch(data, lowerBound, upperBound, x));
    return string.Join(" ", results);
}

If you want to parallelize the operation, you can just call AsParallel() and then AsOrdered() to preserve order:

var results = searchTerms
    .AsParallel()
    .AsOrdered()
    .Select(x => BinarySearch(data, lowerBound, upperBound, x));

If you want to cache the results, you can build a dictionary on the distinct elements in a similar fashion to the above LINQ query. AsOrdered() is not required because it's getting stored in a dictionary. The method will look like this:

public string BinarySearchSetup(long[] data, long[] searchTerms)
{
    var lowerBound = 0;
    var upperBound = data.Length - 1;
    var cache = searchTerms
        .Distinct()
        .AsParallel()
        .ToDictionary(x => x, x => BinarySearch(data, lowerBound, upperBound, x));
    var results = searchTerms.Select(x => cache[x]);
    return string.Join(" ", results);
}

Edit: Regarding BinarySearch(), when I make recursive methods, I like to make a top level method with less parameters that calculates the extra parameters to pass into the recursive method. Like this:

public int BinarySearch(long[] data, long key)
{
    var lowerBound = 0;
    var upperBound = data.Length - 1;
    return BinarySearch(data, lowerBound, upperBound, key);
}

If you don't mind working with ints (which I think arrays are indexed with anyway), you can use Array.BinarySearch(). According to the documentation, a negative number is returned when an element is not found, and it's not necessarily -1, so we will have to handle that.

public int BinarySearch(long[] data, long key)
{
    int result = Array.BinarySearch(data, key);
    return Math.Max(result, -1); 
}
\$\endgroup\$
6
\$\begingroup\$

At first glance, resultString += is a first-class performance killer, speaking of string concatenation.

It's so frequent than there is a special class to overcome that : the StringBuilder class.

Usage is straightforward : stringBuilder.Append(string)

And when you really need the string : stringBuilder.ToString()

Hope this helps !

\$\endgroup\$

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.