Запросы квадрант вызов


Работает один и тот же тест в 10 000 раз с cProfile мне подсказывает, что большинство повреждений происходит в функции count (). Это моя попытка решения Квадрант поисковым вызовом от InterviewStreet (постановка задачи может быть найден здесь).

По данным InterviewStreet, я прошел 3/11 тесткейсам и я выбежал из времени процессора. У меня нет способа узнать, был ли я 3 на 3 и не хватило времени или скажем, 3 на 6 и не хватило времени. Я не знаю, если мой код работает на все входные.

Пожалуйста, помогите мне оптимизировать этот код:

def reflect_x(i, j, coordinates):
    for pair in xrange(i-1, j):
        coordinates[pair][1] = -coordinates[pair][1]
    return coordinates

def reflect_y(i, j, coordinates):
    for pair in xrange(i-1, j):
        coordinates[pair][0] = -coordinates[pair][0]
    return coordinates

def count(i, j, coordinates):
    quad_one, quad_two, quad_three, quad_four = 0, 0, 0, 0
    for pair in xrange(i-1, j):
        x, y = coordinates[pair][0], coordinates[pair][1]

        if x >= 0 and y >= 0:
            quad_one += 1
        elif x < 0 and y >= 0:
            quad_two += 1
        elif x < 0 and y < 0:
            quad_three += 1
        elif x >= 0 and y < 0:
            quad_four += 1

    print "%d %d %d %d" % (quad_one, quad_two, quad_three, quad_four)

def reflect(coordinates, queries):

    for query in queries:
        if query[0] == "X": 
            reflect_x(query[1], query[2], coordinates)
        elif query[0] == "Y":
            reflect_y(query[1], query[2], coordinates)
        elif query[0] == "C":
            count(query[1], query[2], coordinates)
        else:
            print query

if __name__ == "__main__":
    N = int(raw_input())
    coordinates = [[int(pair[0]), int(pair[1])] for pair in (pair.split() for pair in (raw_input() for i in xrange(N)))]

    Q = int(raw_input())
    queries = [[query[0], int(query[1]), int(query[2])] for query in (query.split() for query in (raw_input() for i in xrange(Q)))]

    reflect(coordinates, queries)


Комментарии
6 ответов

def reflect_x(i, j, coordinates):
for pair in xrange(i-1, j):
coordinates[pair][1] = -coordinates[pair][1]
return coordinates

Что-то вроде:

def reflect_x(i, j, coordinates):
coordinates[i-1:j] = ((x,-y) for x,y in coordinates[i-1,j])

Яснее и, возможно, немного быстрее. Кроме того, изменить или вернуть, не сделать оба.

def count(i, j, coordinates):
quad_one, quad_two, quad_three, quad_four = 0, 0, 0, 0

Если у вас есть счет, прикрепленный к вашей переменной, вероятно, означает, что она должна быть в списке

    quad = [0] * 4

for pair in xrange(i-1, j):

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

        x, y = coordinates[pair][0], coordinates[pair][1]

То же, что:

        x, y = coordinates[pair]

...

        if x >= 0 and y >= 0:
quad_one += 1
elif x < 0 and y >= 0:
quad_two += 1
elif x < 0 and y < 0:
quad_three += 1
elif x >= 0 and y < 0:
quad_four += 1

print "%d %d %d %d" % (quad_one, quad_two, quad_three, quad_four)

def reflect(coordinates, queries):

плохое название, эта функция не только отражать

    for query in queries:
if query[0] == "X":
reflect_x(query[1], query[2], coordinates)
elif query[0] == "Y":
reflect_y(query[1], query[2], coordinates)
elif query[0] == "C":
count(query[1], query[2], coordinates)
else:
print query

if __name__ == "__main__":
N = int(raw_input())
coordinates = [[int(pair[0]), int(pair[1])] for pair in (pair.split() for pair in (raw_input() for i in xrange(N)))]

Вам не нужно делать все на одной линии. Вы также можете распаковать Кортеж в предложении for.

    coordinate_lines = (raw_input() for i in xrange(N))
coordinates = [(int(x),int(y)) for x,y in line.split for line in coordinate_lines]

