Нахождение двух пересекающихся массивов среди k отсортированных

Question

[Dmitry]

Дано:
k отсортированных массивов целых чисел.
Нужно найти:
Пересекающиеся массивы, с количеством совместных элементов больше minSupport;

Пример:

На вход:
1,3,7,8
2,3,8,10
3,10,11,12,13,14

minSupport = 1

На выходе:

1 и 2: 2, 8
1 и 3: 3
2 и 3: 3, 10

Вот реализация прямолинейного подхода:

    var minSupport = 2;
    var random = new Random(123);

    var sortedArrays = Enumerable.Range(0,100)
    .Select(x => Enumerable.Range(0,30).Select(t => random.Next(1000)).Distinct()
    .ToList()).ToList();
    var result = new List<int[]>();
    var resultIntersection = new List<List<int>>();

    foreach (var array in sortedArrays)
    {
        array.Sort();
    }

    var sw = Stopwatch.StartNew();

    //****MAIN PART*****//

    for (int i = 0; i < sortedArrays.Count-1; i++)
    {
        for (int j = i+1; j < sortedArrays.Count; j++)
        {
            var intersect = sortedArrays[i].Intersect(sortedArrays[j]).ToList();
            if(intersect.Count()>=minSupport)
            {
                result.Add( new []{i,j});
                resultIntersection.Add(intersect);
            }
        }
    }

    //*****************//

    sw.Stop();

    Console.WriteLine(sw.Elapsed);

Он работает невероятно медленно

Вот пример подхода, который работает чуть побыстрей (раза в 2)

var maxValue = 1000;
    
    var reverseIndexDict = new List<int>[maxValue];
    
    for (int i = 0; i < maxValue; i++)
    {
        reverseIndexDict[i] = new List<int>();
    }
    
    for (int i = 0; i < sortedArrays.Count; i++)
    {
        for (int j = 0; j < sortedArrays[i].Count; j++)
        {
            reverseIndexDict[sortedArrays[i][j]].Add(i);
        }
    }
    
    
    
    for (int i = 0; i < sortedArrays.Count; i++)
    {
        var tempArr = new Dictionary<int, List<int>>();
        
        for (int j = 0; j < sortedArrays[i].Count; j++)
        {
            var sortedArraysij = sortedArrays[i][j];
            
            
            for (int k = 0; k < reverseIndexDict[sortedArraysij].Count; k++)
            {
                if(!tempArr.ContainsKey(reverseIndexDict[sortedArraysij][k]))
                {
                    tempArr[reverseIndexDict[sortedArraysij][k]] = new[]{sortedArraysij}.ToList();
                }
                else
                {
                   tempArr[reverseIndexDict[sortedArraysij][k]].Add(sortedArrays[i][j]);
                }
                
            }
        }
        
        
        for (int j = 0; j < reverseIndexDict.Length; j++)
        {
            if(reverseIndexDict[j].Count>=minSupport)
            {
                result.Add(new[]{i,j});
                resultIntersection.Add(reverseIndexDict[j]);
            }
        }
        
    }

       // Далее фильтруем рез-ты

Как можно сделать это с максимальной скоростью? По каким ключевым словам гуглить?

EDIT:

Реализовал вариант предложенный nickme. Скорость не радует, возрастает в 2 раза на каждые 1000 элементов в диапазоне от 1 до 6 и работает медленней моего второго варианта(на очень больших значениях не тестировал). Вот код, может я где-то напутал что-то.

public void Process(List<int[]> arrays)
{
    var arrayInfoCollection = arrays.Select( (x,i) => new ArrayInfo(i,x)).ToList();
    var minValue = arrayInfoCollection.First().Array[0];
    var minIndex = arrayInfoCollection.First().Id;
    var resultMatrix = new int[arrayInfoCollection.Count,arrayInfoCollection.Count];
    var iterators = (new int[arrayInfoCollection.Count]).ToList();
    
        
    while(iterators.Count!=0)
    {
    
    
    // Находим минимальный элемент
    minValue = arrayInfoCollection[0].Array[iterators[0]];
    for (int i = 0; i < arrayInfoCollection.Count; i++)
    {
        if(arrayInfoCollection[i].Array[iterators[i]]<=minValue)
        {
            minValue = arrayInfoCollection[i].Array[iterators[i]];
                 minIndex = i;            
        }
    }

    
    // Находим пересечения
    for (int i = 0; i < iterators.Count; i++)
    {
               
        if(arrayInfoCollection[i].Array[iterators[i]]==minValue)
        {
            resultMatrix[arrayInfoCollection[i].Id,arrayInfoCollection[minIndex].Id]++;
        }
    }
    
    
    // Двигаемся дальше
    if(arrayInfoCollection[minIndex].Array.Length-1==iterators[minIndex])
    {
       // Если мы уже уперлись в конец массива, удаляем его
       arrayInfoCollection.RemoveAt(minIndex);
       iterators.RemoveAt(minIndex);
    }
    else
    {
       iterators[minIndex]++;
    }
    
    
    }
    
    resultMatrix.Dump();
    
}


public class ArrayInfo
{
    public int Id { get; set; }
    public int[] Array { get; set; }
    
    public ArrayInfo(int id, int[] array)
    {
        Id = id;
        Array = array;
    }
}

Answer 1

[nickme]

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

Comments

[nickme]

