C# Collection - Order by an element (Rotate)

Question

I have an IEnumerable<Point> collection. Lets say it contains 5 points (in reality it is more like 2000)

I want to order this collection so that a specifc point in the collection becomes the first element, so it's basically chopping a collection at a specific point and rejoining them together.

So my list of 5 points:

{0,0}, {10,0}, {10,10}, {5,5}, {0,10}

Reordered with respect to element at index 3 would become:

{5,5}, {0,10}, {0,0}, {10,0}, {10,10}

What is the most computationally efficient way of resolving this problem, or is there an inbuilt method that already exists... If so I can't seem to find one!

Define *computationally efficient*. Are you worried about time, memory, what? What is the resource you are optimizing for, and *what is your budget*? — Eric Lippert, Jan 10 '11 at 15:22
This question was asked in the context of a Polygon which represents a geographical shape... each Polygon may have a PointCollection containing up to 1500 Point(x,y) and I may have up to 30,000 Polygons. The points all have to be reordered. So computationally efficient in this context means pretty much all of these, memory and time. — Dr. Paul Jarvis, Jan 20 '11 at 11:27

score 13 · Accepted Answer · answered Jan 10 '11 at 12:05

13

var list = new[] { 1, 2, 3, 4, 5 };

var rotated = list.Skip(3).Concat(list.Take(3));

// rotated is now {4, 5, 1, 2, 3}

answered Jan 10 '11 at 12:05

ulrichb

19,610
8
73
87

1

Though this is brief, the question asked for "most computationally efficient". This computes the first three elements of the list *twice* which is wasteful; imagine if it was the first ten thousand elements of the list. Can you come up with a solution that is more computationally efficient? – Eric Lippert Jan 10 '11 at 15:21

score 2 · Answer 2 · answered Jan 10 '11 at 12:13

A simple array copy is O(n) in this case, which should be good enough for almost all real-world purposes. However, I will grant you that in certain cases - if this is a part deep inside a multi-level algorithm - this may be relevant. Also, do you simply need to iterate through this collection in an ordered fashion or create a copy?

Linked lists are very easy to reorganize like this, although accessing random elements will be more costly. Overall, the computational efficiency will also depend on how exactly you access this collection of items (and also, what sort of items they are - value types or reference types?).

The standard .NET linked list does not seem to support such manual manipulation but in general, if you have a linked list, you can easily move around sections of the list in the way you describe, just by assigning new "next" and "previous" pointers to the endpoints.

The collection library available here supports this functionality: http://www.itu.dk/research/c5/. Specifically, you are looking for LinkedList<T>.Slide() the method which you can use on the object returned by LinkedList<T>.View().

score 1 · Answer 3 · answered Jan 10 '11 at 16:06

1

Version without enumerating list two times, but higher memory consumption because of the T[]:

public static IEnumerable<T> Rotate<T>(IEnumerable<T> source, int count)
{
    int i = 0;

    T[] temp = new T[count];

    foreach (var item in source)
    {
        if (i < count)
        {
            temp[i] = item;
        }
        else
        {
            yield return item;
        }

        i++;
    }

    foreach (var item in temp)
    {
        yield return item;
    }
}

[Test]
public void TestRotate()
{
    var list = new[] { 1, 2, 3, 4, 5 };

    var rotated = Rotate(list, 3);

    Assert.That(rotated, Is.EqualTo(new[] { 4, 5, 1, 2, 3 }));
}

Note: Add argument checks.

answered Jan 10 '11 at 16:06

ulrichb

19,610
8
73
87

How is this significantly different to your original answer? You still need to enumerate the first `count` elements twice. Now one of those iterations uses a temp buffer rather than needing another partial pass through the original sequence, but it's essentially the same performance complexity (not to mention the extra memory required for the buffer). Having said that, it's good practice to use a buffer *if you'll need a second pass*, because some sequences won't allow a second pass or could yield different data second time around. – LukeH Jan 10 '11 at 18:01
@LukeH: You answered your question by yourself: `source` will be enumerated just once. That's the significant difference, when enumerating `source` is expensive and `count` is near to `source.Count()`. – ulrichb Jan 13 '11 at 17:11

score 0 · Answer 4 · answered Jan 10 '11 at 12:17

0

Another alternative to the Linq method shown by ulrichb would be to use the Queue Class (a fifo collection) dequeue to your index, and enqueue the ones you have taken out.

answered Jan 10 '11 at 12:17

Tim Jarvis

18,465
9
55
92

score 0 · Answer 5 · answered Jan 10 '11 at 16:42

The naive implementation using linq would be:

IEnumerable x = new[] { 1, 2, 3, 4 };
var tail = x.TakeWhile(i => i != 3);
var head = x.SkipWhile(i => i != 3);
var combined = head.Concat(tail); // is now 3, 4, 1, 2

What happens here is that you perform twice the comparisons needed to get to your first element in the combined sequence. The solution is readable and compact but not very efficient. The solutions described by the other contributors may be more efficient since they use special data structures as arrays or lists.

score 0 · Answer 6 · answered Jul 05 '20 at 16:25

You can write a user defined extension of List that does the rotation by using List.Reverse(). I took the basic idea from the C++ Standard Template Library which basically uses Reverse in three steps: Reverse(first, mid) Reverse(mid, last) Reverse(first, last)

As far as I know, this is the most efficient and fastest way. I tested with 1 billion elements and the rotation Rotate(0, 50000, 800000) takes 0.00097 seconds. (By the way: adding 1 billion ints to the List already takes 7.3 seconds)

Here's the extension you can use:

public static class Extensions
{
  public static void Rotate(this List<int> me, int first, int mid, int last)
  {
    //indexes are zero based!
    if (first >= mid || mid >= lastIndex)
      return;
    me.Reverse(first, mid - first + 1);
    me.Reverse(mid + 1, last - mid);
    me.Reverse(first, last - first + 1);
  }
}

The usage is like:

static void Main(string[] args)
{
    List<int> iList = new List<int>{0,1,2,3,4,5};    
    Console.WriteLine("Before rotate:");
    foreach (var item in iList)
    {
      Console.Write(item + " ");
    }
    Console.WriteLine();
    
    int firstIndex = 0, midIndex = 2, lastIndex = 4;
    iList.Rotate(firstIndex, midIndex, lastIndex);
    
    Console.WriteLine($"After rotate {firstIndex}, {midIndex}, {lastIndex}:");
    foreach (var item in iList)
    {
      Console.Write(item + " ");
    }
    Console.ReadKey();
}

C# Collection - Order by an element (Rotate)

6 Answers6

Linked