Вопросы Теги

Как обнаружить блокировку процессора с помощью алгоритма [duplicate]

Симон Моурир дал этот пример : 

object o = null;
DateTime d = (DateTime)o;  // NullReferenceException

, где unboxing преобразование (литье) из object (или из одного из классов System.ValueType или System.Enum или из типа интерфейса) - тип значения (кроме Nullable<>) сам по себе дает NullReferenceException.

В другом направлении конверсия бокса из a Nullable<>, которая имеет HasValue, равную false , на ссылочный тип, может дать ссылку null, которая затем может привести к NullReferenceException. Классический пример: 

DateTime? d = null;
var s = d.ToString();  // OK, no exception (no boxing), returns ""
var t = d.GetType();   // Bang! d is boxed, NullReferenceException

Иногда бокс происходит по-другому. Например, с помощью этого не общего метода расширения: 

public static void MyExtension(this object x)
{
  x.ToString();
}

следующий код будет проблематичным: 

DateTime? d = null;
d.MyExtension();  // Leads to boxing, NullReferenceException occurs inside the body of the called method, not here.

Эти случаи возникают из-за специальных правил, используемых во время выполнения при боксе Nullable<> экземпляров.

59
задан Lazer 12 June 2010 в 04:28
поделиться

6 ответов

BFS не будет работать для ориентированного графика при поиске циклов. Рассмотрим A-> B и A-> C-> B как пути от A до B в графе. BFS скажет, что после прохождения по одному из путей, по которым B посещается. Продолжая движение по следующему пути, он скажет, что отмеченный узел B снова найден, следовательно, существует цикл. Очевидно, что здесь нет никакого цикла.

2
ответ дан Aditya Raman 27 August 2018 в 09:43
поделиться
  • 1
    Можете ли вы объяснить, как DFS четко определит, что цикл не существует в вашем примере. Я согласен, что цикл не существует в приведенном примере. Но если мы перейдем от A- & gt; B, а затем A- & gt; C- & gt; B мы обнаружим, что B уже был посещен, а его родительский A - не C..и читал, что DFS будет определять цикл, сравнивая родительский элемент уже посещенного элемента с текущим узлом, из которого мы проверяем в этот момент. DFS неправильно или что? – smasher 20 October 2017 в 14:44
  • 2
    Все, что вы показали здесь, это то, что эта конкретная реализация не работает, а не то, что с BFS это невозможно. Фактически, это возможно , хотя требуется больше работы и пространства. – Prune 17 November 2017 в 18:45
  • 3
    @Prune: Все потоки (я думаю) здесь пытаются доказать, что bfs не будет работать для обнаружения циклов. Если вы знаете, как противодействовать доказательству, вы должны дать доказательство. Просто говоря, что усилий больше не хватает – Aditya Raman 19 November 2017 в 07:47
  • 4
    Поскольку алгоритм указан в связанных проводках, я не считаю целесообразным повторять схему здесь. – Prune 20 November 2017 в 17:11
  • 5
    Я не мог найти никаких связанных сообщений, поэтому просил об этом. Я согласен с вашей точкой зрения о возможностях bfs и только что подумал о реализации. Спасибо за совет :) – Aditya Raman 23 November 2017 в 10:37

Это зависит от того, говорите ли вы о рекурсивных или итеративных реализациях.

Рекурсивная-DFS дважды посещает каждый узел. Итеративно-BFS посещает каждый узел один раз.

Если вы хотите обнаружить цикл, вам нужно исследовать узлы как до, так и после добавления их смещений - как при запуске на узле, так и при завершении работы с узлом.

Это требует больше работы в Iterative-BFS, поэтому большинство людей выбирают Recursive-DFS.

Обратите внимание, что простая реализация Iterative-DFS с, скажем, std :: stack имеет тот же проблема как Iterative-BFS. В этом случае вам нужно поместить фиктивные элементы в стек, чтобы отслеживать, когда вы «завершаете» работу над узлом.

См. Этот ответ для получения более подробной информации о том, как Iterative-DFS требует дополнительной работы, чтобы определить, когда вы «завершить» с узлом (отвечает в контексте TopoSort):

Топологическая сортировка с использованием DFS без рекурсии

Надеюсь, это объясняет, почему люди предпочитают рекурсивный- DFS для проблем, когда вам нужно определить, когда вы «завершаете» обработку узла.

51
ответ дан Community 27 August 2018 в 09:43
поделиться
  • 1
    (Эффективность памяти, потому что вы быстрее возвращаетесь назад и проще реализовать, потому что вы можете просто позволить стеку заботиться о сохранении открытого списка вместо того, чтобы явно его поддерживать). – Amber 19 May 2010 в 22:47
  • 2
    ИМО, это проще, если вы можете положиться на хвостовую рекурсию. – Hank Gay 19 May 2010 в 22:48
  • 3
    +1 для указания сценария двойного пути. – Eyal Schneider 19 May 2010 в 22:57
  • 4
    & quot; отменить их по мере того, как вы возвращаетесь назад & quot; - при вашей собственной опасности! Это может легко привести к поведению O (n ^ 2), в частности, такая DFS неправильно понимает кросс-ребра, как «дерево». ребра («древовидные» ребра также будут неправильным, поскольку они фактически не образуют дерево) – Dimitris Andreou 20 May 2010 в 09:15
  • 5
    @Dimitris Andreo: вы можете использовать три посещаемых состояния вместо двух для повышения производительности. С ориентированными графами существует разница между «Я видел этот узел раньше» и «Этот узел является частью цикла». С неориентированными графами они эквивалентны. – Mark Byers 20 May 2010 в 13:12

