Способы защиты от зацикливания.

← →
Riply © (2007-08-16 02:13) [0]

Здравтсвуйте !
Допустим, мы работаем следующим образом:
Читаем адрес, идем по нему.
Там читаем следующий адрес и, снова, переходим на него.
И т.д., пока не получаем метку что данный адрес - последний.
Допустим, мы уверены, что она (метка) существует.
Какие методы определения, что мы стали ходить по кругу существуют ?
(Например, семнадцатый по счету адрес отправил нас на четвертый).
P.S.
Надеюсь не очень сумбурно объяснила :)

← →
ferr © (2007-08-16 02:30) [1]

Ваши походы можно представить в виде такой математической структуры как граф. Ваш граф ориентированный. Вам надо проверить является ли он DAG-ом(Direct Acyclic Graph). Это делается одним обходом в глубину за время O(V+E). Это если задан весь граф.

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

Объяснил ещё более сумбурно, 5ый час утра таки. Спрашивайте, отвечу. Задача кстати достаточно лёгкая.

Тема хорошо разобрана в книгах
1) Кормен Лайзерсов Ривест "Алгоритмы : построение и анализ"
2) Седжвик "Фундаментальный алгоритмы на C++" 4-ая часть, 2-ая книга.

← →
ferr © (2007-08-16 02:32) [2]

Кстати для отображения адреса на номер вершины графа я бы посоветовал использовать хеширование.

Например в c#

Dictionary<string, int> refl;

← →
MBo © (2007-08-16 06:58) [3]

Задача на обнаружение цикла в однонаправленном списке.
Пускаем по списку два указателя, один идет с двойной скоростью, второй - с одинарной. Если есть цикл, то они встретятся.

← →
ferr © (2007-08-16 07:13) [4]

> Задача на обнаружение цикла в однонаправленном списке.
> Пускаем по списку два указателя, один идет с двойной скоростью,
> второй - с одинарной. Если есть цикл, то они встретятся.

Ох, если с каждого адреса переход только в 1 другую вершину, то конечно же дело упрощается, что-то я и не заметил.

А разьве Ваш подход имеет практический интерес? Не проще ли красить пройденные вершины в чёрный цвет?

P.S. Мозг соображает неважно, ввиду недосыпа.

← →
ferr © (2007-08-16 07:21) [5]

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

P.S. Прекращаю обсуждать такую простую задачу. =)

← →
Riply © (2007-08-16 07:58) [6]

>[1] ferr © (16.08.07 02:30)
>Тема хорошо разобрана в книгах
>1) Кормен Лайзерсов Ривест "Алгоритмы : построение и анализ"
>2) Седжвик "Фундаментальный алгоритмы на C++" 4-ая часть, 2-ая книга.
Спасибо.

>[3] MBo © (16.08.07 06:58)
Этот способ мне больше понравился (по "понятности" и трудозатратам на реализацию :)

>[5] ferr © (16.08.07 07:21)
>P.S. Прекращаю обсуждать такую простую задачу. =)
Из того, что существует индивид, для которого данная задача является простой,
совсем не следует, что она проста и для другого, случайно выбранного, индивида.
Во как завернула :)

← →
Slym © (2007-08-16 12:02) [7]

проще красить вершины (1 бит на вершину)

← →
oldman © (2007-08-16 12:21) [8]

А если адрес повторился, а вот по кругу не ходим?

1-2-3-4-5-1-7-8

> Ох, если с каждого адреса переход только в 1 другую вершину,
> то конечно же дело упрощается

← →
Riply © (2007-08-16 12:26) [9]

> [7] Slym © (16.08.07 12:02)
> проще красить вершины (1 бит на вершину)
Не поняла. Как "1 бит на вершину" ?
Допустим я стою в начале "Великого Пути", имея на руках только один первый Pointer.
Пошла по нему, чтобы получить второй. Как мне покрасить первый, кроме как запомнить 4 байта ?

← →
Riply © (2007-08-16 12:29) [10]

> [8] oldman © (16.08.07 12:21)
>А если адрес повторился, а вот по кругу не ходим?
>1-2-3-4-5-1-7-8
Если адрес повторился, то ходим. Т.к. в нем (1 в примере) лежит 2.
Если мы снова попадаем в 1, то он снова пошлет нас на 2 :)
А пока мы бродим адреса не переписываются.

