Comprobando la igualdad de números enteros:¿O(1) en C pero O(log n) en Python 3?

Question

Considere estas funciones equivalentes en C y Python 3.La mayoría de los desarrolladores afirmarían inmediatamente que ambos son $O(1)$.

def is_equal(a: int, b: int) -> bool:
  return a == b

int is_equal(int a, int b) {
  return a == b;
}

Pero consideremos lo que está sucediendo bajo la superficie.Los números enteros son simplemente cadenas binarias y, para determinar la igualdad, ambos lenguajes compararán las cadenas bit a bit.En cualquier caso, esta exploración es $O(b)$ dónde $b$ es el número de bits.Dado que los números enteros tienen un tamaño constante en bits en C, esto es simplemente $O(1)$.

EDITAR:C no se compara bit a bit ver esta respuesta

Sin embargo, en Python 3, los números enteros sí no tienen un tamaño fijo y el escaneo permanece $O(b)$ para el número de bits en la entrada, o $O(\log a)$ dónde $a$ es el valor de la entrada en base 10.

Entonces, si estás analizando código en Python, cada vez que comparas dos números enteros, te estás embarcando en un viaje sorprendentemente complejo de $O(\logn)$ con respecto al valor en base 10 de cualquiera de los números.

Para mí esto plantea varias preguntas:

1. ¿Es esto correcto?No he visto a nadie más afirmar que Python compara enteros en tiempo de registro.
2. En el contexto de la realización de una entrevista, ¿debería notar o importarle si un candidato llama a esto? $O(1)$?
3. ¿Deberías notar o preocuparte por esta distinción en el mundo real?

EDITAR:Es fácil de verificar (e intuitivo) que Python no puede comparar enteros arbitrariamente grandes en tiempo constante.Entonces, una mejor manera de formular la pregunta 1 anterior podría ser "¿Cuál (si la hay) es la justificación para llamar a esta operación? $O(1)$?¿Porque es pragmático?¿Convencional?¿Implicado por el modelo de RAM?

Answer 1

tl; DR: Hay un convenio de CS de describir este tipo de operación como $ o (1) $ que se divide en casos extremos para Python. Estos casos son extremadamente raros, por lo que para romper con la convención de $ o (1) $ tiene una utilidad negativa. Este tipo de pragmatismo es normal en Big $ o $ .

Hay muchas respuestas muy buenas a esta pregunta y te animo a leerlas. Pero no creo que ninguno de ellos responda completamente a mis preguntas. Así que aquí hay una síntesis.

es este correcto? No he visto a nadie más afirmando que Python compara INTS en la hora de registro.

Esto es sorprendentemente matizado. Es verdadero que Python compara un INTS muy grande en $ o (\ log n) $ tiempo de ejecución. Pero es correcto para describir esta operación como $ o (\ log n) $ ?

En última instancia, estoy más persuadido por esta toma de @Tomvanderzanden:

Si dijo que la versión C o Python fue $ O (1) $ Cualquier entrevistador debe estar perfectamente feliz. Si lo dijiste (la versión de Python) estaba $ O (\ log n) $ probablemente todavía serían felices, pero creo que eres una persona más bien pedantica que no T siga las convenciones normales.

y

Si era un entrevistador, me gustaría saber si conoce las limitaciones del mundo real de lo que está haciendo y saber qué importa las preocupaciones teóricas, cuándo y que lo trae, y solo, si es apropiado.

Sin embargo, no estoy aceptando eso como la respuesta porque creo que el primer párrafo está actualmente engañoso (feliz de cambiar).

En última instancia, este argumento es pragmático. Por la definición estricta de big $ o $ Python int comparacion todavía está verificable $ o (\ log n) $ . Pero no es útil tratarlo de esa manera, por lo que no deberías. Agregaría que para ser estricto acerca de Big $ o $ es perder el punto de Big $ análisis.

Answer 2

Los números enteros son simplemente cadenas binarias y, para determinar la igualdad, ambos lenguajes compararán las cadenas bit a bit.

