Click here to Skip to main content
14,492,728 members
Rate this:
Please Sign up or sign in to vote.
I want this python code in a more efficient languague as I'm getting "Killed by signal" or "Time limit exceeded" errors

What I have tried:

<pre>import sys


sys.setrecursionlimit(50000)

class Node:
    value = 0
    leaves = 1

    def __init__(self, value):
        self.value = value
        self.children = []

    def setNumOfLeaves(self):
        if node_checked and node_checked.keys() :
            return
        if not self.children:
            return 1
        self.leaves = 0
        for child in self.children:
            self.leaves += child.setNumOfLeaves()
        return self.leaves


n = int(input())
numbers = [int(i) for i in input().split()]
edges = []
nodes = [Node(count) for count in range(n + 1)]
for i in range(n):
    nodes[i] = Node(i)
for i in range(1, n):
    (nodes[numbers[i - 1]]).children.append(nodes[i + 1])
    edges.append((numbers[i - 1], i + 1))
output = 0
node_checked = {}
for edge in edges:
    nodes[edge[0]].setNumOfLeaves()
    node_checked[edge[0]] = True
    v2 = edge[1]
    output += (nodes[v2].leaves) * (nodes[1].leaves - nodes[v2].leaves)
print(output)
Posted
Updated 6-Jan-20 0:52am
Comments
Stefan_Lang 6-Jan-20 6:32am
   
Most languages will have a hard time with a recursion level of 50000! I don't know about Python, but in C/C++ you will have to set a compiler flag and tell it to increase the stack size accordingly. Otherwise your program will simply crash. Check your Python documentation to find out if you can likewise tell it to increase stack size.
Rate this:
Please Sign up or sign in to vote.

Solution 1

1. Learn C++
2. Write the application in C++.

Sorry, but this site does not provide free coding or conversion services.
   
v2
Rate this:
Please Sign up or sign in to vote.

Solution 2

Even if we provided such a service (which we don't) I'd strongly suggest that you don't do it.
When you translate languages, what you end up with isn't "more efficient"; quite the reverse, it's normally less efficient than the original because it isn't designed to work well in that language.
Python is - let's be polite - an interpreted language, C++ is compiled. Python is for beginners, who don't really know what they are doing. C++ is for experts, it's a big, powerful, language that supports a lot of frameworks; python supports one.

You don't get good code by translating: you get good code by designing to a languages strengths, and for a specific framework under which it will run.

So either use that as a specification for a new C++ app, or throw it away and write a proper C++ app to meet the specification / homework question (delete as applicable) that you already have to meet.
   
Rate this:
Please Sign up or sign in to vote.

Solution 3

How about solving the actual problem instead of trying to convert it?

I don't know python, but if I understand this part of the code correctly:
n = int(input())
numbers = [int(i) for i in input().split()]
edges = []
nodes = [Node(count) for count in range(n + 1)]
for i in range(n):
    nodes[i] = Node(i)
for i in range(1, n):
    (nodes[numbers[i - 1]]).children.append(nodes[i + 1])
    edges.append((numbers[i - 1], i + 1))

Then n is some arbitrary integer read from input, numbers is an array with a length determined by different input, and the for loop references elements of that array with indexes 0 through n-1. Do these elements even exist?

Also, the function setNumOfLeaves appears to be doing too many things at the same time: it's used both for initializing the branches/leaves, and for querying the children. Maybe it would help to separate that functionality.
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100