Считая прилегающие ОСП отсортировать массив с 3 разных значения


Это детский сад экскурсия проблему kattis.com:

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

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

Задача

Вам будут даны последовательности чисел 0, 1, и 2, обозначающие экскурсионных маршрутов каждого ребенка от первого до последнего в строке. Пары смежных дети могут поменять позиции, и линии должны быть организованы после того, как номер получателя, начиная с 0 и заканчивая 2. Какое минимальное число обменов, необходимых для организации линии?

Вход

В единственной строке входных данных записана строка, состоящая из символов 0, 1 или 2, обозначающие направления детей. Длина строки не более 1 000 000 символов.

Выход

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

Пример Ввод 1

10210

Пример Выходных Данных 1

5

Это мой код. Мое решение слишком медленно и мне нужна помощь с оптимизацией или иной подход к этой проблеме.

def excursion(str):
    digits = [0, 0, 0]
    x = 0
    for i in range(len(str)):
        for j in range((int(str[i])) + 1, 3):
            x += digits[j]
        digits[int(str[i])] += 1
    return x

print(excursion(input()))


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

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

>>> import random
>>> CASE = ''.join(random.choice('012') for _ in range(10**6))

Времени на этот тест устанавливает базовые показатели для каких-либо улучшений.

>>> from timeit import timeit
>>> timeit(lambda:excursion(CASE), number=1)
1.1623761800583452


  1. Выражение int(str[i])) появляется дважды, так давайте вспомним его в локальную переменную:

    def excursion2(str):
    digits = [0, 0, 0]
    result = 0
    for i in range(len(str)):
    digit = int(str[i])
    for j in range(digit + 1, 3):
    result += digits[j]
    digits[digit] += 1
    return result

    Это экономит около 25% от времени выполнения:

    >>> timeit(lambda:excursion2(CASE), number=1)
    0.867930110078305

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

    def excursion3(str):
    digits = [0, 0, 0]
    result = 0
    for c in str:
    digit = int(c)
    for j in range(digit + 1, 3):
    result += digits[j]
    digits[digit] += 1
    return result

    Это экономит около 3%:

    >>> timeit(lambda:excursion3(CASE), number=1)
    0.8365003759972751

  3. Мы можем сохранить оператора присваивания с помощью map чтобы применить функцию int Героев str:

    def excursion4(str):
    digits = [0, 0, 0]
    result = 0
    for digit in map(int, str):
    for j in range(digit + 1, 3):
    result += digits[j]
    digits[digit] += 1
    return result

    Это экономит около 4%:

    >>> timeit(lambda:excursion4(CASE), number=1)
    0.7819818791467696

  4. Мы могли бы кэшировать объекты в диапазоне, чтобы избежать восстановления их на каждой петле:

    def excursion5(str):
    n = 3
    digits = [0] * n
    ranges = [range(i + 1, n) for i in range(n)]
    result = 0
    for digit in map(int, str):
    for j in ranges[digit]:
    result += digits[j]
    digits[digit] += 1
    return result

    Это экономит около 25%:

    >>> timeit(lambda:excursion5(CASE), number=1)
    0.497486931970343

Совокупное воздействие этих изменений снижается общее время выполнения около 60%. Это достаточно хорошо, чтобы пройти ограничение по времени?

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

Поскольку вы знаете, что там будет только 3 различных значений, вы должны использовать ведро сортировки. Мы будем хранить графов в словаре, а затем построить строку в конце, чтобы избежать затрат на повторное объединение. Этот код является одновременно проще и быстрее.

def excursion(string):
digits = {'0':0, '1':0, '2':0}
for char in string:
digits[char] += 1
return '0'*digits['0'] + '1'*digits['1'] + '2'*digits['2']

n=0b10000001000000
print(len(excursion('2'*n+'1'*n+'0'*n)))

-2
ответ дан 5 февраля 2018 в 07:02 Источник Поделиться