时间戳

首页 > 解决方案 > 将对象添加到优先级队列时，“在 'tuple' 和 'list' 的实例之间不受支持”

python - 将对象添加到优先级队列时，“在 'tuple' 和 'list' 的实例之间不受支持”

问题描述

我试图将一对元素添加到优先级队列中。当我尝试添加一个元素时，我得到了这个错误：

"TypeError: < not supported between instances of 'tuple' and 'list'"

我应该使用另一种方式将元素添加到 priorityQueue 而不是 .put() 吗？

我试图找出一个霍夫曼节点

import queue
S = "testString"
map = [chr(i) for i in range(ord('a'),ord('z')+1)]
aux = auxTemp = list()
freqs = list()

def repsInS(S,map):
    reps = 0
    for i, value in enumerate(map):
        for j, value in enumerate(S):
            if(map[i]==S[j]):
                reps+=1
        aux.append(map[i])
        aux.append(reps)
        auxTemp = aux.copy()
        freqs.append(auxTemp)
        aux.clear()
        reps = 0
        freqs.sort(key= lambda x:x[1])
    return freqs

frecuencias = repsInS(S,map)

class NodoHuffman(object):
    def __init__(self, left=None, right=None, root=None):
        self.left = left
        self.right = right
        self.root = root

    def hijoTemp(self):
        return((self.left, self.right))


def HuffmanTree(frecuencias):
    objs = queue.PriorityQueue()
    for i in frecuencias:
        objs.put(i)

    while (objs.qsize() > 1):
            left = objs.get()
            right = objs.get()
            newNode = NodoHuffman(left,right)
            objs.put((left[1]+right[1],newNode))
    return objs.get()

huff = HuffmanTree(frecuencias)

标签： pythonclasssortinghuffman-code

解决方案

我找到了错误背后的罪魁祸首:)。

该类的工作方式queue.PriorityQueue是存储项目列表。每当您插入.put某些东西时，它都会使用它进行比较<并>找到将其插入的位置。'.get' 将简单地从已经排序的列表中弹出它。

因为tuple和list不能比较，所以.put失败了。这也可能是因为以后可以更改列表，导致优先级队列中断。

repsInS一个简单的解决方法是将with中的行更改freqs.append([t, reps])为freqs.append((t, reps))。

编辑：看起来还有更多......优先级队列使用对象的丰富比较魔术方法对它们进行排序。相反，我让它们使用普通列表并让节点节省自己的重量。这节省了类的复杂性并使代码更易于理解。

这是固定和抛光的代码。

import queue

test_str = 'testString'
test_list = [chr(i) for i in range(ord('a'), ord('z') + 1)]


class HuffmanNode:
    def __init__(self, weight, left=None, right=None, info=None):
        self.weight = weight
        self.left = left
        self.right = right
        self.info = info

    def hijoTemp(self):
        return self.left, self.right


def get_repeats(S, T):
    freqs = []

    for t in T:
        reps = 0
        for s in S:
            if s == t:
                reps += 1
        freqs.append((reps, t))

    freqs.sort(key=lambda x: x[0], reverse=True)
    return freqs # Return list of lists


def create_huffman_tree(freqs):
    objs = [HuffmanNode(w, info=l) for w, l in freqs]
    objs.sort(key=lambda node: node.weight, reverse=True)

    while len(objs) > 1:
        left, right = objs.pop(), objs.pop()
        weight = left.weight + right.weight
        objs.put(HuffmanNode(weight, left, right))

    return objs.pop()

if __name__ == '__main__':
    frecuencias = get_repeats(test_str, test_list)
    huffman_tree = create_huffman_tree(frecuencias)

推荐阅读