← →
Leonid Troyanovsky © (2007-08-16 12:30) [11]

> oldman © (16.08.07 12:21) [8]
> А если адрес повторился, а вот по кругу не ходим?

> 1-2-3-4-5-1-7-8

Такое возможно, если только адреса модифицируются.

--
Regards, LVT.

← →
Leonid Troyanovsky © (2007-08-16 12:36) [12]

> Riply © (16.08.07 12:26) [9]

> Пошла по нему, чтобы получить второй. Как мне покрасить
> первый, кроме как запомнить 4 байта ?

Запоминать в списке, и проверять вхождение туда.
Думаю, что даже сортированный список не потребуется.

Чего тут думать, трясти надо ;)

--
Regards, LVT.

← →
Slym © (2007-08-16 12:38) [13]

акарал... не для этого случая

← →
Riply © (2007-08-16 12:42) [14]

> [12] Leonid Troyanovsky © (16.08.07 12:36)
>Запоминать в списке, и проверять вхождение туда.
>Думаю, что даже сортированный список не потребуется.
Я думала, что есть способы "покрасивше", типа [3] MBo © :)
Правда при нем мы сделаем несколько лишних шагов, пока нас не догонит первый поинтер :(

>Чего тут думать, трясти надо ;)
:)

← →
Игорь Шевченко © (2007-08-16 12:49) [15]

> Допустим, мы работаем следующим образом:
> Читаем адрес, идем по нему.
> Там читаем следующий адрес и, снова, переходим на него.
>
> И т.д., пока не получаем метку что данный адрес - последний.
>
> Допустим, мы уверены, что она (метка) существует.
> Какие методы определения, что мы стали ходить по кругу существуют
> ?

Не советую думать, что программисты, писавшие файловую систему, дурнее паровоза...

← →
Leonid Troyanovsky © (2007-08-16 13:07) [16]

> Riply © (16.08.07 12:42) [14]

> Я думала, что есть способы "покрасивше", типа [3] MBo ©
> :)

Ну, а чего он не устроил?

> Правда при нем мы сделаем несколько лишних шагов, пока нас
> не догонит первый поинтер :(

Если посчитать общее число сравнений, то, возможно он и
есть наикратчайший.

--
Regards, LVT.

← →
Riply © (2007-08-16 13:24) [17]

> [15] Игорь Шевченко © (16.08.07 12:49)
>Не советую думать, что программисты,
>писавшие файловую систему, дурнее паровоза...
А я так (про программистов) и не думаю.
Чего не могу сказать про пользователей с их
супер-пупер-оптимиз-коррект-чист-улучшающими систему программами :)

← →
guav © (2007-08-16 13:37) [18]

> А я так (про программистов) и не думаю.
> Чего не могу сказать про пользователей с их
> супер-пупер-оптимиз-коррект-чист-улучшающими систему программами
> :)

Точно.
Вот есть программа, которая чистит данные с диска, так она зануляет некоторые ссылки, в итоге даже не "ходим по гругу", а "стоим на месте".
Для ссылок типа из атрибута на следующий атрибут, которые только вперёд - просто считать беззнаковыми, проверять "достаточно ли вперёд" и "не слишком ли вперёд".
Для ссылок которые могут быть и назад (ссылка из папки на файл)... у меня std::set , в Delphi близкого аналога не знаю, но суть в том что это (отсортированный) контейнер; он содержит все посещённые метки.

← →
Riply © (2007-08-17 08:22) [19]

>[18] guav © (16.08.07 13:37)
>Точно.
>Вот есть программа, которая чистит данные с диска, так она зануляет некоторые ссылки,
>в итоге даже не "ходим по гругу", а "стоим на месте".
А как называется ?
Это не в целях антирекламы, хочу потестировать свой модуль, после ее "очистки диска" :)

>Для ссылок типа из атрибута на следующий атрибут,
>которые только вперёд - просто считать беззнаковыми,
>проверять "достаточно ли вперёд" и "не слишком ли вперёд".
Это у меня сделано.

