Блог

Главная - Вопросы по программированию - Оптимизация, необходимая для извлечения пары чисел из двух разных наборов после выполнения условия?

Оптимизация, необходимая для извлечения пары чисел из двух разных наборов после выполнения условия?

#c #performance #map #stl

#c #Производительность #словарь #stl

Вопрос:

У меня есть два вектора типа

       typedef long long LL  ;

      vector < LL > store1 , store2 ;

Размер каждого вектора <= 20000.
Теперь мне нужно извлечь все такие пары (один элемент из store1 и один элемент из store2) таким образом, чтобы 

       gcd ( element1 ,element2 ) != 1 ;

Каждый элемент из любого хранилища используется ровно один раз для формирования пары.

Подход, который я использую в настоящее время, очень медленный. Мой подход ;

      ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }

     vector < LL > :: iterator it , fit ;
     LL ans = 0 ;         
           // count of pairs
     for ( it = store1.begin() ; it != store1.end() ; it  )
     {
           LL x = (*it) ;

           for( fit = store2.begin() ; fit != store2.end() ; fit  ){

              LL y = (*fit) ;
              if ( gcd(x,y) != 1){

                   ans   ;
                   store2.erase(fit); break ;
              }   

           }
      }

Ограничение по времени: 1 сек
Все числа <= 10 ^ 9

Я использую 64-разрядный целочисленный тип, чтобы избежать любого переполнения.

A вы можете видеть, что таких пар не может быть более 20000. Я придерживаюсь подхода O (n ** 2), который слишком медленный для моего приложения.

Поздняя правка: я хочу знать, существует ли определенное свойство gcd, благодаря которому извлечение пар становится быстрее. Применение концепций теории чисел, которые могут быть использованы для уменьшения сложности.

Комментарии:

1. Существуют ли какие-либо ограничения на диапазон сохраненных чисел? Похоже, что это 64-разрядные целые числа, но на практике они занимают все это пространство?

2. Мне трудно поверить, что опубликованная процедура выполняется очень медленно (за исключением случаев, когда есть проблемы с производительностью в функции gcd()). Это просто не соответствует заданным требованиям возврата всех совпадающих пар. Все, что он делает для каждой записи первой карты, — это ищет первое совпадение, увеличивает счетчик, удаляет соответствующую запись во второй карте. Получение всех совпадений включает повторение каждой комбинации и добавление совпадения в результирующий контейнер.

3. @stefaanv Используемая функция Gcd является стандартным методом Евклида.

4. @JohnZwinck Я отредактировал свой вопрос и упомянул ограничения.

5. @AmitKumar Я предлагаю вам переосмыслить проблему. Если ваш алгоритм имеет сложность в ^ 2 в долгосрочной перспективе, никакая оптимизация вам не поможет. В краткосрочной перспективе вы могли бы легко распараллелить алгоритм, разделив store2 на все доступные ядра.