1. Bug
If the city contains two identical buildings then skyline
raises an exception:
>>> skyline(deque([(1, 2, 3), (1, 2, 3)]))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "cr66776.py", line 97, in skyline
delete(heapq.heappop(buildings_by_R)[1])
File "cr66776.py", line 87, in delete
buildings_by_H[b[1]].remove(b)
KeyError: 2
This is because the code represents buildings by tuples of numbers, and that means that two identical buildings get stored just once in a set, so when you come to remove the second building, it's not there. To fix this, buildings need to be represented such that each building is unique. One way to do this would be to use a Building
class, as objects are always unique unless they implement an __eq__
method.
2. Review
It's not clear to the reader how the data is represented. The variable b
represents a building, but what are b[0]
, b[1]
and b[2]
? These are the building's left x-coordinate, height, and right x-coordinate respectively, so it would make the code a lot easier to read if these were b.left
, b.height
, and b.right
. It's easy to do this using a class, or collections.namedtuple
.
It's not clear exactly what the helper functions add_point
, insert
, delete
do. In particular, add_point
doesn't always add a point to the skyline list: sometimes it updates the last point in the list. The insert
function adds a building to the buildings_by_R
and buildings_by_H
collections, but also calls add_point
. These functions could do with comments explaining what exactly it is that they do.
Some of the operations could do with a comment to explain their purpose. For example here:
h = buildings_by_H.iloc[-1] if buildings_by_H else 0
It would be worth noting that this finds the height of the highest building currently standing.
The insert
and delete
helper functions are only called once, so there's no particular advantage to making them into functions. The code might be clearer if these functions were inlined at the point of use.
The insert
function contains the following lines of code that manipulate the vaguely named sets
parameter:
def insert(b, sets=[set()]):
s = buildings_by_H.setdefault(b[1], sets[0])
s.add(b)
if s == sets[0]:
sets[0] = set()
It looks as if there was a concern that if the code were written in the obvious way:
def insert(b):
buildings_by_H.setdefault(b[1], set()).add(b)
then a set()
object would be created and immediately discarded each time a building was inserted at a position for which buildings_by_H
already had an entry. This is a valid concern, but the following would seem to be a clearer way to handle it:
def insert(b):
try:
s = buildings_by_H[b[1]]
except KeyError:
buildings_by_H[b[1]] = s = set()
s.add(b)
It's worth making a little effort to avoid using libraries that are not built into Python. Having to install sortedcontainers
is a small but genuine barrier to running code (and might partly account for the time this question has languished without being reviewed). In this case, SortedDict
is used to maintain the collection of currently standing buildings, such that (i) the height of the highest building can be found via buildings_by_H.iloc[-1]
; and (ii) the set of buildings at a given height can by located via buildings_by_H[b[1]]
and so a building can be removed.
However, we can implement (i) by storing the buildings in a heap, because as it says in the heapq
documentation:
The interesting property of a heap is that its smallest element is always the root, heap[0]
.
Python heaps are min-heaps but we want the highest building, so we have to reverse the comparison order on buildings. If buildings are represented by objects, as recommended in §1 above, then this can be done by implementing a __lt__
method on the Building
class.
How do we implement (ii)? You can't easily delete elements from a heap. The insight here is that we don't have to delete the building from the heap, we can leave it in the heap but mark it as finished (if buildings are represented by objects, as recommended in §1, above then this can be done by setting an attribute). We only care about the highest standing building, which is at the root of the heap, so we can just check that one to see if it is finished and pop it if so.
There's a lot of complexity in the add_point
function. This complexity is due to the fact that when add_point(x)
is called, we don't know whether or not we've processed all the buildings that start or end at x
, so when we construct a point (x, h)
we don't know whether we're done with it, or whether we might have to revise it later.
It would simplify this code considerably if we could be sure that all the buildings that start or end at x
have been processed. Then we would know that the point would not need to be revised, and we could just yield
it.
3. Revised code
from collections import defaultdict, namedtuple
from heapq import heappop, heappush
class Building:
def __init__(self, height):
self.height = height
self.finished = False
def __lt__(self, other):
# Reverse order by height, so that when we store buildings in
# a heap, the first building is the highest.
return other.height < self.height
# An event represents the buildings that start and end at a particular
# x-coordinate.
Event = namedtuple('Event', 'start end')
def skyline(buildings):
"""Given an iterable of buildings represented as triples (left, height,
right), generate the co-ordinates of the skyline.
>>> list(skyline([(1,9,3), (1,11,5), (2,6,7), (3,13,9), (12,7,16),
... (14,3,25), (19,18,22), (23,13,29), (24,4,28)]))
... # doctest: +NORMALIZE_WHITESPACE
[(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3),
(23, 13), (29, 0)]
>>> list(skyline([(1, 3, 2), (1, 3, 2)]))
[(1, 3), (2, 0)]
"""
# Map from x-coordinate to event.
events = defaultdict(lambda:Event(start=[], end=[]))
for left, height, right in buildings:
b = Building(height)
events[left].start.append(b)
events[right].end.append(b)
standing = [] # Heap of buildings currently standing.
last_h = 0 # Last emitted skyline height.
# Process events in order by x-coordinate.
for x, event in sorted(events.items()):
# Update buildings currently standing.
for b in event.start:
heappush(standing, b)
for b in event.end:
b.finished = True
# Pop any finished buildings from the top of the heap.
while standing and standing[0].finished:
heappop(standing)
# Top of heap (if any) is the highest standing building, so
# its height is the current height of the skyline.
h = standing[0].height if standing else 0
# Yield co-ordinates if the skyline height has changed.
if h != last_h:
yield x, h
last_h = h
4. Performance comparison
Test case (this is an order of magnitude bigger than the largest case specified in the problem description):
>>> from timeit import timeit
>>> import random
>>> R = lambda n:random.randrange(n) + 1
>>> buildings = sorted((x, R(10000), x + R(1000)) for x in (R(10000) for _ in range(50000)))
Original code:
>>> queue = deque(buildings)
>>> timeit(lambda:skyline(queue), number=1)
1.46421534800902
Revised code:
>>> timeit(lambda:list(skyline(buildings)), number=1)
0.9026356039103121
The revised code is about 40% faster than the original.