python - 输入特定值时在列表中定位字典

Question

假设我们有几个集群表示为下面的字典:

cluster1 = {'Disks' : [0,1,2,3,12] , 'left': True , 'right': False}
cluster2 = {'Disks' : [3,4,5,2] , 'left':True ,'right': False }
cluster3 = {'Disks' : [6,7,8,2] , 'left':False ,'right': False }
cluster4 = {'Disks' : [10,11,12] , 'left':True, 'right':True  }

Listofclusters = [cluster1,cluster2,cluster3,cluster4]

然后我像上面那样制作一个集群列表来存储它们....

如果我想在列表中搜索特定磁盘并希望它告诉我列表中的哪些集群具有这些磁盘我该怎么做？

Answer 1

根据您拥有的数据，应该这样做:

def findClusters(n, clusters):
    answer = []
    for cluster in clusters:
        if n in cluster['Disks']:
            answer.append(cluster)
    return answer

现在，这是一个线性算法。通过一些预处理，您应该能够显着提高运行时间:

def preprocess(clusters):
    """
    Given the list of clusters, return a dictionary that maps 
    Disk numbers to a list of clusters that have that disk
    """

    answer = {}
    for i,cluster in enumerate(clusters):
        for disk in cluster['Disks']
            if disk not in answer:
                answer[disk] = []
            answer[disk].append(i)

    return answer

def findClusters(preprocessedData, clusters, diskNum):
    answer = []
    for clusterid in preprocessedData[diskNum]:
        answer.append(clusters[clusterid])
    return answer

预处理需要线性时间，而实际搜索需要常数时间(找到相关簇)和线性时间(按照找到的簇数的顺序)来创建相关簇的列表