Skip to main content
 首页 » 编程设计

python之不同的结果取决于打印调用

2024年11月01日11Leo_wl

我决定实现一个小的霍夫曼编码脚本。在一个小的概率列表上测试它之后,我在构建过程中打印树时得到正确的结果,如果我不这样做则得到错误的结果。问题的原因可能是什么?

这是我的代码:

from __future__ import division 
import heapq 
 
 
class LeafNode: 
    def __init__(self,symbol,prob): 
        self.symbol = symbol 
        self.prob = prob 
    def __repr__(self): 
        return "(%s: %s)" % (self.symbol, self.prob) 
class InternalNode: 
    def __init__(self,prob,left,right): 
        self.prob = prob 
        self.left = left 
        self.right= right 
    def __repr__(self): 
        return "(internal : %s)" % (self.prob) 
 
def getDict(seq): 
    d = dict() 
    for symbol in seq: 
        if symbol in d: 
            d[symbol] += 1 
        else: 
            d[symbol] = 1 
    return d 
 
def returnProbList(seq): 
    data = getDict(seq) 
    sum_of_all = sum(data.values()) 
    l = sorted(data.items(), key=lambda x:x[1]) 
    return [LeafNode(x[0], x[1]/sum_of_all) for x in l] 
 
def createTree(probs): 
    heapq.heapify(probs) 
    while len(probs) > 1: 
        a = heapq.heappop(probs) 
        b = heapq.heappop(probs) 
        print a,b #removing this shows wrong results. 
        f = InternalNode(a.prob+b.prob,a,b) 
        heapq.heappush(probs,f) 
    return probs[0] 
 
def printSymbols(tree, seq = ''):     
    if isinstance(tree, InternalNode): 
        printSymbols(tree.left, seq+'0') 
        printSymbols(tree.right, seq+'1') 
    else: 
        print tree.symbol, seq 
 
s = "This is some short text I have written. It seems that space is the most common symbol." 
 
#l = returnProbList(s) 
l = [] 
l.append(LeafNode('a4',0.05)) 
l.append(LeafNode('a3',0.2)) 
l.append(LeafNode('a2',0.35)) 
l.append(LeafNode('a1',0.4)) 
 
 
 
#print l 
tree = createTree(l) 
printSymbols(tree) 

使用 pdb 调试它给了我什至不同的结果。

#Without print 
a4 00 
a3 01 
a2 10 
a1 11 
#With print 
a1 0 
a4 100 
a3 101 
a2 11 
#With pdb 
a1 0 
a2 10 
a3 110 
a4 111 

请您参考如下方法:

这真的与打印无关。你的问题在这里:

heapq.heappush(probs,f) 

f 是您的 InternalNode 类的实例,但该类未定义任何顺序。因此 Python 默认按内存地址排序 InternalNode 实例。这根本不是您想要的,内存地址会根据您执行的其他操作(打印、运行 PDB、创建或删除其他对象...)而有所不同。

最简单的解决方法是在你的类中添加一个 __cmp__ 方法:

    def __cmp__(a, b): 
        return cmp(a.prob, b.prob) 

那么输出就会一致。

编辑:嗯,您还获得了 LeafNode 实例的内存地址排序,因此也向其添加一个 __cmp__。