[Москва] ищется php-гуру

[valyala]

В случае крайней паранойи можно и от переменной $i избавиться:

bool is_cyclic($list)
{
    if ($first == null) return false;

    $depth = 1;
    $first = $list;
    for (;;) {
        do {
            $list = $list->next;
            if ($list == null) return false;
            if ($list == $first) return true;
        } while (--$depth);

        // восстанавливаем прежнее значение $depth
        while ($first != $list) {
            $first = $first->next;
            ++$depth;
        }

        $depth += $depth;
    }
}

-~{}~ 01.06.06 15:37:

valyala
а теперь протесть свой код =)))

Влом ) Что, где-то в синтаксисе ошибся? Или алгоритм неверный?

 

[MD]

bool is_cyclic($list)
{
if ($first == null) return false;
....

интересное решение

 

[StUV]

Влом )

на бумажке распиши, если "оперативки" не хватает =)

 

[valyala]

Блин, совсем забыл, как в пхп функции объявляются )
:%s/bool/function/g

bool is_cyclic($list)
{
if ($first == null) return false;
....

интересное решение

Так в этом вся соль решения - функция будет правильно работать в 50% случаев, когда список не циклический )

 

[Alexandre]

ООП, php-5; четкое понимание того, что наличие ключевых слов 'protected', 'class', 'final' еще не делает код объектно-ориентированным; и отсутствие их - тоже не является гарантией того, что код не объектно-О;

мои пять копеек
PHP, по определению Буча - не является объектно-ориентированным языком, а только объектным. Соответственно, наличие слов 'protected', 'class', 'final' не дают повод делать код объектно-ориентированным.
я бы выразился, что РНР из всего ООП, РНР использует только классическое наследование и полиморфизм и немного абстракцию.


PS. задачку на зацикливание списка решал на каком-то из собеседований... решение было на "отлично" (но не на пхп)
РЕШЕНИЕ:
так как мы не ограничены во времени, то задается большой разумно ограниченный цикл...
если цикл выполниклся до конца - есть зацикливание и $first -> $next
далее цикл повторяем для следующего элемента
в итоге мы находим $first = $current
или еще увеличиваем на порядок размер цикла.


хотя мне кажется - возможно задачка тако-го типа должна была быть на РНР-Олимпиаде

PSS. по некоторым другим критериям - я в гуру не тяну
а вообще жаль, что вакансия не в Питере... можно былоб попробовать.

 

[AnToXa]

Alexandre
термин "объектно-ориентированый" является придумкой вообще Алана Кея AFAIK, а Буч - вообще непонятно каким боком тут.

да и если что, вот три признака оо от самого Алана.
1. есть только объекты
2. объекты обмениваются сообщениями
3. нет никакого другого способа взаимодействия между объектами кроме посылки сообщения.
(это на память но погуглив можно найти оригинал).

и тут мы без удивления замечаем, что наследование вообще никаким боком к оо не относится, насчет полиморфизма - скорее да чем нет.

-~{}~ 01.06.06 17:23:

PHP, по определению Буча - не является объектно-ориентированным языком, а только объектным. Соответственно, наличие слов 'protected', 'class', 'final' не дают повод делать код объектно-ориентированным.

да вообще никакие ключевые слова не делают код оо или функциональным или каким-то еще. это все в головах, это просто способ проектировать, думать, и обсуждать(англ. realson, не могу подобрать русский вариант нормальный) код.

 

[Alexandre]

да вообще ни какие ключевые слова не делают код оо это все в головах

+1
просто супер!!!

-~{}~ 01.06.06 17:31:

Буч - вообще непонятно каким боком тут.

просто книгу прочел http://www.books.ru/shop/books/56332

 

[StUV]

Alexandre
а если заранее знать размер списка, то вообще нужен 1 указатель и N итераций =)))

 

[Alexandre]

StUV
Если сделать предположение, что у нас не более n элементов
можно и 1 указателем обойтись не зная точного размера списка....

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

алгоритм не оптимален,
но выполняет наложенные ограничения на память (2 указателя)
или 1 - еще менее оптимальный...

 

[StUV]

ага
N_max = (размер всей доступной памяти)/(размер указателя)

 

[Alexandre]

N_max = (размер всей доступной памяти)/(размер указателя)

ну, в некоторых ОС процесс ограничивают в потребление памяти (не знаю как в Линукс, но была такая ось OS-360 /370)

 

[StUV]

нам ничего не известно о работе node->next()
может он данные с базы тянет =)
---
зы: и где модеры "Работы" ?

 

[si]

Alexandre
у тебя не решение а костыли.