DjangoBB LoFi version

Полная версия: Задача. Текстовый редактор

Начало » Центр помощи » Задача. Текстовый редактор

1 2

sharkk

Март 30, 2016 20:38:01

Текстовый редактор OLE (One-Line Editor) работает с текстом, состоящим ровно из одной строки строчных латинских букв. Редактор поддерживает следующие команды, длиной в один символ каждая:
L – переместить курсор на 1 символ влево
R – переместить курсор на 1 символ вправо
X – удалить символ справа от позиции курсора
строчная латинская буква – вставить справа от текущей позиции курсора указанную букву, переместить курсор на один символ вправо
Команды, пытающиеся переместить курсор за пределы строки или удалить символ справа от последнего символа строки, игнорируются редактором.
Требуется по данному начальному состоянию строки, начальной позиции курсора и последовательности команд определить результат работы редактора.
Длина исходной строки находится в диапазоне от 1 до 1000000 символов. Длина строки команд находится в диапазоне от 1 до 100000 символов.
0 <= p <= длина исходной строки.
Исходные данные
Входной файл состоит из 3 строк. В первой строке содержится позиция курсора p, (0 - курсор перед первым символом, 1 - после первого перед вторым, и т.д.) во второй строке - начальное состояние строки редактора, в третьей - последовательность команд.
Результат
Выходной файл должен содержать строку, полученную в результате выполнения команд.

def k(p, text, command):
    text_const = [chr(i) for i in range(ord('a'), ord('z') + 1)]
    text = list(text)
    command = list(command)
    for i in command:
        if i in text_const:
            buf_text = []
            cur = len(text)
            while p != cur:
                buf_text.append(text.pop())
                cur -= 1
            text.append(i)
            while len(buf_text) != 0:
                text.append(buf_text.pop())
            p += 1
        if i == 'L':
            p -= 1
        if i == 'R':
            p += 1
        if i == 'X':
            cur = len(text)
            buf_text = []
            while p != cur:
                buf_text.append(text.pop())
                cur -= 1
            buf_text.pop()
            while len(buf_text) != 0:
                text.append(buf_text.pop())
    return text

print(''.join(k(1, 'abc', 'deLXX')))

Надо уложиться в 2е секунды. Буду рад любой подсказке

py.user.next

Март 31, 2016 04:04:48

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

sharkk

Апрель 1, 2016 00:55:51

Спасибо. Исправил, но все равно долго. Может алгоритм какой есть?)
Если я верно понимаю то - обход по списку n и условие проверки тоже n тогда n^2. Так?)

def k(p, text, command):
    text_const = [chr(i) for i in range(ord('a'), ord('z') + 1)]
    text = list(text)
    command = list(command)
    cur = len(text)
    for i in command:
        if i in text_const:
            buf_text = []
            while p != cur:
                buf_text.append(text.pop())
                cur -= 1
            text.append(i)
            while len(buf_text) != 0:
                text.append(buf_text.pop())
                cur += 1
            p += 1
            cur += 1
        if i == 'L':
            p -= 1
        if i == 'R':
            p += 1
        if i == 'X':
            buf_text = []
            while p != cur:
                buf_text.append(text.pop())
                cur -= 1
            buf_text.pop()
            while len(buf_text) != 0:
                text.append(buf_text.pop())
                cur += 1
    return text

py.user.next

Апрель 1, 2016 03:19:35

Ты должен сделать только один список - из текста. Сделать два указателя: один - текущая позиция (он изначально равен p, можешь его и использовать), другой - указатель на последний элемент (его сначала вычисляешь через длину текста, а в процессе добавления/удаления символа увеличиваешь/уменьшаешь на единицу). И просто надо проходить по командам (их вообще не надо превращать в список, они уже строкой идут изначально) и выполнять их над списком текста, меняя текущий указатель. Символы для добавления a-z вообще не нужны, потому что определяются через islower().

>>> 'l'.islower()
True
>>> 'L'.islower()
False
>>>

