Поиск двух одинаковых элементов в IEnumerable

#c_sharp #net #алгоритм

Есть метод, возвращающий большое количество элементов

static IEnumerable MultiplicatedNumberSequence(long n, long a, long beta, long m)
        {
            for (long i = 1; i <= n; i++)
            {
                a = (beta * a) % m;
                yield return (double)a / m;
            }
        }


Количество элементов n = 2^31. Метод возвращает 2^31 степени элементов. a равняется
остатку от деления на m, значит a ограничено и целое. Значит если взять больше чем
2^31 элементов среди них найдутся одинаковые. Элементов слишком много чтобы загнать
все в массив или отсортировать. Как можно быстро (не ожидая часы и дни) найти в коллекции
два одинаковых элемента, их индексы и разность между индексами двух одинаковых элементов?
Никак не могу придумать адекватный метод. Загнать в List<> не выходит, не хватает памяти,
а брать элементы по порядку и сравнивать с оставшимися самоубийство, потому что количество
итераций будет (2^31)^2 = 2^62. 
    

Ответы

Ответ 1

По всей видимости, с приведенной последовательностью это быстро сделать не получится
- получив на вход IEnumerable можно сделать очень немногое.

Однако, если параметры последовательности известны, к этой задаче можно подойти аналитически,
без генерирования самой последовательности!

Ваша последовательность, если ее не делить на 0 - это же a * beta^i % m.

Если beta взаимно просто с m - то, как следует из малой теоремы Ферма, 

beta ^ (φ(m) - 1) % m = 1


Иными словами, цикл всегда есть, начинается он с первого элемента, а его длина должна
быть делителем φ(m) - 1, где φ - функция Эйлера.

Теперь что если beta не является взаимно простой с m - тогда их общий множитель,
оказавшись внутри a, уже не "покинет" эту переменную. У цикла появляется префикс (он
начинается не с 1).

Таким образом, критерий начала цикла - тот факт, что gcd(a, m) = gcd(a*beta, m),
где gcd - наибольший общий делитель:

// Алгоритм Евклида
int gcd(int a, int b) {
  while (b > 0) {
    var c = a % b;
    a = b;
    b = c;
  }
  return a;
}

int first = 0;
while (gcd(a, m) != gcd(a*beta, m)) {
  a = (a * beta) % m;
  first++;
}


В принципе, знания первого элемента цикла достаточно чтобы найти его повтор за разумное
время. Но если есть желание поковыряться, можно пойти дальше. Теперь можно сделать
эквивалентное преобразование оставшейся последовательности, сократив a и m на их НОД
- это не изменит длину цикла, но позволит воспользоваться формулой:

int d = gcd(a, m);
m /= d;
a /= d;


Теперь осталось перебрать делители φ(m) - 1 и найти среди них длину цикла (к примеру,
при помощи алгоритма быстрого возведения в степень). Тут проще всего начать с заведомо
подходящей длины φ(m) - 1 и пытаться разделить ее на все простые делители меньшие квадратного
корня, каждый раз проверяя цикл при помощи быстрого возведения в степень.

Итоговое время работы - O(M^½ * log M), то есть время порядка 2^21. В специальном
случае когда M - степень двойки, все еще сильнее упрощается и остается только O((log
M)^2) (а зная заранее что M - степень двойки, можно алгоритм написать совсем просто,
обойдясь даже без алгоритма Евклида).


Ответ 2

Обновление: Функция будет периодической с самого начала лишь для случая, когда beta
и m не взаимно просты. Для изучения периода лучше возвращать из функции MultiplicatedNumberSequence
не преобразованный double, а число a. Судя по всему, при этом у текущего члена последовательности
возрастает НОД с m. Поэтому для пропускания «префикса» сделаем так:

static long gcd(long a, long b)
{
    while (a != 0 && b != 0)
    {
        var temp = b;
        b = a % b;
        a = temp;
    }
    return a + b;
}

long prevgcd = -1;
var seq = MultiplicatedNumberSequence(...)
            .SkipWhile(v => prevgcd != (prevgcd = gcd(v, m)));


Оставшийся «хвост» последовательности периодичен, начиная с начала, так что можно
просто запомнить первый элемент и прокрутить до его повторения. Впрочем, это по сути
совпадает с методом @Pavel Mayorov, изложенным в другом ответе.



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

var seq = MultiplicatedNumberSequence(...);

using (var tortoise = seq.GetEnumerator())
using (var hare = seq.GetEnumerator())
{
    while (true)
    {
        // продвигаем первый обход на шаг
        if (!tortoise.MoveNext())
            break;
        // а второй на два
        if (!hare.MoveNext() || !hare.MoveNext())
            break;
        if (hare.Current != tortoise.Current)
            continue;
        // если вы тут, вы нашли повторяющиеся значения
        // делайте с ними что хотите
        // например, вы можете завести счётчик и подсчитать индексы
    }
}


Литература: https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare (там
есть и другие методы).



Поскольку вы сравниваете действительные числа, возможно, сравнение типа a != b следует
заменить на Math.Abs(b - a) > eps.



Это работает для случая последовательности (xn), вычисляемой по правилу xk = f(xk
− 1) для обратимой функции f.

Почему этот алгоритм работает? Пускай у нас для некоторых k, m выполняется xk = xk
+ m. Применяя f в обратную сторону, получим xk − 1 = xk + m − 1, ..., x0 = xm. Отсюда
x0 = xm = x2‌m. Значит, минимальный цикл найдётся, когда «заяц» будет на 2‌m, а черепаха
на m.


Ответ 3

Особый алгоритм для случая, когда m - степень простого числа

Данный алгоритм работает со сгенерированной последовательностью, не зная значений
ее параметров.

Если beta делится на простое число - то последовательность быстро закончится серией
нулей. Если beta не делится на него - то последовательность циклическая. 

Ну и плюс так как последовательность конечная - она может закончиться раньше чем
это случится. Больше вариантов нет.

Зная это, можно написать алгоритм, где эти варианты будут проверены:

var seq = MultiplicatedNumberSequence(...).GetEnumerator();

const double eps = 1e-10;
double firstElement = 0;
int first = -1, second = -1;

using (seq as IDisposable) {
  for (int i=1; seq.MoveNext(); i++) {
    if (Math.Abs(seq.Current) < eps) { // Достигли нуля - дальше будут только они
      first = i;
      second = i+1;
      break;
    }
    if (i == 1) 
      firstElement = seq.Current;
    else if (Math.Abs(seq.Current - firstElement) < eps) { // Цикл замкнулся
      first = 1;
      second = i;
      break;
    }
  }
}

// Выход алгоритма: индексы совпадающих элементов - first и second.