I wanted to in the most generic way possible write a method in C# to achieve the following.

  • Take in a string, a set of objects, and a function to access the field of a given object
  • Look at all of the strings from the fields of these objects to match against provided string
  • If provided string is not unique in a case insensitive manner, append _x to the end, where x is an incrementing integer until a unique string is found

With that in mind, I created this.

private string GetUniqueStringForModel<T>(string originalString, IEnumerable<T> enumerableObjects, Func<T, string> stringFieldFunction) where T : class
{
    var uniqueString = originalString;
    var duplicateCount = 1;

    while (enumerableObjects.Select(stringFieldFunction).ToList().Any(currentString => string.Equals(currentString, uniqueString, StringComparison.InvariantCultureIgnoreCase)))
    {
        uniqueString = originalString + "_" + duplicateCount++;
    }

    return uniqueString;
}

I would rather have not put the ToList() in but when working with Entity Framework it was complaining about doing the string comparison in LINQ (presumably because it couldn't compile it SQL).

Any thoughts or ideas for improvement?

  • 1
    I guess that StringComparison.InvariantCultureIgnoreCase comparison really bothers EF. Can't you handle this on your DB column? A case insensitive collation SQL_Latin1_General_CP1_CI_AS should work (assuming that this column is always compared this way). – Adriano Repetti Sep 24 at 12:24
  • 2
    I think you would get much better answers if you included more context like how this method is called, what kind of models you are working with etc. Since the enumerableObjects appear to be a hidden IQueryable I believe it should be possible to delegate more work to the sql server. – t3chb0t Sep 24 at 18:25
up vote 10 down vote accepted

There's certainly room for improvement.

  1. Move that that Select(stringFieldFunction).ToList() out of the while loop. Iterating an IEnumerable might be quite expensive, and there's no need to repeat that work when you find a duplicate.
  2. Select only those strings that have originalString as a prefix. That will reduce the amount of items you need to check against when adjusting the suffix.
  3. Instead of making a list, turn those results into a (hash)set, for faster lookup.

Regarding EF complaining: apparently it doesn't support those StringComparsion overloads, so it'll have to fetch all rows from the database and run your Any predicate in memory, which may be slower as expected. Maybe an alternative approach like using ToUpperInvariant can be translated to SQL?


Applying the above changes will give you the following:

private string GetUniqueValue<T>(string value, IEnumerable<T> items, Func<T, string> getValue)
{
    var possibleDuplicates = items
        .Select(getValue)
        .Where(val => val.StartsWith(value, StringComparison.InvariantCultureIgnoreCase))
        .ToHashSet();

    var result = value;
    var suffix = 1;
    while (possibleDuplicates.Contains(result))
    {
        result = value + "_" + suffix;
        suffix += 1;
    }
    return result;
}

Addendum

As t3chb0t and ErikE already pointed out, if you want the benefits of Linq-to-SQL, then you need to use IQueryable<T>. Not only that, you also need to make sure that you're using the Queryable Linq extension methods, not the Enumerable variants.

The difference is that Enumerable methods have Func<> parameters, while the Queryable variants have Expression<Func<>> parameters. An Expression is a data structure that represents a piece of code, which makes translation to SQL possible. Because stringFieldFunction is a Func, not an Expression<Func>, the Enumerable.Select variant is used. That cannot be translated to SQL, so all data has to be loaded from the database before the Select (and any subsequent operation) can be performed on it.

To recap: use IQuerable<T>, make sure you're using Queryable Linq methods, and only use supported methods within your expressions.

  • I like solution with HashSet very much and I would like to discuss some algorithm improvements. How about trying to split string by the last _ (before [0-9]*) then putting everything into Map<string, int> (assuming 0 when _number does not exist) and finally just querying the map returning just value if does not exist and $"{value}_{map.Get(prefix) + 1}" otherwise. What do you think? – mpasko256 Sep 24 at 16:48
  • I forgot to mention: by putting next value I mean:Math.Max(actual, existing) – mpasko256 Sep 24 at 16:53
  • 1
    I guess all the answers are wrong away because it looks like that the items is actually an IQueryable thus things like StartsWith(value, StringComparison.InvariantCultureIgnoreCase) are pointless or won't work at all. I'm pretty sure it can be solved in a much better way that compiles to sql if OP had only posted enough context. – t3chb0t Sep 24 at 17:22
  • @mpasko256: I don't really see what you mean. Maybe you could show some code? – Pieter Witvoet Sep 24 at 19:36
  • 1
    @t3chb0t: if that's the case then he should also be passing in an Expression<Func<>> instead of a Func<>... it looks like the OP started with an IQueryable implementation and then tried to generalize it to IEnumerable, without realizing the implications. I'll add some notes about that. – Pieter Witvoet Sep 25 at 10:08

It will be more efficient to call .ToList() just once:

// ...
var list = enumerableObjects.Select(stringFieldFunction).ToList();
while (list.Any(currentString => string.Equals(currentString, uniqueString, StringComparison.InvariantCultureIgnoreCase)))
{
    uniqueString = originalString + "_" + duplicateCount++;
}
private string GetUniqueStringForModel<T>(
    string originalString,
    IQueryable<T> databaseQueryable,
    Expression<Func<T, string>> stringFieldFunction
) where T : class {
    var lowerBound = originalString.ToLowerInvariant();
    var upperBound = originalString.ToUpperInvariant() + "z";
    var candidates = new HashSet<string>(
       databaseQueryable
          .Select(stringFieldFunction)
          .Where(field => field >= lowerBound && field < upperBound)
          .ToSet()
    );

    return Enumerable
       .Range(0, int.MaxValue)
       .Select(i => originalString + (i == 0 ? "" : $"_{i}"))
       .First(candidate => !candidates.Contains(candidate));
}

There are a few things going on here.

First, since you are using Entity Framework and received the error you did, I believe that your IEnumerable is actually an IQueryable. If you want to add predicates to the query that are performed on the database server, you need to maintain the IQueryable as that data type and not prematurely force it to become an IEnumerable. This is of crucial importance to understand and I encourage you to go study the difference between these and what effects it has. The exact same code is compiled completely differently when cast to an IQueryable instead of an IEnumerable—differently in a way necessary for being able to project your C# code to SQL for doing the majority of the work in the database.

Second, your Func can work, but it must contain only methods and operators that work with Entity Framework and must be an Expression<Func<>>. If you want to use a method that is not supported, you will have materialize the entire result set in memory using .ToList() and then iterate over it locally (using a regular Func).

My goal in the above code was to fetch the set of values that could possibly match the originalString. Notice that by assigning the values to variables, this leaves the queryable's Where clause susceptible to being read by EF, because it will be compiled as an Expression instead of to byte code. (That is why you need IQueryable instead of IEnumerable). The trick I used to select the appropriate range may not be a good one (I haven’t touched C# for 16 months). Study the operators and your data and pick a better one. Find the greatest value that can be added (not "z") and add that.

Third, the very limited set of results is being converted to a Set so that we can get O(1) lookup time. I promise you that performing a ToList() on an IQueryable (masked as an IEnumerable) on each new number suffix attempt is a superbly wonderful way to destroy performance. Please don't do that. Your code as written will read every single row from the underlying IQueryable on every iteration of the while loop—hopefully there are some conditions on it and this isn’t the entire table!

Fourth, you have to pay attention to the string comparison in the database and for the HashSet. Do you want case sensitivity or case insensitivity? Is there another kind of collation that might be needed to perform foreign language support? You need to provide the HashSet a StringComparer that will perform properly.

Fifth, why even provide a stringFieldFunction when the caller can just do .Select(stringFieldFunction) itself? This doesn't seem useful to me. Don't add unnecessary parameters. Doing it in the caller will avoid having to muck about with Func vs. Expression<Func>.

  • I think HashSet<string>.Contains() is case sensitive. String.Upper() is a canonical function so is supported by any LINQ provider. - Although I am not sure if it performs the same in memory as in the db. (In memory it will use the .Net library, in database it will use the appropriate db function) – Taemyr Sep 26 at 8:08
  • The solution is to pass the appropriate StringComparer into the constuctor of the HashSet. – Taemyr Sep 26 at 8:14
  • @Taemyr That’s why I said “you need to provide the HashSet a comparator they will perform properly.” Of course I meant Comparer. – ErikE Sep 26 at 14:22

ToUpper translates into SQL allowing you to avoid the StringComparison.InvariantCultureIgnoreCase.

In addition the IsNumeric function allows you to guard so that you can use parse the string to get the counter directly (In LinqtoEntities with a MSSQL backend .Cast() performs this function).

Finally when operating with queryables you need to use an Expression rather than a Func

This allows the following;

private string GetUniqueStringForModel<T>(
  string originalString, 
  IQueryable<T> enumerableObjects, 
  Expression<Func<T, string>> stringFieldFunction
) where T : class
{
IQueryable<String> enumerableStrings=Queryable.Select<T,string> 
(enumerableObjects,stringFieldFunction);

if(!enumerableObjects.Select(stringFieldFunction).Any(
x=>x.ToUpper()==originalString.ToUpper()))
return originalString;

originalString=originalString+"_";
var length=originalString.Length;

if(!enumerableStrings.Any(
x=>x.ToUpper().StartsWith(originalString.ToUpper())&&
System.Data.Objects.SqlClient.SqlFunctions.IsNumeric(
x.Substring(length)) == 1))
return originalString+"1";

var highest=
  enumerableStrings
  .Where(x=>(x.ToUpper().StartsWith(originalString.ToUpper())) &&
    System.Data.Objects.SqlClient.SqlFunctions.IsNumeric(
    x.Substring(length)) == 1)
  .Select(x=>x.Substring(length))
  .Cast<int>()
  .Max()+1;
return originalString+highest;
}

Not quite the same as your code, if you have "Foo", "Foo_1" and "Foo_5" your code will return "Foo_2" while the above should return "Foo_6", but it's only 3 db calls, and each only return a single row.

  • You can use LinqToEntities in LinqPad if you load the correct library... :) – ErikE Sep 25 at 5:24
  • @ErikE So you can. Thanks. – Taemyr Sep 25 at 12:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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