Алгоритм эффективного декартова произведения

Question

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

foreach (int i in is) {
   foreach (int j in js) {
      //Pair i and j
   }
}

Это очень упрощенная версия того, что я делаю в своем коде. Два целых числа являются ключами поиска, которые используются для извлечения одного / нескольких объектов, и все объекты из двух поисков объединяются в новые объекты.

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

Редактировать

Итак, еще немного предыстории моего конкретного использования этого алгоритма, чтобы увидеть, могут ли быть какие-то уловки, которые я могу использовать в ответ на комментарий Марка. Вся система представляет собой механизм запросов SPARQL, который обрабатывает запросы SPARQL по наборам данных Graph, SPARQL - это язык, основанный на шаблонах, поэтому каждый запрос состоит из серии шаблонов, сопоставляемых с графиками. В случае, когда два последующих шаблона не имеют общих переменных (они не пересекаются), необходимо вычислить декартово произведение решений, полученных этими двумя шаблонами, чтобы получить набор возможных решений для общего запроса. Может быть любое количество шаблонов, и мне, возможно, придется вычислять декартовы произведения несколько раз, что может привести к довольно экспоненциальному расширению возможных решений, если запрос состоит из серии непересекающихся шаблонов.

Почему-то из существующих ответов я сомневаюсь, есть ли какие-нибудь хитрости, которые могли бы применить

Обновление

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

Поскольку каждый BGP (базовый шаблон графика), который представляет собой набор тройных шаблонов, выполняется как блок (по сути), механизм может свободно изменять порядок шаблонов в BGP для достижения оптимальной производительности. Например, рассмотрим следующий BGP:

?a :someProperty ?b .
?c :anotherProperty ?d .
?b a :Class .

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

?b a :Class .
?a :someProperty ?b .
?c :anotherProperty ?d .

Нам все еще понадобится декартово произведение, чтобы получить окончательные результаты, так как 2-й и 3-й паттерны все еще не пересекаются, но при переупорядочении мы ограничиваем размер результатов 2-го паттерна, что означает, что размер нашего декартового произведения будет намного меньше .

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

Answer 1

Сложность декартового произведения: O ( n ² ), ярлык отсутствует.

В определенных случаях важен порядок, в котором вы повторяете две оси. Например, если ваш код посещает каждый слот в массиве - или каждый пиксель в изображении - тогда вы должны попытаться посетить слоты в естественном порядке. Изображение обычно располагается в «линиях сканирования», поэтому пиксели на любом Y расположены рядом. Следовательно, вы должны выполнить итерации по Y во внешнем цикле и X во внутреннем.

Необходим ли вам декартово произведение или более эффективный алгоритм, зависит от решаемой вами проблемы.

Answer 2

Вы не можете реально изменить производительность вложенного цикла без каких-либо дополнительных знаний, но это будет зависеть от конкретного использования. Если у вас есть n предметов в is и m предметов в js, это всегда будет O (n * m).

Вы можете изменить вид этого:

var qry = from i in is
          from j in js
          select /*something involving i/j */;

Это все еще O (n * m), но имеет номинальные дополнительные издержки LINQ (хотя вы не заметите это при обычном использовании).

Что вы делаете в вашем случае? Там могут быть хитрости ...

Одна вещь, которую определенно следует избегать, это то, что вызывает перекрестное соединение с буфером - подход foreach хорош и не буферизируется, но если вы добавляете каждый элемент в List<> тогда остерегайтесь последствий для памяти. То же OrderBy и т. Д. (При неправильном использовании).

Answer 3

Я не могу предложить ничего лучше, чем O (n ^ 2), потому что это размер вывода , и алгоритм, следовательно, не может быть быстрее.

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

Действительно (псевдокод)

bool IsInSet(pair (x,y), CartesianProductSet P)
{
   return IsInHash(x,P.set[1]) && IsInHash(y,P.set[2])
}

где декартово произведение вычисляется так:

// Cartesian product of A and B is
P.set[1]=A; P.set[2]=B;

Если вы реализуете наборы как хэши, то поиск в декартовом произведении из m наборов - это просто поиск в m хешах, которые вы получаете бесплатно. Построение декартового произведения и поиск IsInSet каждый занимает O(m) время, где m - это число , которое вы умножаете , и оно намного меньше n - размера каждого набора.

Answer 4

Дополнительная информация была добавлена ​​к вопросу.

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

Среда выполнения C # действительно очень быстрая, но для очень тяжелой работы вам может потребоваться перейти к собственному коду.

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

Answer 5

Я не знаю, как писать Java-подобные-итераторы на C #, но, возможно, вы знаете и можете перенести мое решение отсюда на C # самостоятельно.

Может быть интересно, если ваши комбинации слишком велики, чтобы держать их в памяти полностью.

Однако, если вы фильтруете по атрибуту по коллекции, вы должны фильтровать перед построением комбинации. Пример:

Если у вас есть числа от 1 до 1000 и случайные слова, и вы их объединяете, а затем фильтруете те комбинации, где число делится на 20, а слово начинается с «d», у вас может быть 1000 * (26 * x) = 26000 * х комбинаций для поиска.

Или вы сначала фильтруете числа, что дает вам 50 чисел, и (если они распределены одинаково) 1 символ, что в итоге составляет всего 50 * x элементов.

Answer 6

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

cartprod(is,istart,ilen, js,jstart,jlen) {
  if(ilen <= IMIN && jlen <= JMIN) { // base case
    for(int i in is) {
      for(int j in js) {
        // pair i and j
      }
    }
    return;
  }
  if(ilen > IMIN && jlen > JMIN) { // divide in 4
    ilen2= ilen>>1;
    jlen2= jlen>>1;
    cartprod(is,istart,ilen2,            js,jstart,jlen2);
    cartprod(is,istart+ilen2,ilen-ilen2, js,jstart,jlen2);
    cartprod(is,istart+ilen2,ilen-ilen2, js,jstart+jlen2,jlen-jlen2);
    cartprod(is,istart,ilen2,            js,jstart+jlen2,jlen-jlen2);
    return;
  }
  // handle other cases...
}

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