1
\$\begingroup\$

I wrote this piece of code to append index to any duplicate entry in List<T> like in the sample below.

Input

["dupe", "not dupe", "dupe", "also not dupe"]

Output

["dupe1", "not dupe", "dupe2", "also not dupe"]

But the problem is it's O(n^2) in the second loop and I'm working on a large list (30+ items). I'm very new to C# and didn't know much built-in functions, so I wanted to know is there anything I can do to optimize this?

List<string> duplicate = new List<string>(); // For storing duplicate item
IEnumerable<IGrouping<string, string>> g = header.GroupBy(i => i);

// Find duplicate and store it in duplicate
foreach (var item in g)
    if (item.Count() > 1)
        duplicate.Add(item.Key);

// Loop through duplicate to append the index
foreach (var item in duplicate) {
    int start = 1;
    for (int i = 0; i < header.Count; i++) {
        // If header[i] is a duplicate item append index to it.
        if (string.Equals(header[i], item, StringComparison.OrdinalIgnoreCase)) {
            header[i] = string.Format("{0}{1}", header[i], start);
            start++;
        }
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ do you need to preserve the order of the list or are you allowed to sort it? \$\endgroup\$
    – Vogel612
    Dec 17, 2019 at 9:01
  • \$\begingroup\$ It's a database columns name I think the order needs to be preserved. \$\endgroup\$
    – phwt
    Dec 17, 2019 at 9:04

3 Answers 3

2
\$\begingroup\$

If you collect the indices along with the duplicates, you don't need to loop over the list again:

var header = new List<string>();
var duplicates = header.Select((x, index) => new { x, index }).ToLookup(x => x.x, x => x.index);
foreach(var duplicate in duplicates.Where(x => x.Count() > 1)) {
  var start = 1;
  foreach(var index in duplicate) {
    header[index] = $"{duplicate.Key}{start++}";
  }
}

This uses string interpolation ($-strings) as a shorthand for string.Format.


On premature optimisation:

You seem concerned about the \$O(n^2)\$ performance of your solution. At the same time you mention your actual input will have ~30 items. Before spending too much time worrying about the efficiency of your code, did you try to find out whether your current solution is problematic? It seems to me that the list is small enough that even a less efficient solution should be quick enough.

Before trying to optimise specific parts of your code, ask yourself two things:

  1. Do I need to optimise? Is execution time currently a problem?
  2. Where is the efficiency problem in the code?

Before optimising, profile your program to figure out where the problems actually are. Before that, efficiencies like \$O(n^2)\$ or \$O(n \log n)\$ are purely academic.

\$\endgroup\$
2
\$\begingroup\$

Here is way where you can preserve the order, and you only iterate twice (including duplicated iteration`):

var duplicated = header
                .GroupBy(x => x)
                .Where(x => x.Count() > 1)
                .ToDictionary(x => x.Key, x => 0);

for (int i = 0; i < header.Length; i++)
{
    if (duplicated.TryGetValue(header[i], out int value))
    {
        value++;
        duplicated[header[i]] = value;
        header[i] = $"{header[i]}{value}";
    }
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Saying you iterate only once is slightly misleading, given that you construct duplicated by iterating as well. \$\endgroup\$
    – JAD
    Dec 17, 2019 at 15:29
  • \$\begingroup\$ @JAD thank you for mentioning that, I have clarified it. \$\endgroup\$
    – iSR5
    Dec 17, 2019 at 22:49
1
\$\begingroup\$

If you do not explicitly need the first dupe to be renamed to dupe1 then you can use:

List<string> input = new List<string>() { "dupe", "not dupe", "dupe", "also not dupe" };
List<string> output = new List<string>();

Dictionary<string, int> duplicates = new Dictionary<string, int>();

foreach (string item in input)
{
    string value = item;
    if (!duplicates.ContainsKey(item))
    {
        duplicates.Add(item, 0);
    }
    else
    {
        duplicates[item]++;
        value += duplicates[item];
    }

    output.Add(value);
}

If starting with dupe1 is important, then you can use a lookahead, like this:

List<string> input = new List<string>() { "dupe", "not dupe", "dupe", "also not dupe" };
List<string> output = new List<string>();

Dictionary<string, int> duplicates = new Dictionary<string, int>();

int index = 0;
foreach (string item in input)
{
    string value = item;

    if (input.IndexOf(item, index + 1) >= 0)
    {
        value += "1";
    }

    if (!duplicates.ContainsKey(item))
    {
        duplicates.Add(item, 1);
    }
    else
    {
        duplicates[item]++;
        value += duplicates[item];
    }

    output.Add(value);
    index++;
}
```
\$\endgroup\$
2
  • \$\begingroup\$ It looks like this doesn't modify the first of each duplicates. \$\endgroup\$
    – JAD
    Dec 17, 2019 at 10:02
  • \$\begingroup\$ Yes, that's the first line in my answer. \$\endgroup\$
    – pritaeas
    Dec 17, 2019 at 10:03

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.