Соберитесь с детьми, пора рассказать. А это история о захватывающей дух гонке между черепахой и зайцем. Спойлер: в конце концов, черепаха догоняет зайца. Ну вроде…

Хорошо, я давно не писал, потому что ... Ну, я не хотел. Затем вчера я наткнулся на этот вопрос на HackerRank, который оказался последним вопросом в разделе C ++, и нашел его довольно интересным. Но прежде чем непосредственно погрузиться в вопрос, давайте начнем с более простой задачи и постепенно будем ее развивать.

Обнаружение циклов в связанных списках

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

Есть несколько подходов к этой проблеме. Давайте рассмотрим их один за другим:

  1. Мы можем немного изменить структуру данных, добавив в узлы логический флаг. Затем все, что нам нужно, - это перебрать связанный список и отметить посещенные узлы. Если в какой-то момент мы встретим отмеченный узел, это означает, что мы нашли цикл.
struct Node {
    int data;
    Node* next;
    bool visited = false;
}
bool containsCycle(Node* head) {
    while (head != NULL) {
        if (head->visited) {
            return true;
        }
        head->visited = true;
        head = head->next;
    }
    return false;
}

2. Вышеупомянутый алгоритм работает отлично и требует O (n) для завершения. Однако вы не всегда можете изменить существующую структуру данных. Значит, вам нужен альтернативный метод маркировки. Мы можем ввести вспомогательный набор для хранения посещенных узлов вместо их маркировки.

unordered_set<Node*> lookup;
bool containsCycle(Node* head) {
    while (head != NULL) {
        if (lookup.count(head) > 0) {
            return true;
        }
        lookup.insert(head);
        head = head->next;
    }
    return false;
}

3. Использование поиска также работает в O (n), но мы использовали дополнительное пространство для хранения посещенных узлов (плюс, мы потратили дополнительное время на функцию хеширования). Очевидно, что существует лучший и более разумный способ решения этой проблемы, который подводит нас к самой теме этого сообщения: Алгоритмы определения цикла Флойда и Брента…

Алгоритм Флойда

В этом методе мы будем использовать два указателя вместо одного, один из них выполняет итерацию быстрее, чем другой. Быстрого назовем зайцем, а медленного - черепахой - отсюда и история.

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

bool floyd(Node* head) {
    Node* tortoise = head;
    Node* hare = head;
    while (hare != NULL && hare->next != NULL) {
        tortoise = tortoise->next;
        hare = hare->next->next;
        if (tortoise == hare) {
            return true;
        }
    }
    return false;
}

Это так просто. Но для того, чтобы по-настоящему понять, что эта стратегия работает, возьмите ручку и бумагу, нарисуйте разные футляры и посчитайте шаги. Давай, сделай это сейчас! Я считаю, что эта стратегия работает для стрелок с разной скоростью.

Итак, вы хотите найти начальный узел цикла? Легко… Просто держите зайца там, где встречаются оба указателя, и инициализируйте черепаху обратно к голове. Затем переместите оба указателя на один шаг, пока они снова не встретятся. Ваш цикл начинается там, где они встретились.

// Keep the hare at the meeting point
tortoise = head;
while (tortoise != hare) {
    tortoise = tortoise->next;
    hare = hare->next;
}
Node* cycleStart = tortoise;

Сумасшедший, правда? Как это вообще работает? Давайте рассмотрим простой пример, используя рисунок. Предположим, что черепаха и заяц встретились в точке встречи после того, как заяц совершит один полный оборот цикла.

Расстояние, пройденное черепахой, равно x + y, а расстояние, пройденное зайцем, равно x + y + z + y. Заяц движется вдвое быстрее, чем черепаха, а значит, преодолевает вдвое большее расстояние. Оттуда;

Бааам! На самом деле это всего лишь один случай, и для полного доказательства вам нужно рассмотреть несколько раундов как для зайца, так и для черепахи. И если вы хотите перемещать их с разной скоростью, вы можете попробовать это, используя разные постоянные множители. Тем не менее, этого достаточно, чтобы проиллюстрировать логику алгоритма.

Посмотрим, как работает алгоритм Брента.

Алгоритм Брента

Алгоритм Брента работает аналогично алгоритму Флойда, но использует другую стратегию для перемещения указателей. На этот раз заяц движется со степенью двойки, каждый раз удваивая свою скорость. Амбициозная черепаха провела время в своей лаборатории и теперь может путешествовать со скоростью света. Итак, он просто ждет, пока заяц достигнет следующего пункта назначения, и просто телепортируется туда. Затем заяц снова удваивает свою скорость, и это продолжается до тех пор, пока скорость зайца не превысит длину цикла. В следующий раз, когда они встречаются, заяц совершает полный круговой обход и снова оказывается в месте расположения черепахи.

bool brent(Node* head) {
    Node* tortoise = head;
    Node* hare = tortoise->next;
    unsigned int power = 1;
    unsigned int length = 1;
    while (hare != NULL) {
        if (hare == tortoise) {
            return true;
        }
        if (length == power) {
            tortoise = hare;
            length = 0;
            power *= 2;
        }

        hare = hare->next;
        length++;
    }
    return false;
}

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

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

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

