Дано:
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;
}
}
