C＃集合 - 按元素排序（旋转）

我有一个IEnumerable<Point>集合。可以说它包含5点（实际上它更像2000）C＃集合 - 按元素排序（旋转）

我想订购这个集合，以便集合中的一个特定点成为第一个元素，所以它基本上是在特定点上切割集合并重新连接他们在一起。

所以我的5点列表：

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

在指数3相对于元素重新排序将变成：

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

什么是解决这一计算最为有效的方法问题，还是有一种已经存在的内置方法...如果是这样，我似乎无法找到一个！

来源

2011-01-10 Dr. Paul Jarvis

定义*计算效率高*。你担心时间，记忆，什么？您正在优化的资源是什么，以及*您的预算*是什么？ – 2011-01-10 15:22:09

这个问题是在一个表示地理形状的多边形的上下文中提出的......每个多边形可能有一个包含多达1500个点（x，y）的PointCollection，我可能有多达30,000个多边形。点都必须重新排序。因此，在这种情况下，计算效率非常高，意味着几乎所有这些，内存和时间。 – 2011-01-20 11:27:15

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}

来源

2011-01-10 12:05:34 ulrichb

虽然这很简短，但问题是“计算效率最高”。这将计算列表中的前三个元素*两次*这是浪费的;想象一下，如果这是列表中的第一万个元素。你能想出一个计算效率更高的解决方案吗？ – 2011-01-10 15:21:13

在这种情况下，一个简单的数组副本是O（n），对于几乎所有现实世界的目的而言，这应该足够好。但是，我会在某些情况下授予您 - 如果这是多层算法中的一部分 - 这可能是相关的。另外，你是否需要以有序的方式遍历这个集合或创建一个副本？

链接列表很容易重组，像这样，虽然访问随机元素将会更加昂贵。总的来说，计算效率还取决于你准确访问这个项目集合（以及它们是什么类型的项目 - 值类型或引用类型？）。

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

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

来源

2011-01-10 12:13:03 Sander

ulrichb显示的Linq方法的另一种替代方法是使用队列类（一个fifo集合）将您的索引出列，并排出已取出的那些。

来源

2011-01-10 12:17:15

版本没有列举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 })); 
}

注：添加参数检查。

来源

2011-01-10 16:06:33 ulrichb

天真实现使用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

这里发生的是，你执行两次，以获得你的第一个元素组合序列中所需要的比较。该解决方案可读性强，但效率不高。由其他贡献者描述的解决方案可能更有效率，因为他们使用特殊的数据结构作为数组或列表。

来源

2011-01-10 16:42:49 fausto

C＃集合 - 按元素排序（旋转）

回答

相关问题