Пропуск значений из определенных ключей в диктанте

Question

В настоящее время я создаю службу на основе определения местоположения, которая рассчитывает маршруты для пользователей, разделяющих автомобили для определенного события. Чтобы рассчитать кратчайшее расстояние, необходимо знать расстояние проезда между пользователями, потому что одно из ограничений системы заключается в том, что каждый водитель не должен преодолевать расстояние, превышающее определенное расстояние, чтобы забрать конкретного пассажира. , Чтобы не вызывать Google Maps API дважды для одного и того же маршрута, я заполняю Dict в начале программы, чтобы сохранить расстояния. Расстояния генерируются так:

def generateDistances(self):
    users = self.drivers + self.passengers
    for user1 in users:
        for user2 in users:
            if user1 != user2:
                distance = GetDistance(user1.location, user2.location)
                self.distances.append({'Start' : user1, 'End' : user2, 'Distance' : distance['Distance']['meters'], 'Duration': distance['Duration']['seconds']})
        self.distances.append({'Start' : user1, 'End' : self.destination, 'Distance' : distance['Distance']['meters'], 'Duration': distance['Duration']['seconds']})

Метод GetDistance просто выбирает маршрут между двумя местоположениями из API Карт Google, основываясь на их широте и долготе. Затем программа вызывает следующую функцию, чтобы найти расстояние в Dict:

def getSavedDistance(self, user1, user2):
    if user1 == user2:
        return 0
    for record in self.distances:
        if record['Start'] == user1:
            if record['End'] == user2:
                return record['Distance']
    logging.warn("No distance from %s to %s found" % (user1.userid, user2.userid))

Тем не менее, я запустил это на Google App Engine, и он работает очень медленно, и, как вы можете себе представить, время выполнения увеличивается в геометрической прогрессии по мере увеличения размера проблемы (то есть больше пользователей). То, что я хочу сделать, - это инициализировать dict с расстояниями по прямой линии между каждым пользователем (рассчитанным математически, без необходимости вызовов API), и когда система проверяет длину маршрута, она сначала проверяет расстояние по прямой линии. Если расстояние по прямой больше максимального расстояния, то маршрут слишком длинный - фактическое расстояние вычислять не нужно. В противном случае система просто увидит, что проезжаемое расстояние не является обязательным, и сделает необходимые вызовы API, чтобы вставить его туда.

Итак, я придумал что-то подобное для инициализации расстояний (обратите внимание, что это не работает, поскольку я не могу вставить ноль в значения dict):

def initialiseDistances(self):
    users = self.drivers + self.passengers
    for user1 in users:
        for user2 in users:
            if user1 != user2:
                self.distances.append({'Start' : user1, 'End' : user2, 'Distance' : null, 'Duration' : null, 'StraightLine' : GetStraightLineDistance(user1.location, user2.location)})
        self.distances.append({'Start' : user1, 'End' : self.destination, 'Distance' : null, 'Duration' : null, 'StraightLine' : GetStraightLineDistance(user1.location, self.destination)})

... и тогда метод getSavedDistance можно изменить на что-то вроде этого:

def getSavedDistance(self, user1, user2):
    if user1 == user2:
        return 0
    for record in self.distances:
        if record['Start'] == user1:
            if record['End'] == user2:
                if record['Distance'] == null:
                    distance = GetDistance(user1.location, user2.location)
                    record['Distance'] = distance['Distance']['meters']
                    record['Duration'] = distance['Duration']['seconds']
                    return record['Distance']
    logging.warn("No distance from %s to %s found" % (user1.userid, user2.userid))

Это позволило бы системе заполнять только те значения расстояния, которые фактически используются, и избегать повторения одного и того же вызова API дважды. Тем не менее, по-видимому, я не могу вставить ноль в значение dict. У кого-нибудь есть идея, как я мог бы вставить какое-то значение в этот диктат, который говорит мне, что для расстояния еще нет значения?

Спасибо

Answer 1

Создайте свой self.distances a словарь , сопоставляющий кортеж (start_user, end_user) с необходимой вам информацией. То, что вы делаете, включает в себя O (N) доступ к списку элементам только для одного поиска , вместо одного поиска. С помощью dict, если у вас нет никакой информации для (user1, user2), вам не нужно тратить время и память на ввод фиктивной «нулевой» записи в вашу структуру данных.

info = self.distances_DICT.get((user1, user2))
if info is None: 
    self.calculate_the_distance_or_whatever_else_you_need_to_do(user1, user2))

Answer 2

Поскольку это Python, None является нулевым значением.Сравните с None, используя is None, но не == None.

Answer 3

Могу ли я предложить другой подход? Сделайте ваши self.distances диктовкой (user1, user2), которая изменит ваш поиск с O (n) на O (1). Предполагая, что GetDistance(user1, user2) совпадает с GetDistance(user2, user1), вы можете убедиться, что каждый кортеж, используемый в качестве ключа словаря, отсортирован, чтобы вы могли повторно использовать одно и то же значение для каждого направления.

---

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

class DistanceFinder(object):
    distances = {}
    def GetDistance(self, user1, user2):
        userkey = (user1, user2)
        if userkey in self.distances:
            return self.distances[userkey]
        result = [... calculations go here ...]
        self.distances[userkey] = result
        return result

Веселая работа в Python 3.2:

from functools import lru_cache
class DistanceFinder:
    @lru_cache(maxsize=None)
    def GetDistance(self, user1, user2):
        return [... calculations go here ...]

Это кэширование встроено. Хорошо, а?