Вложенные циклы - постоянное количество итераций

Question

По просьбе @mypetition я редактирую свой вопрос, хотя думаю, что детали астрономии здесь не важны.У меня есть файл вида:

   a          e        q          Q          i        lasc       aper      M          H      dist   comment     i_f      i_h      i_free
45.23710   0.1394   38.93105   51.54315    5.0300    19.9336   286.2554   164.9683   8.41   51.3773   warm     0.000    62.000     4.796
46.78620   0.1404   40.21742   53.35498    3.1061   148.9657   192.3009   337.5967   7.37   40.8789   cold     0.000    42.000     2.473
45.79450   0.1230   40.16178   51.42722    8.0695   104.6470   348.5004    32.9457   8.45   41.3089   warm     0.000    47.000     6.451
42.95280   0.0145   42.32998   43.57562    2.9273   126.3988   262.8777   163.4198   7.36   43.5518   cold     0.000   161.000     2.186

Всего 1.6e6 строк.Это орбитальные элементы.Мне нужно вычислить минимальное расстояние пересечения орбиты (MOID) между каждой парой орбит, например, строка 1 с линией 2, строка 1 с линией 3 и так далее, пока я не достигну конца файла.Затем я начинаю со второй строки и перехожу в конец файла.Затем начните с третьей строки, и agin перейдите к концу файла и т. Д. Так как у меня 1.6e6 орбит, это будет ~1e12 пар орбит.

Я не хочу загружать все эти вычисления 1e12на 1 процессор и ждать вечно, поэтому я планирую использовать кластер и запускать несколько последовательных заданий.

Мне нужно перебрать элементы 1.6e6, где я начинаю с первых элементов и перехожу к концуфайл, затем начните со второго и переходите к концу файла и т. д., пока я, наконец, не начну с T-1 и не перейду к T.Это приведет к 10^12 итерациям, и я планирую разделить их на несколько заданий, где каждое задание выполняет C=10^7 вычисления, поэтому я могу запускать их на компьютерном кластере.
Я придумал следующий вложенный цикл:

for i in range( M, N)
  for j in range( i+1, T)

где M=1 и меняется в зависимости от количества рабочих мест, которые у меня будут.T=1.6e6 является константой (количество строк для перебора).Я хочу найти индекс N, чтобы общее количество операций составляло C=10^7.Вот как я подошел к проблеме: [T-(N+1) + T-(M+1)]*(M-N+1)/2=C - потому что количество операций - это просто сумма арифметических рядов выше.Итак, я решаю квадратное уравнение и получаю корни.Вот код Python для этого:

import numpy as np
import math

C=1.0e7  # How many calculations per job do you want?
T=1.6e6  # How many orbits do you have?
M=1      # what is the starting index of outer loop?
#    N = end index of outer loop (this is to be calculated!)
P=1
l=0
with open('indx.txt','w') as f:

   while P<T:
      l=l+1
      K=np.roots([-1,2*T,M**2-2*T*(M-1)-2*C])
      N=int(round(K[1]))

      f.write("%s %s\n" % (P,P+N))
      M=K[1]+1
      P=P+N+1

Однако, сохраняя вышеуказанные решения, обновляя M = M + N, я заметил, что условие C = 10 ^ 7 не выполняется.Вот список первых нескольких индексов.

M N

1 7
8 21
22 41
42 67
68 99
100 138
139 183
184 234
235 291
 ....
 ....
1583930 1588385
1588386 1592847
1592848 1597316
1597317 1601791

Но если вы посмотрите на пару до последнего, цикл по i=1592848 - 1597316 и j=i+1, T произведет больше вычислений, чем C=10^7, то есть примерно(2685 + 7153) * 4468/2 ~ 2,2e7.

Любая идея о том, как решить эту проблему, поддерживая постоянную C = 1e7, что обеспечит количество заданий (с аналогичным временем выполнения), которые мне нужно выполнить, чтобы перебрать строки 1.6e6.

Надеюсь, этого объяснения достаточно в соответствии со стандартами @mypetition, и я надеюсь решить проблему.

Ваша помощь будет высоко оценена!

Answer 1

Я не знаю, может ли природа каждой работы подойти к разным видам раскола, но если они это сделают, вы можете попытаться использовать тот же трюк, который использовал Гаусс, чтобы придумать ∑1..n = n(n + 1) / 2

Хитрость заключалась в том, чтобы выровнять последовательность с обратной ее копией:

1  2  3  4  5  6  7  8  
8  7  6  5  4  3  2  1 
-- -- -- -- -- -- -- --
9  9  9  9  9  9  9  9  = 8 * 9 is twice the sum so (8*9)/2 = ∑1..8 = 36

Исходя из этого, если вы разбили пару рядов вниз пов середине вы получите 4 пары прогонов, которые будут обрабатывать одинаковое количество элементов:

1  2  3  4    
8  7  6  5  
-- -- -- -- 
9  9  9  9  

Таким образом, вы бы разделили 8 прогонов на 4 задания.Каждое задание будет обрабатывать n + 1 (9) элементов и вычислять два прогона с дополнительным числом элементов

Job 1 would do run 8..8 and run 1..8 (length 1 and 8)
Job 2 would do run 7..8 and run 2..8 
Job 3 would do run 6..8 and run 3..8
Job 4 would do run 7..8 and run 4..8

В более общих чертах:

Задание i из (N + 1)/ 2 выполняет прогоны (N-i + 1) .. N и i..N

Если отдельные прогоны нельзя распараллеливать дальше, это должно дать вам оптимальный спред (практически квадратный корень из общего числавремя обработки)

в Python (псевдокод):

size = len(array) 
for index in range((size+1)//2):
    launchJob(array, run1Start=index, run2Start=size-index-1)

примечание: вы можете настроить начальные точки, если вы не используете индексы на основе нуля.

note2: если вы не обрабатываете последний элемент самостоятельно (т. Е. Исключается N..N), одно из ваших заданий будет иметь N элементов для обработки вместо N + 1 ивам придется сделать исключение для этого

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

например, 2 задания: [1,8,2,7] и [3,6,4,5] = 18 на задание

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