Веб-скребок: расширительный/контрактный ограничивающий ящик в зависимости от результатов.

Question

Клиент хочет знать местоположение магазинов своих конкурентов, поэтому я становлюсь квази-злым и соскабливает сайт конкурента.

Сервер принимает ограничительную рамку (то есть координаты нижнего и верхнего правого угла) в качестве параметров и возвращает местоположения, найденные в ограничивающей рамке. Эта часть работает нормально, и я могу успешно получить хранилища с учетом ограничивающей рамки.

Проблема заключается в том, что только первые 10 мест в пределах прямоугольника возвращаются - так в густонаселенных районах, ограничивающее окно 10 градусов будет возвращать слишком много места:

Я мог бы просто всегда используйте меньшую ограничительную рамку, но я стараюсь избегать ненужных обращений к серверу, гарантируя возврат всех магазинов.

Поэтому мне нужно уменьшить размер прямоугольника поиска, когда найдено 10 магазинов (поскольку может присутствовать более 10 магазинов) и рекурсивно искать с меньшим размером прямоугольника поиска, а затем вернуться к большему прямоугольнику для следующая ячейка сетки.

Я написал функцию, которая извлекает магазины с сервера данного габаритный прямоугольник:

stores = checkForStores(<bounding box>) 
if len(stores) >= 10: 
    # There are too many stores. Search again with a smaller bounding box 
else: 
    # Everything is good - process these stores 

, но я борюсь с тем, как установить соответствующий ограничивающий прямоугольник для функции checkForStores.

Я попытался создать основные ячейки сетки, используя for петли на широте и долготе:

cellsize = 10 
for minLat in range(-40, -10, cellsize): 
    for minLng in range(110, 150, cellsize): 
     maxLat = minLat + cellsize 
     maxLng = minLng + cellsize 

... но я не знаю, как продолжать искать с меньшим ограничивающего параллелепипеда, если 10 магазины найдены. Я также попытался использовать петли while, но я не могу заставить их работать.

Благодарим за любые советы или указания, с чего начать.

Answer 1

Вот как вы можете это сделать, используя рекурсию. Код должен быть понятным, но вот как это работает: Предоставляя некоторый граничный ящик, он проверяет количество хранилищ в нем, а если их больше или равно 10, он делит это поле на более мелкие и вызывает себя каждый из этих новых граничных ящиков. Он делает это до тех пор, пока не будет найдено менее 10 магазинов. В этом случае найденные магазины просто сохраняются в списке.

Примечание: поскольку используется рекурсия, может возникнуть ситуация, когда максимальная глубина рекурсии будет превышена. Это теоретически. В вашем случае, даже если бы пройти 40 000 х 40 000 км краевого поля, это заняло бы только 15 шагов, чтобы достичь roughtly граничного окна 1 х 1 км с cell_axis_reduction_factor=2:

In [1]: import math 

In [2]: math.log(40000, 2) 
Out[2]: 15.287712379549449 

Во всяком случае, в таком случае вы могли бы попробуйте увеличить номер cell_axis_reduction_factor.

Также обратите внимание: в Python, в соответствии с PEP 8, функции должны быть в нижнем регистре, с подчеркиванием, поэтому я переименовал checkForStores функцию check_for_stores.

# Save visited boxes. Only for debugging purpose. 
visited_boxes = [] 


def check_for_stores(bounding_box): 
    """Function mocking real `ckeck_fo_stores` function by returning 
    random list of "stores" 
    """ 
    import random 
    randint = random.randint(1, 12) 
    print 'Found {} stores for bounding box {}.'.format(randint, bounding_box) 
    visited_boxes.append(bounding_box) 
    return ['store'] * randint 


