как получить значение дискретного массива?

Question

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

scores = [ (500, 1), (450, 3), (400, 6), (300, 7), (225, 9) ] 

это означает (value, rank), например, там 3-1=2500, 6-3=3450, поэтому реальный список:

[ 500, 500, 450, 450, 450, 400, 300, 300, 225] 

сейчас, учитывая список ранга, я хочу знать, что такое значение этих рангов, например [1, 5, 7, 8], значение 1st равно 500, 5th значение 450, 7th значение 300, 8th значение равно 300, так что это возвращение [500, 450, 300, 300]

как я могу сделать это эффективно?

---

Edit:

скажем len(scores) является M, требуемая длина списка является N, M >> N, и M может быть очень и очень большой (в любом случае это статика результат данных 3GB).

---

Моя ошибка:

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

И еще одна вещь, должно быть важно: оценки не сортируются, так что это может быть:

scores = [(450, 3), (300, 7), (500, 1), (400, 6), (255, 9)] 
total = 10 # this means we get two 255 here 

Answer 1

rank = [1, 5, 7, 8] 
scores = [ (500, 1), (450, 3), (400, 6), (300, 7), (225, 9) ] 
arr = [] 
for i in xrange(1, len(scores)): 
    arr.extend([scores[i-1][0]] * abs(scores[i][1] - scores[i-1][1])) 

arr.append(scores[-1][0]) 
print arr 

for i in rank: 
    print arr[i-1], 

>>> [500, 500, 450, 450, 450, 400, 300, 300, 225] 
>>> 500 450 300 300 

Answer 2

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

values = [] 
i = len(scores) - 1 
for rank in reversed(ranks): 
    while scores[i][1] > rank: 
     i -= 1 
    values.append(scores[i][0]) 
values = values[::-1] 

Или, если вы имели в виду "эффективно" как в короткий/простой код, вот два пути:

>>> [min(v for v, r in scores if r <= rank) for rank in ranks] 
[500, 450, 300, 300] 

>>> [next(v for v, r in scores[::-1] if r <= rank) for rank in ranks] 
[500, 450, 300, 300] 

---

Update: Я просто видел контрольных показателей @unutbu и поскольку он проигнорировал затраты на подготовку для своего самого быстрого решения и дал непригодный тип данных другим решениям и проигнорировал мое основное решение (просто сравнив мои медленные) и использовал оригинал ranks без рекламы apting его его сильно отличается scores, я сделал более справедливым СРАВНЕНИЕ себя:

(Update 2: unutbu обновил ориентиры и исправлены все эти вопросы)

same result: True 
7.620430773809753 seconds for numpy 
4.5830411517407095 seconds for parallel 

Это с unutbu-х scores но изменено на исходный тип данных (список кортежей) и с адаптированным ranks. Это 10000 очков и 100 рангов, как оригинал (я также пробовал 10 рангов и 1000 рангов, времена не сильно изменились).Код:

from timeit import timeit 
import numpy as np 

def search_numpy(scores, ranks): 
    scores = np.array(scores) 
    values, cutoffs = scores[:,0], scores[:,1] 
    return values[np.searchsorted(cutoffs, ranks, side='right')-1] 

def search_parallel(scores, ranks): 
    values = [] 
    i = len(scores) - 1 
    for rank in reversed(ranks): 
     while scores[i][1] > rank: 
      i -= 1 
     values.append(scores[i][0]) 
    return values[::-1] 

scores = np.array([ (500, 1), (450, 3), (400, 6), (300, 7), (225, 9) ] * 2000).cumsum(axis=0) 
values, cutoffs = scores[:,0], scores[:,1] 
ranks = cutoffs[::100] 
scores = list(map(tuple, scores)) 
ranks = list(ranks) 
print('same result:', all(search_parallel(scores, ranks) == search_numpy(scores, ranks))) 
print(timeit(lambda: search_numpy(scores, ranks), number=1000), 'seconds for numpy') 
print(timeit(lambda: search_parallel(scores, ranks), number=1000), 'seconds for parallel') 

