получение «не поддерживается между экземплярами« кортеж »и« список »» при добавлении объекта в приоритетную очередь - PullRequest
Новая
       23

получение «не поддерживается между экземплярами« кортеж »и« список »» при добавлении объекта в приоритетную очередь

0 голосов
/ 05 июня 2019

Я пытаюсь добавить пару элементов в приоритетную очередь.Когда я пытаюсь добавить элемент, я получаю эту ошибку: 

"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)

1 Ответ

0 голосов
/ 07 июня 2019

Я нашел виновника ошибки :).

Класс queue.PriorityQueue работает путем хранения списка элементов. Всякий раз, когда вы .put что-то вводите, он сравнивает его, используя < и >, чтобы найти место для вставки. «.get» просто вытолкнет его из уже отсортированного списка.

Из-за того, что tuple и list нельзя сравнивать, .put завершается ошибкой. Это также может быть связано с тем, что вы можете изменить список после, что приведет к разрыву очереди приоритетов.

Простое исправление - изменить строку в repsInS с 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)
...