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(',')
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
Also try calling gc.collect in each iteration.
It is possible to solve the problem without creating "big" variables like
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:
smallest_number_limit = 0;
candidate = float('inf')
for number in numbers():
if candidate > number > smallest_number_limit:
candidate = number
if float('inf') == candidate:
smallest_number_limit = candidate
previous = next(numbers)
for number in numbers:
yield number - previous
previous = number
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
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.