Скорость лимит трафика проверить интервалы


Дали 2 списка кортежей limits и speedsоба имеют формат [(speed1, время1), (скорость2, время2)]. Моя цель-написать функцию, чтобы проверить, действительно ли существует период времени, в течение которого скорость превышает предельное значение (возвращает true, если превышает). Например, учитывая ограничения = [(50,100), (30, 20)], скорости = [(30, 80), (10, 30), (40, 10)], возвращает значение true.

Пример входных данных предполагает, что в течение первых 100 км, максимальная скорость-50. В 101-120 км, ограничение скорости 30. Поскольку в списке скоростях, последние 10 км на скорости 40 > 30, то мы возвращаем значение true.

Мы можем предположить, что эти данные корректны, так пределы и скорость список всегда начинается и заканчивается одновременно.

Могу ли я иметь некоторые указатели на правильность и как код может быть переработан?

def speed_check(limits, speeds):
  i, j = 0, 0
  prev_limit_range, prev_speed_range = 0, 0
  while j < len(speeds) and i < len(limits):
    if limits[i][0] < speeds[j][0]:
      return True
    if limits[i][1] + prev_limit_range < speeds[j][1] + prev_speed_range:
      prev_limit_range += limits[i][1]
      i += 1
    elif limits[i][1] + prev_limit_range > speeds[j][1] + prev_speed_range:
      prev_speed_range += speeds[j][1]
      j += 1
    else:
      prev_limit_range += limits[i][1]
      prev_speed_range += speeds[j][1]
      i += 1
      j += 1

  return False

assert speed([(30, 15), (55, 20)], [(30, 15), (55, 20)]) == False
assert speed([(30, 15), (55, 20)], [(30, 14), (65, 20)]) == True


832
8
задан 2 апреля 2018 в 08:04 Источник Поделиться
Комментарии
2 ответа

Во-первых, давайте посмотрим на ваш ответ с комментариями:

def speed_check(limits, speeds):
# Explicit assignment of temporary variables
i, j = 0, 0
prev_limit_range, prev_speed_range = 0, 0
# Assumption that speeds and limits will not change during iteration
while j < len(speeds) and i < len(limits):
# Multiple if statements make it so that we can't just swap lines of
# code without breaking things.
if limits[i][0] < speeds[j][0]: # speed > limit would be more readable
return True
# Operator precedence does not jump to the eye. Use parenthesis
if limits[i][1] + prev_limit_range < speeds[j][1] + prev_speed_range:
prev_limit_range += limits[i][1]
i += 1
elif limits[i][1] + prev_limit_range > speeds[j][1] + prev_speed_range:
prev_speed_range += speeds[j][1]
j += 1
else:
# Manual incrementation of local variables.
prev_limit_range += limits[i][1]
prev_speed_range += speeds[j][1]
i += 1
j += 1

return False

Питон-мудрый, есть несколько деталей реализации, которые могут быть решены по-разному. Давайте посмотрим, что мы можем сделать.

Если вы думаете об этой проблеме графически, проводя оси Х на расстояние и y-оси на скорости, тогда все, что вы хотите проверить, является ли кривая на реальную скорость не пересекает кривую для ограничения скорости.

Вы могли бы сломать вашу проблему в части:

def get_graph(speedlist):
"""Generate a list of tuples into a flatten list as in:
[(1,2), (3, 4)] -> [1, 1, 3, 3, 3, 3]
"""
return [item for x in [y[1]*[y[0]] for y in speedlist] for item in x]

def check_exceeds(speeds, limits):
speed_graph = get_graph(speeds)
limits_graph = get_graph(limits)
return any([x > y for x, y in zip(speed_graph, limits_graph)])

Такой подход позволяет избежать трех проблем, которые я вижу в своей реализации: превышение если-заявления, явной индексации, и явные итерации. Зачем эти вопросы? Ну, это легко сделать ошибки при индексации и перебор вручную, и легко забыть, возможные ветви при использовании если/еще условия. Питон предлагает много инструментов, так что вы не должны делать все сами, и это считается хорошей практикой, чтобы использовать этот инструмент, чтобы сделать ваш код более читабельным и безопасным.

