Python algorithm mimicking mark/sweep garbage collection I don't have much experience with Python and would love some feedback on my implementation of this program.

I am given a file with an integer representing a number of memory-cells, followed by a list of ordered pairs representing links between either a pointer and a memory-cell, or memory-cell and a memory-cell. You could use the list to draw diagram akin to those used in text-book "which cells are marked and which are reclaimed" problems regarding mark/sweep GC.

I was tasked with creating a Python script that takes in such a list, and runs a simulated mark/sweep on it and my solution (below) is fully functional.

Here's an example input file:



6
ptr1,0
0,1
1,2
ptr2,3
3,2
4,5


And here is the script:



import sys
import re

def RepresentsInt(s):
    try: 
        int(s)
        return True
    except ValueError:
        return False

#recursive function that traces through a mem-node structure
#setting each node's check_flag to 1 if traversed
def node_trace(pointer, node_pointer_list, nodes_dict):
    if RepresentsInt(pointer[0]):
        if nodes_dict[pointer[0]][1] == 1:
            #returns if the current node has been traversed already
            return
        else:
            #checks the current node as marked and traversed
            nodes_dict[pointer[0]][0] = 1
            nodes_dict[pointer[0]][1] = 1

    for x in node_pointer_list:
    #recurs for each node the current node points to
        if x[0] == pointer[1] and nodes_dict[x[0]][1] == 0:
            node_trace(x, node_pointer_list, nodes_dict)

        #catches the node at the end of a chain
        if RepresentsInt(x[0]):
            if nodes_dict[x[0]][1] == 1:
                nodes_dict[x[1]][0] = 1
                nodes_dict[x[1]][1] = 1
        else:
        #catches a single-link chain from a variable to a mem-block
            nodes_dict[x[1]][0] = 1
            nodes_dict[x[1]][1] = 1


sysArgs = list(sys.argv)
inputFile = sysArgs[1]
inFile = open(inputFile)
node_pointer_list = []
nodes_dict_0 = {}      #contains node records of the format, ['mem-cell': traversed_flag, marked_flag]
                       #traversed/marked _flag is 0 if unchecked, 1 if checked

#read, parse, and store the contents of the input file
node_count = 0
for line in inFile:
    #grabs the number of nodes which is stored in the first line of the file
    if node_count == 0:
        node_count = int(line)
    else:
        #read and parse a line as required
        splitLine = line.rstrip()
        splitLine = re.split(r'[,]', splitLine)

        node_pointer_list.append([splitLine[0], splitLine[1]])



#create a dictionary for all nodes, with flags for "checked" and "traversed"
#initialized to 0
count = 0
while count &lt; node_count:
    nodes_dict_0[str(count)] = [0, 0]
    count += 1

#simulates the mark phase of a mark-sweep algorithm using the
#reference structure described in the input file
for item in node_pointer_list:
    if not RepresentsInt(item[0]):
        #if the link begins with a variable pointer
        #follow the trace marking all nodes along the way
        node_trace(item, node_pointer_list, nodes_dict_0)

print("\nMarked: ")
for item in sorted(nodes_dict_0.items()):
    if item[1][1] == 1:
        print(item[0])

print("\nReclaimed: ")
for item in sorted(nodes_dict_0.items()):
    if item[1][1] == 0:
        print(item[0])


Running the above script with the example input file produces the following output:



Marked:
0
1
2
3

Reclaimed:
4
5


which is correct.

My question simply this: Is the way I implemented this a reasonable solution or are there egregious inefficiencies, needlessly roundabout approaches etc that wouldn't be obvious to an novice that I could improve-on beyond just providing the required functionality?

More specifically: is a recursive algorithm the best approach in python? Is using a dictionary to track the marked status of nodes the most efficient way to do so? Is the way I structured the algorithm as efficient as it could be in terms of big-O?
There are several suboptimal areas of this solution that are interrelated. Please feel free to ask questions if anything I've written here is unclear.

