Задали мне недавно одну задачку, над которой маюсь уже несколько дней. Имеется односвязный список, который используется в многопоточной системе, и изменяется несколькими потоками. Нужно определить, является ли список зацикленным(последний элемент указывает на первый).
Вариант с приравниванием рефералов по двум маркерам аля на каждый оборот внешнего цикла, берущего i-й элемент, внутренним циклом выбираются и сравниваются все последующие рефералы, не подошел. Уже думал над "локальной интерпретацией" этой методы, где при выборке каждого последующего элемента из списка идет сравнение с последующими рефералами, но есть сомнения касательно правильности подхода.
Был бы благодарен за любые предложения касательно решения сей задачи.
Алгоритм следующий:
1) Каждый элемент списка помещаем в нашу обертку, одним из полей которой будет являться ThreadLocal переменная - флаг. Изначально флаг выключен.
2) Когда мы посещаем элемент, поднимаем флаг.
3) Если нашли поднятый флаг - список зациклен. Если уперлись в next==null - нет.
Если такое действие над списком нужно производить не 1 раз, тогда у поднятого флага должно быть 2 значения, которые мы чередуем при каждом запуске.
Не обязательно его делать ThreadLocal. Как я уже говорил, весь проход в целом нужно делать синхронизованным. Иначе лист можно поменяться так, что результат не будет валидным.
Касательно п.1, то изначально был набросок варианта с использованием HashSet'а с целью вычисления повторяющегося элемента, вычисляемого выводом метода add, мол "заливать в Set либо до next==null, либо до add-->false.
Нельзя проверить зацикленность многопоточно поскольку это в любом случае не атомарная операция.
Придется делать доступ до метода синхронизированным. И дальше можно:
1. Сделать фиктивный флаг для каждого node что мы тут уже были
2. Пустить два итератора. Первый по правилу i=i+1, второй по правилу i=i+2. И если второй догонит первый, то у вас есть цикл.
3. Вариант с удалением ссылок на next.
Касательно второго варианта. А что, если "извернуться" и в методе получения элемента списка пустить
один итератор, который будет выполнять сравнение текущей ячейки с next?
А можно поподробнее касательно 3го варианта? Что он из себя представляет?
Armitage89: Причем тут изворот. Вам нужно проверить ситуацию сможет ли итератор догнать другой итератор. Там нет сравнение со следующим.
Идете по списку и удаляете ссылки next(правда нужно, чтобы последний элемент указывал не на NULL, а на конкретный фиктивный node) или делаете ссылку на фиктивный элемент. Можно даже сделать массив ссылок, чтобы потом можно было восстановить лист.
Николай Павлов: вариант с двумя итераторами был отвергнут, аргументируя это тем, что проверка должна выполняться "на ходу", без остановки работы других потоков. Я конечно понимаю, что работа с псевдозацикленным списком должна была бы выполняться с осознанием этого факта, но имеем что имеем.
А разве при удалении ссылок не благоприятным будет факт "упирания" в null?
Armitage89: кстати если у вас есть условие что цикл с последнего на первый, то можно сделать.
делаете head volatile и начинаете итерироваться, если вы нашли head то цикл есть.
Николай Павлов: насколько я понял логику подобных списков, то, при условии, что в this.next вписывается значение head.next, после чего уже идет обновление head.next на this, реферал на начальный элемент
должен был бы быть чем-то сталым, и применять к нему volatile нет нужды. Можно было бы разбить саму процессию на этап определения зацикленности списка, попутно его заблокировав для спокойного выполнения проверки и определения точки конца списка, будь то head.next = null, либо head.next = firstElem. А дальше, при выполнении последующих операций по извлечению элементов делать проверку типа while(head.next != firstElem).
Если я ничего не напутал, то мы получим и нормальную проверку списка, и сможем спокойно оперировать с последующими операциями со списком.
Armitage89: Ну если есть просто head элемент, то да. Скорее всего нужды нету. Но если это какой-то
контеинер, то лучше поставить, а то вдруг другой поток успеет увидеть null.
Проблема тут в том, что если можно делать edit для элемента, то цикл могут после того, как вы прошли этот элемент итератором, если есть только добавление и удаление, то нужно просто с head сравнивать и этого должно хватить. Можно конечно еще навертеть это на cas, чтобы на момент проверки никто не изменил ссылку текущего элемента с head на нормальную.
В любом случае, получается маразм в условии. Может они просто хотели посмотреть на ваше рассуждение?
Даже gc в java не может обойтись без stop wolrd) А задача практически идентичная
Николай Павлов: да вот самому интересна "среда" использования подобного списка. Предполагаю вариант, где существует объект обработчик, который принимает на вход контейнеры, и занимается последующим взаимодействием с ним. Если правильно продумать момент приема объекта списка, то думаю можно обыграть сам момент последующего обращения. Было бы проще, если бы на старте стояло условие "список с элементами", то тут на стадии приема уже можно было без проблем определить "конечную точку".
Касательно вопроса "хода рассуждений", то пожалуй вы правы, ибо предыдущие задачи, где данная задача является последней в списке, имели в себе контекст более на наличие мышления нежели на знания каких-то тонкостей языка.
Вариант конечно, но по подсчету шагов можно и просто при каждом вызове метода получения элемента
делать проверку, прогоняя по циклу аля while(next!=null), с целью упереться либо в стену null, либо всетаки получить next==this, но незнаю насколько этот подход "гуманен".
Armitage89: сразу вспомнилась недавняя лекция на хекслете по спискам Erlang. Они там тоже однонаправленные и добавление новых элементов происходит только в начало, потому что это не требует менять старый список, чтобы получить новый, при этом сохранив одноразовость переменных (и ссылочную прозрачность для многопоточной работы): https://ru.hexlet.io/lessons/practical_erlang_list...
UA3MQJ: хм. А согласно определению википедии, односвязный список имеет характеристику к-ва элементов. Тоись на этапе считывания какбы можно пойти путем пересчета рефералов next. Правда по к-ву шагов, с учетом того, что конструкция может двигаться в момент проверки, это будет эквивалентным. Да и к-во элементов - весч не сталая, а значит начав с 40 элементов, на середине пробежки их может оказаться 30, и... приехали.
предположительно, у нас есть класс, принимающий объекты тематики "список"(аля реализующий интерфейс OneWayList). При этом заранее неизвестно что именно это за реализация - конечная\замкнутая. Отсюда нужно сделать соответствующие телодвижения по определению "с чем имеем дело".
Правда это всё в рамках моих догадок касательно заданного текста задачи.
Средний
Простой