I have been working on a file parser that takes a very specific file format and parses it into a list that is arranged into node data and the neighbors that it relates to. I am new to Python (this is my very first program in this language), so I am not familiar with more advanced methods of solving the problem using Python.
The program runs very quickly: I get an average of about
Elapsed time: 0.0006923562137193841 with a test file, but think it could be even better, especially if I task it with a significantly larger file.
Seeking from question:
- Optimization in the form of cleaner methods
- Decrease the overall runtime
- Verification of estimated runtime: \$O(N * E)\$. I got this because there are
Nnodes, which each contain
Eedges. However, this may or may not be incorrect.
- General style comments for Python coding
Input file example:
The following would be 1 line of data in the file. This file could contain thousands of lines, each line identifying a node and the neighbors that it has.
100 Alpha 123 321 ((101,Beta,123,321)(101,Gamma,123,321)(102,Alpha,123,321)(103,Alpha,123,321)(104,Beta,123,321)(105,Alpha,123,321)(099,Gamma,123,321)(098,Beta,123,321)(097,Beta,123,321)(222,Gamma,123,321)(223,Beta,123,321)(234,Gamma,123,321)(451,Beta,123,321)(999,Beta,123,321)(879,Gamma,123,321)(369,Gamma,123,321)(741,Beta,123,321)(753,Beta,123,321)(357,Beta,123,321)(159,Alpha,123,321))
The parsing would end with the line containing only
"At the last row".
import os import timeit __author__ = 'Evan Bechtol' """ Parses through a file given the appropriate filepath. Once a filepath has been received, the Parser instance opens and begins parsing out the individual nodes and their neighbor node relationships. Each node is an index of the nodeList, which contains a sub-list of the nodes that are neighbors of that node. The structure is created as follows: nodeList: A list that is 'n' nodes long. The sub-list containing neighbors is of length 'e', where 'e' is the number of neighbor-edges. numNeighbors: A list that contains the number of neighbors for each node from 0 to (n-1) Resulting runtime of class: O(N*E) """ class Parser: # Constructor accepting filepath for file to read # as am argument. The constructor also calls readFile with # the filepath to begin parsing the specific file. def __init__(self, filePath): self.nodeList =  self.numNeighbors =  self.readFile(filePath) # Add nodes the the nodeList in order that they appear def setNodeData(self, id, sector, freq, band, neighborList): tmpData = ((id), (sector), (freq), (band), (neighborList)) return tmpData # Add neighbors to the neighborList in the order that they appear def setNeighborData(self, id, sector, freq, band): tmpData = ((id), (sector), (freq), (band)) return tmpData # Returns the entire nodeList as a string def getNodeList(self): return str(self.nodeList) # Return a specific node of the nodeList with all of its' neighbors def getNodeListIndex(self, index): return str(self.nodeList[index]) # Return a specific neighbor for a given node def getNodeNeighbor(self, node, neighbor): return str(self.nodeList[node][neighbor]) # Retrieves the location of the line to begin retrieving node and # neighbor data in the file. This eliminates any data above the actual # data required to build node and neighbor relationships. def searchForStartLine(self, data): startLine = "-default- - - - - " numLines = 0 for line in data: numLines += 1 if startLine in line: return numLines # Removes parenthesis from the line so that neighbors can be parsed. # Returns the line with all parenthesis removed and individual neighbors # are separated by spaces. def removeParens(self, line): # First, remove all parenthesis line = line.strip("((") line = line.strip("))") line = line.replace(")(", " ") return line # Splits the provided line into the required sections for # placement into the appropriate lists. # The reference node is parsed first and stored into the nodeList # # Once the nodeList is updated, the neighbor data is then parsed from # the line and stored in the neighborList for the reference node. def splitLine(self, line): # Separate into individual reference nodes splitLine = line.split() line = self.extractNode(line, splitLine) # Get each individual node from the specific line. This is referred to as the # "reference node", which represents the node that we will be creating a specific # list of neighbors for. # Each reference node is unique and contains a unique neighborList. def extractNode(self, line, splitLine): # Get all of the node data first and store in the nodeList nodeId = splitLine sector = splitLine freq = splitLine band = splitLine line = self.removeParens(splitLine) # Separate into individual neighbors neighbor = line.split() # Contains the number of neighbors for each reference node self.numNeighbors.append(len(neighbor)) # Place each neighbor tuple into the neighborList neighborList = self.extractNeighbors(neighbor) self.nodeList.append(self.setNodeData(nodeId, sector, freq, band, neighborList)) return line # Get the parsed list of neighbors for all nodes, then append # them to the neighborList in order that they are read. def extractNeighbors(self, neighbor): # Create a temporary storage for the neighbors of the reference node neighborList =  # Separate each neighbor string into individual neighbor components for i in range(len(neighbor)): neighbor[i] = neighbor[i].replace(",", " ") neighbor[i] = neighbor[i].split() nodeId = neighbor[i] sector = neighbor[i] freq = neighbor[i] band = neighbor[i] # Append the components to the neighborList neighborList.append(self.setNeighborData(nodeId, sector, freq, band)) return neighborList # Read the file and remove junk data, leaving only the node and neighbor # data behind for storage in the data structure def readFile(self, fileName): # Check if the file exists at the specified path if not os.path.isfile(fileName): print ('File does not exist.') # File exists, will attempt parsing else: with open(str(fileName)) as file: data = file.readlines() # Look for the first sign of data that we can use, read from that location currentLine = self.searchForStartLine(data) # Read from file until we find the last line of data that we need lastLine = "At the last row" for line in data: if lastLine in data[currentLine + 1]: break else: nodeId = data self.splitLine(data[currentLine]) currentLine += 1 return file.read() # Read file, given the exact file path startTime = timeit.timeit() parse = Parser("<file_path>") #print(parse.getNodeNeighbor(1, 0)) print (parse.nodeList) endTime = timeit.timeit() print ("Elapsed time: " + str(endTime - startTime))