Как я могу сделать этот код перечисления векторов быстрее? - PullRequest
Новая
       12

Как я могу сделать этот код перечисления векторов быстрее?

1 голос
/ 08 мая 2011

У меня есть три больших набора векторов: A, B1 и B2. Эти наборы хранятся в файлах на диске. Для каждого вектора a из A мне нужно проверить, можно ли представить его как a = b1 + b2, где b1 от B1 и b2 от B2. Векторы имеют 20 компонентов, и все компоненты имеют неотрицательные числа.

Как я сейчас решаю эту проблему (псевдокод): 

foreach a in A  
  foreach b1 in B1
    for i = 1 to 20
      bt[i] = a[i] - b1[i]
      if bt[i] < 0 then try next b1
    next i

    foreach b2 in B2
      for i = 1 to 20
        if bt[i] != b2[i] then try next b2
      next i

      num_of_expansions++
    next b2
  next b1
next a

Мои вопросы:
1. Любые идеи о том, как сделать, если быстрее?
2. Как сделать это параллельно?
3. Вопросы 1, 2 для случая, когда у меня есть B1, B2, ..., Bk, k> 2?

1 Ответ

1 голос
/ 08 мая 2011

Вы можете сортировать В1 и В2 по норме.Если a = b1 + b2, то || a ||= || b1 + b2 ||<= || b1 ||+ || b2 ||, поэтому для любых a и b1 можно эффективно исключить все элементы B2, имеющие норму <|| a ||- || b1 ||.Также может быть какой-то способ использовать распределение норм в B1 и B2, чтобы решить, следует ли поменять роли двух наборов в этом.(Я не вижу ничего странного, как это сделать, но мне кажется, что что-то подобное должно иметь место, если распределения норм в B1 и B2 значительно отличаются.) </p>

Что касается параллелизмаКажется, что каждый цикл можно превратить в параллельные вычисления, поскольку все вычисления одной внутренней итерации не зависят от всех других итераций.

EDIT

Продолжение анализа: так как b2 = a - b1, мы также имеем || b2 ||<= || a ||+ || b1 ||.Таким образом, для любых данных a и b1 вы можете ограничить поиск в B2 теми элементами с нормами в диапазоне || a ||± || b1 ||.Это говорит о том, что для B1 вы должны выбрать набор с наименьшей средней нормой. </p>

...