По вашим утверждениям, там тоже не надо сравнивать True ни Falseв случае, если ваша функция определена таким образом, что она возвращает логическое значение:

assert check_exceeds([(30, 15), (55, 20)], [(30, 15), (55, 20)])
assert not check_exceeds([(30, 15), (55, 20)], [(30, 14), (65, 20)])

(быстрый ответ, как я отвечала на пост на сайте StackOverflow, прежде чем он мигрировал)

6
ответ дан 2 апреля 2018 в 08:04 Источник Поделиться

Ваш код, кажется, работает хорошо на тестовых случаев (одно имя функции фиксируется), давайте посмотрим, как его можно улучшить.

Стиль

Есть официальный стандартный Python стиль руководства называют ПЭП 8. Это настоятельно рекомендуется к прочтению. Он дает рекомендации, помогающие писать код, который можно как читать, так и последовательным. Сообществе Python пытается следовать этим правилам, более или менее строго (ключевой аспект ОПТОСОЗ 8 является то, что оно содержит рекомендации, а не строгие правила, чтобы слепо следовать).

Между прочим, он посоветовал


Используйте 4 пробела на каждый уровень отступа.

Упрощение логики

Сравнение кажется сложным, но это на самом деле довольно проста: сравнить 2 значения и рассмотрим 3 ситуации: они равны или первое число меньше или первое число больше. Чтобы избежать повторения (и вычислений) различных чисел, вы могли бы сразу вычислить разницу.

    diff = (limits[i][1] + prev_limit_range) - (speeds[j][1] + prev_speed_range)
if diff < 0:
prev_limit_range += limits[i][1]
i += 1
elif diff > 0:
prev_speed_range += speeds[j][1]
j += 1
else:
prev_limit_range += limits[i][1]
prev_speed_range += speeds[j][1]
i += 1
j += 1

По реорганизации условий, мы имеем:

diff = limits[i][1] - speeds[j][1] + prev_limit_range - prev_speed_range

и кажется, что только разные между prev_limit_range и prev_speed_range актуально: мы могли бы использовать одну переменную для этого.

prev_diff = 0
while j < len(speeds) and i < len(limits):
if limits[i][0] < speeds[j][0]:
return True
diff = limits[i][1] - speeds[j][1] + prev_diff
if diff < 0:
prev_diff += limits[i][1]
i += 1
elif diff > 0:
prev_diff += -speeds[j][1]
j += 1
else:
prev_diff += limits[i][1] - speeds[j][1]
i += 1
j += 1

Но потом, prev_diff += limits[i][1] - speeds[j][1] соответствует prev_diff = prev_diff + limits[i][1] - speeds[j][1] = diff = 0.

Кроме того, хранить соответствующие данные в переменную, все становится немного чище.

    lim, speed = limits[i][1], speeds[j][1]
diff = speed - lim
if diff > prev_diff:
prev_diff += lim
i += 1
elif diff < prev_diff:
prev_diff += -speed
j += 1
else:
prev_diff = 0
i += 1
j += 1

Итератор

Вместо того, чтобы явно имеем дело с индексами, вы могли бы использовать итераторы и просто решить, какой итератор Вам "аванс" на (Я не 100% уверен, что это делает вещи лучше в вашем случае, но это всегда хорошая техника, чтобы знать):

def speed_check(limits, speeds):
prev_diff = 0
speed_iter, limit_iter = iter(speeds), iter(limits)
try:
speed_val = next(speed_iter)
limit_val = next(limit_iter)
while limit_val[0] >= speed_val[0]:
diff = speed_val[1] - limit_val[1]
if diff > prev_diff:
prev_diff += limit_val[1]
limit_val = next(limit_iter)
elif diff < prev_diff:
prev_diff += -speed_val[1]
speed_val = next(speed_iter)
else:
prev_diff = 0
limit_val = next(limit_iter)
speed_val = next(speed_iter)
return True
except StopIteration: # no more values
return False

1
ответ дан 2 апреля 2018 в 04:04 Источник Поделиться