Что касается оптимизации: во-первых, вы должны понимать, что вы на самом деле не волнует, что это координаты. Все что тебя волнует-это квадранты. Операции отражения просто переместить вас из одного квадранта в другой.

Я вынужден не согласиться с Джефф Меркадо, а я не думаю, что его подход будет работать. (возможно, я пропустил то, что он намекал.) В основном то, что у вас в худшем случае за o(Н*М) время работы. Так как n и Q-большие числа, вы не можете уйти с делать это. Его подход уменьшает сложность до O(1) для операции подсчета, но оставляет за o(n) для отражения операций. Вот еще собираюсь дать вам о(Н*м).

Мы должны сократить расходы отражать операции, а также.

В принципе, для каждого сектора мы должны отслеживать точки в квадранте. Мы поместим их в какую-то структуру данных. Нам нужна структура данных, которая позволит эффективную реализацию:


  1. Найти все точки с индексами между стартом индекс/стоп

  2. Замена этих точек между двумя различными версиями данных структура

  3. Найти количество всех точек в настоящее время в структуру данных

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

3
ответ дан 24 августа 2011 в 04:08 Источник Поделиться

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


  • Отразить Х: для каждой точки в диапазоне, отменяет координата X

  • Отражения г: для каждой точки в диапазоне, отменяет координата Y

  • Графа: для каждой точки в диапазоне, посчитайте, сколько лжи на каждый квадрант

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

Каждая операция-Это О(N) один. Граф будет страдать больше всех, так как вы пытаетесь выяснить, в каком квадранте каждая точка принадлежит как вы придумали графов. Профилирование кода против ваших тестов будет не очень эффективным, как вы можете поспорить, они будут иметь намного больше, чтобы бросить на вас. Вы должны выяснить, как можно уменьшить эти О(Н) алгоритмов как-то пройти свои испытания. На самом деле, вы можете уменьшить графа за O(1) с алгоритмами у меня в голове (два других будут иметь одинаковую сложность, однако).

А не просто даем вам ответ, я буду давать некоторые советы.


  1. Есть еще один способ вы могли бы эффективно что-то рассчитывать в диапазоне?
    Я не уверен, как я могу действительно объяснить это, но рассмотрим такой пример:

    Предположим, что вы отслеживали свой баланс в банке для каждого дня в месяце. Вы бы такие данные:


    1 $5000
    2 $5020
    3 $4980
    4 $4780
    5 $5280
    6 $5280
    7 $5580
    и т. д...
    Как бы вы определить, сколько денег вы заработали/потеряли между днем 1 и днем 2? Как насчет день 2 и день 4? Есть ли способ, чтобы представить эту проблему подобным образом?

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

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

1
ответ дан 24 августа 2011 в 07:08 Источник Поделиться

Мне удалось получить представление за пределами процессора, используя подход, аналогичный к тому, что Уинстон Эверт описаны выше. Впервые я попробовал его в Рубин, и врезался в стену на 5/11 тестов. Переключение на Java сразу довели ее до 9/11, и немного больше оптимизации получили его через.

За пределы процессора на эту проблему чрезвычайно туго. У меня есть сомнения в том, любой интерпретируемый язык будет в состоянии удовлетворить их, если только есть лучше структуру данных, чем тот, который я использовал. Используя скомпилированный язык, этот срок должен быть 1/4 от интерпретируемый язык, но это путь более чем в 4 раза быстрее. Моя рекомендация будет проверить ваш подход с использованием Python или что-то реализовать в Java или C.

Если вы используете Java, один общий совет, чтобы оба буфер стандартного ввода и вывода. В мои последние несколько попыток, большинство времени было потрачено просто чтение входных данных и вывода результата. Избегайте использование Java.утиль.Сканер, как это, кажется, настоящая собака.

1
ответ дан 30 августа 2011 в 10:08 Источник Поделиться

Я пробовал эту проблему разными способами, а я до сих пор не обходя скорость проверки. Я попытался с помощью списков и множеств, как моя структура данных, и оба не имеют требуемой асимптотической эффективности. @Уинстон Эверт правильно: вам нужно как минимум за o(журнал N) время для всех трех операций, и лучший способ сделать это с двоичным деревом поиска.