No exactamente.C intLos s tienen el tamaño de una palabra de máquina y se comparan con una sola instrucción de máquina;Pitón ints están representados en base $2^{30}$ (ver por ej. https://rushter.com/blog/python-integer-implementation/) y se compararon dígito por dígito en esa base.Entonces la base relevante del logaritmo es $2^{30}$.

Si al menos uno de números pueden estar acotados por $2^{30d}$ para cualquier fijado $d$, la comparación es $O(1)$ (porque primero se compara el número de dígitos), y si no pueden, es probable que otras operaciones sean mucho más preocupantes que la comparación de igualdad.Entonces, en la práctica, diría que es muy poco probable que importe y, si es así, lo sabrás (y estarías usando no ints pero algo como el Biblioteca aritmética de precisión múltiple GNU en C también).

Answer 3

La complejidad se define en relación con un modelo de cálculo.P y NP, por ejemplo, se definen en términos de máquinas de Turing.

Para comparación, considere la palabra modelo RAM.En este modelo, la memoria se divide en palabras, se puede acceder a las palabras en un tiempo constante, y el tamaño del problema se puede representar utilizando $ o (1) $ palabras.

Entonces, por ejemplo, al analizar una operación de clasificación basada en comparación, asumimos que la cantidad de elementos $ n $ se pueden almacenar en $ o (1) $ palabras, por lo que se necesita tiempo constante para leer o escribir un número entre $ 1 $ y $ n $ .

Answer 4

es este correcto? No he visto a nadie más afirmando que Python compara INTS en la hora de registro.

No (y un poco si). Considere la siguiente reclamación provocadora (pero no verdadera): una computadora solo puede tener una cantidad finita de memoria (limitada por el número de átomos en el universo), por lo que la versión de Python también es $ O (1) $ .

El problema es que estamos tratando de hacer una declaración sobre asintóticos (pertenecientes a lo que sucede en el infinito) sobre una máquina de estado finita (una computadora). Cuando estamos analizando la complejidad del código, en realidad no analizamos el código en sí mismo, ya que se ejecutará en una computadora, estamos analizando un modelo idealizado del código.

Supongamos que le pedí que analizara un algoritmo de clasificación escrito en C. Podría indicar que utiliza INTS para indexar la matriz, por lo que solo podría ordenar una serie de tamaño hasta $ 2 ^ {31} -1 $ . Sin embargo, cuando analizamos tal pieza de código, pretendemos que podría manejar matrices arbitrariamente grandes. Claramente, no estamos diciendo que la comparación de C INTEGER es $ o (1) $ porque solo puede manejar los números de 32 bits.

En el contexto de realizar una entrevista, ¿debe notar o cuidar si un candidato lo llama O (1)?

Por lo general, no. Supongamos que estoy realizando una entrevista y le pido que escriba un programa de computadora C o Python que cuenta el número de empleadas que aparecen en la base de datos de empleados.

sería increíblemente pedante si me quejo tu programa C era incorrecto porque solo podía contar hasta $ 2 ^ {31} -1 $ .

Generalmente asumimos que los números son lo suficientemente pequeños como para que puedan caber dentro de una palabra / entero. Asumimos que la adición (o cualquier otra operación de número) se puede realizar en $ o (1) $ , porque sería muy molesto tener que escribir $ o (\ log n) $ en todas partes y simplemente haría que todo está ilegible aunque $ \ log n $ es tan pequeño. Realmente no importa de todos modos.

Si dijo que la versión C o Python fue $ O (1) $ Cualquier entrevistador debe estar perfectamente feliz. Si lo dijiste (la versión de Python) estaba $ O (\ log n) $ probablemente todavía serían felices, pero creo que eres una persona más bien pedantica que no T siga las convenciones normales.

¿Debes notar o preocuparse por esta distinción en el mundo real?

¡Sí! Comienza a importar cuando los números se vuelven tan grandes, se viola el supuesto que son pequeños. Digamos que está entrevistando para Google y le solicitaron que calcule la cantidad de consultas de búsqueda realizadas por los usuarios de mujeres en el último año. El entrevistador estaría bastante justificado para quejarse si escribió un programa C usando INTS.

Podría cambiar a los largos y aún así estar justificados al llamarlo $ o (1) $ , y de manera similar, llamando a la versión de Python $ o (1) $ también está justificado. El $ o (1) $ v.s. $ o (\ log n) $ cosa solo comienza a importar cuando los números aumentan mucho. Por ejemplo, si su tarea es escribir un programa que calcula los dígitos de $ \ pi $ o alguna tarea similar. Si escribió un programa de Python para esta tarea y no mencionó las peculiaridades de la complejidad cuando se le solicitó, el entrevistador le importaría.

Si era un entrevistador, me gustaría saber si conoce las limitaciones del mundo real de lo que está haciendo y saber qué importa las preocupaciones teóricas, cuándo y que lo trae, y solo, si es apropiado.

¿Cuándo debe cuidar?

Hasta ahora, he sido un poco vago sobre los números "grandes" y "pequeños". En el modelo RAM comúnmente utilizado, se le permite asumir que las operaciones enteras se pueden realizar en $ o (1) $ en números que tienen más $ o (\ log n) $ bits (donde $ n $ es la longitud de la entrada). La justificación para este supuesto es que si tenemos una entrada de longitud $ n $ , los punteros / índices en nuestro lenguaje de programación deben ser lo suficientemente largos como para poder abordar el Todo el espacio de entrada. Entonces, en el modelo de RAM, si la entrada es el número binario de $ n $ (binario) dígitos, la complejidad de la comprobación de la igualdad es $ O (\ frac {n} {\ log n}) $ Dado que podemos verificar la igualdad de un grupo de $ o (log n) $ < / span> bits en una $ o (1) $ operación.

Answer 5

Aunque esto pueda parecer un punto trivial, tu primera frase es incorrecta. Las funciones no son equivalentes..Para que sean equivalentes, la función C debería usar GMP (o similar) para implementar aritmética de precisión arbitraria.Ahora bien, la razón por la que esta observación no es trivial es que en la medida en que es razonable decir que los dos son equivalentes, es precisamente en la medida en que es razonable decir que el código Python es de tiempo constante.Es decir, si vamos a ignorar que los números enteros de Python son bignums, podemos (y debemos) tratarlos consistentemente como de tamaño fijo.

De manera análoga, considere la función C int is_equal(char a, char b) { return a == b; } y la función de Python def is_equal(a: str, b: str) -> bool: return a == b.Ahora es más obvio que las funciones no son equivalentes, pero la razón es exactamente la misma que la suya no lo es.Simplemente esperamos ver cadenas masivas en Python todo el tiempo, pero realmente no esperamos entradas masivas aunque, por supuesto, sabemos que son posibles.Entonces, la mayoría de las veces ignoramos el hecho de que los números enteros de Python son grandes y los analizamos como si fueran de tamaño fijo.En los raros casos en los que nos preocupamos por los tiempos de las operaciones de bignum, podemos utilizar las complejidades "reales".Y, por supuesto, también utilice GMP en su código C.

Todo esto es para decir:aunque no te diste cuenta, ya conoces la respuesta a la versión reformulada de tu pregunta al final, y la respuesta es "la misma justificación con la que describiste esas funciones como equivalentes".Python es inusual porque no tiene un tipo entero de tamaño fijo (bueno, no es uno que la gente use comúnmente:es posible escribir uno, por supuesto, y hay uno en numpy).Pero como cuestión de pragmatismo, no queremos que esto nos impida realizar el análisis de complejidad "habitual" de algoritmos que procesan números enteros y obtener las respuestas "habituales".Rara vez es necesario advertir que si le pasamos un par de números enteros de 10 GB que son casi iguales, puede llevar un poco de tiempo compararlos.

En algunos casos, podría formalizar esto (si realmente lo necesita) diciendo que está restringiendo su análisis a números enteros pequeños.Luego, podría considerar la complejidad de algún algoritmo en términos del tamaño de algún conjunto de números enteros, tratando todas las operaciones aritméticas como O(1).Si está considerando algoritmos que realmente son lineales o peores en la magnitud del número entero, entonces podría formalizarlo diciendo que va a ignorar el factor logarítmico, ya que lo único que realmente le importa es si la complejidad está más cerca de lineal o cuadrático, porque O(n log n) es tan bueno como lineal para sus propósitos.Sin embargo, casi siempre no es necesario formalizar la complejidad de los algoritmos. en pitón.Si has llegado al punto de especificar un lenguaje de programación, ya no estás haciendo informática abstracta ;-)

