Самый эффективный способ преобразовать список отсчетов в список чисел - PullRequest
Новая
       4

Самый эффективный способ преобразовать список отсчетов в список чисел

4 голосов
/ 18 марта 2020

У меня есть список отсчетов, где каждый индекс представляет число, а его число показывает, сколько из этого числа находится в списке: 

a = [3,5,1,2]

превращается в 

b = [0,0,0,1,1,1,1,1,2,3,3]

I думал, что мы могли бы сделать что-то вроде: 

b = []
for ix, el in enumerate(a):
    b.extend([ix]*a[ix])
print(b)

Но если я не ошибаюсь, потребуется k (count val) время, чтобы поместить его в список b, так как расширение занимает k времени, но это также должно быть выполнено n раз, что дает нам время выполнения n * k, где n - число признаков, а k - количество отсчетов для каждого индекса

Другая идея состоит в том, чтобы вместо массива отсчетов мы могли иметь массив чистые элементы: 

a = [[0,0,0],[1,1,1,1,1],[2],[3,3]]

, но чтобы сгладить это, потребуется еще некоторое время (я думаю, что n * k раз) 

b = [item for sublist in a for item in sublist]

есть ли способ сделать это более эффективным? Может быть, преобразовать в строку, убрав все скобки и превратить обратно в список?

1 Ответ

2 голосов
/ 18 марта 2020

Вы можете использовать numpy np.repeat для эффективного подхода: 

np.repeat(np.arange(len(a)), a)
# array([0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 3])

Вот время - 

a_large = np.concatenate([a]*10_000, axis=0)

def op(a):
    b = []
    for ix, el in enumerate(a):
        b.extend([ix]*a[ix])

def yatu(a):
    np.repeat(np.arange(len(a)), a)

%timeit op(a_large)
# 17.1 ms ± 422 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit yatu(a_large)
# 368 µs ± 1.91 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
...