Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Страницы: 1 2 >
Riply © (2007-08-16 02:13:00)
Здравтсвуйте !
Допустим, мы работаем следующим образом:
Читаем адрес, идем по нему.
Там читаем следующий адрес и, снова, переходим на него.
И т.д., пока не получаем метку что данный адрес - последний.
Допустим, мы уверены, что она (метка) существует.
Какие методы определения, что мы стали ходить по кругу существуют ?
(Например, семнадцатый по счету адрес отправил нас на четвертый).
P.S.
Надеюсь не очень сумбурно объяснила :)

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

исследователь (2007-08-18 23:39:00) [2]
Удалено модератором
Примечание: оффтоп

Leonid Troyanovsky (2007-08-18 14:53:00) [3]

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

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

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

--
Regards, LVT.

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

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

Leonid Troyanovsky (2007-08-18 14:01:00) [5]

> Riply © (18.08.07 12:18) [23]

> Для 100 000 элементов выигрыш в два раза,

А если сравнить c [3]?

--
Regards, LVT.

(2007-08-18 13:40:00) [6]
Удалено модератором
Примечание: Плохо кончится, парень.

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

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

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

ferr (2007-08-17 13:53:00) [9]
> O(ln(n))

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

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

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

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

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

guav (2007-08-17 12:12:00) [11]

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

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

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

см Leonid Troyanovsky © [12]

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

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

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

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

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

guav (2007-08-16 13:37:00) [13]

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

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

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

Leonid Troyanovsky (2007-08-16 13:07:00) [15]

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

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

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

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

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

--
Regards, LVT.

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

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

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

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

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

Slym (2007-08-16 12:38:00) [18]
акарал... не для этого случая

Leonid Troyanovsky (2007-08-16 12:36:00) [19]

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

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

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

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

--
Regards, LVT.

Leonid Troyanovsky (2007-08-16 12:30:00) [20]

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

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

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

--
Regards, LVT.

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »