Python-сообщество

Это классическая задача поиска циклов в последовательности: http://en.wikipedia.org/wiki/Cycle_detection
Там же есть код 2х решений на Питоне.

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

Отредактировано (Авг. 27, 2010 21:48:56)

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

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

Но это возможно.
Мне пришел в голову такой алгоритм после того, как один бухгалтер стал возмущаться, что решение с двумя указателями - это не решение.
И так, мы бежим одним указателем по списку. Второй указатель мы создать не можем и памяти нам хватает только для того, чтобы запомнить один элемент списка. Что мы делаем? Мы эмулируем второй указатель. Это значит, что мы запоминаем каждый k-й элемент списка в ту же самую единственную ячейку, где k меняется как 2k. Вот пример:
1) Пусть N - это порядковый номер елемента списка, на который указывает наш указатель (N = 1,2,3,4,…..)
2) Запоминаем текущий N-й елемент списка в нашу единственную ячейку
3) Делаем N шагов указателем по списку, проверяя каждый раз елемент из списка с элементом из нашей ячейки.
4) Если элемент не найден, то, очевидно, номер текущего элемента списка есть N = 2*N (заменяем N на 2 умножить на N ) и переходим к пункту 2)
5) Если удалось найти совпадение элементов, то далее элементарно определяем длину цикла списка, продолжая бежать по списку. Конец.

Назовем этот алгоритм алгоритмом Ширкалина.

Отредактировано (Авг. 28, 2010 06:43:40)

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

И так, мы бежим одним указателем по списку. Второй указатель мы создать не можем и памяти нам хватает только для того, чтобы запомнить один элемент списка. Что мы делаем? Мы эмулируем второй указатель. Это значит, что мы запоминаем каждый k-й элемент списка в ту же самую единственную ячейку, где k меняется как 2k. Вот пример:
1) Пусть N - это порядковый номер елемента списка, на который указывает наш указатель (N = 1,2,3,4,…..)

2) Запоминаем текущий N-й елемент списка в нашу единственную ячейку

3) Делаем N шагов указателем по списку, проверяя каждый раз елемент из списка с элементом из нашей ячейки.

4) Если элемент не найден, то, очевидно, номер текущего элемента списка есть N = 2*N (заменяем N на 2 умножить на N ) и переходим к пункту 2)

5) Если удалось найти совпадение элементов, то далее элементарно определяем длину цикла списка, продолжая бежатьпо списку. Конец.

Назовем этот алгоритм алгоритмом Ширкалина.

Отредактировано (Авг. 28, 2010 12:10:27)

Ed
Это спорное утверждение. Кэш нужен, чтобы хранить уже прочитанные элементы итератора. По идее он должен включать начало и первый цикл как минимум. Его можно уменьшать по мере прохождения, так что он может быть и меньше. Кэш динамический, естественно. В случае питона - просто список элементов, которые мы уже достали из итератора.

Ed
Оч хорошо, посмотрим на ваш алгоритм. Возьмем последовательность 2,1,5,1,7,8,1,6,3,1,6,3,1,6,3…
Ответом должен по идее быть цикл 1,6,3, если я правильно понял условие задачи.

Ed
Я предполагаю, что мог вас неправильно понять. Предлагаю показать код. Алгоритм по виду простой, так что думаю вас не затруднит его запрограммировать.

def gen():
    """ simple cycle list generator """
    for i in [1,5,7,45,18,2]: # head of list
        yield i
    while True:
        for i in [65,87,44,70,59,21,3,4]: # cycle of list
            yield i

def getCycleLength( source ):
    """ the function detects the cycle in singly connected list and returns its length """
    mem = next(source) # remember 1st item
    N = 1 # the next index of item to memorize
    for i, item in enumerate( source, 1 ):
        if item == mem:
            return i - N//2 # return the length of cycle
        if i == N: 
            mem = item  # remember Nth item
            N = N*2 + 1 # double the index for next item to memorize

print( "Cycle length = ", getCycleLength( iter(gen()) ) )

def gen1():
    a = 23
    while True:
        a = (a*a + 4) % 856421
        yield a

Отредактировано (Сен. 1, 2010 10:14:03)

Isem
Каждый элемент нашего односвязного списка уникален, иначе бы это был уже не список.

>>> type([1,1,1])
<type 'list'>

Далее ваши рассуждения уже не относятся к условию задачи.

есть итератор, довольно сложный, который генерирует, например, длинные строки (1000 символов каждая, скажем).
Нужно определить длину цикла этого итератора. Но надо учитывать, что цикл может начинаться (и заканчиваться, соответственно) не с первого элемента, а совсем с другого. Сама же последовательность итератора может быть очень длинная.

Отредактировано (Сен. 1, 2010 10:21:43)

Isem
В качестве еще одного примера списка можно посмотреть вот такой генератор:

def gen1():
    a = 23
    while True:
        a = (a*a + 4) % 856421
        yield a

У списка, генерируемого этим генератором длина цикла = 28, а длина ‘головы’ списка выражается 4-х значным числом.

time python brent.py
28 2705

real    0m0.106s
user    0m0.068s
sys     0m0.014s

Ed
С каких это пор список подразумевает уникальность элементов?
http://en.wikipedia.org/wiki/Linked_lis … ther_lists

Кроме того, не забывайте, мы с вами на каком мы с вами форуме:
Код:

>>> type()
<type ‘list’>

a=3.0
b=3.0
print( a == b ) # выдаст True
print( a is b ) # выдаст False

Ed
Кроме того, я здесь давал ссылку на статью в википедии, где приводятся 2 алгоритма решение общей задачи. Ни о какой уникальности речь не шла. Вы вроде не возражали. Я так не играю. Это сильно смахивает на подгонку условия под неработающую программу. Всего хорошего!

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

Отредактировано (Сен. 1, 2010 12:40:58)

Ed
Хороший пример, спасибо. Хоть в общем случае кэша может и не хватить, но в этом конкретном все прекрасно работает:
Код:

time python brent.py
28 2705

real 0m0.106s
user 0m0.068s
sys 0m0.014s