Answer 3

Создан две функции:

Function1: Создание стоимости всех рангов от 1 до последнего ранга от входа.

Fucntion2: Создать список целевого значения из списка Target Rank и списка Значения

Демы:

def getScores(scores): 
    """ Create Value rank list from 1 to last rank""" 
    start_rank = 1 
    start_value = 0 
    last_rank = scores[-1][1] 
    value_scores = [] 
    for value, rank in scores: 
     if start_rank==rank: 
      value_scores.append(value) 
      start_rank += 1 
     elif start_rank<rank: 
      # Set Previous Value to rank if not present in the Input. 
      for j in range(start_rank, rank+1): 
       value_scores.append(value) 
       start_rank += 1 

    return value_scores 


def getRankScores(target_rank, value_scores): 
    """ Get Target Rank Value""" 

    target_values = [] 
    for i in target_rank: 
     try: 
      target_values.append(value_scores[i-1]) 
     except IndexError: 
      #- Outof Range. 
      #Handle exception for Rank which value is not present in the Values. 
      target_values.append(value_scores[-1]) 

    return target_values 


scores = [ (500, 1), (450, 3), (400, 6), (300, 7), (225, 9) ] 
target_rank = [1, 5, 7, 8] 

value_scores = getScores(scores) 
print "value_scores:", value_scores 

target_values = getRankScores(target_rank, value_scores) 
print "Result:-", target_values 

Выхода:

value_scores: [500, 450, 450, 400, 400, 400, 300, 225, 225] 
Result:- [500, 400, 300, 225] 

Answer 4

Я попытался с помощью itertools ,

import itertools 

scores = [(500, 1), (450, 3), (400, 6), (300, 7), (225, 9)] 
result = [[scores[i][0]for j in range(abs(scores[i+1][1]-scores[i][1]))] if i+1 != len(scores) else [scores[-1][0]] 
      for i in range(len(scores))] 
score_list = list(itertools.chain(*result)) 

print score_list 

Результаты:

[500, 500, 450, 450, 450, 400, 300, 300, 225] 

Теперь на основе score_list вы можете получить значение, основанное на ранг.

rank_list = [1, 5, 7, 8] 

for i in rank_list: 
    print "Score holding rank {} :- {}".format(i, score_list[i-1]) 

Дисплеи:

Score holding rank 1 :- 500 
Score holding rank 5 :- 450 
Score holding rank 7 :- 300 
Score holding rank 8 :- 300 

Answer 5

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

В следующей функции я нахожу максимальный ранг (и соответствующее значение), меньший или равный данному рангу. Тогда я просто использую это значение.

def find_rank_value(to_be_looked_up_rank): 
    proxy_rank, value = max((rank, value) for value, rank in scores if rank<= to_be_looked_up_rank) 
    return value 

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

list_of_ranks = [1, 5, 7, 8] 

list_of_values = [find_rank_value(rank) for rank in list_of_ranks] 

list_of_values 

Out:

[500, 450, 300, 300] 

Answer 6

scores = [(500, 1), (450, 3), (400, 6), (300, 7), (225, 9)] 
ranks = [1, 5, 7, 8] 

values = [] 
v, r = zip(*scores) 
for rank in ranks: 
    while rank not in r: 
     rank -= 1 
    values.append(v[r.index(rank)]) 

Answer 7

Если мы можем предположить, что ряды в scores появляются в отсортированном порядке, то мы можем использовать bisect.bisect_right, чтобы найти нужный индекс в O(log(n)) времени. Если len(scores) велика, это будет быстрее, чем цикл по scores для каждого значения в ranks:

import bisect 
import operator 

scores = [ (500, 1), (450, 3), (400, 6), (300, 7), (225, 9) ] 
values, cutoffs = zip(*scores) 
ranks = [1, 5, 7, 8] 
print([values[bisect.bisect_right(cutoffs, rank)-1] for rank in ranks]) 

