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
N
nodes, which each containE
edges. 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][4][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[0]
sector = splitLine[1]
freq = splitLine[2]
band = splitLine[3]
line = self.removeParens(splitLine[4])
# 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][0]
sector = neighbor[i][1]
freq = neighbor[i][2]
band = neighbor[i][3]
# 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[0]
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[0][4][0])
endTime = timeit.timeit()
print ("Elapsed time: " + str(endTime - startTime))
readFile
checks for a file's existence and then simply prints a message if it can't find it. It's not really a style issue, but as a potential user of your Parser class, I think I would expect it to at least throw an exception in that case. You could bypess the existence check altogether and just letopen
throw an exception for you if it can't be opened. By the way, a file not existing is only one of the reasons a file could fail to be opened. See also "EAFP" in the Python glossary. \$\endgroup\$