Эффективный алгоритм Декартова произведения

Вы не можете действительно изменить производительность вложенного цикла без дополнительных знаний, но это будет зависеть от конкретного пользователя. Если у вас есть n элементов в это и 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 хорош и не буферизируется - но если вы добавляете каждый элемент в Список <> , то остерегайтесь последствий для памяти.

Я не могу предложить ничего лучше, чем 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 sets - это просто поиск в m хэшах, которые вы получаете бесплатно.

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

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

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

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

Если локальность кеша (или локальная память, необходимая для поддержки 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...
}

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