Эффективный способ получить индекс минимального значения в длинном векторе Python

Question

У меня длинный список значений долготы (len (Lon) = 420481) и еще один список значений широты.Я хочу найти соответствующую широту к минимуму долготы.

Я пытался:

SE_Lat = [Lat[x] for x,y in enumerate(Lon) if y == min(Lon)]

, но это занимает целую вечность.

Кто-нибудь знает большеэффективный способ?

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

minDiff = [min(abs(x - lon_new) for x in lons)] # not very quick, but works
[(lat,lon) for lat,lon in izip(lats,lons) if abs(lon-lon_new)==minDiff]

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

Answer 1

Могу ли я порекомендовать numpy?

import numpy
nplats = numpy.array(lats)
nplons = numpy.array(lons)

# this part is 20x faster than using the built-in python functions
index = numpy.argmin(nplats)

print nplats[index], nplons[index]

это намного быстрее, чем решение min (izip ()) (~ 20x при использовании моей настройки при использовании 420481 случайно созданных записей), хотя, конечно, вы быВам нужно хранить значения данных в NumPy, чтобы воспользоваться этим ускорением.

Answer 2

min(itertools.izip(Lat, Lon), key=operator.itemgetter(1))[0]

Answer 3

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

SE_Lat = [Lat[x] for x,y in enumerate(Lon) if y == min(Lon)]

Мы знаем из ОП, что len(Lon) == 420481.Теперь нахождение минимального значения является операцией O (N) (вы должны смотреть на каждое значение хотя бы один раз).В понимании списка условие переоценивается на каждую итерацию .Приведенный выше код пересчитывает минимальное значение при каждом проходе через цикл, превращая то, что должно быть операцией O (N), в O (N ^ 2) (в данном случае всего 177 миллиард итераций).

Простое кэширование результата min(Lon) в локальной переменной и использование его в условии цикла вместо его пересчета, каждая итерация, вероятно, приведет к снижению времени выполнения до приемлемого уровня.

Однако,способ, которым я лично поступил бы в этом направлении (предполагая, что позже мне понадобятся все значения широты, долготы и индекса):

min_longitude, min_index = min(longitude, index for index, longitude in enumerate(Lon))
min_latitude = Lat[min_index]

Хотя существует множество возможностей, и какой из них лучше, будет зависеть отТочный вариант использования.

Answer 4

Просто сначала найдите индекс:

index = min(enumerate(Lon), key=operator.itemgetter(1))[1] 
Lat[index]

Answer 5

Вот мой первоначальный ответ:

>>> lats = [1,2,3,4]
>>> lons = [5,4,8,9]
>>> from itertools import izip
>>> min(izip(lats,lons), key=lambda x:x[1])
(2, 4)

Но я вижу, что ОП, казалось, допускает наличие нескольких совпадений при минимальном значении lon, и для этого я не думаю, что естьоднострочник.Хитрость в том, что вы хотите найти min (lons) только один раз, а не один раз для каждого lat, lon пары:

>>> lats = [1,2,3,4]
>>> lons = [5,4,8,4]
>>> minlon = min(lons)
>>> [(lat,lon) for lat,lon in izip(lats,lons) if lon==minlon]
[(2, 4), (4, 4)]

Этот однострочный может работать на вас, так как аргумент лямбда minlon долженвычисляется один раз:

>>> filter(lambda latlon,minlon=min(lons):latlon[1]==minlon, izip(lats,lons))
[(2, 4), (4, 4)]

Не уверен, насколько хорошо он будет работать со списками из 420481 элементов.А для удобочитаемости и долгосрочной поддержки я бы, вероятно, выбрал более явное 2-строчное решение.

Последний пункт: иногда вы получаете только один проход через последовательность, например, когда это итератор иливыход генератора.Для поддержки нескольких совпадений и выполнения только одного прохода через два списка это было лучшее, что я мог сделать:

from itertools import izip

def get_lats_at_min_lon(lats, lons):
    minlon = 200
    minlats = []
    for lat,lon in izip(lats, lons):
        if lon < minlon:
            minlats = [lat]
            minlon = lon
        elif lon == minlon:
            minlats.append(lat)
    return minlon, minlats

lats = iter([1,2,3,4])
lons = iter([5,4,8,4])

print get_lats_at_min_lon(lats,lons)

Отпечатки:

(4, [2, 4])

Answer 6

pairs = zip(latitudes, longitudes)
minLonPair = min(pairs, key=lambda p:p[1])
print(minLonPair[0])

Согласно решению Игнасио, если вы используете python2, вам нужно будет использовать izip вместо zip. Однако это верно для всего, что вы делаете в python2.