Для вставки символа в список текста используй insert().

sharkk
Может алгоритм какой есть?)

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

sharkk

Апрель 2, 2016 17:10:47

Изначально примерно так было, но временная сложность insert O(n). От него и стал уходить в сторону append O(1), думал поможет )).
Так имел ввиду?

def k(p, text, command):
    text = list(text)
    for i in command:
        if i.islower():
            text.insert(p, i)
            p += 1
        if i == 'L':
            p -= 1
        if i == 'R':
            p += 1
        if i == 'X':
            text.pop(p)
    return text

sharkk

Апрель 2, 2016 19:09:50

Создав два списка до и после курсора и опперируя ими, сохратил время прилично, может будет достаточно.

def k(p, text, command):
    text_before = list(text[:p])
    text_after = list(text[p:])
    cur = len(text_after)
    if p < 0:
        pass
    if p > len(text):
        pass
    else:
        for i in command:
            if i.islower():
                text_before.append(i)
                p += 1
            if i == 'L':
                if p == 0:
                    pass
                else:
                    text_after.insert(0, text_before.pop())
                    p -= 1
                    cur += 1
            if i == 'R':
                if cur == 0:
                    pass
                else:
                    text_after.append(text_after.pop(0))
                    p += 1
                    cur -= 1
            if i == 'X':
                if cur == 0:
                    pass
                else:
                    text_after.pop(0)
                    cur -= 1
    return text_before + text_after

py.user.next

Апрель 3, 2016 02:24:58

sharkk
но временная сложность insert O(n). От него и стал уходить в сторону append O(1)

Во-первых, ты их ещё не написал, чтобы оптимизировать.
Во-вторых, по скорости они практически не отличаются.

Вот ошибки

Короткий вариант

[guest@localhost oneedit]$ python3 -m doctest oneedit1.doct 
**********************************************************************
File "oneedit1.doct", line 27, in oneedit1.doct
Failed example:
    f(-1, '', 'a')
Expected:
    ''
Got:
    'a'
**********************************************************************
File "oneedit1.doct", line 29, in oneedit1.doct
Failed example:
    f(1, '', 'a')
Expected:
    ''
Got:
    'a'
**********************************************************************
File "oneedit1.doct", line 31, in oneedit1.doct
Failed example:
    f(2, 'a', 'b')
Expected:
    'a'
Got:
    'ab'
**********************************************************************
File "oneedit1.doct", line 53, in oneedit1.doct
Failed example:
    f(0, 'a', 'LRb')
Expected:
    'ab'
Got:
    'ba'
**********************************************************************
File "oneedit1.doct", line 55, in oneedit1.doct
Failed example:
    f(0, 'a', 'LLRb')
Expected:
    'ab'
Got:
    'ba'
**********************************************************************
File "oneedit1.doct", line 57, in oneedit1.doct
Failed example:
    f(0, 'a', 'LLLRb')
Expected:
    'ab'
Got:
    'ba'
**********************************************************************
File "oneedit1.doct", line 59, in oneedit1.doct
Failed example:
    f(1, 'a', 'RLb')
Expected:
    'ba'
Got:
    'ab'
**********************************************************************
File "oneedit1.doct", line 61, in oneedit1.doct
Failed example:
    f(1, 'a', 'RRLb')
Expected:
    'ba'
Got:
    'ab'
**********************************************************************
File "oneedit1.doct", line 63, in oneedit1.doct
Failed example:
    f(1, 'a', 'RRRLb')
Expected:
    'ba'
Got:
    'ab'
**********************************************************************
File "oneedit1.doct", line 67, in oneedit1.doct
Failed example:
    f(0, '', 'X')
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python3.3/doctest.py", line 1287, in __run
        compileflags, 1), test.globs)
      File "<doctest oneedit1.doct[27]>", line 1, in <module>
        f(0, '', 'X')
      File "./oneedit1.py", line 14, in k
        text.pop(p)
    IndexError: pop from empty list
