Comments 20
Пример с аудиторией — это скорее live lock.
мне кажется код тут не помешал бы.
слишком сухо получилось.
слишком сухо получилось.
>> В следующий раз (с моей стороны) – алгоритм топологической сортировки, который, в том числе, может быть применен при компиляции и анализе цепи активаций нейронов в нейросети.
Какие-нибудь бы попроще примеры на первый раз — например, определение порядка, в котором строить артефакты при помощи make-файла :)
Какие-нибудь бы попроще примеры на первый раз — например, определение порядка, в котором строить артефакты при помощи make-файла :)
Не совсем понят практическую ценность.
Можете практических примеров привести поболее?
И желательно, чтобы они были описаны в формате:
1. Система делает А.
2. Пользователь делает Б.
3. Система делает В.
4.…
И где-то там в середке уже вплетается этот алгоритм, но что именно он делает для внешнего мира? Снутри то одной картинки хватило.
Можете практических примеров привести поболее?
И желательно, чтобы они были описаны в формате:
1. Система делает А.
2. Пользователь делает Б.
3. Система делает В.
4.…
И где-то там в середке уже вплетается этот алгоритм, но что именно он делает для внешнего мира? Снутри то одной картинки хватило.
В том же примере с java2me, виртуальная машина могла бы определить deadlock, и запустить запрос разрешения у пользователя в отдельном потоке.
Главная практическая польза — реализация алгоритма на уровне ОС.
Главная практическая польза — реализация алгоритма на уровне ОС.
Позволю себе отметить, что это скорее академический интерес, нежели практическая польза.
Что для конкретного пользователя это даёт в конкретной системе?
Что для конкретного пользователя это даёт в конкретной системе?
Алгоритм поиска в глубину является вспомогательным в других более практических алгоритмах: тут. Думаю, потом эти алгоритмы появятся в след. статьях, с указанием практического применения.
И так просто вспомнилось, когда мне нужно было C# загрузить файлы по некоторой маске (*.pdf) в БД из некоторой директории (в которой есть поддиректории), то я незадумываясь писал рекурсивную процедуру обхода директорий. Порядок в котором они обходились — и есть Поиск в глубину. В первую попавшуюся до упора, чуть назад в следующую… и.т.д.
И так просто вспомнилось, когда мне нужно было C# загрузить файлы по некоторой маске (*.pdf) в БД из некоторой директории (в которой есть поддиректории), то я незадумываясь писал рекурсивную процедуру обхода директорий. Порядок в котором они обходились — и есть Поиск в глубину. В первую попавшуюся до упора, чуть назад в следующую… и.т.д.
Как раз вчера столкнулся с необходимостью поиска в глубину во время решения одной олимпиадной задачи. Тоже первым делом написал рекурсивную процедуру, но по быстродействию не проходило.
Посмотрел у другого участника его реализацию — вместо рекурсии используется очередь. То есть вместо вызова новой функции новое состояние ставится в очередь на обработку и по одному последовательно обрабатывается. Разница в быстродействии оказалась в 3-4 раза в пользу очереди. Количество состояний было ~50к, глубина рекурсии около 20 шагов.
Посмотрел у другого участника его реализацию — вместо рекурсии используется очередь. То есть вместо вызова новой функции новое состояние ставится в очередь на обработку и по одному последовательно обрабатывается. Разница в быстродействии оказалась в 3-4 раза в пользу очереди. Количество состояний было ~50к, глубина рекурсии около 20 шагов.
«По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс»
Ой, рано отправил.
«По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс» — не совсем верно. Для взаимной блокировки нужна минимум пара ресурсов. Взаимной блокировки при споре об одном ресурсе быть не может. Пример: процесс A требует ресурс X и использует ресурс Y, а процесс B требует ресурс Y и использует ресурс X.
В примере с людьми в проходе тоже есть два ресурса — входы в этот проход с двух сторон. «Петя» стоит на входе в проход и ему нужен чтоб был свободен и выход чтоб пройти. Та же ситуация у «Васи» с другой стороны двери.
«По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс» — не совсем верно. Для взаимной блокировки нужна минимум пара ресурсов. Взаимной блокировки при споре об одном ресурсе быть не может. Пример: процесс A требует ресурс X и использует ресурс Y, а процесс B требует ресурс Y и использует ресурс X.
В примере с людьми в проходе тоже есть два ресурса — входы в этот проход с двух сторон. «Петя» стоит на входе в проход и ему нужен чтоб был свободен и выход чтоб пройти. Та же ситуация у «Васи» с другой стороны двери.
Контур и цикл в графе стало быть одно и то же? Никогда не встречал термин «контур» в этом контексте.
Sign up to leave a comment.
Алгоритмы на графах — Часть 1: Поиск в глубину и проблема взаимоблокировок