Найти ранг и процент ранга в списке

У меня есть несколько очень больших списков, с которыми я работаю (> 1M строк), и я пытаюсь найти быстрый (самый быстрый?) способ, учитывая поплавок, ранжировать этот поплавок по сравнению со списком поплавков и найти его процент ранга по сравнению с диапазоном списка. Вот моя попытка, но она очень медленная:

X =[0.595068426145485,
0.613726840488019,
1.1532608695652,
1.92952380952385,
4.44137931034496,
3.46432160804035,
2.20331487122673,
2.54736842105265,
3.57702702702689,
1.93202764976956,
1.34720184204056,
0.824997304105564,
0.765782842381996,
0.615110856990126,
0.622708022872803,
1.03211045820975,
0.997225012974318,
0.496352327702226,
0.67103858866700,
0.452224068868272,
0.441842124852685,
0.447584524952608,
0.4645525042246]

val = 1.5
arr = np.array(X) #X is actually a pandas column, hence the conversion
arr = np.insert(arr,1,val, axis=None) #insert the val into arr, to then be ranked
st  = np.sort(arr)

RANK      = float([i for i,k in enumerate(st) if k == val][0])+1 #Find position
PCNT_RANK = (1-(1-round(RANK/len(st),6)))*100 #Find percentage of value compared to range


print RANK, PCNT_RANK
>>> 17.0 70.8333

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

Спасибо.


python pandas numpy performance rank
person ajsp    schedule 17.06.2016    source источник
comment
Иногда bisectmodule оказывается на удивление полезным. Реализация ранга в ответе @tzaman в Как мне ранжировать список в ванильном Python? может быть хорошей основой, особенно. если чаще нужно ранжировать по сравнению с той же большой последовательностью.   -  person Dilettant    schedule 17.06.2016

Ответы (2)


arrow_upward
1
arrow_downward

Две медленные части вашего кода:

  • st = np.sort(arr). Сортировка списка занимает в среднем время O(n log n), где n — размер списка.

  • RANK = float([i for i, k in enumerate(st) if k == val][0]) + 1. Итерация по списку занимает O(n) времени.

Если вам не нужно сортировать список, то, как указывает @ChrisMueller, вы можете просто повторить его один раз без сортировки, что занимает время O(n) и будет самым быстрым вариантом.

Если вам нужно отсортировать список (или получить доступ к нему предварительно отсортированным), то самый быстрый вариант для второго шага — RANK = np.searchsorted(st, val) + 1. Поскольку список уже отсортирован, поиск индекса займет всего O(log n) времени с помощью бинарного поиска, вместо того, чтобы перебирать весь список. Это все равно будет намного быстрее, чем ваш исходный код.

person leekaiinthesky    schedule 17.06.2016
comment
Я полагаю, что мог бы заранее отсортировать списки в SQL, они никогда не меняются, поэтому я немного смущен, что не подумал об этом до публикации. - person ajsp; 18.06.2016

arrow_upward
6
arrow_downward

Сортировка массива кажется довольно медленной. Если вам не нужно, чтобы массив был отсортирован в конце, то логические операции numpy выполняются быстрее.

arr = np.array(X)
bool_array = arr < val # Returns boolean array
RANK = float(np.sum(bool_array))
PCT_RANK = RANK/len(X)

Или, что еще лучше, используйте понимание списка и избегайте numpy вообще.

RANK = float(sum([x<val for x in X]))
PCT_RANK = RANK/len(X)

Сделав некоторое время, приведенное выше решение numpy дает 6,66 нас в моей системе, а метод понимания списка дает 3,74 нас.

person Chris Mueller    schedule 17.06.2016