Хотя, не все так однозначно… Пусть n — суммарная длина всех массивов, а k — их количество. Первый вариант, предложенный автором, требует k(k-1)/2 попарных сравнений массивов, если их длины примерно равны и для составления пересечения применяется вариант слияния, то время должно быть порядка (k(k-1)/2)*(n/k)=O(nk). Сложность моего предложения тоже O(kn) — худший случай: каждый элемент просматриваем один раз, чтобы найти текущий минимум, выполняем порядка k сравнений. Ситуацию можно улучшить (усложнением алгоритма), если при поиске минимального текущего элемента использовать, например, двоичное поиска, это даст нам O(nlogk). Поэтому вопрос — какого порядка k и n и насколько близки длины массивов? И как работает метод Intersect?

[Dmitry]

Метод intersect работает как (m+n), где m и n длина массивов. Длина массивов около 30 элементов, всего их несколько десятков тысяч. А я немного не понял, почему в моем случае (k(k-1)/2) умножается на (n/k)? Откуда n/k берется?

[nickme]

n — суммарная длина массивов, k — число массивов, поэтому время сравнения двух массивов примерно равно 2n/k.
Т.е. k порядка 10⁴, тогда, наверное, стоит применить какое-нибудь дерево, т.к. log(k) будет существенно меньше, чем k…

Answer 2

[MikhailEdoshin]

Сливать отсортированные массивы удобно с помощью кучи. Пусть n — общее число элементов и k — количество массивов. Делаем кучу из k элементов, укладываем в нее первые элементы массивов. Затем на каждом шаге извлекаем из нее минимальный элемент (log k) и добавляем обратно тот, который следует за ним в массиве (log k). Общая сложность этого шага — 2n log k.

Answer 3

[PuzzleW]

а откуда информация про то что Intersect работает со сложностью n+m ?!

Answer 4

[PuzzleW]

читаю msdn.microsoft.com/ru-ru/library/bb355408.aspx
цитирую:
При перечислении объекта, возвращенного данным методом, Intersect перечисляет элементы first, собирая в коллекцию все различающиеся элементы этой последовательности. Затем выполняется перечисление элементов последовательности second, с пометкой элементов, входящих в обе последовательности. В заключение, помеченные элементы выдаются в том порядке, в котором они были собраны.

если я правильно понимаю, Intersec имел в виду то что ваши массивы отсортированы.
он втупую перечисляет первое множество (возможно тратя кучу времени на убирание дубликатов) затем добавляет к нему второе (опять же, гарантированно тратя кучу времени на проверку нет ли такого же элемента в первом множестве, чтобы «пометить» что элемент присутствует в обоих множествах)

// буду рад ошибаться в оценка трудоемкости алгоритма реализованного в Intersect

в вашем же случае (хожу думаю уже весь вечер) мне кажется очень важным учесть то что ваши массивы отсортированы.
т.е. вам нужно реализовать свою собственную функцию поиска пересекающихся элементов, которая будет учитывать характер ваших входных данных.
ну например, даже эвристики вида: если A[A.length] < B[1] то выходим, нам тут ничего не светит будут экономить вам кучу времени… (правда только в редких случаях :) )

пока я думаю об общем алгоритме такого вида:
берем за A массив у которого A[1] < B[1] (индексацию массива начинаем с 1, не с нуля, хотя это не принципиально)
i=1;
j=1;
count=0;
просматриваем A[] до нахождения элемента >= B[j] естественно увеличивая i
если A[i]==B[j] то j++; продолжаем просмотр A начиная с текущего i (ну да, не забываем count++ :) )
если A[i] > B[j] то нам не судьба найти совпадение с B[j], можно обменивать массивы местами (в том смысле что B[j] теперь у нас «начало» попытки найти первый совпадающий элемент, а значит, и пересекающуюся последовательность.
ну и не забыть окончание массива, а также граничные случаи типа массива в 1 элемент, массивов у которых нет пересекающихся элементов и т.п.

и прежде чем пробовать реализовывать алгоритм на базе моих фантазий (честно, Кормен и Кнут были уже очень давно, я бы порекомендовал измерить скорость работы intersect, ну например скормив ему два однаковых массива (только не додумайтесь передать один и тот же массив — это могут проверять и время выполнения будет = O(length()) или O(count())), а также варианты двух разных массивов отсортированных в одном и том же и в противоположных направлениях. а также ЭТИ же массивы, но НЕ ОТСОРТИРОВАННЫЕ. т.е. генерите random массивы, тестируете на них intersect, после чего сортируете их и тестируете intersect повторно, все рамках одного тестового прогона. Если я прав — то время выполнения практически не должно будет отличаться. Если же отличается — то в моем предложении наверное нет смысла)

ps пытаюсь без листика и ручки понять смысл алгоритма предложенного nickme — все больше подозрения что я предложил эту же идею, но в упрощённо-извращённом формате.

pps очень тяжело у вас условие описано — вам нужны ВСЕ возможные массивы, в которых (одновременно) мощность пересечения >= заданной? или вас устроят только пары массивов, удовлетворяющих этому же условию? если пары то какие, есть ли необходимость выводить все или нет, ну и так далее. уточните задачу а ещё лучше будет если вы дадите понимание чуть более высокого уровня — что потом вы будете делать с результатом? может быть проще будет реализовать алгоритм нацеленный на итоговый результат, чем рассчитывать ваш текущий промежуточный шаг.

Comments

[Dmitry]

m+n потому что я подразумевал, что мы учтем тот факт, что массивы отсортированы и заимплементим свою функцию нахождения пересечений. А у вас получается, что мы ищем пересечения A с B, B c С, C с D и т.д. Но на м нужно найти пересечения и A c C, а если найти пересечения каждый с каждым, то как раз получается мой первый вариант только с быстрым intersectom (m+n). В целом этот кусочек часть алгоритма априори.