C# Collection - 按元素排序（旋转）

Question

我有一个 IEnumerable 集合。假设它包含 5 个点（实际上它更像是 2000），

我想对这个集合进行排序，以便集合中的特定点成为第一个元素，所以它基本上是在特定点处切割集合并将它们重新连接在一起。

所以我的 5 点列表：

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

相对于索引处的元素重新排序3 将变为：

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

解决此问题的计算效率最高的方法是什么问题，或者是否存在已经存在的内置方法...如果是这样，我似乎找不到一个！

Answer 1

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}

Answer 2

在这种情况下，简单的数组复制是 O(n)，这对于几乎所有现实世界的目的来说应该足够了。但是，我同意您在某些情况下 - 如果这是多级算法深处的一部分 - 这可能是相关的。另外，您是否只需要以有序的方式迭代该集合或创建一个副本？

链表很容易像这样重新组织，尽管访问随机元素的成本会更高。总体而言，计算效率还取决于您访问此项目集合的具体方式（以及它们是什么类型的项目 - 值类型还是引用类型？）。

标准.NET链接列表似乎不支持这种手动操作，但一般来说，如果您有一个链接列表，您可以按照您描述的方式轻松移动列表的各个部分，只需分配新的“下一个”和“上一个” " 指向端点的指针。

此处提供的集合库支持此功能：http://www.itu.dk/research/c5/< /a>.
具体来说，您正在寻找可在 LinkedList.View() 返回的对象上使用的 LinkedList.Slide() 方法。

Answer 3

没有枚举list两次的版本，但由于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 }));
}

注意：添加参数检查。

Answer 4

ulrichb 所示的 Linq 方法的另一种替代方法是使用队列类（fifo 集合）将索引出队，并将已取出的索引入队。

Answer 5

使用 linq 的简单实现是：

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

这里发生的情况是，您执行了两次所需的比较来获取组合序列中的第一个元素。
该解决方案可读且紧凑，但效率不高。
其他贡献者描述的解决方案可能更有效，因为他们使用特殊的数据结构作为数组或列表。

Answer 6

您可以编写一个用户定义的 List 扩展，通过使用 List.Reverse() 进行旋转。我从 C++ 标准模板库中获取了基本思想，它基本上分三个步骤使用 Reverse： Reverse(first, mid) Reverse(mid, last) Reverse(first, last)

据我所知，这是最有效和最快的方式。我用 10 亿个元素进行了测试，旋转 Rotate(0, 50000, 800000) 需要 0.00097 秒。 （顺便说一句：向列表添加 10 亿个整数已经需要 7.3 秒）

这是您可以使用的扩展：

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);
  }
}

用法如下：

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();
}