En el contexto de realizar una entrevista, si nota o cuida si un candidato llama a esto $O(1)$?

Depende de la entrevista, supongo, pero como profesional del software, trabajando principalmente en Python durante los últimos 10 años, no preguntaría eso en una entrevista.Si hiciera una pregunta que tuviera oculta la complejidad de la comparación de números enteros (como, no sé, "¿cuál es la complejidad de este algoritmo de clasificación?"), entonces aceptaría una respuesta que ignorara todo el problema.También aceptaría uno que abordara este tema.Creo que vale la pena comprender y calcular la complejidad como parte de la programación práctica, pero no lo considero tan importante. para programación Hay que tener mucho cuidado al afirmar formalmente que estás hablando de números enteros de tamaño razonable.

Tampoco haría nunca una pregunta en la que quiera que el candidato ofrezca la información de que los enteros de Python son de precisión arbitraria, cuando obviamente no es relevante para la pregunta por alguna razón relacionada con los datos involucrados.Si la pregunta implica que los números involucrados pueden ser superiores a 2⁶⁴ luego, en una entrevista C, me gustaría que el candidato se diera cuenta de que este es un problema con el que deben lidiar, y en una entrevista con Python, me gustaría que el candidato supiera que no lo es, pero no lo esperaría. hacer todo lo posible para expresarlo.No hay tiempo en una entrevista para exponer cada pequeño hecho que hace que algo no sea un problema.

