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

valyala

Новичок
В случае крайней паранойи можно и от переменной $i избавиться:
PHP:
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

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

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

valyala

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

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

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

Alexandre

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


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


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

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

AnToXa

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

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

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

-~{}~ 01.06.06 17:23:

PHP, по определению Буча - не является объектно-ориентированным языком, а только объектным. Соответственно, наличие слов 'protected', 'class', 'final' не дают повод делать код объектно-ориентированным.
да вообще никакие ключевые слова не делают код оо или функциональным или каким-то еще. это все в головах, это просто способ проектировать, думать, и обсуждать(англ. realson, не могу подобрать русский вариант нормальный) код.
 

StUV

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

Alexandre

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

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

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

StUV

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

;)
 

Alexandre

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

StUV

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