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

Ответ 1

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

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

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

Ответ 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 и т.д. (Если используется ненадлежащим образом).

Ответ 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 lookup each принимают O(m) время, где m - это количество наборов, которые вы умножаете, и оно намного меньше n - размер каждого набора.

Ответ 4

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

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

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

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

Ответ 5

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

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

Ответ 6

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

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

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

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

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