0

大きなテキスト ファイル (116253 ワードで 1.08 MB) を読み込もうとしていますが、プログラムがテキスト ファイルの約 1/20 で停止するという問題が発生しています (関数で停止し、ステートメントをRead実行することさえできません)。 print)。

これが私が今持っている機能です:

from binary_search_tree import BinarySearchTree
from tree_node import TreeNode
import sys

sys.setrecursionlimit(5000000)

MovieTree = BinarySearchTree()

def Read(filename):
    file = open('movieData.txt')
    for line in file:
        MovieTree[line.strip()] = line
        print(line)
    file.close()

Read('movieData.txt')
print(MovieTree)

これは宿題であるため私に与えられた binary_search_tree と tree_node は、以前に使用されていたので機能すると仮定しています。

誰が問題が何であるかについて何か考えがありますか?

二分探索木:

from tree_node import TreeNode

class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__()

    def __str__(self):
        """Returns a string representation of the tree
           rotated 90 degrees counter-clockwise"""

        def strHelper(root, level):
            resultStr = ""
            if root:
                resultStr += strHelper(root.rightChild, level+1)
                resultStr += "| " * level
                resultStr += str(root.key) + "\n"
                resultStr += strHelper(root.leftChild, level+1)                
            return resultStr


        return strHelper(self.root, 0)


    def __contains__(self,key):
        if self._get(key,self.root):
            return True
        else:
            return False

    def get(self,key):
        if self.root:
            res = self._get(key,self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            return None

    def _get(self,key,currentNode):
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key,currentNode.leftChild)
        else:
            return self._get(key,currentNode.rightChild)

    def __getitem__(self,key):
        return self.get(key) 

    def __setitem__(self,k,v):
        self.put(k,v)

    def put(self,key,val):
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
        self.size = self.size + 1

    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key,val,currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key,val,
                                          parent=currentNode)
        else:
            if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key,val,
                                          parent=currentNode)

    def delete(self,key):
      if self.size > 1:
          nodeToRemove = self._get(key,self.root)
          if nodeToRemove:
              self.remove(nodeToRemove)
              self.size = self.size-1
          else:
              raise KeyError('Error, key not in tree')
      elif self.size == 1 and self.root.key == key:
          self.root = None
          self.size = self.size - 1
      else:
          raise KeyError('Error, key not in tree')

    def __delitem__(self,key):
        self.delete(key)


    def remove(self,currentNode):
      if currentNode.isLeaf(): #leaf
        if currentNode == currentNode.parent.leftChild:
            currentNode.parent.leftChild = None
        else:
            currentNode.parent.rightChild = None
      elif currentNode.hasBothChildren(): #interior
        succ = currentNode.findSuccessor()
        succ.spliceOut()
        currentNode.key = succ.key
        currentNode.payload = succ.payload

      else: # this node has one child
        if currentNode.hasLeftChild():
          if currentNode.isLeftChild():
              currentNode.leftChild.parent = currentNode.parent
              currentNode.parent.leftChild = currentNode.leftChild
          elif currentNode.isRightChild():
              currentNode.leftChild.parent = currentNode.parent
              currentNode.parent.rightChild = currentNode.leftChild
          else:
              currentNode.replaceNodeData(currentNode.leftChild.key,
                                 currentNode.leftChild.payload,
                                 currentNode.leftChild.leftChild,
                                 currentNode.leftChild.rightChild)

        else:
          if currentNode.isLeftChild():
              currentNode.rightChild.parent = currentNode.parent
              currentNode.parent.leftChild = currentNode.rightChild
          elif currentNode.isRightChild():
              currentNode.rightChild.parent = currentNode.parent
              currentNode.parent.rightChild = currentNode.rightChild
          else:
              currentNode.replaceNodeData(currentNode.rightChild.key,
                                 currentNode.rightChild.payload,
                                 currentNode.rightChild.leftChild,
                                 currentNode.rightChild.rightChild)

ツリーノード:

class TreeNode:
   def __init__(self,key,val,left=None,right=None,
                                       parent=None):
      self.key = key
      self.payload = val
      self.leftChild = left
      self.rightChild = right
      self.parent = parent

   def hasLeftChild(self):
      return self.leftChild

   def hasRightChild(self):
      return self.rightChild

   def isLeftChild(self):
      return self.parent and \
             self.parent.leftChild == self

   def isRightChild(self):
      return self.parent and \
             self.parent.rightChild == self

   def isRoot(self):
      return not self.parent

   def isLeaf(self):
      return not (self.rightChild or self.leftChild)

   def hasAnyChildren(self):
      return self.rightChild or self.leftChild

   def hasBothChildren(self):
      return self.rightChild and self.leftChild

   def replaceNodeData(self,key,value,lc,rc):
      self.key = key
      self.payload = value
      self.leftChild = lc
      self.rightChild = rc
      if self.hasLeftChild():
          self.leftChild.parent = self
      if self.hasRightChild():
          self.rightChild.parent = self

   def __iter__(self):

      if self:
         if self.hasLeftChild():
              for elem in self.leftChild:
                 yield elem
         yield self.key
         if self.hasRightChild():
              for elem in self.rightChild:
                 yield elem

   def findSuccessor(self):
      succ = None
      if self.hasRightChild():
          succ = self.rightChild.findMin()
      else:
          if self.parent:
              if self.isLeftChild():
                  succ = self.parent
              else:
                  self.parent.rightChild = None
                  succ = self.parent.findSuccessor()
                  self.parent.rightChild = self
      return succ

   def findMin(self):
      current = self
      while current.hasLeftChild():
          current = current.leftChild
      return current

   def spliceOut(self):
      if self.isLeaf():
         if self.isLeftChild():
            self.parent.leftChild = None
         else:
            self.parent.rightChild = None
      elif self.hasAnyChildren():
         if self.hasLeftChild():
            if self.isLeftChild():
               self.parent.leftChild = self.leftChild
            else:
               self.parent.rightChild = self.leftChild
            self.leftChild.parent = self.parent
         else:
            if self.isLeftChild():
               self.parent.leftChild = self.rightChild
            else:
               self.parent.rightChild = self.rightChild
            self.rightChild.parent = self.parent
4

2 に答える 2

1

1.08 MB は小さなファイルです。BinarySearchTree を使用する理由 これは、データをディクショナリにダンプすることで簡単に処理できます。

BinarySearchTree が割り当ての一部である場合、バグがあるように見えます。その _put() メソッドからトレースを開始します。

ところで、sys.setrecursionlimit(5000000)問題を回避するために使用しないでください。データのサイズが 2^5000000 程度でない限り、適切な二分探索はこの制限に達しません。バランスのとれた二分木を持つ 116253 語の場合、12 レベルの再帰のみが必要です。

于 2012-11-13T18:39:09.593 に答える
1

ここでもスタックオーバーフローでクラッシュします。

あなたのコードには再帰が含まれていないので、それはあなたの先生があなたに与えたクラスの中になければなりません. メソッドでオーバーフローが発生していると思いますput(self, key, val)

残念ながら、私は Python をほとんど知らないので、これ以上のヘルプを提供することはできません。

于 2012-11-13T16:22:56.827 に答える