Как сравнить два элемента в списке за постоянное время

Question

Предположим, у меня есть список элементов, таких как [5, 3, 1, 2, 4], и я хочу сравнить два элемента по позиции.В зависимости от того, что произойдет первым в списке, оно больше или true.Итак:

compare(5, 3) # true
compare(2, 1) # false
compare(3, 4) # true

Как я могу сделать это в постоянное время?Один из способов сделать это - использовать карты, где ключ - это элемент, а значение - это позиция в списке:

order = {5: 0, 3: 1, 1: 2, 2: 3, 4: 4}

Тогда мы амортизируем O (1) время, ноO (N) пробел.У кого-нибудь есть более элегантное решение?

Answer 1

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

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

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

Answer 2

Если вам нужно начать со списка, и вы делаете операцию только несколько раз, используйте:

def compare(ls, n1, n2):
    return ls.index(n1) > ls.index(n2)

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

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

коррекция : приведенная выше функция сравнения займет O (1) время, потому что доступы в python занимают O (1) время, см. http://wiki.python.org/moin/TimeComplexity