**********************************************************************
File "oneedit1.doct", line 73, in oneedit1.doct
Failed example:
    f(1, 'a', 'X')
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python3.3/doctest.py", line 1287, in __run
        compileflags, 1), test.globs)
      File "<doctest oneedit1.doct[30]>", line 1, in <module>
        f(1, 'a', 'X')
      File "./oneedit1.py", line 14, in k
        text.pop(p)
    IndexError: pop index out of range
**********************************************************************
File "oneedit1.doct", line 78, in oneedit1.doct
Failed example:
    f(0, '', 'XX')
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python3.3/doctest.py", line 1287, in __run
        compileflags, 1), test.globs)
      File "<doctest oneedit1.doct[32]>", line 1, in <module>
        f(0, '', 'XX')
      File "./oneedit1.py", line 14, in k
        text.pop(p)
    IndexError: pop from empty list
**********************************************************************
File "oneedit1.doct", line 80, in oneedit1.doct
Failed example:
    f(0, 'a', 'XX')
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python3.3/doctest.py", line 1287, in __run
        compileflags, 1), test.globs)
      File "<doctest oneedit1.doct[33]>", line 1, in <module>
        f(0, 'a', 'XX')
      File "./oneedit1.py", line 14, in k
        text.pop(p)
    IndexError: pop from empty list
**********************************************************************
File "oneedit1.doct", line 82, in oneedit1.doct
Failed example:
    f(1, 'ab', 'XX')
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python3.3/doctest.py", line 1287, in __run
        compileflags, 1), test.globs)
      File "<doctest oneedit1.doct[34]>", line 1, in <module>
        f(1, 'ab', 'XX')
      File "./oneedit1.py", line 14, in k
        text.pop(p)
    IndexError: pop index out of range
**********************************************************************
File "oneedit1.doct", line 85, in oneedit1.doct
Failed example:
    f(1, '', 'X')
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python3.3/doctest.py", line 1287, in __run
        compileflags, 1), test.globs)
      File "<doctest oneedit1.doct[35]>", line 1, in <module>
        f(1, '', 'X')
      File "./oneedit1.py", line 14, in k
        text.pop(p)
    IndexError: pop from empty list
**********************************************************************
File "oneedit1.doct", line 87, in oneedit1.doct
Failed example:
    f(2, 'a', 'X')
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python3.3/doctest.py", line 1287, in __run
        compileflags, 1), test.globs)
      File "<doctest oneedit1.doct[36]>", line 1, in <module>
        f(2, 'a', 'X')
      File "./oneedit1.py", line 14, in k
        text.pop(p)
    IndexError: pop index out of range
**********************************************************************
1 items had failures:
  16 of  37 in oneedit1.doct
***Test Failed*** 16 failures.
[guest@localhost oneedit]$

Длинный вариант

[guest@localhost oneedit]$ python3 -m doctest oneedit2.doct 
**********************************************************************
File "oneedit2.doct", line 27, in oneedit2.doct
Failed example:
    f(-1, '', 'a')
Expected:
    ''
Got:
    'a'
**********************************************************************
File "oneedit2.doct", line 39, in oneedit2.doct
Failed example:
    f(0, 'a', 'Rb')
Expected:
    'ab'
Got:
    'ba'
**********************************************************************
File "oneedit2.doct", line 41, in oneedit2.doct
Failed example:
    f(0, 'a', 'RRb')
Expected:
    'ab'
Got:
    'ba'
**********************************************************************
File "oneedit2.doct", line 48, in oneedit2.doct
Failed example:
    f(0, 'a', 'RbLLc')
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python3.3/doctest.py", line 1287, in __run
        compileflags, 1), test.globs)
      File "<doctest oneedit2.doct[19]>", line 1, in <module>
        f(0, 'a', 'RbLLc')
      File "./oneedit2.py", line 20, in k
        text_after.insert(0, text_before.pop())
    IndexError: pop from empty list