Так что я пытаюсь сделать, это иметь четыре Бсц, по одному на каждый квадрант. Вот мой набросок дерева до сих пор:

class Node:
left, right, index, count = None, None, 0, 0

def __init__(self, data):
self.left = None
self.right = None
self.data = data
self.count = 1

class Tree:
root = None

def __init__(self):
self.root = None

def add_node(self, data):
return Node(data)

def insert(self, root, data):
if root == None:
return self.add_node(data)
else:
root.count += 1
if data < root.data:
root.left = self.insert(root.left, data)
else:
root.right = self.insert(root.right, data)
return root

def find(self, root, target):
if root == None:
print "Error in find (", target, "): root is None"
return 0
else:
if target == root.data:
return root
elif target < root.data:
return self.find(root.left, target)
else:
return self.find(root.right, target)

На данных переменной будет индекс узла в списке представительство координаты мы передали. Весь смысл использования БСТ здесь, как я вижу, заключается в том, что потенциально мы можем двигаться целый сегмент точек из одного квадранта в другой, захватывая узел, что сегмент в целом произошел от и вставки узла в дерево, обновляя считать параметр из дерева, как мы идем. Для этого нам нужен метод для добавления узлов в деревьях:

    def insert_node(self, root, node):
if root == None:
return node
else:
root.count += node.count
if node.data < root.data:
root.left = self.insert_node(root, node)
else:
root.right = self.insert_node(root, node)
return root

Хитрый способ, который я не знаю, как сделать, часть, которая захватывает интервал, но не более того. Очевидно, мы не получаем конкретное [я, J] искать в дереве, так как мы не знаем, какое дерево I и J находятся. Мы только получаем спектр. Этот метод будет захватывать первый узел, который попадает в диапазон [Я, J] в дереве:

    def find_in_range(self, root, i, j):
if root == None:
print "Error in find_in_range (", i, j, "): root is None"
return 0
else:
if i <= root.data and root.data <= j:
return root
elif root.data > i and root.data > j:
return self.find_in_range(root.left, i, j)
elif root.data < i and root.data < j:
return self.find_in_range(root.right, i, j)
else:
print "Error in find_in_range(", i, j, "): no criteria matched"

В том случае, когда мы рекурсивно слева, а затем найти узел в ассортименте, все произошли от права на этот узел и далее в интервале [я, inf-файл), так что мы можем просто позвонить find_in_range снова с новыми параметрами и бороться с правом конце узел. Маленький портной и мы выбрали именно узлы [Я, J] в нашем квадранте. Тот же самый аргумент работает, если мы рекурсивно права.

Проблема, которую я имею, является то, что если мы начнем первыми find_in_range и мы уже в диапазоне, я не знаю, где конечные точки. У кого-нибудь есть для меня предложение? Если я могу решить эту проблему, остальное-лишь детали.

1
ответ дан 31 августа 2011 в 12:08 Источник Поделиться

чтобы оптимизировать ваш подсчет попробовать:

def count(i, j, coordinates):
quad_one, quad_two, quad_three, quad_four = 0, 0, 0, 0
current_coordinates = coordsinates[i-1:j]

for pair in current_coordinates:
x, y = pair[0], pair[1]
...

И увидеть, если это уменьшает его. Я не уверен, что это быстрее нарезать или xrange()

просто как Примечание: П= И Г= - это (ИМХО) почти нечитаемая каша. (вы можете не читать все, а потом обработает его?)

0
ответ дан 24 августа 2011 в 07:08 Источник Поделиться

Я написал решение, которое берет на себя все размышления и объединяет их в один набор инструкций отражение. Например, Х я следовал J по Г Я J-это эквивалентно одной "диагонали" отражение, т. е. все точки из первого квадранта с в квадрант 3 РД. Это была не простая задача, как вы можете себе представить, но это правильно. Результатом является то, что сложность-это все-таки за o(n), но она будет выполнена качественно, т. е. вместо того, чтобы сначала делать х отражение сопровождается y рефлексии, мы вообще ни одного отражения. К сожалению, этого не пройти онлайн судья.

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

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

Нижней строке. Это жесткая проблема.

0
ответ дан 29 августа 2011 в 02:08 Источник Поделиться