Python - Оптимизирующая комбинация 2 среди N с N очень большим - PullRequest
Новая
       27

Python - Оптимизирующая комбинация 2 среди N с N очень большим

0 голосов
/ 20 января 2019

Я пытаюсь найти пары элементов, которые удовлетворяют определенному условию.Точнее, я хочу сформировать комбинацию из 2 (неупорядоченных) элементов среди 50 000 элементов так, чтобы соблюдалось определенное условие.

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

Пока мой сценарий следующий. 

# Load the dataset (I have a custom function for it called loadFile)
df = loadFile(path_input,filename_input)

# Reset the index because I want to use the column "index" from 0 to 49,999
df = df.reset_index(drop=False)

# Initiate the list of pairs & get the number of elements
pairs = list()
nb_rows = df.shape[0]

# Loop over all the rows of my dataframe
for ind_x, x in df.iterrows():
    # Just print to know where we stand from 1 to 50,000
    print("{} out of {}".format(ind_x+1,nb_rows))
    # Loop over all the rows of my dataframe
    for ind_y, y in df.iterrows():
        # We only consider the y-row if it was not covered yet by the previous pairs
        # I also don't want to cover the case where both elements are equal
        if ind_x<ind_y:
            # Here is a custom condition (a simple function) returning a boolean
            if distance(x["location"],y["location"])<x["cutoff"]:
                pairs.append((x["id"],y["id"]))

Фактически,если мое пользовательское условие всегда соблюдается, мой сценарий может пройти через все 50 000 * 49 999/2 ~ 1 250 миллионов возможных пар ..

Для одного элемента "ind_x", текущий циклНа запуск скрипта уходит приблизительно 5 секунд, что составляет 50 000 * 5 / (60²) = 69 часов (много).

Есть ли способ ускорить мой скрипт, либо сам цикл, либоизменить мой подход, чтобы сэкономить время?

Заранее спасибо,

М

1 Ответ

0 голосов
/ 21 января 2019

Это просто классическая проблема поиска множеств окрестности. Пока ваше расстояние Евклидово, есть много специализированных пакетов с быстрыми методами для ее решения, но хорошим вариантом является использование scipy's cKDTree : 

from scipy.spatial import cKDTree

def close_point_pairs(X, max_d):
    # create the tree from the data points
    tree = cKDTree(X)

    # find all pairs of points 
    pairs = tree.query_ball_tree(tree,max_d)

    # pair indices
    return np.array([(x, pt) for x, ptlist in enumerate(pairs) for pt in ptlist if pt>x])

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

df = pd.DataFrame(500*np.random.random(size=10**4), columns=['location'])
%timeit close_point_pairs(df['location'].values[:,np.newaxis], max_d=1.0)
530 ms ± 123 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Примечание. Мне пришлось добавить np.newaxis, потому что точки были только 1D, неясно, каковы ваши точки местоположения, но если они имеют более высокое измерение, вы должны удалить их.

Если вам нужны уникальные идентификаторы из исходного DataFrame, вы можете просто проиндексировать их или создать словарь перевода.

...