**********************************************************************
File "oneedit2.doct", line 50, in oneedit2.doct
Failed example:
    f(1, 'a', 'LbRRc')
Expected:
    'bac'
Got:
    'bca'
**********************************************************************
File "oneedit2.doct", line 53, in oneedit2.doct
Failed example:
    f(0, 'a', 'LRb')
Expected:
    'ab'
Got:
    'ba'
**********************************************************************
File "oneedit2.doct", line 55, in oneedit2.doct
Failed example:
    f(0, 'a', 'LLRb')
Expected:
    'ab'
Got:
    'ba'
**********************************************************************
File "oneedit2.doct", line 57, in oneedit2.doct
Failed example:
    f(0, 'a', 'LLLRb')
Expected:
    'ab'
Got:
    'ba'
**********************************************************************
1 items had failures:
   8 of  37 in oneedit2.doct
***Test Failed*** 8 failures.
[guest@localhost oneedit]$

Сравнение по времени: первые результаты - для короткого; вторые результаты - для длинного.

[guest@localhost oneedit]$ ./oneeditcmp.py 
[2.9612534179996146, 2.9638922090007327, 2.9655386000004]
[2.245790377999583, 2.2452530009995826, 2.2453736839997873]
[guest@localhost oneedit]$

То есть длинный даже в два раза не быстрее короткого.

sharkk
сохратил время прилично

Приличное сокращение - это от пяти раз. Если бы оно было быстрее в пять раз или хотя бы в три раза, то можно было бы говорить о приличном сокращении времени. А так ты просто усложнил код.
А чем это чревато, ну, вот давай теперь исправь эти ошибки в длинном коде - сразу поймёшь.

sharkk

Апрель 3, 2016 09:30:42

изначально был вот этот вариант. Доработанный с тобой канечно

Время Elapsed time: 250.039 sec

def k(p, text, command):
    text = list(text)
    for i in command:
        if i.islower():
            text.insert(p, i)
            p += 1
        if i == 'L':
            p -= 1
        if i == 'R':
            p += 1
        if i == 'X':
            text.pop(p)
    return text

    return text

Второй с двумя списками который.
Время Elapsed time: 24.508 sec

def k(p, text, command):
    text_before = list(text[:p])
    text_after = list(text[p:])
    cur = len(text_after)
    if p < 0:
        pass
    if p > len(text):
        pass
    else:
        for i in command:
            if i.islower():
                text_before.append(i)
                p += 1
            if i == 'L':
                if p == 0:
                    pass
                else:
                    text_after.insert(0, text_before.pop())
                    p -= 1
                    cur += 1
            if i == 'R':
                if cur == 0:
                    pass
                else:
                    text_after.append(text_after.pop(0))
                    p += 1
                    cur -= 1
            if i == 'X':
                if cur == 0:
                    pass
                else:
                    text_after.pop(0)
                    cur -= 1
    return text_before + text_after

Время мерял примитивно, потому что больше никак не умею

В 10 раз это существенно

, но видимо рано радоваться.

test_text = [chr(i) for i in range(ord('a'), ord('z') + 1)]
test_command = test_text + ['L', 'R', 'X']

start = time.time()
my_list = []
for i in range(1000000):
    item = random.choice(test_text)
    my_list.append(item)

my_command = []
for i in range(100000):
    item = random.choice(test_command)
    my_command.append(item)

print("Elapsed time: {:.3f} sec".format(time.time() - start))

Подскажи, как ты тесты прогонял?
Спасибо за участие.

py.user.next

Апрель 3, 2016 10:05:58

sharkk
Время мерял примитивно, потому что больше никак не умею

Вот этим меряй

#!/usr/bin/env python3
 
import timeit
import oneedit1, oneedit2
 
def f1():
    oneedit1.k(0, 'abcd' * 100, 'abcd' * 100)
 
