Недостаточно протестировано, используйте на свой страх и риск.
import numpy
a = numpy.random.random(100)
# a_by_a[i,j] = a[i] > a[j]
a_by_a = a[numpy.newaxis,:] > a[:,numpy.newaxis]
# by taking the upper triangular, we ignore all cases where i < j
a_by_a = numpy.triu(a_by_a)
# argmax will give the first index with the highest value (1 in this case)
print numpy.argmax(a_by_a, axis = 1)
Меньшая версия памяти:
a = numpy.random.random(100)
@numpy.vectorize
def values(i):
try:
return (a[i:] > a[i]).nonzero()[0][0] + i
except IndexError:
return -1 # no valid values found
b = values(numpy.arange(100))
Более быстрая версия:
@np.vectorize
def values(i):
try:
return next(idx for idx, value in enumerate(A[i+1:]) if value > A[i]) + i + 1
except StopIteration:
return -1 # no valid values found
return values(np.arange(len(A)))
Еще более быстрая версия:
def future6(A):
# list of tuples (index into A, value in A)
# invariant: indexes and values in sorted order
known = []
result = []
for idx in xrange(len(A) - 1, -1, -1):
value = A[idx]
# since known is sorted a binary search could be applied here
# I haven't bothered
# anything lower then the current value
# cannot possibly be used again, since this value will be first index instead
# of those
known = [(x,y) for x,y in known if y > value]
if known:
# all values in known are > current value
# they reverse sorted by index
# the value with the lowest index is first
result.append(known[-1][0])
else:
# no values exist this high, report -1
result.append(-1)
# add to end of the list to maintain invariant
known.append( (idx, value) )
# let numpy worry about reversing the array
return np.array(result)[::-1]
Благодарим киборга за некоторые идеи, использованные здесь.
Разница в алгоритмах
Киборг показал значительные различия между различными алгоритмами в зависимости от данных, вводимых в них.Я собрал некоторые статистические данные из запущенных алгоритмов, чтобы посмотреть, смогу ли я выяснить, что происходит.
Случайные данные:
Average distance between value and its target: 9
Average length of ascends list: 24
Average length of segment in ascends list: 1.33
Average length of known list: 9.1
Поскольку списки действительно короткие, алгоритм восхождений в основном распадается на линейный поиск.Он очищает подъемы, которые не могут быть использованы в будущем, поэтому он все же заметно лучше, чем линейный поиск.
Колеблющийся:
Average distance between value and its target: 31.46
Average length of ascends list: 84
Average length of segment in ascends list: 1.70
Average length of known list: 57.98
Колебания имеют тенденцию кРазместите разные части дальше друг от друга.Это естественно затрудняет алгоритм линейного поиска.Оба «умных» алгоритма должны отслеживать дополнительные данные.Мой алгоритм значительно затухает, поскольку каждый раз сканирует данные.Алгоритм возрастания затрагивает меньше своих данных и работает лучше.
Ascending:
Average distance between value and its target: 2.57
Average length of ascends list: 40
Average length of segment in ascends list: 3.27
Average length of known list: 3037.97
Понятно, почему у моего алгоритма есть проблемы, он должен отслеживать огромное количествовосходящих значений.Короткое расстояние между значением и целью объясняет хорошую производительность линейного поиска.Ascends до сих пор не работает с очень длинными сегментами.
Лучшие алгоритмы
У моего алгоритма нет причин для линейного поиска по данным.Он отсортирован, и нам просто нужно удалить небольшие значения из конца списка.
def future6(A):
# list of tuples (index into A, value in A)
# invariant: indexes and values in sorted order
known = []
result = []
for idx in xrange(len(A) - 1, -1, -1):
value = A[idx]
# since known is sorted a binary search could be applied here
# I haven't bothered
# anything lower then the current value
# cannot possibly be used again, since this value will be first index instead
# of those
while known and known[-1][1] < value:
known.pop()
if known:
# all values in known are > current value
# they reverse sorted by index
# the value with the lowest index is first
result.append(known[-1][0])
else:
# no values exist this high, report -1
result.append(-1)
# add to end of the list to maintain invariant
known.append( (idx, value) )
# let numpy worry about reversing the array
return np.array(result)[::-1]
Но мне приходит в голову, что мы можем повторно использовать предыдущие вычисленные значения B вместо создания новых структур данных.Если j> i, A [i]> A [j], то B [i]> B [j].
def future8(A):
B = [-1] * len(A)
for index in xrange(len(A)-2, -1, -1):
target = index + 1
value = A[index]
while target != -1 and A[target] < value:
target = B[target]
B[index] = target
return np.array(B)
Мои результаты тестов:
Random series:
future2 ascends : 0.242569923401
future6 full list: 0.0363488197327
future7 vectorize: 0.129994153976
future8 reuse: 0.0299410820007
Oscillating series:
future2 ascends : 0.233623981476
future6 full list: 0.0360488891602
future7 vectorize: 1.19140791893
future8 reuse: 0.0297570228577
Ascending trend series:
future2 ascends : 0.120707035065
future6 full list: 0.0314049720764
future7 vectorize: 0.0640320777893
future8 reuse: 0.0246520042419
Восходящие секции
У Киборга была очень интересная идея воспользоваться преимуществами восходящих сегментов.Я не думаю, что какой-либо из его тестовых примеров действительно демонстрирует поведение, которое он преследовал после этого.Я не думаю, что секции были достаточно длинными, чтобы воспользоваться.Но я полагаю, что реальные данные вполне могут иметь такие разделы, поэтому использование их было бы очень полезно.
Но я не думаю, что это сработает.Требуется O (n) время, чтобы подготовить необходимые данные для выполнения двоичного поиска.Это было бы хорошо, если мы выполняем бинарный поиск много раз, но как только мы находим значение в середине восходящего раздела, мы никогда не возвращаемся к чему-либо слева.В результате, даже при бинарном поиске мы тратим не более O (n) времени на обработку данных.
Это может сработать, если будет дешевле построить необходимые данные, чем потом сканировать восходящий участок.Но сканирование довольно дешевое, и вам будет сложно найти способ обработки восходящих участков, который дешевле.