wake-up-neo.net

Python findet Zahlen zwischen Bereichen in Liste oder Array

Ich habe eine Liste mit Millionen von Zahlen, die immer bis zum Ende zunehmen. Ich muss Zahlen innerhalb eines bestimmten Bereichs suchen und zurückgeben, z. Zahlen größer als X aber kleiner als Y können sich die Zahlen in der Liste ändern und die Werte, nach denen ich suche, ändern sich ebenfalls

Ich habe diese Methode verwendet. Bitte beachten Sie, dass dies ein einfaches Beispiel ist. Die Zahlen sind nicht einheitlich oder die gleichen wie in meinem Programm gezeigt

l = [i for i in range(2000000)]
nums = []
for element in l:
    if element > 950004:
        break
    if element > 950000:
        nums.append(element)
#[950001, 950002, 950003, 950004]

Obwohl es schnell ist, brauche ich irgendwie etwas schneller für das, was mein Programm macht. Die Zahlen ändern sich stark. Ich frage mich, ob es einen besseren Weg gibt, dies mit einer Pandaserie oder einem Numpy-Array zu tun? aber bisher habe ich nur ein Beispiel in numpy gemacht:

a = numpy.array(l,dtype=numpy.int64)

Wäre eine Pandaserie funktionaler? Verwendung von Query ()? Was wäre der beste Weg, um dies mit einem Array zu erreichen, im Gegensatz zu einer Python-Liste von Python-Objekten

6
citizen2077

Hier ist eine Lösung mit binärer Suche. Sie sprechen von Millionen von Zahlen. Technisch ist die binäre Suche der Algorithmus schneller, indem die Laufzeitkomplexität auf O (log n) verringert wird, wobei der letzte Slicing-Schritt vernachlässigt wird.

import bisect

l = [i for i in range(2000000)]
lower_bound = 950000
upper_bound = 950004

lower_bound_i = bisect.bisect_left(l, lower_bound)
upper_bound_i = bisect.bisect_right(l, upper_bound, lo=lower_bound_i)
nums = l[lower_bound_i:upper_bound_i]
9
Calculator

Im Folgenden sind zwei Implementierungen für die binäre Suche (basierend auf Code aus hier ) aufgeführt - eine, die nach einer oberen Grenze sucht und eine, die nach einer unteren Grenze sucht. Funktioniert das besser für Sie? 

def binary_search_upper(seq, limit):
    min = 0
    max = len(seq) - 1
    while True:
        if max < min:
            return -1
        m = (min + max) / 2
        if m == (len(seq) -1) or (seq[m] <= limit and seq[m+1] > limit):
            return m
        Elif seq[m] < limit:
            min = m+1
        else:
            max = m - 1

def binary_search_lower(seq, limit):
    min = 0
    max = len(seq) - 1
    while True:
        if max < min:
            return -1
        m = (min + max) / 2
        if m == 0 or (seq[m] >= limit and seq[m-1] < limit):
            return m
        Elif seq[m] < limit:
            min = m+1
        else:
            max = m - 1


l = [i for i in range(2000000)]
print binary_search_upper(l, 950004)
print binary_search_lower(l, 950000)
2
Maor Veitsman

Sie können numpy verwenden, um eine Untermenge Ihrer Liste mithilfe eines booleschen Slice abzurufen.

import numpy as np
a = np.arange(2000000)
nums = a[(950000<a) & (a<=950004)]
nums
# returns
array([950001, 950002, 950003, 950004])
0
James