The solution is not "modeling" memory and then performing mark-and-sweep as it probably should be. Instead it is preserving the data-input file in node_pointer_list and repeatedly walking it to find what is needed, because of your for x in node_pointer_list: in node_trace(). This is causing the solution to unnecessarily iterate over the node_pointer_list inside each call to node_trace(), which is making its running time O(N^2) when it should be O(N). It is also making the code 2-3x longer than it should be. Further, the solution is quite hard to read.

I'll try to break down those issues one at a time, though keep in mind they are all interrelated. I'm intentionally explaining rather than providing code, so you can do the learning work to make a better solution. I'll start by talking about code readability.

The way you use if not RepresentsInt(item[0]): to determine if a line is a "pointer" line is very non-intuitive. It would be easier to read if the literal "ptr" appeared somewhere near where you are testing if it is a line containing "ptr", such as:

if item[0].find("ptr") == 0:


Why do you have both "marked" and "traversed" flags? They contain the same information.

A code line like this below, is very hard for anyone to read the meaning of. Someone reading the code is forced to dig around to find out the meaning of the zeroes and ones to understand it.

nodes_dict[x[1]][0] = 1


To make it more readable, you need to get the word "TRAVERSED" in there somewhere, since what you are doing is setting a traversed flag. If you stick with your two element arrays, you can make a TRAVERSED_FLAG symbol to make it more readable, as in:

nodes_dict[x[1]][TRAVERSED_FLAG] = 1


Better style would be to define a class, and give the class a .traversed field. If you also make some of the other changes I highlight below, this access becomes: 

current_object.traversed = 1


I don't know if you are comfortable with classes or not, so I'll provide one explanation based on classes, and one based on arrays...

With Classes

You can put the marked field, and the list of an object's references in a single class that represents a memory position in your heap. The class definition would look something like:

class MemoryObject:
    def __init__(self):
        self.marked = 0
        self.references = []  # list of either &lt;int&gt; or &lt;MemoryObject&gt;


First you would instantiate an array of these for the number of memory-spaces according to your data-file, with an additional one as the RootMemoryObject. Then you would walk the file's references, adding to each MemoryObject's references list. You can either store an int reference in the list, and look it up later, or you can look up the MemoryObject now and store that directly in references. When you see a "ptr" entry, you put that in the RootMemoryObject.

The first step of mark-and-sweep is to walk all memory locations and set .marked=0. Then you would call node_trace(RootMemoryObject), which would mark the object visited, and recurse through the objects referenced by that object's .references. Because you have the list of that object's references, you don't need the inefficient loop for x in node_pointer_list:.

Without Classes

Instead of node_pointer_list, you want an array of lists of references. As you walk the datafile, you would insert each reference into the appropriate list for that pointer number. Further, you want an additional "root_references" list to hold references which appear in "ptr" entries.

To start the recursion, you would do for reference in root_references: node_trace(reference), which would mark the reference visited (returning if it was already visited), then look up each child reference and recursively call node_trace(child_reference) on it. Because you have the list of that object's references, you don't need the inefficient loop for x in node_pointer_list:.

Other Factors

The running time you are shooting for is O(N), where N is the number of nodes in your memory. You are currently O(N^2). After you remove the extra loop in node_trace(), you will be properly O(N) because you already have a check to be sure you're not traversing a set of children more than one.

Using recursion is good. An alternative is to use a work-list. To use a work list, you put the root(s) in a list, and then while the work-list is non-empty, you remove an item from the work-list and call node_trace() on it. node_trace puts any child nodes that need to be visited into the work list, and exits. 

Both will have the same O(N) running time, but can potentially have different memory consumption. The recursive version's maximum memory consumption is proportional to the depth of object references. The work-list version's maximum memory consumption is hard to calculate, as it can be wildly different based on how you prioritize the work list and what your in-memory objects look like.

If you have 1000 objects in a linked list, each pointing to the next, the work-list will only require 1 entry, whereas the recursive version will require a 1000 depth stack. However, if instead you have 1 object with 999 pointers to leaf objects, then the recursive version will only require a maximum of 1 stack frame, while the work list will have a maximum of 999 entries. So you can see neither is better universally, there are just tradeoffs.