BFS может быть разумным, если граф неориентирован (будь моим гостем, показывая эффективный алгоритм с использованием BFS, который будет сообщать о циклах в ориентированном графике!), где каждый «перекрестный край» определяет цикл. Если кросс-ребро {v1, v2}, а корень (в дереве BFS), который содержит эти узлы, r, тогда цикл равен r ~ v1 - v2 ~ r (~ - путь, - - единственный край) о котором можно сообщать почти так же легко, как в DFS.

Единственная причина использования BFS - если вы знаете, что ваш (неориентированный) график будет иметь длинные пути и малую дорожку (другими словами, глубокую и узкую). В этом случае BFS потребует пропорционально меньше памяти для своей очереди, чем стек DFS (оба по-прежнему линейны, конечно).

Во всех остальных случаях DFS явно побеждает. Он работает как с направленными, так и неориентированными графами, и тривиально сообщать о циклах - просто конкатьте любой задний край на путь от предка до потомка, и вы получите цикл. В целом, гораздо лучше и практичнее, чем BFS для этой проблемы.

7
ответ дан Dimitris Andreou 27 August 2018 в 09:43
поделиться
  1. DFS легче реализовать
  2. . Когда DFS найдет цикл, стек будет содержать узлы, образующие цикл. То же самое не относится к BFS, поэтому вам нужно сделать дополнительную работу, если вы хотите также распечатать найденный цикл. Это делает DFS намного более удобным.
20
ответ дан IVlad 27 August 2018 в 09:43
поделиться

Если вы поместите цикл в случайное пятно в дереве, DFS будет стремиться к циклу, когда он покрыт примерно половиной дерева, а в половине случаев он будет уже пройден там, где идет цикл, а половина времени (и будет находить его в среднем по половине остальной части дерева), поэтому он будет оценивать в среднем около 0,5 * 0,5 + 0,5 * 0,75 = 0,625 дерева.

Если вы разместите цикл в случайном месте в дереве, BFS будет стремиться поражать цикл только тогда, когда он оценивает слой дерева на этой глубине. Таким образом, вам обычно приходится оценивать листья балансного двоичного дерева, что обычно приводит к оценке большего количества дерева. В частности, 3/4 времени по крайней мере одна из двух ссылок появляется в листьях дерева, и в этих случаях вы должны оценивать в среднем 3/4 дерева (если есть одна ссылка) или 7 / 8 дерева (если их два), поэтому вы уже ожидаете поиска 1/2 * 3/4 ​​+ 1/4 * 7/8 = (7 + 12) / 32 = 21/32 = 0.656 ... дерева, даже не добавляя затраты на поиск дерева с циклом, добавленным от листовых узлов.

Кроме того, DFS проще реализовать, чем BFS. Таким образом, он может использоваться, если вы не знаете что-то о своих циклах (например, циклы, вероятно, будут близки к корню, из которого вы выполняете поиск, и в этот момент BFS дает вам преимущество).

2
ответ дан Rex Kerr 27 August 2018 в 09:43
поделиться
  • 1
    Там много магических чисел. Я не согласен с тем, что «DFS быстрее». аргументы. Это зависит полностью от ввода, и в этом случае вход не является более распространенным, чем другой. – IVlad 19 May 2010 в 22:56
  • 2
    @Vlad - Цифры не волшебство. Они являются средствами, утверждаются как таковые и почти тривиальны для расчета с учетом сделанных мной предположений. Если аппроксимация по среднему значению является плохим приближением, это будет действительной критикой. (И я прямо заявил, что если вы можете сделать предположения о структуре, ответ может измениться.) – Rex Kerr 20 May 2010 в 04:10
  • 3
    цифры магические, потому что они ничего не значат. Вы взяли случай, когда DFS лучше справляется и экстраполирует эти результаты на общий случай. Ваши заявления необоснованны: «DFS будет стремиться к циклу, когда он покрыт примерно половиной дерева»: подтвердите это. Не говоря уже о том, что вы не можете говорить о циклах в дереве. Дерево по определению не имеет цикла. Я просто не понимаю, в чем дело. DFS будет идти в одну сторону, пока не достигнет тупика, поэтому у вас нет способа узнать, сколько из GRAPH (НЕ дерева) оно будет исследовать в среднем. Вы только что выбрали случайный случай, который ничего не доказывает. – IVlad 20 May 2010 в 08:35
  • 4
    @Vlad - Все нециклические полностью связанные неориентированные графы - это (unrooted unirected) деревья. Я имел в виду «график, который будет деревом для одной ложной ссылки». Возможно, это не основное приложение для алгоритма - возможно, вы хотите найти циклы в некотором запутанном графе, который имеет очень много ссылок, которые делают его не деревом. Но если он является древовидным, усредненным по всем графам, любой узел в равной степени может быть источником упомянутой ложной ссылки, что делает ожидаемое покрытие дерева 50% при попадании ссылки. Поэтому я согласен с тем, что пример, возможно, не был репрезентативным. Но математика должна быть тривиальной. – Rex Kerr 20 May 2010 в 14:40

Чтобы доказать, что график является циклическим, вам просто нужно доказать, что он имеет один цикл (край указывает на себя прямо или косвенно).

В DFS мы берем одну вершину за раз и проверяем, имеет цикл. Как только будет найден цикл, мы можем опустить проверку других вершин.

В BFS нам нужно отслеживать множество вершинных ребер одновременно, а чаще всего в конце вы узнаете, имеет ли он цикл. По мере роста размера графика BFS требует большего пространства, вычислений и времени по сравнению с DFS.

1
ответ дан Steve C 27 August 2018 в 09:43
поделиться
Другие вопросы по тегам:

Похожие вопросы: