Оптимизирующая функция для сравнения каждого значения в массиве друг с другом

Question

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

Функция следующая:

def compare(list, length):
    result = np.zeros(length*length)
    i=0
    for row in range(length):
        for col in range(length):
            if row != col:
              result[i] = list[col] - list[row]
            else:
              result[i] = list[row]
            i = i + 1
    return result.reshape((length,length))

Это мучительно медленно, есть ли способ использовать мой GPU для достижения того же результата? Или хотя бы оптимизировать эту функцию, чтобы она выполнялась быстрее?

Идея состоит в том, чтобы взять список чисел типа

0 1 2 3 4 5

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

[[ 0.  1.  2.  3.  4.  5.]
 [-1.  1.  1.  2.  3.  4.]
 [-2. -1.  2.  1.  2.  3.]
 [-3. -2. -1.  3.  1.  2.]
 [-4. -3. -2. -1.  4.  1.]
 [-5. -4. -3. -2. -1.  5.]]

Я пытался использовать @jit, но результаты кажутся странно медленно

@jit(nopython=True, parallel=True)
def compare2(list, length):
    result = np.zeros(length*length)
    i=0
    for row in range(length):
        for col in range(length):
            if row != col:
              result[i] = list[col] - list[row]
            else:
              result[i] = list[row]
            i = i + 1
    return result.reshape((length,length))

дает следующий результат в списке из ~ 300 элементов:

compare: Elapsed time is 0.062655 seconds.
compare2: Elapsed time is 0.423727 seconds.

РЕДАКТИРОВАТЬ:

Я использую функция сравнения внутри другого l oop для генерации списка таблиц. Я объединил их в одну функцию, и теперь @jit превосходит исходную функцию в 15 раз.

Answer 1

Что касается алгоритма сравнения, кажется, что он оптимизирован только потому, что вам нужно создать матрицу таблицы сравнения n * n (n = размер списка). Итак, вам нужно всего n ^ 2 записей. Это означает, что сложность Времени достаточно справедлива.

Теперь перейдем к следующему пункту: как вы можете это сделать с помощью графического процессора?

• вы можете использовать библиотеку "cudf"

cuDF

Это то же самое, что и "Panda", но предназначено для операций с графическим процессором и аналогично зеркалу "Panda". на ГПУ. Вам просто нужно преобразовать кадр данных «Panda» в кадр данных «cudf», как показано ниже.

import pandas as pd
import numpy as np
import cudf

pandas_df = pd.DataFrame({'a': np.random.randint(0, 100000000, size=100000000),
                          'b': np.random.randint(0, 100000000, size=100000000)})

cudf_df = cudf.DataFrame.from_pandas(pandas_df)

Теперь просмотрите разницу ниже:

# Timing Pandas
# Output: 82.2 ms per loop
%timeit pandas_df.a.mean()

# Timing cuDF
# Output: 5.12 ms per loop
%timeit cudf_df.a.mean()

# Timing Pandas
# Output: 39.2 s per loop
%timeit pandas_df.merge(pandas_df, on='b')

# Timing cuDF
# Output: 2.76 s per loop
%timeit cudf_df.merge(cudf_df, on='b')

Подробнее см. https://towardsdatascience.com/heres-how-you-can-speedup-pandas-with-cudf-and-gpus-9ddc1716d5f2

Answer 2

Python l oop очень медленно. Numpy функции в основном написаны на c и работают намного быстрее.

import numpy as np



def compare(list, length):
    """
    >>> print(compare([0, 1, 2, 3, 4, 5], 6))
    [[ 0  1  2  3  4  5]
     [-1  1  1  2  3  4]
     [-2 -1  2  1  2  3]
     [-3 -2 -1  3  1  2]
     [-4 -3 -2 -1  4  1]
     [-5 -4 -3 -2 -1  5]]
    """
    return np.diag(list) - np.subtract.outer(list, list)