В то время как цикл с Cython?или лучший способ удалить элементы, попадающие в заданный диапазон - PullRequest
Новая
       11

В то время как цикл с Cython?или лучший способ удалить элементы, попадающие в заданный диапазон

0 голосов
/ 15 мая 2018

Я в основном ищу более быстрый / лучший / эффективный способ выполнения фрагмента моего кода на Python.

Вот упрощенная версия моей части кода. 

import numpy as np

A = np.random.choice(100,80) # randomly select integers
A = np.sort(A) # sort it
B = np.unique(A) # drop the duplicate values

Что я хочу сделать с этим вектором B, так это удалить его элементов, которые попадают в заданный диапазон от предыдущего значения. Например, если у меня есть отсортированный вектор B = [1,2,5,7,8,11,20,25,30] и значение диапазона, которое я хотел бы присвоить, равно 10, то мой код должен вывести C = [1,11,25]. (2,5,7,8 были удалены, потому что он имеет расстояние меньше 10 с элементом 1. Следующий элемент равен 11. 20 удален, потому что 20 имеет расстояние меньше 10 с элементом 11. Далее 25, так что 30 это удалены). Вы поняли идею.

Я написал код следующим образом: 

def RemoveViolations(vec, L):
    S = []
    P = 0 # pointer
    C = 0 # counter
    while C < vec.size:
        S.append(vec[C])
        preC = np.where(vec>S[P]+L)[0]
        if preC.size:
            C = preC[0]
        else:
            C = vec.size+1
        P = P+1

    return np.asarray(S)

Итак, теперь я могу сделать это C = RemoveViolations(B,10), которое работает как заклинание.

Теперь проблема в том, что это очень медленный код в python. У меня как отсортированный вектор размером 1 миллион, и для завершения этого кода требуется некоторое время. Есть ли лучший способ сделать это?

Если мне нужно реализовать Cython, как бы я изменил код для работы в среде C ++? Я слышал, что это не очень сложно, но быстрый поиск не сработал.

Спасибо!

1 Ответ

0 голосов
/ 15 мая 2018

Сложность вашего алгоритма заключается в следующем: вот решение на чистом python, которое выполняется на 0.15s на моем 8-летнем ноутбуке (вашей реализации потребовалось 200 секунд; i / ea улучшение в 1300 раз для n = 1000000):

import random


def get_filtered_values(dist, seq):

    prev_val = seq[0]
    compare_to = prev_val + dist
    filtered = [prev_val]

    for elt in seq[1:]:
        if elt <= compare_to:           # <-- change to `<` to match desired results; 
                                        # this matches the results of your implementation 
            continue
        else:
            compare_to = elt + dist
            filtered.append(elt)
    return filtered


B = [1,2,5,7,8,11,20,25,30]
print(get_filtered_values(10, B))

n = 1000000
C = sorted(list(set([random.randint(0, n) for _ in range(n)])))
get_filtered_values(10, C)

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

...