>Для ссылок которые могут быть и назад (ссылка из папки на файл)... у меня std::set ,
>в Delphi близкого аналога не знаю, но суть в том что это (отсортированный) контейнер;
>он содержит все посещённые метки.
Организуем :)
А бывали такие случаи, что он (std::set) реально помогал в работе ?

← →
guav © (2007-08-17 12:12) [20]

> А как называется ?
> Это не в целях антирекламы, хочу потестировать свой модуль,
> после ее "очистки диска" :)

Всё равно не хочу светить название, давай почтой скажу в ответ на твой проект, когда потестирую его.

> А бывали такие случаи, что он (std::set) реально помогал
> в работе ?

см Leonid Troyanovsky © [12]

> Думаю, что даже сортированный список не потребуется.

Преимуществo сортированного контейнера std::set в том, что поиск требует времени не O(n), а O(ln(n)) . Если устраивает линейный поиск, то можно взять и не-сортированный контейнер.

← →
Riply © (2007-08-17 12:21) [21]

> [20] guav © (17.08.07 12:12)
>Всё равно не хочу светить название, давай почтой
>скажу в ответ на твой проект, когда потестирую его.
Хорошо. Надеюсь, что скоро (сегодня\завтра) смогу его выслать.

> O(ln(n))

Обычно пишут O(log(n)) подразумевая что основание не имеет значение т.к. символ О поедает постоянный коэффициент. Некоторые авторы предпочитают употреблять под символом log(n) двоичный логарифм. Т.к. в set количество операций пропорционально именно двоичному логарифму то уместнее писать O(log(n)). Ну это так, глупости с моей стороны.

Что касается поиска аналогов для дельфи то можно искать любые хорошие реализации балансированных деревьев, например самых популярных, таких как AVL и RB.

Данный подход даст Вам гарантированную оценку O(log(n), если вы работаете со строками то можно попробовать такой контейнер как Trie, в русской литературе именуемый бором(данный подход проще и работает порой быстрее). Если же хочется завернутся ещё больше то можно попробовать хеширование, но тут надо очень хорошо представлять что делаешь.

P.S. Зачем Вам, в Вашей задаче аналоги std::set я пока что-то не понимаю.

>[12] Leonid Troyanovsky © (16.08.07 12:36)
>Запоминать в списке, и проверять вхождение туда.
>Думаю, что даже сортированный список не потребуется.
>Чего тут думать, трясти надо ;)

Потрясла :)
Сортированный список требуется.
Для 100 000 элементов выигрыш в два раза, причем "не сортированнй" был поставлен
в более выгодные условия: его сразу заполнили нулевыми элементами
(перебор шел, разумеется, не по всему списку, а по кол-ву "реальных" элементов),
в то время как сортировааный (бедалага :) добавлял по одному.

>[22] ferr © (17.08.07 13:53)
>P.S. Зачем Вам, в Вашей задаче аналоги std::set я пока что-то не понимаю.
А что тебя смущает ?

← →
имя (2007-08-18 13:40) [25]

Удалено модератором
Примечание: Плохо кончится, парень.

> [25] RipIay © (18.08.07 13:40)
>Похоже, что я уже всех достала:(
Одного закомлексованного идиота,
видимо не сумевшего выбраться из переходного возраста, достала точно.

> [26] Leonid Troyanovsky © (18.08.07 14:01)
>А если сравнить c [3]?
Это пока еще не пробовала.

> Riply © (18.08.07 14:19) [27]

> Это пока еще не пробовала.

Расскажи, если попробуешь.
Может, все вопросы и отпадут.

--
Regards, LVT.

Удалено модератором
Примечание: оффтоп

>[28] Leonid Troyanovsky © (18.08.07 14:53)
>Расскажи, если попробуешь.
>Может, все вопросы и отпадут.
Способ, предложенный [3] MBo © (16.08.07 06:58),
при "малых затратах" на переход от поинтера к поинтеру,
может дать сто очков вперед остальным.
Очень серьезным его недостатком является невозможность указать место,
откуда началось "зацикливание" (во всяком случае, я не знаю как). В моей задаче это не подходит.
Резюме: Способ [3] - самый оптимальный при "малых затратах на переход", и когда нужно
знать только одно: зациклена цепочка или нет.

Способы защиты от зацикливания. Найти похожие ветки