8
\$\begingroup\$

I'm solving easy CodeEval challenges in Python 2.7. Usually my solutions use around 256 bytes of memory according to CodeEval. With Road Trip however while time used is still low (30-40ms), memory is >5881866 bytes. As I'm somewhat of a beginner, is there an easy way to decrease memory usage?

For each test case, which consists of one line of input that lists cities and their locations on a line, the task is to find the incremental distances when visiting them all. Input follows the template ("city_name", distance;"city_name", distance;):

Rkbs,5453; Wdqiz,1245; Rwds,3890; Ujma,5589; Tbzmo,1303;
Vgdfz,70; Mgknxpi,3958; Nsptghk,2626; Wuzp,2559; Jcdwi,3761;
Yvnzjwk,5363; Pkabj,5999; Xznvb,3584; Jfksvx,1240; Inwm,5720;
Ramytdb,2683; Voclqmb,5236;

The data set is pretty big for this challenge:

  • The route length is an integer in range [10000, 30000]
  • The number of cities is in range [500, 600]

My solution is as follows:

test_cases = open(file)
for line in test_cases:
    line = line.strip()
    if line == "": continue
    line = line.replace(';', ' ').replace(',', ' ').split()
    distances = sorted(map(int, [line[i] for i in range(1, len(line), 2)]))
    result = [distances[i] - distances[i-1] for i in range(1, len(distances))]
    result.insert(0, distances[0])
    print ','.join(map(str, result))
\$\endgroup\$
  • 1
    \$\begingroup\$ You probably want to think about some solution that uses generators... You can start by looking at this until someone posts a more detailed answer \$\endgroup\$ – BusyAnt Jul 19 '16 at 15:26
5
\$\begingroup\$

I don't think it's a good idea to preprocess the line so much. line = line.strip() duplicates the line, for no benefit. I don't know why if line == "": continue should be needed. line = line.replace(';', ' ').replace(',', ' ').split() degrades the data, and takes two passes to do it.

Here's how I would read the input:

for line in fileinput.input():
    route = itertools.chain([0], sorted(
        int(city.group(1)) for city in re.finditer(r'[A-Za-z]+,(\d+);', line)
    ))

Using fileinput.input() will let you take input from either a file specified on the command line, or sys.stdin if no file is specified. re.finditer() will look for the pattern and capture the numbers that you need.

In Python 2, you should use xrange() instead of range(). However, if you capture just the numbers, as I've done above, then you wouldn't need to use range() or xrange() to extract every other item.

Each of your list comprehensions results in another temporary copy of the data. result.insert(0, distances[0]) is also bad for performance, since every entry must be copied to make room for one entry at the front of the list.

To finish off the solution, I would do this:

print(','.join(str(b - a) for a, b in pairwise(route)))

… using the pairwise() recipe from itertools.

\$\endgroup\$
  • \$\begingroup\$ I had to read a bit to follow every suggestion you've made. According to codeeval using your methods for getting the distances and building the output, memory usage drops to 2,985,984 bytes - quite an improvement, although I would've expected a value way below 1 MB. Thank you very much for the tips - my experience with re and itertools is almost non-existent, so I have to fix that. Strangely - removing only the list insertion last night had no effect on either memory or space performance, but I understand how it's a bad practice in this case. Thanks! \$\endgroup\$ – Alaris Jul 20 '16 at 10:33
1
\$\begingroup\$

The code seems fine, although I'd like to replace cryptic line-parsing line with something more expressive, like:

distances = set()
for city_info in line.strip().split(';'):
    if not city_info: continue
    name, distance = city_info.strip().split(',')
    distances.add(distance)

Also, you insert to the beginning of the list. This is not that fast and can be trivially replaced. Say, last 2 lines of your code could be replaced with something like:

print '0,' + ','.join(map(str, result))

Or maybe even like:

print '0,' + ','.join(str(distance_diff) for distance_diff in result)

if 2.7 supports this and if you find comprehensions more comprehensible than maps (many people do, but again, many people don't and there is a difference in performance, too).

is there an easy way to decrease memory usage?

First of all, it'd be nice to know how memory usage is measured. Several programs using around 256 bytes looks a bit suspicious to me, there may be caveats that are not obvious.

Still, ~10 kb to process a pair of city name and an integer looks a bit too much.

If we're talking about simple solutions, that doesn't include looking into how GC (of Python implementation used at CodeEval) works. Let's simply use del on every "big" variable after we're done with it: you don't need line when you have your distances, and you don't need your distance's when you have your result.

Also try calling gc.collect in each iteration.


It is possible to solve the problem without creating "big" variables like distance and result. You will need to have an iterator over numbers in the line that does not use O(n) memory - let's call it numbers(line). We'll also need following stuff:

def low_footprint_sort(numbers):
    smallest_number_limit = 0;
    while True:
        candidate = float('inf')
        for number in numbers():
            if candidate > number > smallest_number_limit:
                candidate = number
        if float('inf') == candidate:
            break
        else:
            yield candidate
            smallest_number_limit = candidate

def neighbour_diffs(numbers):
    previous = next(numbers)
    for number in numbers:
        yield number - previous
        previous = number

With that, neighbour_diffs(low_footprint_sort(lambda: numbers(line))) would give you numbers you'd have in your result without additional O(n) memory footprint.

Then you use the same approach - instead of constructing large string via join, you print numbers one by one.

That code sacrifices performance and readability for tiny gains in memory consumption (which would only come to play after your lists are big enough - generators have their housekeeping too). You could also try more sophisticated reading from file, that eliminates the need for storing line in memory too.

That would result in an overengineered contraption with memory consumption (theoretically) independent of string length and number of strings, yay!


However, that being possible certainly does not mean it's a good idea.

You should generally find yourself on the other end of these tradeoffs.

If you were interested in low-hanging fruit - try fiddling with dels and collect()s. I don't see other obvious solutions that are better.

If you were interested in a bit more challenging ways to curb the memory footprint even if it costs some complexity - well, there are ways too.

Either way, it's only suitable for programming puzzles.

\$\endgroup\$
1
\$\begingroup\$

One way to conserve memory is to eliminate the results list and just print the differences directly from distances:

    sys.stdout.write(str(distances[0])+',')
    for i in range(1,len(distances)-1):
        sys.stdout.write(str(distances[i] - distances[i-1])+',')
    print(str(distances[i+1] - distances[i]))
\$\endgroup\$
  • \$\begingroup\$ Indeed, the large results list appears useless. Your code however need to look like this to work: sys.stdout.write(str(dist[0])) for i in range(1,len(wtf)): sys.stdout.write(',' + str(dist[i] - dist[i-1])) sys.stdout.write('\n') Thanks for introducing me to sys.stdout.write() :) \$\endgroup\$ – Alaris Jul 20 '16 at 10:49
  • \$\begingroup\$ @Alaris - Actually both will work equally well. But, in my example, there is one less operation since print automatically adds '\n'. \$\endgroup\$ – tinstaafl Jul 20 '16 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.