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

Question

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

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

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

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

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

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

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

Update

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

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

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

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

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

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

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

Answer 1

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

В конкретных случаях важно, чтобы порядок, в котором вы выполняете итерацию двух осей. Например, если ваш код посещает каждый слот в массиве - или каждый пиксель в изображении - тогда вы должны попытаться посетить слоты в натуральном порядке. Изображение обычно выложено в «scanlines», поэтому пиксели на любом 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 (Н * м), но имеет номинальную дополнительные накладные LINQ (вы не заметите его в нормальный использование).

Что вы делаете в ? Там может быть трюки ...

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

Я не могу предложить ничего лучше, чем 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 6

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

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

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

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

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