¿Cómo puedo seleccionar elementos menores que un número entero dado, de una lista ordenada?

Tengo una matriz de números primos, por ejemplo, entre números enteros de 0 a 1000

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997] 

Me dan entrada

 n = int(input()) 

¿Cuál es la forma más eficiente de dividir la matriz en una nueva matriz donde el último elemento de la matriz será menor que n ?

Related of "¿Cómo puedo seleccionar elementos menores que un número entero dado, de una lista ordenada?"

Puede hacer uso del hecho de que los primes ya están ordenados, con bisect , como este

 >>> from bisect import bisect >>> primes[:bisect(primes, n)] 

bisect realiza una búsqueda binaria en la lista de entrada y devuelve el índice del elemento que es menor que n .

Tienes una list , no una matriz. Si realmente necesitas dividir la lista y crear una nueva, eso llevará un tiempo lineal, sin importar cómo lo hagas. La respuesta de thefourtheye es probablemente lo mejor que vas a hacer:

 small_primes = primes[:bisect.bisect(primes, n)] 

Si tiene NumPy, sabe cómo crear vistas que parecen secciones, pero en realidad hacen referencia en lugar de copiar los datos. De hecho, si los primes fueran un ndarray , podría usar exactamente el mismo código que la respuesta de los ndarray y sería O (registro N).

 small_primes = primes[:bisect.bisect(primes, n)] 

Si solo necesita iterar la “matriz” una vez en lugar de usarla como una lista, puede usar un iterador perezoso:

 small_primes = itertools.takewhile(lambda p: p 

Ahora el costo inicial es 0; pero hay una comparación adjunta a cada valor en el momento en que lo consumes. Por supuesto, es más eficiente en espacio que cualquier otra cosa.

De manera realista, es improbable que "lo más eficiente" aquí sea importante, y si es importante, tendrá que medirlo, y si no está usando NumPy o ejecutando su código en PyPy, es casi seguro que desee hacer uno de esos antes de cualquier micro-optimizaciones ...

No explicaste por qué estás preguntando por “la forma más eficiente”, o qué quieres decir con (¿tiempo, espacio, algo más?), Y dudo que este sea un cuello de botella de rendimiento que valga la pena optimizar en cualquier lugar, pero si es:

Sólo tienes 168 elementos. Y no va a tener muchas listas similares, por lo que es poco probable que el espacio sea relevante. Mientras tanto, para que un algoritmo lineal sobre N = 168 sea importante, debe llamarlo un millón de veces, pero solo hay 1000 valores posibles. Entonces, solo crea una tabla:

 prime_slices = [[prime for prime in primes if prime < n] for n in range(1000)] 

Ahora, para obtener los números primos hasta n :

 prime_slices[n] 

Eso es tiempo constante. Por supuesto, la configuración lleva tiempo O (N ^ 2), pero eso no es nada, ya que solo ocurre una vez en lugar de guardar el trabajo O (N) de millones de veces. Y ocupa espacio O (N ^ 2), pero en realidad es solo un puntero constante de 15 K, que casi con toda seguridad puede permitirse.

Si no necesita de nuevo la lista completa de primos, truncar los números primos puede ser el método más rápido:

 primes[bisect(primes, n):]=[] 

Pero como siempre con el rendimiento, mídelo si te importa.