4
\$\begingroup\$

I've already made an implementation of unsorted List but I'm not happy with results it gives. It looks like Big-O is nearly \$N^2\$ which is, I suppose, not correct for my list.

Here's the graph that shows the problem:

screenshot

The X axis represents number of total operations: adding new elements and same number of deleting max element, Y axis represents time in milliseconds.

If you could show me some lines that could be made better, that would be great. Unfortunately, implementation must contain array types instead of easier and faster List types.

TList.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace list
{
    class TList
    {
        // elements of list
        int[] elements;
        int size;
        public TList()
        {
            size = 1;
            elements = new int[size];
        }
        public void Push(int data)
        {
            size++;
            if(size > elements.Length)
            {
                int[] new_elements = new int[elements.Length * 2];
                elements.CopyTo(new_elements, 0);
                elements = new_elements;
            }
            elements[size - 1] = data;
        }
        public int MaxIndex()
        {
            var index = 0;
            var max = elements[0];
            for(var i=1;i< size;i++)
            {
                if(elements[i]>max)
                {
                    max = elements[i];
                    index = i;
                }
            }
            return index;
        }
        public int[] DeleteAt(int indexToRemove)
        {
            return elements = elements.Where((source, indexOfElements) => indexOfElements != indexToRemove).ToArray();
        }

    }
}

Another (better?) way to delete:

public void DeleteAt(int indexToRemove)
{
    int[] new_elements = new int[elements.Length - 1];
    for (int i = 0, j = 0; i < size - 1; i++, j++)
    {
        if (i == indexToRemove)
            j++;
        new_elements[i] = elements[j];
    }
    elements = new_elements;
    size--;
}
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Your delete method is the problem. \$\endgroup\$ – Dmitry Dovgopoly Nov 8 '15 at 11:12
  • 1
    \$\begingroup\$ Okay, do you have an idea how to make it better? :) \$\endgroup\$ – adek111 Nov 8 '15 at 11:17
  • 1
    \$\begingroup\$ You can use fixed size arrays, and resizeing when you'll run in a overflow. With your current code you'll be recreating your array on a delete. \$\endgroup\$ – Stefan Nov 8 '15 at 11:20
1
\$\begingroup\$

For now I'm asking how to optimise deleting of MaxIndex from unsorted list

MaxIndex looks fine. Hard to optimize that further. Maybe you can write a normal for loop that goes from zero to less than the array length so that the JIT can optimize away the range check. You then need to insert if (i >= size) break;. The .NET JIT is not good at optimizing so you have to help. RyuJIT, though, does range checks in loops much, much better.

Your delete is highly inefficient. First of all LINQ is the slowest way to create a new array. Better would be to new it manually and then use Array.Copy to copy over the relevant two sections.

Doing it in-place would be again much faster, at least 2x.

The DeleteAt is probably worse than Array.Copy. It is not very good. It does a lot per item and it does not use memcpy like Array.Copy does. Also, there is no need to create a new array. Just copy in place and do size--.

\$\endgroup\$
14
  • 1
    \$\begingroup\$ Is there any way to achieve clean O(n) different from using original c# list ? OP problem is that he want to have the best function that delete the biggest element from the unosorted list. Finding the biggest element require unorded list to be sorted somehow. Maybe there is a way to choose efficient sorting algorithm which will find the biggest element in O(logn) or something like that. \$\endgroup\$ – davoid Nov 8 '15 at 13:52
  • \$\begingroup\$ Not sure what you mean. If the list is unordered O(N) is the best that can be done because the last element we look at could be the minimum. Sorting in this case is also O(N) (not logN as commonly believed, that's for comparison sorting only. Radix is faster for example). \$\endgroup\$ – usr Nov 8 '15 at 14:16
  • \$\begingroup\$ What does clean O(n) different from using original c# list mean? This answer is O(N) and it's "clean" in my opinion. \$\endgroup\$ – usr Nov 8 '15 at 14:17
  • \$\begingroup\$ I mean, in order to find the maximum element of unorded list you have to check all of them, compare each other. And you have to choose between sorting all elements, and then deleting the first, the second etc or comparing every time you want to delete. The second option has no sense imo. Moreover since we have ideal list implementation (list T class) with O(n), OP wants to be close to this. \$\endgroup\$ – davoid Nov 8 '15 at 14:23
  • \$\begingroup\$ @davoid well that's more or less what I need now. This Array.Copy works like a charm, it speeded up 3x comparing to my second deleteAt function. But still, I suppose, it has O(n^2) right? \$\endgroup\$ – adek111 Nov 8 '15 at 14:32
1
\$\begingroup\$

Deleting an element from list is the same task as shifthing the part of the list after the deleted element. Sample code to demostrate the idea:

public void DeleteAt(int indexToRemove)
{
    for (int i = indexToRemove+1; i < size ; i++)
    {
       //copy current element to previous cell
       elements[i-1] = element[i];
    }

    size--;
}

You don't need a new array and the number of operations is minimal. But according to this answer the is a faster way to do it by using Array.Copy. The number of operations will be the same, but internal optimization of .net will up the speed.

public void DeleteAt(int indexToRemove)
{
    int shiftStart = indexToRemove + 1;
    Array.Copy(elements, shiftStart , elements, indexToRemove, size - shiftStart);
    size--;
}

Where elements is both destination and source of Copy, shiftStart is the first element after deleted, size - shiftStart is the number of elements after the deleted.

\$\endgroup\$
0
\$\begingroup\$

MaxIndex and Delete are O(N) and calling them N times results in quadratic time complexity. You can easily debug a program for performance hotspots by pausing the debugger a few times and seeing where it stops most often. That's the hotspot. Here, it will always stop in MaxIndex and Delete.

Probably, you should choose a data structure that quickly gives you the max value and is able to quickly delete it. Most trees can do that. Search for priority queues. They have been implemented for .NET.

If you want to keep the original order of items you can store the items a second time in a linked list. That way you can access the original order as well as the min element. Deletions and insertions are also fast for both structures.

\$\endgroup\$
6
  • \$\begingroup\$ Yea I know that tree stuctures give big-O of log(n), my point is to compare working time of unsorted list and tournament(winner) tree. Maybe you know some more about this tree? There's not that much info about it, and coding this tree is, I suppose, much harder to do. \$\endgroup\$ – adek111 Nov 8 '15 at 12:40
  • \$\begingroup\$ @adek111 yeah, trees are harder. I think comparing an N^2 structure with a logN structure is pointless, isn't it? Shouldn't you pick structures that play in the same league? Are you fixed on using a tournament tree or would any tree at all do for your situation? \$\endgroup\$ – usr Nov 8 '15 at 12:41
  • \$\begingroup\$ I totally agree that comparing these two structures is pointless, but that was the order I received... And yes, it has to be tournament tree. \$\endgroup\$ – adek111 Nov 8 '15 at 12:48
  • 1
    \$\begingroup\$ @adek111 OK, so if you are required to use an unordered list you have basically lost and this is going to be N^2. \$\endgroup\$ – usr Nov 8 '15 at 12:49
  • \$\begingroup\$ @adek111 And you're supposed to do it in a language that has almost no notion of memory management... So basically the core idea is that you're supposed to learn how to create two datastructures and your question becomes "how to implement tournament tree"... \$\endgroup\$ – Zdeněk Jelínek Nov 8 '15 at 12:52

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.