EDIT: Misstated the big-O, in this particular case (should've found my coworkers actual code). Both are O(m x n), one just has a large constant.
Here's a pattern I've noticed with code written for processing a data file by a lot of people (python-esque, using a function (match) that's "left as an exercise for the reader" to implement):
def search(filename, value):
with open(filename, "r") as f:
for line in f:
if match(value,line):
print(line)
# we don't care about not matching
def main():
for v in [search1, search2, search3, ...]:
search("data.dat", v)
What happened is that
one time they needed that search function, and so they made
search and it worked well. They realized they could run that same search function repeatedly, and for small data files and few searches it was quick enough. But the performance is O(m x n) [EDIT: originally wrote O(m x n)], where m is the number of lines, n is the number of search values. [EDIT: wrong: a second m because it takes a time proportional to the size of the file to
read the file.]
The data file is read every time something is searched. If you've got an SSD, it's not really noticeable. If you've got a spinning disk, it becomes a problem. If you're hitting network storage, you're downloading that file n times. The main issue being that each read (each iteration of the inner for) hits the hard drive, network, or similar. A simple performance hack is to move the read into main, put the whole thing into one list of lines and pass that list to search instead of the filename (modifying search appropriately):
def search(data, value):
for line in data:
if match(value,line):
print(line)
# we don't care about not matching
def main():
with open("data.dat", "r") as f:
data = f.read().splitlines()
for v in [search1, search2, search3, ...]:
search(data, v)
It's still O(m x n) [EDIT: It's now O(m x n). We've removed one of the m factors because we do the read once, and never again.]
For very large files and very large search parameter lists, this will still take a long time, but it's much faster than the previous version when you're dealing with large files.
EDIT:
Shortest code I can think of to get the actual worst case that I've had a few coworkers pull off:
def search(filename, value):
with open(filename, "r") as f:
data = f.read().splitlines()
for line in data:
if match(value,line):
print(line)
# we don't care about not matching
def main():
for v in [search1, search2, search3, ...]:
search("data.dat", v)
With, of course, other code in between because as vonmoltke points out, the above has clear problems. My point was about the structure of the bad pattern, not the specific implementation of it.