我有上千个 MyClass
类型的对象
class MyClass{
array<MyClass> objectsBehind;
Boolean large;
}
其中 objectsBehind
是一个 MyClass
对象的数组,这个数组中的任何对象都是 1000 个原始对象的一部分。
我将它们放在一个数组中并对它们进行排序,使一个对象在数组中的索引高于其 objectsBehind
数组中的对象。例如,索引为 546 的对象在其 objectsBehind
数组中不能有任何对象在排序数组中具有高于 546 的索引。
我的问题是这样的。 1000 个对象中大约有 20 个具有 large = true
属性。如果不违反 objectsBehind
属性,将这些“大”对象按顺序分组在排序数组中是有益的。例如,最好有这个:
array[45].large = false; array[46].large = true, array[47].large = true, array[48].large = true, array[49].large = false;
比
array[45].large = true; array[46].large = false, array[47].large = true, array[48].large = false, array[49].large = true;
在第一个序列中,我将三个大对象组合在一起,而不是在第二个示例中将它们分散开。
我想不出一个好的方法来做到这一点。有什么想法吗?
最佳答案
这可能很容易做到。
首先,要在每个此类对象的 objectsBehind
数组中的所有对象之前对对象进行排序,您可以使用 Topological Sort .
拓扑排序会将每个主迭代“同时”放置一些元素到输出集合中。
这些 对象按大属性排序,这样所有大对象排在第一位,然后是所有非大对象。您可能想在此处添加另一个排序标准,以便您可以依赖大对象和非大对象内部的已知顺序。
基本上,这是拓扑排序的工作原理(我学到的那个):
- 首先创建几个数据结构来保存“图形”,即。对象之间的所有链接:
- 您需要一个包含每个对象的字典,以及它链接到的所有对象的列表(在您的情况下实际上不需要,因为每个对象都在
objectsBehind
属性(property)) - 您需要一个字典,其中包含链接到的每个对象以及有多少此类链接指向该对象
- 您需要一个包含所有没有链接的对象的哈希集(目前)
- 您需要一个包含每个对象的字典,以及它链接到的所有对象的列表(在您的情况下实际上不需要,因为每个对象都在
- 相应地填充这些数据结构
- 将所有对象放入哈希集中(就好像它们根本没有入站链接一样)
- 遍历所有有链接的对象,我们称这个对象迭代为A
- 添加对象(具有来自它的链接)以及它到第一个字典的所有链接(同样,您的对象不需要这样做)
- 通过增加来自 A 对象的每个链接的入站链接数来调整第二个字典
- 当您增加一个对象的入站链接数量时,从哈希集中删除同一对象(我们现在知道它至少有一个入站链接)
- 开始一个基本上说“只要哈希集中有东西”的循环,这将查看哈希集,它现在包含所有没有入站链接的对象
- 在每次循环迭代中,首先输出哈希集中的所有对象。这是剩下的“先到”。您想要订购这些以产生稳定的排序。在您的情况下,我会首先订购所有大型对象,然后是所有非大型对象。
- 制作哈希集的副本,用于枚举目的,并清除哈希集,为下一次循环迭代做准备
- 循环遍历副本中的所有对象,对于每个对象,循环遍历它的所有出站链接,对于每个链接,减少第二个字典中目标上的入站链接数量
- 当这样一个数字,即指向一个对象的入站链接数,在减少后达到零时,这意味着不再有任何“活”链接指向它,因此将它添加到哈希集中
- 循环(第 4 点及以后)
如果在第 8 点和第 4 点之后,哈希集中没有对象,但第二个字典中有未达到零入站链接的对象,这意味着图中有循环 , IE。沿着“对象 1 指向对象 2,对象 2 指向对象 3,对象 3 指向对象 1”。
这是一个这样的解决方案,您可以在LINQPad 中进行测试.
请注意,有很多方法可以进行拓扑排序。例如,这里的这个版本将获取所有之前没有对象的对象,并同时输出这些对象。但是,您可以将直接在其中一些之后的对象分组,直接在它们之后的对象之后,并且仍然不违反任何约束。
例如,检查下面代码中 4 和 7 之间的关系(您必须运行它)。
const int OBJECT_NUM = 10;
void Main()
{
Random r = new Random(12345);
var objects = new List<MyClass>();
for (int index = 1; index <= OBJECT_NUM; index++)
{
var mc = new MyClass { Id = index, IsLarge = (r.Next(100) < 50) };
objects.Add(mc);
}
for (int index = 0; index < objects.Count; index++)
{
var temp = new List<MyClass>();
for (int index2 = index + 1; index2 < objects.Count; index2++)
if (r.Next(100) < 10 && index2 != index)
temp.Add(objects[index2]);
objects[index].ObjectsBehind = temp.ToArray();
}
objects.Select(o => o.ToString()).Dump("unsorted");
objects = LargeTopoSort(objects).ToList();
objects.Select(o => o.ToString()).Dump("sorted");
}
public static IEnumerable<MyClass> LargeTopoSort(IEnumerable<MyClass> input)
{
var inboundLinkCount = new Dictionary<MyClass, int>();
var inputArray = input.ToArray();
// the hash set initially contains all the objects
// after the first loop here, it will only contain objects
// that has no inbound links, they basically have no objects
// that comes before them, so they are "first"
var objectsWithNoInboundLinks = new HashSet<MyClass>(inputArray);
foreach (var source in inputArray)
{
int existingInboundLinkCount;
foreach (var target in source.ObjectsBehind)
{
// now increase the number of inbound links for each target
if (!inboundLinkCount.TryGetValue(target, out existingInboundLinkCount))
existingInboundLinkCount = 0;
existingInboundLinkCount += 1;
inboundLinkCount[target] = existingInboundLinkCount;
// and remove it from the hash set since it now has at least 1 inbound link
objectsWithNoInboundLinks.Remove(target);
}
}
while (objectsWithNoInboundLinks.Count > 0)
{
// all the objects in the hash set can now be dumped to the output
// collection "at the same time", but let's order them first
var orderedObjects =
(from mc in objectsWithNoInboundLinks
orderby mc.IsLarge descending, mc.Id
select mc).ToArray();
foreach (var mc in orderedObjects)
yield return mc;
// prepare for next "block" by clearing the hash set
// and removing all links from the objects we just output
objectsWithNoInboundLinks.Clear();
foreach (var source in orderedObjects)
{
foreach (var target in source.ObjectsBehind)
{
if (--inboundLinkCount[target] == 0)
{
// we removed the last inbound link to an object
// so add it to the hash set so that we can output it
objectsWithNoInboundLinks.Add(target);
}
}
}
}
}
public class MyClass
{
public int Id; // for debugging in this example
public MyClass[] ObjectsBehind;
public bool IsLarge;
public override string ToString()
{
return string.Format("{0} [{1}] -> {2}", Id, IsLarge ? "LARGE" : "small", string.Join(", ", ObjectsBehind.Select(o => o.Id)));
}
}
输出:
unsorted
1 [LARGE] -> 5
2 [LARGE] ->
3 [small] ->
4 [small] -> 7
5 [small] ->
6 [small] ->
7 [LARGE] ->
8 [small] ->
9 [LARGE] -> 10
10 [small] ->
sorted
1 [LARGE] -> 5
2 [LARGE] ->
9 [LARGE] -> 10
3 [small] ->
4 [small] -> 7
6 [small] ->
8 [small] ->
7 [LARGE] ->
5 [small] ->
10 [small] ->
关于arrays - 算法:根据约束对数组中的对象进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18000211/