Требуется: более быстрый способ проверить все комбинации в очень большом хэше

Question

У меня есть хэш с около 130 000 элементов, и я пытаюсь проверить все комбинации в этом хэше (130 000 x 130 000 комбинаций).Мой код выглядит так:

 foreach $key1 (keys %CNV)
 {

  foreach $key2 (keys %CNV)
  {
         if (blablabla){do something that doesn't take as long}
  }

 }

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

-Abdel

Редактировать: Обновление по блаблабле.

Привет, ребята, спасибо за все отзывы!Действительно ценю это.Я изменил оператор foreach на:

for ($j=1;$j<=24;++$j)
 {
  foreach $key1 (keys %{$CNV{$j}})
  {

   foreach $key2 (keys %{$CNV{$j}})
   {
                        if (blablabla){do something}
                        }
                }
        }

Хеш теперь многомерный:

$CNV{chromosome}{$start,$end}

Я подробно остановлюсь на том, что именно пытаюсь сделать, в соответствии с просьбой.

Blablabla выглядит следующим образом:

if  ( (($CNVstart{$j}{$key1} >= $CNVstart{$j}{$key2}) && ($CNVstart{$j}{$key1} <= $CNVend{$j}{$key2})) ||
   (($CNVend{$j}{$key1} >= $CNVstart{$j}{$key2}) && ($CNVend{$j}{$key1} <= $CNVend{$j}{$key2})) ||
   (($CNVstart{$j}{$key2} >= $CNVstart{$j}{$key1}) && ($CNVstart{$j}{$key2} <= $CNVend{$j}{$key1})) ||
   (($CNVend{$j}{$key2} >= $CNVstart{$j}{$key1}) && ($CNVend{$j}{$key2} <= $CNVend{$j}{$key1})) 
  )    

Короче говоря: хеш-элементы представляют собой определенную часть ДНК (так называемый "CNV", пока думайте о нем как о гене),с началом и концом (которые представляют собой целые числа, представляющие их положение в этой конкретной хромосоме, хранящиеся в хешах с одинаковыми ключами:% CNVstart &% CNVend).Я пытаюсь проверить для каждой комбинации CNV, перекрываются ли они.Если в семье есть два элемента, которые перекрывают друг друга (я имею в виду семью людей, чью ДНК я имею и прочитал; в выражении foreach также есть утверждение «за», которое позволяет программе проверять это для каждой семьи, что делает еедлится еще дольше), я проверяю, есть ли у них одинаковый «номер копии» (который хранится в другом хэше с теми же ключами), и распечатываю результат.

Спасибо, ребята, за ваше время!

Answer 1

Похоже, Algorithm::Combinatorics может помочь вам здесь. Он предназначен для обеспечения «эффективной генерации комбинаторных последовательностей». Из его документов:

Алгоритм :: Комбинаторика - это эффективный генератор комбинаторных последовательности. ... итераторы не используют рекурсия, ни стеки, ни написаны в к.

Вы можете использовать его подпрограмму combinations, чтобы обеспечить все возможные 2 комбинации клавиш из вашего полного набора ключей.

С другой стороны, сам Perl написан на C. Поэтому я, честно говоря, понятия не имею, поможет ли это вообще.

Answer 2

Ваша оптимизация с выводом j во внешний цикл была хорошей, но решение все еще далеко от оптимального.

В вашей задаче есть простое решение O (N + M), где N - это общее значение.число CNVs, а M - число совпадений.

Идея такова: вы проходите по длине ДНК, отслеживая все «текущие» CNV.Если вы видите новый запуск CNV, вы добавляете его в список, и вы знаете, что он перекрывается со всеми другими CNV, которые в настоящее время находятся в списке.Если вы видите конец CNV, вы просто удаляете его из списка.

Я не очень хороший программист на Perl, поэтому воспринимайте следующее как псевдокод (это больше похоже на сочетание Java и C #:)):

// input:
Map<CNV, int> starts;
Map<CNV, int> ends;

// temporary:
List<Tuple<int, bool, CNV>> boundaries;
foreach(CNV cnv in starts)
    boundaries.add(starts[cnv], false, cnv);
foreach(CNV cnv in ends)
    boundaries.add(ends[cnv], true, cnv);

// Sort first by position, 
// then where position is equal we put "starts" first, "ends" last
boundaries = boundaries.OrderBy(t => t.first*2 + (t.second?1:0));

HashSet<CNV> current;

// main loop:
foreach((int position, bool isEnd, CNV cnv) in boundaries)
{
    if(isEnd)
        current.remove(cnv);
    else
    {
        foreach(CNV otherCnv in current)
            OVERLAP(cnv, otherCnv); // output of the algorithm
        current.add(cnv);
    }
}

Answer 3

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

for ($j=1;$j<=24;++$j)
 {
            foreach $key1 (sort keys %{$CNV{$j}})
            {


                foreach $key2 (sort keys %{$CNV{$j}})
                {

                    if (($CNVstart{$j}{$key2} < $CNVstart{$j}{$key1}) && ($CNVend{$j}{$key2} < $CNVstart{$j}{$key1}))
                    {
                    next;
                    }


                    if (($CNVstart{$j}{$key2} > $CNVend{$j}{$key1}) && ($CNVend{$j}{$key2} > $CNVend{$j}{$key1}))
                    {
                    last;
                    }

        if  ( (($CNVstart{$j}{$key1} >= $CNVstart{$j}{$key2}) && ($CNVstart{$j}{$key1} <= $CNVend{$j}{$key2})) ||
           (($CNVend{$j}{$key1} >= $CNVstart{$j}{$key2}) && ($CNVend{$j}{$key1} <= $CNVend{$j}{$key2})) ||
           (($CNVstart{$j}{$key2} >= $CNVstart{$j}{$key1}) && ($CNVstart{$j}{$key2} <= $CNVend{$j}{$key1})) ||
           (($CNVend{$j}{$key2} >= $CNVstart{$j}{$key1}) && ($CNVend{$j}{$key2} <= $CNVend{$j}{$key1})) 
          )    {print some stuff out}

    }
    }
}

Что я сделал:

• сортировка ключей хеш-функции для каждого цикла foreach
• сделать "далее", если CNV с $ key2 все еще не достигли CNV с $ key1 (т.е. start2 и end2 оба меньше, чем start1)
• и, вероятно, наиболее экономят время: завершите foreachЦикл, если CNV с $ key2 обогнал CNV с $ key1 (то есть, start2 и end2 больше, чем end1)

Большое спасибо за ваше время и отзывы, ребята!

Answer 4

Структура данных в вопросе не подходит для проблемы. Давайте попробуем это так.

use Set::IntSpan::Fast::XS;
my @CNV;
for ([3, 7], [4, 8], [9, 11]) {
    my $set = Set::IntSpan::Fast::XS->new;
    $set->add_range(@{$_});
    push @CNV, $set;
}

# The comparison is commutative, so we can cut the total number in half.
for my $index1 (0 .. -1+@CNV) {
    for my $index2 (0 .. $index1) {
        next if $index1 == $index2; # skip if it's the same CNV
        say sprintf(
            'overlap of CNV %s, %s at indices %d, %d',
            $CNV[$index1]->as_string, $CNV[$index2]->as_string, $index1, $index2
        ) unless $CNV[$index1]->intersection($CNV[$index2])->is_empty;
    }
}

Выход:

overlap of CNV 4-8, 3-7 at indices 1, 0

Мы не получим перекрытие 3-7, 4-8, потому что это дубликат.

Есть также Bio :: Range , но для меня это не выглядит так эффективно. Вы обязательно должны связаться с bio.perl.org / open-bio людей; Скорее всего, то, что вы делаете, уже сделано миллион раз, прежде чем у них уже есть оптимальный алгоритм.

Answer 5

определить бла-бла.

Вы можете написать это так:

foreach $ key1 (keys% CNV) {

if (blah1)
{
    foreach $key2 (keys %CNV)
    {
        if (blah2){do something that doesn't take as long}
    }
}

}

Этот проход должен быть O (2N) вместо O (N ^ 2)

Answer 6

Может быть, используя параллелизм? Но вы должны быть осторожны с тем, что вы делаете с возможным матчем, чтобы не было проблем.

например. возьмите $ key1, разделите его на $ key1A и §key1B. Создайте два отдельных потока, каждый из которых содержит «половину цикла».

Я не уверен, насколько точно стоит запускать новые потоки в Perl, но если ваши позитивные действия не нужно синхронизировать, я думаю, что на подходящем оборудовании вы будете быстрее.

Стоит попробовать imho.

Answer 7

Теперь я не воин Perl, но, исходя из предоставленной информации, она одинакова на любом языке программирования; если вы не отсортируете «хеш» в свойстве, которое хотите проверить, и не выполните бинарный поиск, вы не улучшите производительность при поиске.

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