用于选择机器组的数据结构
我有一个旧的批处理系统。调度器将所有计算节点存储在一个大数组中。这在很大程度上是可以的，因为大多数查询都可以通过过滤满足查询的节点来解决。
我现在遇到的问题是，除了一些基本属性( cpus、内存、OS的数量)之外，还有一些奇怪的分组属性(city、infiniband、network )。
现在的问题是，当用户请求使用infiniband的节点时，我不能只给他任何节点，而是必须给他连接到一个infiniband交换机的节点，这样节点就可以使用infiniband进行通信。
如果用户只请求一个这样的属性(我只需要对每个属性的数组进行分区，然后尝试分别选择每个分区中的节点)，这还是可以的。
问题在于合并多个这样的属性，因为这样我就必须生成子集的所有组合(主数组的分区)。
好的是，大多数属性都处于子集或等价关系中(对于位于一个城市的infiniband交换机上的机器来说，这是有意义的)。但不幸的是这不是严格意义上的事实。
有什么好的数据结构来存储这种半层次的、多树的东西吗？
编辑:示例
node1 : city=city1, infiniband=switch03, networkfs=server01
node2 : city=city1, infiniband=switch03, networkfs=server01
node3 : city=city1, infiniband=switch03
node4 : city=city1, infiniband=switch03
node5 : city=city2, infiniband=switch03, networkfs=server02
node6 : city=city2, infiniband=switch03, networkfs=server02
node7 : city=city2, infiniband=switch04, networkfs=server02
node8 : city=city2, infiniband=switch04, networkfs=server02用户请求：
2x node with infiniband and networkfs所需的输出是：(node1, node2)、(node5,node6)或(node7,node8)。
在一个很好的情况下，这个例子不会发生，但在某些情况下，我们实际上有这些奇怪的跨站点连接。如果city2中的节点全部位于infiniband switch04上，那么就很容易了。不幸的是，现在我必须生成具有相同infiniband交换机和相同网络文件系统的节点组。
实际上，这个问题要复杂得多，因为用户不请求整个节点，而且属性很多。
编辑:为查询添加了所需的输出。
回答 4
Stack Overflow用户
发布于 2012-06-26 13:35:48
我猜不会有一个“简单有效”的算法和数据结构来解决这个问题，因为你所做的就像求解一组联立方程。假设总共有10个类别(如city、infiniband和network)，并且用户为其中的3个指定了所需的值。用户请求5个节点，比方说。然后，您的任务是推断其余7个类别的值，以便至少有5个记录存在，这些记录的所有10个类别字段都等于这些值(指定的3项和推断的7项)。可能有多种解决方案。
不过，如果不存在太多不同的类别，并且每个类别中也没有太多不同的可能性，那么您可以进行简单的强制递归搜索，以找到可能的解决方案，在每个递归级别上，您都考虑某个特定类别，并“尝试”每一种可能性。假设用户请求k记录，并可以选择通过required_city、required_infiniband等规定任何数量的需求：
either(x, y) := if defined(x) then [x] else y
For each city c in either(required_city, [city1, city2]):
For each infiniband i in either(required_infiniband, [switch03, switch04]):
For each networkfs nfs in either(required_nfs, [undefined, server01, server02]):
Do at least k records of type [c, i, nfs] exist? If so, return them.either()函数只是将搜索限制在包含用户给出的约束点的子空间的一种方法。
基于此，您将需要一种快速查找任意给定[c, i, nfs]组合的点数(行)的方法--嵌套哈希表在这方面工作得很好。
Stack Overflow用户
发布于 2012-06-26 13:56:29
步骤1:为每个属性创建一个索引。例如，对于每个property+value对，使用该属性创建一个已排序的节点列表。将每个这样的列表放入某种类型的关联数组中--类似于和stl映射，每个属性对应一个，并按值进行索引。这样，当您完成时，您有一个几乎恒定的时间函数，它可以返回与单个property+value对匹配的节点列表。列表只是按节点编号排序。
步骤2:给定一个查询，对于所需的每个property+value对，检索节点列表。
步骤3:从最短列表开始，将其命名为list 0，然后将其与其他列表中的每个列表进行比较，从而从列表0中删除不在其他列表中的元素。
现在，您应该只有请求了所有属性的节点。
您的另一个选择是使用数据库，它已经设置为支持这样的查询。它可以在内存中使用类似于带有SQL扩展的BerkeleyDB来完成。
Stack Overflow用户
发布于 2012-06-26 14:16:50
如果按照查询中提到的每个条件对列表进行排序是可行的(或者按照每个相关标准预先排序列表)，那么这是非常有效的。
所谓“相对标准”，我指的不是形式"x必须是5“的标准，这是很容易过滤的，但是表单的标准"x对于结果集中的每一项必须是相同的”。如果还存在"x必须是5“形式的条件，那么首先对它们进行筛选，然后执行以下操作。
它依赖于在多个列上使用稳定的排序来快速找到匹配的组(而不尝试组合)。
复杂性是查询中的节点数*查询中的条件数(对于算法本身)+节点数*日志(节点数)*条件数(如果不是预排序)。所以节点*日志(节点)*准则。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace bleh
{
class Program
{
static void Main(string[] args)
{
List<Node> list = new List<Node>();
// create a random input list
Random r = new Random();
for (int i = 1; i <= 10000; i++)
{
Node node = new Node();
for (char c = 'a'; c <= 'z'; c++) node.Properties[c.ToString()] = (r.Next() % 10 + 1).ToString();
list.Add(node);
}
// if you have any absolute criteria, filter the list first according to it, which is very easy
// i am sure you know how to do that
// only look at relative criteria after removing nodes which are eliminated by absolute criteria
// example
List<string> criteria = new List<string> {"c", "h", "r", "x" };
criteria = criteria.OrderBy(x => x).ToList();
// order the list by each relative criteria, using a ***STABLE*** sort
foreach (string s in criteria)
list = list.OrderBy(x => x.Properties[s]).ToList();
// size of sought group
int n = 4;
// this is the algorithm
int sectionstart = 0;
int sectionend = 0;
for (int i = 1; i < list.Count; i++)
{
bool same = true;
foreach (string s in criteria) if (list[i].Properties[s] != list[sectionstart].Properties[s]) same = false;
if (same == true) sectionend = i;
else sectionstart = i;
if (sectionend - sectionstart == n - 1) break;
}
// print the results
Console.WriteLine("\r\nResult:");
for (int i = sectionstart; i <= sectionend; i++)
{
Console.Write("[" + i.ToString() + "]" + "\t");
foreach (string s in criteria) Console.Write(list[i].Properties[s] + "\t");
Console.WriteLine();
}
Console.ReadLine();
}
}
}https://stackoverflow.com/questions/11207319
复制相似问题
腾讯云开发者