Si quisiera comprobar la comprensión de la complejidad en una entrevista, lo más probable es que comenzara pidiendo algún código para algún problema en el que haya una solución "ingenua" realmente sencilla con poca complejidad y al menos una solución menos sencilla con una complejidad decente. utilizando técnicas bien conocidas.Si el candidato ofrece una solución ingenua, entonces puede preguntar cuál es la complejidad y cómo modificarían el código para mejorarlo.Si el candidato ofrece una mejor solución, entonces puede describir la solución ingenua, señalar las pocas líneas de código que tiene y preguntar qué tiene de malo (tal vez preguntando: "si estuvieras revisando el código de alguien y te dieran esto, ¿qué ¿Qué dirías al respecto"?).Para la mayoría de los fines prácticos, lo único que le importa es si pueden distinguir entre lineal, cuadrático y peor que cuadrático.También aparece O(n log n), pero principalmente debido a la clasificación o las estructuras de datos donde se habla de complejidad en términos del número de comparaciones.El costo de cada comparación generalmente se considera irrelevante, porque el diseñador del algoritmo generalmente no tiene control sobre él (lo proporciona el usuario del algoritmo o la estructura de datos).

En el caso sorprendentemente improbable de que yo fuera el entrevistador para un puesto como académico de informática que cubriera aritmética de precisión arbitraria, entonces ciertamente me gustaría que los candidatos conocieran las complejidades de varios algoritmos para diversas operaciones y, de hecho, conocieran el estado del arte para los no triviales.

Answer 6

es este correcto? No he visto a nadie más afirmando que Python compara INTS en el tiempo de registro. Python de hecho tiene un formato entero de precisión arbitraria. Sin embargo, tenemos que hacer una comparación justa aquí. Si consideramos el subconjunto de enteros en el límite de $ [0,2 ^ {64}] $ , encontramos que la operación de Python es un tiempo constante.

Lo que está viendo es uno de los límites en cuanto a medir la complejidad computacional utilizando la notación de BIG-OH. Describe lo que sucede como n se acerca al infinito, pero no necesariamente hace un buen trabajo para comparar el comportamiento para números más pequeños. Vemos esto famoso en algoritmos de multiplicación de matriz . Hay algunos algoritmos que son más eficientes en un sentido más grande, pero en realidad son más lentos en la práctica hasta que llegue a las matrices de Gargantuan.

En el contexto de realizar una entrevista, ¿debe notar o cuidar si un candidato lo llama O (1)?

Depende de lo que los está contratando. Para la gran mayoría de los trabajos, llamarlo O (1) debería estar bien. De hecho, es como tendemos a enseñarlo en la escuela. Si quisiera convertirlo en una oportunidad útil para aprender sobre su candidato, puede preguntarles por qué piensan que la adición es un tiempo constante (a lo que la respuesta es que el modelo que solían para determinar BIG-OH lo asumió ... lo cual es una respuesta válida)

Si está contratando a alguien para buscar cosas como explotaciones en su código, es posible que desee empujar más. Un bignum producido por su propio código es una cosa, pero ¿se le permite al usuario ingresar el número de su propia elección? Si es así, pueden crear ataques de tiempo y DOSS utilizando el hecho de que esta adición puede ser terriblemente lenta. Detectar este riesgo podría ser parte de su trabajo.

¿Debes notar o preocuparse por esta distinción en el mundo real?

prácticamente hablando: no. No hasta que se ejecute de forma inquieta, y corregir el problema en la depuración. Python hace un lote de cosas que son "generalmente seguras" y son muy eficientes. Esta es la razón por la que se ha asumido como uno de los idiomas más populares del mundo.

Para una situación equivalente: ¿Qué tan rápido es x.y en Python? Pensamos en ello como O (1), pero en realidad hay una búsqueda de hash allí. Esa búsqueda de hash utiliza un mecanismo de sondeo conocido, y la búsqueda resultante es en realidad O (N). Nunca verás esto en código normal. Pero en el código donde un adversario llega a llenar su diccionario con su propio contenido, pueden introducir intencionalmente las llaves de navegación que chocan de esta manera.

Answer 7

Nunca he encontrado un texto que trató las operaciones de enteros "regulares", como cualquier cosa, además de un tiempo constante, con la suposición implícita de que el tamaño tenía un límite superior finito razonable (por ejemplo, 64 bits).Tal vez sería más preciso afirmar el supuesto, pero a una audiencia de CS, creo que está implícita.

Hacerlo introduciría mucha complejidad en las discusiones de temas esencialmente no relacionados.Las implementaciones de BIGINT típicamente no se implementan poco a poco, sino en la base (tamaño de la palabra de la máquina), de modo que O (B)> O (1) problema solo se pone en cuenta por números fabulosamente grandes.

Personalmente, mientras entrevistando a alguien, podría apreciar el rigor y la amplitud del conocimiento asociada con conocer los enteros de Python fueron longitud arbitraria, pero algo más allá de afirmar la suposición de que todas las matemáticas son O (1) se sentirían extremadamente pedantes.Si el análisis comenzó a llegar demasiado lejos con el tema con aritmética, y el tiempo perdido, consideraría este candidato malo.