def f2():
    oneedit2.k(0, 'abcd' * 100, 'abcd' * 100)
 
def main():
    t1 = timeit.Timer('f1()', 'from __main__ import f1')
    t2 = timeit.Timer('f2()', 'from __main__ import f2')
 
    for t in t1, t2:
        print(t.repeat(3, 10000))
 
if __name__ == '__main__':
    main()

[guest@localhost oneedit]$ ./oneeditcmp.py 
[4.735752986998705, 4.707463580001786, 4.698070088001259]
[2.4176531019984395, 2.4280325540021295, 2.428312857999117]
[guest@localhost oneedit]$

sharkk
Подскажи, как ты тесты прогонял?

Ну, я их написал сначала, а потом запустил.

>>> from oneedit1 import k as f
>>>
>>> # Команды без перемещений курсора
>>> f(0, '', '')
''
>>>
>>> f(0, '', 'a')
'a'
>>> f(0, '', 'ab')
'ab'
>>> f(0, 'a', 'b')
'ba'
>>> f(0, 'ab', 'cd')
'cdab'
>>>
>>> f(1, 'ab', 'c')
'acb'
>>> f(1, 'ab', 'cd')
'acdb'
>>>
>>> f(2, 'ab', 'c')
'abc'
>>> f(2, 'ab', 'cd')
'abcd'
>>>
>>> # Игнорирование команд с курсором за границами
>>> f(-1, '', 'a')
''
>>> f(1, '', 'a')
''
>>> f(2, 'a', 'b')
'a'
>>>
>>> # Команды с перемещениями курсора
>>> f(0, '', 'Ra')
'a'
>>> f(0, '', 'RRa')
'a'
>>> f(0, 'a', 'Rb')
'ab'
>>> f(0, 'a', 'RRb')
'ab'
>>> f(1, 'a', 'Lb')
'ba'
>>> f(1, 'a', 'LLb')
'ba'
>>>
>>> f(0, 'a', 'RbLLc')
'cab'
>>> f(1, 'a', 'LbRRc')
'bac'
>>>
>>> f(0, 'a', 'LRb')
'ab'
>>> f(0, 'a', 'LLRb')
'ab'
>>> f(0, 'a', 'LLLRb')
'ab'
>>> f(1, 'a', 'RLb')
'ba'
>>> f(1, 'a', 'RRLb')
'ba'
>>> f(1, 'a', 'RRRLb')
'ba'
>>>
>>> # Команды с удалением
>>> f(0, '', 'X')
''
>>> f(0, 'a', 'X')
''
>>> f(0, 'ab', 'X')
'b'
>>> f(1, 'a', 'X')
'a'
>>> f(1, 'ab', 'X')
'a'
>>>
>>> f(0, '', 'XX')
''
>>> f(0, 'a', 'XX')
''
>>> f(1, 'ab', 'XX')
'a'
>>>
>>> f(1, '', 'X')
''
>>> f(2, 'a', 'X')
'a'
>>>

Команда для запуска тестов

python3 -m doctest oneedit1.doct

sharkk

Апрель 3, 2016 18:03:51

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

.
Если интересно, могу ссылку на сайт с логином дать

def f(p, text, command):
    text_before = list(text[:p])
    text_after = list(text[p:])
    cur = len(text_after)
    if p < 0:
        p = 0
    if p > len(text):
        p = len(text)
    else:
        for i in command:
            if i.islower():
                text_before.append(i)
                p += 1
            if i == 'L' and text_before != []:
                if p == -1:
                    p = 0
                else:
                    text_after.insert(0, text_before.pop())
                    p -= 1
                    cur += 1
            if i == 'R' and text_after != []:
                if cur == -1:
                    cur = 0
                else:
                    text_after.append(text_after.pop(0))
                    p += 1
                    cur -= 1
            if i == 'X' and text_after != []:
                if cur == -1:
                    cur = 0
                else:
                    text_after.pop(0)
                    cur -= 1
    return text_before + text_after