tortoise = head;
hare = head;
for (unsigned int i = 0; i < length; i++) {
    hare = hare->next;
}

while (tortoise != hare) {
    tortoise = tortoise->next;
    hare = hare->next;
}
Node* cycleStart = tortoise;

До этого момента мы видели разные методы обнаружения циклов в связанных списках. С тех пор, как я узнал об этом, прошли годы, но только недавно я видел, что эти стратегии на самом деле предназначены для решения более общей проблемы, по сути, определенной функции. Теперь давайте наконец обсудим вышеупомянутый вопрос HackerRank.

Обнаружение цикла функций

В вопросе нам дается функция. Учитывая положительные целые числа N, S, P, Q; он спрашивает нас, сколько различных целых чисел будет сгенерировано данной функцией.

f(0) = S mod 2^31
for i = 1 to N
    f(i) = (f(i-1) * P + Q) mod 2^31

Теперь вы можете сохранить каждое сгенерированное целое число в наборе и просто посмотреть, существует ли уже следующее в наборе. Но это было бы слишком просто ... Первое, что вам нужно заметить, это следующее: как только вы получите целое число, которое уже было сгенерировано ранее, остальные целые числа будут повторяться. У нас есть цикл, народ!

Функция, указанная в вопросе, является функцией, которая отображается на себя и фактически для любой функции, которая отображает конечный набор целых чисел на себя в виде

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

Я не собираюсь делиться алгоритмами, которые решают вопрос, и оставлю это как упражнение - к тому же я ** дырявый и нахожу это довольно интересным. Вместо этого я поделюсь результатами тестов для трех разных тестовых случаев:

  • Первый случай: 100 миллионов итераций, 31 отдельное целое число.
  • Второй случай: 10 миллионов итераций, все различные целые числа.
  • Третий случай: 100 миллионов итераций, все различные целые числа.
clock_t begin = clock();
int count = count(100000000, 569099406, 1607140150, 823906344);
clock_t end = clock();

cout << "TEST CASE 1" << endl;
cout << "Distinct Integer Count: " << count << endl;
cout << "Algorithm Runtime: " << float(end - begin) /  CLOCKS_PER_SEC  << "s" << endl;

begin = clock();
count = count(10000000, 658061970, 695098531, 1430548937);
end = clock();

cout << endl;
cout << "TEST CASE 2" << endl;
cout << "Distinct Integer Count: " << count << endl;
cout << "Algorithm Runtime: " << float(end - begin) /  CLOCKS_PER_SEC  << "s" << endl;

begin = clock();
count = count(100000000, 923092883, 976061291, 1205350525);
end = clock();

cout << endl;
cout << "TEST CASE 3" << endl;
cout << "Distinct Integer Count: " << count << endl;
cout << "Algorithm Runtime: " << float(end - begin) /  CLOCKS_PER_SEC  << "s" << endl;

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

TEST CASE 1
Distinct Integer Count: 31
Algorithm Runtime: 0.115112s
TEST CASE 2
Distinct Integer Count: 10000000
Algorithm Runtime: 1.54522s
TEST CASE 3
Distinct Integer Count: 100000000
Algorithm Runtime: 14.1766s

Он прошел большинство тестовых случаев, но 14 секунд в последнем тестовом примере были слишком большими. Теперь посмотрим, что произойдет, когда я реализовал алгоритм Флойда на втором:

TEST CASE 1
Distinct Integer Count: 31
Algorithm Runtime: 0s
TEST CASE 2
Distinct Integer Count: 10000000
Algorithm Runtime: 0.19692s
TEST CASE 3
Distinct Integer Count: 100000000
Algorithm Runtime: 1.76177s

В 10 раз лучше! Оказывается, использование такой большой вспомогательной структуры данных не очень хорошая идея и приводит к множеству промахов в кеше. третий - алгоритм Брента:

TEST CASE 1
Distinct Integer Count: 31
Algorithm Runtime: 0s
TEST CASE 2
Distinct Integer Count: 10000000
Algorithm Runtime: 0.11419s
TEST CASE 3
Distinct Integer Count: 100000000
Algorithm Runtime: 0.909387s

Он работает почти в два раза быстрее, чем алгоритм Флойда. Это потому, что в алгоритме Флойда есть дополнительный шаг для вычисления длины цикла.

Опять же, если в какой-то момент вы чего-то не поняли, просто нарисуйте пример, и он будет ясен как день. В противном случае вы можете попытаться решить вопрос самостоятельно, чтобы понять, как работают алгоритмы Флойда и Брента. Вы также можете попробовать вариант поиска, но этого будет недостаточно.

Друзья мои, это было долгое время, хе-хи… Причина, по которой я пишу эти сообщения, состоит в том, что большинство учебных материалов сосредоточены только на проведении собеседований по программированию, но они, кажется, никогда не говорят об этих концепциях в контексте. Я считаю, что понимание того, как что-то получилось, и размышления над этим - гораздо лучшая стратегия для жизни. В нем также есть некоторая степень волнения, хотя временами это сложно. Вы не скаковая лошадь; будь как черепаха, медленным и устойчивым. Обещаю, рано или поздно ты получишь то, что заслужил. Заботиться…