7
\$\begingroup\$

I have a list of authors, where seeking duplicity. The indexes of these duplicates are stored in a list of lists named duplicity. For example, at index 0 in the list duplicity is nested list, which refer to indexes of authors list with duplicates author A, index 1 author duplicity B, etc. I also have list edge, where indexes of nodes(authors) are stored that are connected by an edge. Program passes through and removes duplicate authors by list duplicity.

For example I have stored in duplicity list indexes 1, 2, 3. These refers to authors list, where are stored names of authors. It also refers to edge list, where are stored start and end point of edges. For example if I have authors stored on indexes 1,2,3 and they are connected altogether, than the edge list is 1,2, 1,3, 2,3. Because authors on indexes 1,2,3 are same, I need make them one. So I pass edge list and replace all 2 and 3 to 1.

The problem is that progress of code below is very slow. I'm sure that in the code is something useless which raise complexity, but I can not figure it out. I think, the main failure in my code is the first part with the for loops. It many times passes authors list and if there are tens of thousands items, it's really slow. Can you help me optimize this code?

 for (int i = 0; i < authors.GetDuplicates().Count; i++)
        {
            for (int j = 0; j < edge.Count; j++)
            {
                for (int k = 0; k < authors.GetDuplicates()[i].Count - 1; k++)
                {
                    if (edge[j] == authors.GetDuplicates()[i].ElementAt(k))
                    {
                        edge[j] = authors.GetDuplicates()[i].ElementAt(k + 1);
                    }
                }
            }
        }

 public static List<List<int>> GetDuplicates(this IList<string> source)
    {
        HashSet<string> itemsSeen = new HashSet<string>();
        HashSet<string> itemsYielded = new HashSet<string>();
        List<List<int>> duplicates = new List<List<int>>();
        List<int> dupLow = new List<int>();
        HashSet<int> temp = new HashSet<int>();

        int c = 0;

        foreach (string item in source)
        {
            if (!itemsSeen.Add(item))
            {
                if (itemsYielded.Add(item))
                {
                    if (item != "-")
                    {
                        int w = 0;

                        for (int j = 0; j < authors.Count; j++)
                        {
                            if (authors[j] == authors[c])
                            {
                                temp.Add(w);
                            }
                            w++;
                        }

                        dupLow = new List<int>(temp);
                        duplicates.Add(dupLow);
                        temp.Clear();
                    }
                }
            }
            c++;
        }
        return duplicates;
    }

EDIT:
We have four authors, A and B are authors of one book and C and A are authors of different book. Authors within one book are connected by edge. We can see, there are two authors "A". So we replace in edges index of author A (index 0) to 3. At the end books are connected by common author.

authors | edge | remove dup. | bad result
[0] A    [0] 0   [0] 3    [0] 4
[1] B    [1] 1   [1] 1    [1] 1

[2] C    [2] 2   [2] 2    [2] 2
[3] A    [3] 3   [3] 3    [3] 3


The result should look like this:
The result should look like this:

\$\endgroup\$
1
  • 1
    \$\begingroup\$ please post a follow up question to this when you have a new version, we would love to see it. \$\endgroup\$
    – Malachi
    Dec 11, 2014 at 18:48

3 Answers 3

3
\$\begingroup\$

I'm not sure I follow the code, but I would try removing the repeated calls to GetDuplicates:

foreach (var duplicate in authors.GetDuplicates())
{
    for (int j = 0; j < edge.Count; j++)
    {
        for (int k = 0; k < duplicate.Count - 1; k++)
        {
            if (edge[j] == duplicate[k])
            {
                edge[j] = duplicate[k + 1];
            }
        }
    }
}

I've also replaced the calls to ElementAt with use of the indexer, as I think it's clearer.

\$\endgroup\$
7
  • \$\begingroup\$ This is faster, but gives me wrong result. In duplicate list, I store data in list of lists, so therefore I used authors.GetDuplicates()[i].ElementAt(k) , where "i" refers to upper list and "k" to nested list. \$\endgroup\$
    – Tomas
    Dec 10, 2014 at 22:38
  • \$\begingroup\$ @Tomas can you please provide an example of authors, edge, and the expected result where this gives the wrong answer? I'm confused since on the ith iteration, duplicate[k] should be equal to authors.GetDuplicates()[i].ElementAt(k). Thanks. \$\endgroup\$
    – mjolka
    Dec 10, 2014 at 23:06
  • \$\begingroup\$ Of course, a just must deal with text formatting to make it clear. \$\endgroup\$
    – Tomas
    Dec 10, 2014 at 23:38
  • \$\begingroup\$ @Tomas you could post the example on ideone if that makes it easier. \$\endgroup\$
    – mjolka
    Dec 10, 2014 at 23:42
  • \$\begingroup\$ Edited first post. \$\endgroup\$
    – Tomas
    Dec 10, 2014 at 23:55
2
\$\begingroup\$

This little bit of code

        if (!itemsSeen.Add(item))
        {
            if (itemsYielded.Add(item))
            {
                if (item != "-")
                {

can be simplified into

if (!itemsSeen.Add(item) && itemsYielded.Add(item) && item != "-")
{

I am not sure I follow exactly how the code works, but I think you could benefit from using List<>'s built in Contains() method. Check it out MSDN List(T).Contains Method

You should be able to get rid of the k for loop by using the Contains() Method

\$\endgroup\$
1
  • \$\begingroup\$ Thank you, that I certainly can change. I think, the main failure in my code is the first part with the for loops. It several times passes authors list and if there are tens of thousands items, it's really slow. \$\endgroup\$
    – Tomas
    Dec 10, 2014 at 21:49
1
\$\begingroup\$
for (int i = 0; i < authors.GetDuplicates().Count; i++)
{
    for (int j = 0; j < edge.Count; j++)
    {
        for (int k = 0; k < authors.GetDuplicates()[i].Count - 1; k++)
        {
            if (edge[j] == authors.GetDuplicates()[i].ElementAt(k))
            {
                edge[j] = authors.GetDuplicates()[i].ElementAt(k + 1);
            }
        }
    }
}  

What are you doing here ? You are calling GetDuplicates() on almost every line of code.

Assuming authors.GetDuplicates().Count == 3 with each containing list having Count == 2 and edge.Count == 3 you will for the best case call authors.GetDuplicates() 28 times , where one time is enough.

var duplicates = authors.GetDuplicates()
for (int i = 0; i < duplicates.Count; i++)
{
    for (int j = 0; j < edge.Count; j++)
    {
        for (int k = 0; k < duplicates[i].Count - 1; k++)
        {
            if (edge[j] == duplicates[i].ElementAt(k))
            {
                edge[j] = duplicates[i].ElementAt(k + 1);
            }
        }
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ I see the problem now. You are right in yours assumptions. I edited the code and now it's work better. Thank you. \$\endgroup\$
    – Tomas
    Dec 11, 2014 at 10:13

Your Answer

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

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