高效排序一个IList&LT; T&GT;没有复制源列表 [英] Efficiently sort an IList<T> without copying the source list
问题描述
由于测试情况如下哪能:
- 排序
的IList&LT;的TestObject&GT;
的基础上匹配的指数编号
在的IList&LT; INT&GT;
列表 - 不匹配值被移到列表的末尾,并依他们的原始索引。在这种情况下,由于3和4不索引列表中不存在,我们希望看到
列表[3] == 3
和列表[4 ] == 4
。 - 虽然我知道这是可以使用LINQ可以实现,我需要求助于在原列表,而不是创建一个新的(因如何列表存储)。
- 信号源列表必须是
的IList
(我不能使用名单,其中,T&GT;
)李>
下面的测试:
公共类的TestObject
{
公众诠释编号{获得;组; }
}
[测试]
公共无效Can_reorder_using_index_list()
{
IList的&LT;的TestObject&GT;名单=新的名单,其中,的TestObject&GT;
{
新的TestObject {n = 1},
新的TestObject {ID = 2},
新的TestObject {n = 3},
新的TestObject {n = 4},
新的TestObject {n = 5}
};
IList的&LT; INT&GT; indexList =新[] {10,5,1,9,2};
// TODO排序
Assert.That(名单[0] .ID,Is.EqualTo(5));
Assert.That(名单[1] .ID,Is.EqualTo(1));
Assert.That(名单[2] .ID,Is.EqualTo(2));
Assert.That(名单[3] .ID,Is.EqualTo(3));
Assert.That(名单[4] .ID,Is.EqualTo(4));
}
更新:
按照要求,这是我做的尝试,但是1)它仅适用于名单,其中,T&GT;
2)我不知道这是最有效的方法
VAR克隆= list.ToList();
list.Sort((X,Y)=&GT;
{
VAR xIndex = indexList.IndexOf(x.Id);
VAR yIndex = indexList.IndexOf(y.Id);
如果(xIndex == -1)
{
xIndex = list.Count + clone.IndexOf(X);
}
如果(yIndex == -1)
{
yIndex = list.Count + clone.IndexOf(Y);
}
返回xIndex.CompareTo(yIndex);
});
更新2:
由于@leppie,@jamiec,@米奇小麦 - 这是工作code:
公共类TestObjectComparer:的Comparer&LT;的TestObject&GT;
{
私人只读的IList&LT; INT&GT; indexList;
私人只读Func键&LT;的TestObject,INT&GT; currentIndexFunc;
私人只读INT listCount;
公共TestObjectComparer(IList的&LT; INT&GT; indexList,Func键&LT;的TestObject,INT&GT; currentIndexFunc,INT listCount)
{
this.indexList = indexList;
this.currentIndexFunc = currentIndexFunc;
this.listCount = listCount;
}
公众覆盖INT比较(TestObject中的x,的TestObject Y)
{
VAR xIndex = indexList.IndexOf(x.Id);
VAR yIndex = indexList.IndexOf(y.Id);
如果(xIndex == -1)
{
xIndex = listCount + currentIndexFunc(X);
}
如果(yIndex == -1)
{
yIndex = listCount + currentIndexFunc(Y);
}
返回xIndex.CompareTo(yIndex);
}
}
[测试]
公共无效Can_reorder_using_index_list()
{
IList的&LT;的TestObject&GT;名单=新的名单,其中,的TestObject&GT;
{
新的TestObject {n = 1},
新的TestObject {ID = 2},
新的TestObject {n = 3},
新的TestObject {n = 4},
新的TestObject {n = 5}
};
IList的&LT; INT&GT; indexList =新[] {10,5,1,9,2,4};
ArrayList.Adapter((IList的)列表).Sort(新TestObjectComparer(indexList中,x =&GT; list.IndexOf(x)中,list.Count));
Assert.That(名单[0] .ID,Is.EqualTo(5));
Assert.That(名单[1] .ID,Is.EqualTo(1));
Assert.That(名单[2] .ID,Is.EqualTo(2));
Assert.That(名单[3] .ID,Is.EqualTo(3));
Assert.That(名单[4] .ID,Is.EqualTo(4));
}
一直在研究这个了一下,确实为previously说,你将需要的 ArrayList.Adapter ,但是你会注意到它需要一个非通用的IList所以有些铸件会要求:
ArrayList.Adapter((IList的)名单)
你还需要编写一个比较器,其中的逻辑做你的排序预订购得到遏制。对不起这个名字,但是:
公共类WeirdComparer:IComparer的,IComparer的&LT;的TestObject&GT;
{
私人的IList&LT; INT&GT;订购;
公共WeirdComparer(IList的&LT; INT&GT;阶)
{
this.order =秩序;
}
公众诠释比较(对象x,对象Y)
{
返回比较((的TestObject)X,(的TestObject)Y);
}
公众诠释比较(TestObject中的x,的TestObject Y)
{
如果(order.Contains(x.Id))
{
如果(order.Contains(y.Id))
{
返回order.IndexOf(x.Id).CompareTo(order.IndexOf(y.Id));
}
返回-1;
}
其他
{
如果(order.Contains(y.Id))
{
返回1;
}
返回x.Id.CompareTo(y.Id);
}
}
}
修改:增加了实现上述comparerr 的
随后的使用情况如下:
的IList&LT; INT&GT; indexList =新[] {10,5,1,9,2};
ArrayList.Adapter((IList的)名单).Sort(新WeirdComparer(indexList));
另外,这个线程说明一个很好的方式,把它变成一个扩展方法,这将使你的code更具可重用性,更容易IMO阅读。
Given the test case below how can I:
- Sort the
IList<TestObject>
based on the index of a matchingId
in theIList<int>
list. - Unmatched values are moved to the end of the list and sorted by their original index. In this case, since 3 and 4 do not exist in the index list, we expect to see
list[3] == 3
andlist[4] == 4
. - Whilst I know this can be achieved with linq, I need to resort the original list rather than creating a new one (due to how the list is stored).
- The source list must be an
IList
(I can't useList<T>
)
Here's the test:
public class TestObject
{
public int Id { get; set; }
}
[Test]
public void Can_reorder_using_index_list()
{
IList<TestObject> list = new List<TestObject>
{
new TestObject { Id = 1 },
new TestObject { Id = 2 },
new TestObject { Id = 3 },
new TestObject { Id = 4 },
new TestObject { Id = 5 }
};
IList<int> indexList = new[] { 10, 5, 1, 9, 2 };
// TODO sort
Assert.That(list[0].Id, Is.EqualTo(5));
Assert.That(list[1].Id, Is.EqualTo(1));
Assert.That(list[2].Id, Is.EqualTo(2));
Assert.That(list[3].Id, Is.EqualTo(3));
Assert.That(list[4].Id, Is.EqualTo(4));
}
Update:
As requested, this is what I did try, but 1) it only works with List<T>
and 2) I'm not sure it's the most efficient way:
var clone = list.ToList();
list.Sort((x, y) =>
{
var xIndex = indexList.IndexOf(x.Id);
var yIndex = indexList.IndexOf(y.Id);
if (xIndex == -1)
{
xIndex = list.Count + clone.IndexOf(x);
}
if (yIndex == -1)
{
yIndex = list.Count + clone.IndexOf(y);
}
return xIndex.CompareTo(yIndex);
});
Update 2:
Thanks to @leppie, @jamiec, @mitch wheat - this is the working code:
public class TestObjectComparer : Comparer<TestObject>
{
private readonly IList<int> indexList;
private readonly Func<TestObject, int> currentIndexFunc;
private readonly int listCount;
public TestObjectComparer(IList<int> indexList, Func<TestObject, int> currentIndexFunc, int listCount)
{
this.indexList = indexList;
this.currentIndexFunc = currentIndexFunc;
this.listCount = listCount;
}
public override int Compare(TestObject x, TestObject y)
{
var xIndex = indexList.IndexOf(x.Id);
var yIndex = indexList.IndexOf(y.Id);
if (xIndex == -1)
{
xIndex = listCount + currentIndexFunc(x);
}
if (yIndex == -1)
{
yIndex = listCount + currentIndexFunc(y);
}
return xIndex.CompareTo(yIndex);
}
}
[Test]
public void Can_reorder_using_index_list()
{
IList<TestObject> list = new List<TestObject>
{
new TestObject { Id = 1 },
new TestObject { Id = 2 },
new TestObject { Id = 3 },
new TestObject { Id = 4 },
new TestObject { Id = 5 }
};
IList<int> indexList = new[] { 10, 5, 1, 9, 2, 4 };
ArrayList.Adapter((IList)list).Sort(new TestObjectComparer(indexList, x => list.IndexOf(x), list.Count));
Assert.That(list[0].Id, Is.EqualTo(5));
Assert.That(list[1].Id, Is.EqualTo(1));
Assert.That(list[2].Id, Is.EqualTo(2));
Assert.That(list[3].Id, Is.EqualTo(3));
Assert.That(list[4].Id, Is.EqualTo(4));
}
Been looking at this for a bit, and indeed as previously said, your going to need ArrayList.Adapter, however you'll note it takes a non-generic IList so some casting will be required:
ArrayList.Adapter((IList)list)
You'll also need to write a comparer, of which the logic to do your sorting willl be contained. Excuse the name but:
public class WeirdComparer : IComparer,IComparer<TestObject>
{
private IList<int> order;
public WeirdComparer(IList<int> order)
{
this.order = order;
}
public int Compare(object x, object y)
{
return Compare((TestObject) x, (TestObject) y);
}
public int Compare(TestObject x, TestObject y)
{
if(order.Contains(x.Id))
{
if(order.Contains(y.Id))
{
return order.IndexOf(x.Id).CompareTo(order.IndexOf(y.Id));
}
return -1;
}
else
{
if (order.Contains(y.Id))
{
return 1;
}
return x.Id.CompareTo(y.Id);
}
}
}
EDIT: Added implementation to above comparerr
Then the usage would be as follows:
IList<int> indexList = new[] { 10, 5, 1, 9, 2 };
ArrayList.Adapter((IList)list).Sort(new WeirdComparer(indexList));
By the way, this thread explains a nice way to turn this into an extension method which will make your code more reusable and easier to read IMO.
这篇关于高效排序一个IList&LT; T&GT;没有复制源列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!