def split_bounding_box(bounding_box, cell_axis_reduction_factor=2): 
    """Returns generator of bounding box coordinates splitted 
    from parent `bounding_box` 

    :param bounding_box: tuple containing coordinates containing tuples of 
      lower-left and upper-right corner coordinates, 
      e.g. ((0, 5.2), (20.5, 14.0)) 
    :param cell_axis_reduction_factor: divide each axis in this param, 
             in order to produce new box, 
             meaning that in the end it will 
             return `cell_axis_reduction_factor`**2 boxes 
    :return: generator of bounding box coordinates 

    """ 
    box_lc, box_rc = bounding_box 
    box_lc_x, box_lc_y = box_lc 
    box_rc_x, box_rc_y = box_rc 

    cell_width = (box_rc_x - box_lc_x)/float(cell_axis_reduction_factor) 
    cell_height = (box_rc_y - box_lc_y)/float(cell_axis_reduction_factor) 

    for x_factor in xrange(cell_axis_reduction_factor): 
     lc_x = box_lc_x + cell_width * x_factor 
     rc_x = lc_x + cell_width 

     for y_factor in xrange(cell_axis_reduction_factor): 
      lc_y = box_lc_y + cell_height * y_factor 
      rc_y = lc_y + cell_height 

      yield ((lc_x, lc_y), (rc_x, rc_y)) 


def get_stores_in_box(bounding_box, result=None): 
    """Returns list of stores found provided `bounding_box`. 

    If there are more than or equal to 10 stores found in `bounding_box`, 
    recursively splits current `bounding_box` into smaller one and checks 
    stores in them. 

    :param bounding_box: tuple containing coordinates containing tuples of 
      lower-left and upper-right corner coordinates, 
      e.g. ((0, 5.2), (20.5, 14.0)) 
    :param result: list containing found stores, found stores appended here; 
        used for recursive calls 
    :return: list with found stores 

    """ 
    if result is None: 
     result = [] 

    print 'Checking for stores...' 
    stores = check_for_stores(bounding_box) 
    if len(stores) >= 10: 
     print 'Stores number is more than or equal 10. Splitting bounding box...' 
     for splitted_box_coords in split_bounding_box(bounding_box): 
      get_stores_in_box(splitted_box_coords, result) 
    else: 
     print 'Stores number is less than 10. Saving results.' 
     result += stores 

    return result 


stores = get_stores_in_box(((0, 1), (30, 20))) 
print 'Found {} stores in total'.format(len(stores)) 
print 'Visited boxes: ' 
print visited_boxes 

Вот пример вывода:

Checking for stores... 
Found 10 stores for bounding box ((0, 1), (30, 20)). 
Stores number is more than or equal 10. Splitting bounding box... 
Checking for stores... 
Found 4 stores for bounding box ((0.0, 1.0), (15.0, 10.5)). 
Stores number is less than 10. Saving results. 
Checking for stores... 
Found 4 stores for bounding box ((0.0, 10.5), (15.0, 20.0)). 
Stores number is less than 10. Saving results. 
Checking for stores... 
Found 10 stores for bounding box ((15.0, 1.0), (30.0, 10.5)). 
Stores number is more than or equal 10. Splitting bounding box... 
Checking for stores... 
Found 1 stores for bounding box ((15.0, 1.0), (22.5, 5.75)). 
Stores number is less than 10. Saving results. 
Checking for stores... 
Found 9 stores for bounding box ((15.0, 5.75), (22.5, 10.5)). 
Stores number is less than 10. Saving results. 
Checking for stores... 
Found 4 stores for bounding box ((22.5, 1.0), (30.0, 5.75)). 
Stores number is less than 10. Saving results. 
Checking for stores... 
Found 1 stores for bounding box ((22.5, 5.75), (30.0, 10.5)). 
Stores number is less than 10. Saving results. 
Checking for stores... 
Found 6 stores for bounding box ((15.0, 10.5), (30.0, 20.0)). 
Stores number is less than 10. Saving results. 
Found 29 stores in total 
Visited boxes: 
[ 
((0, 1), (30, 20)), 
((0.0, 1.0), (15.0, 10.5)), 
((0.0, 10.5), (15.0, 20.0)), 
((15.0, 1.0), (30.0, 10.5)), 
((15.0, 1.0), (22.5, 5.75)), 
((15.0, 5.75), (22.5, 10.5)), 
((22.5, 1.0), (30.0, 5.75)), 
((22.5, 5.75), (30.0, 10.5)), 
((15.0, 10.5), (30.0, 20.0)) 
]