{"id":41,"date":"2020-07-31T13:18:00","date_gmt":"2020-07-31T17:18:00","guid":{"rendered":"https:\/\/andygrigg.com\/?p=41"},"modified":"2020-08-02T18:37:04","modified_gmt":"2020-08-02T22:37:04","slug":"the-surveying-problem-2","status":"publish","type":"post","link":"https:\/\/andygrigg.com\/?p=41","title":{"rendered":"The Surveying Problem Part 3: The Recursive Solution"},"content":{"rendered":"\n

As I mentioned in my previous post, I have been working on some possible solutions to the following problem:<\/p>\n\n\n\n

You are working for a company that is responsible for processing survey data for an Oil and Gas company. You are given data that summarizes whether oil was found at a certain grid reference. The assumption is that if oil is found in contiguous grid references (or grid elements), then they form a single oil reservoir. The objective is to write a program that will determine the number and locations of the reservoirs.<\/p><\/blockquote>\n\n\n\n

The question was posed to me in an interview context, so I only had access to standard Python libraries. As a result, the solution I came up with used a recursive algorithm, here’s the code:<\/p>\n\n\n\n

\"\"\" Generate a grid of elements with a random layout of elements that contain oil\nbuild_grid: Build the grid with an optional random seed\nget_neighbors: Find the number of active neighbor elements for a given element\n\"\"\"\n\nimport random\nimport itertools\n\nTHRESHOLD = 0.85\n\ndef get_neighbors(this_element, grid):\n    \"\"\" Returns a list of neighbor location objects\n\n     this_element: A 2-tuple representing the x and y coordinates of an element\n     grid: A dictionary containing all elements and their state\n     \"\"\"\n    x_coord, y_coord = this_element\n    x_offsets = [-1, 0, 1]\n    y_offsets = [-1, 0, 1]\n\n    neighbors = list()\n    for x_offset in x_offsets:\n        for y_offset in y_offsets:\n            if x_offset == 0 and y_offset == 0:\n                continue\n\n            coord = (x_coord + x_offset, y_coord + y_offset)\n            if coord in grid:\n                neighbors.append(coord)\n    return neighbors\n\n\ndef build_grid(size, seed=None):\n    \"\"\" Build a square grid of elements, where each element may or may not contain oil\n\n     size: The number of elements along one edge of the grid\n     seed: Random seed to be used to generate the grid\n     \"\"\"\n    random.seed(seed)\n\n    initial_grid = set()\n    for location in itertools.product(range(0, size), repeat=2):\n        if random.random() > THRESHOLD:\n            initial_grid.add(location)\n\n    grid = set()\n    # Cluster the grid. If an active element is not isolated,\n    # or if an inactive element has at least 4 active neighbors\n    for location in itertools.product(range(0, size), repeat=2):\n        state = location in initial_grid\n        sites_nearby = get_neighbors(location, initial_grid)\n        neighbor_count = len(sites_nearby)\n        if (state and neighbor_count != 0) or neighbor_count >= 4:\n            grid.add(location)\n\n    return grid\n<\/pre>\n\n\n\n
<\/div>\n\n\n\n
<\/div>\n\n\n\n
It’s worth saying that whilst I came up with the broad algorithm during the interview, the version above contains a few improvements over the original, both to the structure of the code and the performance.<\/p>\n\n\n\n
One example: the code in the previous post had the locations object as a dict()<\/code>, where each key was a 2-tuple representing the x and y coordinates, and each value was either True<\/code> or False<\/code>. This was fine, but when trying with large grids (1000 x 1000+) I was using a not-insignificant amount of memory, so I switched to using a list containing the True<\/code> 2-tuples only.<\/p>\n\n\n\n
Performance Optimization<\/h2>\n\n\n\n
However, imagine my horror when I realized that while I reduced my RAM usage, I slowed down the performance on a 100×100 grid by a factor of over 1000! I must admit I had to resort to the Profiler in PyCharm to point me in the right direction, which pointed me firmly in the direction of my get_neighbors<\/code> method.<\/p>\n\n\n\n
\"\"<\/figure><\/div>\n\n\n\n
The Profiler wasn’t kind enough to tell me that it was specifically my coord in all_locations<\/code> call that was causing the slowdown, but the get_neighbors<\/code> function doesn’t do a whole lot, so I quickly realized this must be the cause. After a quick Google, I came up with the Python TimeComplexity page1<\/a><\/sup>TimeComplexity<\/a><\/span>. As long as the keys stored in a dict<\/code> have sensible hashing functions (which my 2-tuples do), an in<\/code> call with a dict<\/code> is O(1), compared to O(n) for a list.<\/p>\n\n\n\n
I moved away from a dict<\/code> because I had no values, so instead of switching to a list, I should have switched to a set<\/code>. A set<\/code> is basically a dict<\/code> without values (it turns out in CPython that’s exactly how it’s implemented), and is an extremely useful type, especially when you want to perform set-type operations. Here’s the call graph using a set instead of a list, as you can see the bottleneck in get_neighbors<\/code> is gone.<\/p>\n\n\n\n
\"\"<\/figure><\/div>\n\n\n\n
In case you are wondering, the other 60% is in _find_and_load<\/code>, so not much we can do there. This was for a grid size of around 100×100 though, and the _find_and_load<\/code> overhead decreases as expected as the grid size is increased.<\/p>\n\n\n\n
That’s pretty much it in terms of the recursive approach. Performance is not bad, here are some results for some example runs:<\/p>\n\n\n\n
Grid Size<\/th>Time<\/th># of Reservoirs<\/th>Time \/ Reservoir<\/th>Time \/ Element<\/th>Reservoir Frequency<\/th><\/tr><\/thead>
10×10<\/td>1.528E-05 s<\/td>2<\/td>7.64E-06 s<\/td>1.528E-07 s<\/td>0.02<\/td><\/tr>
100×100<\/td>3.417E-03 s<\/td>306<\/td>1.117E-05 s<\/td>3.417E-07 s<\/td>0.0306<\/td><\/tr>
1000×1000<\/td>3.657E-01 s<\/td>28,425<\/td>1.287E-05 s<\/td>3.657E-07 s<\/td>0.0284<\/td><\/tr>
10000×10000<\/td>8.298E+01 s<\/td>2,841,360<\/td>2.920E-05 s<\/td>8.298E-07 s<\/td>0.0284<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
The Time\/Element and Time\/Reservoir results are pretty flat, which is probably what I would expect. The average number of reservoirs per element (reservoir frequency) is also reasonably flat, which trends towards 0.0284. It might be interesting to look into this a bit more, especially how it depends on how the grid itself was made and the clustering rules.  #TODO<\/p>\n\n\n\n
Memory Use<\/h2>\n\n\n\n
One definite negative to the code above is that even with a shift to storing only active elements in a set, it’s extremely memory intensive. The final run on a 10,000×10,000 grid was using around 4 Gb of memory at peak, which I think is probably due to two factors:<\/p>\n\n\n\n
Firstly, I can’t use a yield-type idiom because I’m bouncing around looking at elements before and after the one I am processing. Also, during the clustering process, both the original and clustered grids have to be in memory at once, so I can examine the current state while I build the new state.<\/p>\n\n\n\n
Secondly, native Python types are pretty bloated, memory-wise2<\/a><\/sup>https:\/\/stackoverflow.com\/questions\/1331471\/in-memory-size-of-a-python-structure<\/a><\/span>. An int<\/code> is 24 bytes and the overhead for a tuple<\/code> is 56 bytes, which means each element needs 104 bytes. The original grid is 15% active, which means for a grid of 10,000 x 10,000 elements 1.5 Gb of RAM is required. Assuming the clustered grid is around 10% active, that’s 2.5 Gb of memory to store both the original and clustered grid. <\/p>\n\n\n\n
Next Steps<\/h2>\n\n\n\n
So, pros and cons to this approach, and definitely worth looking at more. However, my plan is to dig into the graph-based approach to see how the code complexity and performance changes.<\/p>\n","protected":false},"excerpt":{"rendered":"
As I mentioned in my previous post, I have been working on some possible solutions to the following problem: You are working for a company that is responsible for processing survey data for an Oil and Gas company. You are given data that summarizes whether oil was found at a certain grid reference. The assumption […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[10],"tags":[13,14,15,5],"class_list":["post-41","post","type-post","status-publish","format-standard","hentry","category-code","tag-memory","tag-performance","tag-profiling","tag-python"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/posts\/41","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/andygrigg.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=41"}],"version-history":[{"count":21,"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/posts\/41\/revisions"}],"predecessor-version":[{"id":128,"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/posts\/41\/revisions\/128"}],"wp:attachment":[{"href":"https:\/\/andygrigg.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=41"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/andygrigg.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=41"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/andygrigg.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=41"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}