дает

[500, 450, 300, 300] 

---

Для очень больших len(scores) или len(ranks) вы получите лучше с использованием NumPy. Эквивалент NumPy bisect.bisect - np.searchsorted.Обратите внимание, однако, что np.searchsorted может принимать целый список (или массив) ranks в качестве аргумента и возвращать массив индексов, тогда как bisect.bisect должен вызываться один раз для каждого rank. Таким образом, проблема может быть решена только с одним вызовом np.searchsorted:

import numpy as np 

scores = np.array([ (500, 1), (450, 3), (400, 6), (300, 7), (225, 9) ]) 
values, cutoffs = scores[:,0], scores[:,1] 
ranks = [1, 5, 7, 8] 

print(values[np.searchsorted(cutoffs, ranks, side='right')-1]) 
# [500, 450, 300, 300] 

---

Ниже приведены некоторые тесты, когда len(scores) умеренно большой. С учетом этой установки:

import bisect 
import numpy as np 

scores = [ (500, 1), (450, 3), (400, 6), (300, 7), (225, 9) ] 
scores = np.array(scores * 2000).cumsum(axis=0) 
values, cutoffs = scores[:,0], scores[:,1] 
ranks = cutoffs[::100] 
scores_list = list(map(tuple, scores)) 
ranks_list = list(ranks) 

def using_numpy(scores, ranks): 
    # ranks does not have to be in sorted order 
    scores = np.asarray(scores) 
    values, cutoffs = scores[:,0], scores[:,1] 
    return values[np.searchsorted(cutoffs, ranks, side='right')-1] 

def using_bisect(scores, ranks): 
    # ranks does not have to be in sorted order 
    values, cutoffs = zip(*scores) 
    return [values[bisect.bisect_right(cutoffs, rank)-1] for rank in ranks] 

def using_reverse(scores, ranks): 
    # ranks must be sorted for this method to work 
    ranks.sort() 
    values = [] 
    i = len(scores) - 1 
    for rank in reversed(ranks): 
     while scores[i][1] > rank: 
      i -= 1 
     values.append(scores[i][0]) 
    values = values[::-1] 
    return values 

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

for func in (using_reverse, using_bisect): 
    assert np.allclose(func(scores_list, ranks_list), using_numpy(scores, ranks)) 

Это показывает using_numpy гораздо быстрее, чем using_reverse, если вы передаете массив NumPy в using_numpy и списков using_reverse:

In [241]: %timeit using_numpy(scores, ranks) 
100000 loops, best of 3: 8.58 µs per loop 

In [239]: %timeit using_reverse(scores_list, ranks_list) 
1000 loops, best of 3: 827 µs per loop 

In [250]: %timeit using_bisect(scores_list, ranks_list) 
1000 loops, best of 3: 835 µs per loop 

Если вы указали время, необходимое для конвертации списки scores_list в массив NumPy , то using_numpy становится медленнее, чем using_reverse:

In [242]: %timeit using_numpy(scores_list, ranks_list) 
100 loops, best of 3: 3.77 ms per loop 

Однако, как правило, когда вы используете NumPy, вы строите массивы раз и затем выполнить много вычислений. Таким образом, в то время как преобразование в массивы NumPy составляет дорого, это разовая стоимость, скажем < 4 мс (для примера выше). После , который вы получите, чтобы наслаждаться быстрыми вычислениями на основе NumPy (что в приведенном выше случае почти в 100 раз быстрее). Если ваша программа настолько короткая, что заканчивается за время, которое составляет порядка 4 мс, тогда преобразование в массивы NumPy может быть непомерно дорогостоящим. Однако, если ваша программа занимает значительно больше времени , чем 4 мс (что обычно имеет место, когда производительность имеет значение), то преобразование в массивы NumPy было бы небольшой ценой.