Verificação de igualdade de números inteiros:O(1) em C, mas O(n log n) no Python 3?

Question

Considere estas funções equivalentes em C e Python 3.A maioria dos devs seria imediatamente a alegação de que ambos são $S(1)$.

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

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

Mas vejamos o que está acontecendo sob a superfície.Os números inteiros são apenas sequências binárias e, para determinar a igualdade, ambas as línguas, irá comparar as seqüências de caracteres de bit por bit.Em qualquer caso, a verificação é $S(b)$ onde $b$ é o número de bits.Desde números inteiros têm um tamanho constante em bits em C, isto é simplesmente $S(1)$.

EDITAR:C não se compara bit a bit veja esta resposta

No Python 3 no entanto, inteiros fazer não tem tamanho fixo, e o scan continua $S(b)$ o número de bits na entrada, ou $O(\log a)$ onde $a$ é o valor da entrada na base 10.

Então, se você estiver análise de código em Python, a qualquer momento que você compara dois números inteiros, você está embarcando em uma surpreendente jornada complexa de $O( log n)$ com respeito ' a base 10 valor de cada número.

Para mim, isso levanta várias questões:

1. Isso está correto?Eu ainda não vi ninguém reclamar que o Python compara ints na hora de log.
2. No contexto da realização de uma entrevista, caso você perceba ou não se preocupam se um candidato chama isso de $S(1)$?
3. Caso você perceba ou se preocupam com esta distinção no mundo real?

EDITAR:Isso é facilmente verificado (e intuitiva) de que o Python não pode comparar-se arbitrariamente grande ints em tempo constante.Para um melhor maneira de fazer a pergunta 1 acima poderia ser: "o Que (se houver) é a justificativa para chamar esta operação de $S(1)$?Porque é pragmática?Convencional?Expressa pela RAM modelo?

Answer 1

TL;DR:Há um CS convenção de descrever este tipo de operação, como $S(1)$ o que acontece para quebrar em casos extremos, para Python.Estes casos são extremamente raros, de modo a romper com a convenção de $S(1)$ negativo utilitário.Este tipo de pragmatismo é normal em grandes $O$.

Há um monte de boas respostas para esta pergunta, e eu encorajo você a lê-los.Mas eu não acho que qualquer um deles totalmente responder minhas perguntas.Então aqui está uma síntese.

Isso está correto?Eu ainda não vi ninguém reclamar que o Python compara ints na hora de log.

Esse é surpreendentemente variada.É verdadeiro que o Python compara muito grande ints em $O( log n)$ o tempo de execução.Mas é correto para descrever esta operação como $O( log n)$?

Finalmente, estou mais convencido por este exame a partir @TomvanderZanden:

Se você disse que o C ou Python versão foi $S(1)$ qualquer entrevistador deve ser perfeitamente feliz.Se você disse que ele (a versão do Python) foi $O( log n)$ eles provavelmente ainda ser feliz, mas acho que você está um pouco pedante pessoa que não siga normal convenções.

e

Se eu fosse um entrevistador, eu teria o cuidado se você souber o mundo real, limitações de que você está fazendo e sabe o que preocupações teóricas importa quando e que você levá-los até se e apenas se for necessário.

No entanto, eu não sou de aceitar que, como a resposta, porque eu acho que o primeiro parágrafo é atualmente enganosa (feliz a alteração).

Em última análise, este é um argumento pragmático.Por definição estrita do big $O$ Python int comparação ainda é verificável $O( log n)$.Mas não é útil para tratá-lo dessa forma, então você não deve.Eu gostaria de acrescentar que, para ser rigoroso sobre o grande $O$ é perder o ponto do big $O$ análise.

Answer 2

Os números inteiros são apenas sequências binárias e, para determinar a igualdade, ambas as línguas, irá comparar as seqüências de caracteres de bit por bit.

Não é bem assim.C ints são de tamanho de palavra e em comparação com uma única instrução de máquina;Python ints são representados em base $2^{30}$ (veja o exemplo: https://rushter.com/blog/python-integer-implementation/) e comparados, dígito por dígito, em que base.Assim, o relevante base do logaritmo é $2^{30}$.

Se pelo menos um de números podem ser delimitadas por $2^{30}$ para qualquer fixo $d$, a comparação é $S(1)$ (porque o número de dígitos é comparado o primeiro), e se eles não podem, outras operações são susceptíveis de muito mais preocupação do que a comparação de igualdade.Assim, na prática, eu diria que é muito pouco provável que importa e se isso acontecer você vai saber (e estaria usando não ints, mas algo como o GNU Vários Aritmética de Precisão Biblioteca em C bem).

Answer 3

A complexidade é definida em relação a um modelo de computação.P e NP, por exemplo, são definidos em termos de máquinas de Turing.

Para efeito de comparação, considere a palavra de RAM do modelo.Neste modelo, a memória é dividida em palavras, as palavras podem ser acessados em tempo constante, e o tamanho do problema pode ser representado usando $S(1)$ palavras.

Assim, por exemplo, ao analisar-se uma comparação baseada no tipo de operação, assumimos que o número de elementos $n$ pode ser armazenado em $S(1)$ palavras, por isso leva tempo constante para ler ou escrever um número entre $1$ e $n$.

Answer 4

Isso está correto?Eu ainda não vi ninguém reclamar que o Python compara ints na hora de log.

Não (e um pouco sim).Considere o seguinte instigante (mas não de verdade) reclamação:Um computador pode ter apenas uma quantidade finita de memória (limitada pelo número de átomos no universo), então a versão do Python é também $S(1)$.

O problema é que estamos tentando fazer uma declaração sobre a asymptotics (relacionadas ao que acontece no infinito) sobre uma máquina de estado finito (um computador).Quando estamos analisando a complexidade do código, nós, na verdade, não analisar o código propriamente dito como ele seria executado em um computador, estamos analisando alguns idealizado modelo de código.

Suponha que eu pedi para você analisar um algoritmo de ordenação escrito em C.Você poderá estado utiliza ints para indexar a matriz, de modo que ele só podia ordenar uma matriz de tamanho até $2^{31}-1$.Porém, temos que analisar como um pedaço de código, nós fingimos que ele poderia lidar com arbitrariamente grandes matrizes.Claramente, não estamos dizendo C inteiro comparação é $S(1)$ porque ele só pode manipular números de 32 bits.

No contexto da realização de uma entrevista, caso você perceba ou não se preocupam se um candidato chama isso de O(1)?

Geralmente, não.Suponha que eu sou a realização de uma entrevista e pedir-lhe para escrever um C ou python programa de computador que conta o número de mulheres que aparecem na base de dados de funcionários.

Seria incrivelmente pedante, se eu reclamou o seu programa em C é incorreta, pois poderia apenas contar até $2^{31}-1$.

Geralmente assumimos que os números são pequenos o suficiente para que eles podem caber dentro de uma palavra/número inteiro.Nós assumimos a adição (ou qualquer outro número operação) pode ser feito em $S(1)$, porque seria muito chato ter que escrever $O( log n)$ em todos os lugares e fazem de tudo, ilegíveis, mesmo que $\log n$ é tão pequena que realmente não importa, de qualquer maneira.

Se você disse que o C ou Python versão foi $S(1)$ qualquer entrevistador deve ser perfeitamente feliz.Se você disse que ele (a versão do Python) foi $O( log n)$ eles provavelmente ainda ser feliz, mas acho que você está um pouco pedante pessoa que não siga normal convenções.

Caso você perceba ou se preocupam com esta distinção no mundo real?

Sim!Ele começa a matéria, quando os números ficam tão grande a suposição de que eles são pequenos é violada.Vamos dizer que você está entrevistando para o Google e eles pediram para calcular o número de consultas de pesquisa feitas por usuários do sexo feminino no ano passado.O entrevistador seria perfeitamente justificado para reclamar se você escreveu um programa em C usando ints.

Você pode alternar usando anseia e ainda ser justificada, chamando-o de $S(1)$, e , da mesma forma, chamando a versão do Python $S(1)$ também é justificada.O $S(1)$ v. s. $O( log n)$ a coisa só começa a se importa quando os números ficam muito por muito tempo.Por exemplo, se a sua tarefa é escrever um programa que calcula dígitos do $\pi$ ou algum semelhante tarefa.Se você escreveu um programa Python para esta tarefa e não mencionou as peculiaridades de complexidade, quando solicitado, o entrevistador deve tomar cuidado.

Se eu fosse um entrevistador, eu teria o cuidado se você souber o mundo real, limitações de que você está fazendo e sabe o que preocupações teóricas importa quando e que você levá-los até se e apenas se for necessário.

Quando você deveria se preocupar?

Até agora, eu tenho sido um pouco vago sobre "grandes" e "pequenos", e não números.No comumente usado RAM modelo, que você está autorizado a assumir que operações com números inteiros pode ser feito em $S(1)$ em números que têm, no máximo, $O( log n)$ bits (onde $n$ é o comprimento de entrada).A justificativa para esta hipótese é que se nós temos uma entrada de comprimento $n$, os indicadores/índices na nossa linguagem de programação deve ser longa o suficiente para ser capaz de abordar todo o espaço de entrada.Assim, na RAM o modelo, se a entrada é um número binário de $n$ (binário) dígitos, a complexidade de verificar a igualdade é $O(\frac{n}{\log n})$ uma vez que podemos verificar a igualdade de um grupo de $O( log n)$ bits em um único $S(1)$ operação.

Answer 5

Embora isso possa parecer trivial ponto, sua primeira frase está incorreta. As funções não são equivalentes.Para torná-los equivalentes, a função C deve usar GMP (ou similar) para implementar arbitary-aritmética de precisão.Agora, a razão pela qual esta observação não é trivial, é que a medida em que é razoável dizer que os dois são equivalentes, é, precisamente, a medida em que é razoável dizer que o código Python é a constante de tempo!Isto é, se vamos ignorar que Python números inteiros são bignums, que podem (e devem) consistentemente tratá-los como tamanho fixo.

Analogamente, considere a função C int is_equal(char a, char b) { return a == b; } e a função de Python def is_equal(a: str, b: str) -> bool: return a == b.É mais evidente agora que as funções não são equivalentes, mas a razão para isso é exatamente a mesma que a razão de vocês não são.Nós apenas esperar para ver enormes cadeias de caracteres em Python o tempo todo, mas realmente não espera enorme ints, mesmo que, naturalmente, sabemos que eles são possíveis.Assim, na maioria das vezes ignoramos o fato de que Python números inteiros são grandes, e analisamos como se eles são de tamanho fixo.Nos casos raros em que nós nos preocupamos com os intervalos de grande nī umero de operações, você pode usar o "real" complexidades.E, claro, também usar PBF no seu código C.

Tudo isso é para dizer:apesar de você não perceber isso, você já sabe a resposta para a sua reapresentação versão da sua pergunta, e a resposta é, "a mesma justificação pelo que você descreveu essas funções como equivalentes".Python é incomum em não ter um tamanho fixo de tipo inteiro (bem, não que as pessoas comumente usam:é possível escrever um claro, e há um em numpy).Mas como uma questão de pragmatismo, não queremos isso para nos impedir de fazer o "costume" de complexidade de análise de algoritmos que crunch números inteiros, e recebendo o "costume" das respostas.Raramente é necessário fornecer a ressalva de que, se passar um par de 10GB números inteiros que são quase iguais, pode demorar um pouco para compará-los.

Em alguns casos, você pode formalizar isso (se você realmente precisa) dizendo que você está restringindo sua análise para pequenos números inteiros.Em seguida, você pode considerar a complexidade de alguns algoritmo em termos do tamanho de uma matriz de números inteiros, o tratamento de todas as operações aritméticas como O(1).Se você está considerando algoritmos que realmente são lineares ou pior na magnitude do número inteiro, então você pode integrá-la dizendo que você está indo para ignorar o log-factor, pois tudo o que importa realmente é se a complexidade é mais próximo do linear ou quadrática, porque O(n log n) é tão bom linear para os seus propósitos.Quase todo o tempo, porém, você não precisa formalizar a complexidade de algoritmos em Python.Se você já atingiu o ponto de especificação de uma linguagem de programação, você não está realmente fazendo o resumo de ciência da computação mais ;-)

No contexto da realização de uma entrevista, você deve aviso ou cuidado se um candidato chama isso de $S(1)$?

Depende entrevista para o que, eu suponho, mas como um software profissional, trabalhando principalmente em Python para os últimos 10 anos, eu não iria pedir que em uma entrevista.Se faço uma pergunta que tinha a complexidade de inteiro comparação escondido dentro dele (como, sei lá, "o que é a complexidade deste algoritmo de ordenação?"), então eu aceitar uma resposta que ignoraram a questão.Eu também aceitar que é abordada.Eu acho que vale a pena compreensão e complexidade de computação, como parte das práticas de programação, eu só não considerá-lo importante que para a programação para ser muito cuidadoso sobre formalmente, informando que você está falando de razoável porte números inteiros.

Eu também nunca faça uma pergunta na qual eu quero que o candidato, para oferecer a informação que o Python números inteiros são arbitrários precisão, quando ele obviamente não é relevante para a questão, por algum motivo para fazer com os dados envolvidos.Se a pergunta implica que os números envolvidos pode ir mais alto do que 2⁶⁴ em seguida, em uma entrevista C eu gostaria que o candidato perceber que este é um problema que precisa para lidar com, e em Python entrevista, eu gostaria que o candidato saiba que ele não é, mas eu não esperaria sair de seu caminho para o estado.Não há tempo, em uma entrevista ao estado, cada pequeno fato que faz com que algo seja um não-problema.

Se eu quisesse verificar a compreensão da complexidade em uma entrevista, então provavelmente gostaria de começar por pedir para algum código para algum problema, onde há realmente um simples "ingênuo" solução com baixa complexidade, e pelo menos uma menos uma solução direta com decente complexidade utilizando-se as técnicas conhecidas.Se o candidato dispõe o ingênuo solução, então você pode pedir que a complexidade é e como eles gostariam de modificar o código para melhorá-lo.Se o candidato oferece uma solução melhor, em seguida, você pode descrever o ingênuo solução, como algumas linhas de código isso é, e pergunte o que há de errado com ele (talvez por perguntar, "se você fosse analisar de alguém código e deram-lhe esta, o que você diria sobre isso"?).Para a maioria dos fins práticos, tudo o que você se preocupa é se eles podem dizer a diferença entre o linear, quadrática, e o pior-que-quadrática.O(n log n) também aparece, mas principalmente por causa da classificação ou estruturas de dados onde você está falando sobre a complexidade em termos do número de comparações.O custo de cada comparação é geralmente considerada irrelevante, porque o algoritmo de designer normalmente não tem nenhum controle sobre ele (é fornecida pelo usuário do algoritmo ou estrutura de dados).

Na surpreendentemente evento improvável de que eu era o entrevistador para uma posição como um CS acadêmica, abrangendo arbitrário-aritmética de precisão, então, certamente, eu gostaria de candidatos para saber as complexidades de algoritmos diferentes para várias operações, e, de fato, conhecer o estado da arte para o não-trivial queridos.

Answer 6

Isso está correto?Eu ainda não vi ninguém reclamar que o Python compara ints na hora de log.Python, de facto, têm uma precisão arbitrária formato de número inteiro.No entanto, temos de fazer uma comparação justa aqui.Se considerarmos o subconjunto dos números inteiros sobre o limite de $[0,2^{64}]$, vemos que o Python é a operação de tempo constante.

O que você está vendo é um dos limites para medição de complexidade computacional usando o big-oh notação.Ele descreve o que acontece à medida que n se aproxima do infinito, mas não, necessariamente, fazer um bom trabalho de comparar o comportamento para números menores.Vemos isso na famosa algoritmos de multiplicação de matrizes.Existem alguns algoritmos que são mais eficientes em um big-oh sentido, mas, na verdade, são mais lentos na prática, até chegar à gigantesca de matrizes.

No contexto da realização de uma entrevista, caso você perceba ou não se preocupam se um candidato chama isso de O(1)?

Depende do que você está contratando-os para.Para a grande maioria dos postos de trabalho, chamando-o de O(1) deve ser fino.Na verdade, é como nós tendemos a ensinar na escola.Se você queria transformá-lo em uma boa oportunidade para aprender mais sobre o seu candidato, você poderia perguntar-lhes por que eles acham disso é a constante de tempo (para o qual a resposta é que o modelo utilizado para determinar o big-oh assumiu que...o que é uma resposta válida)

Se você for contratar alguém para olhar para as coisas como exploits em seu código, você pode querer empurrar mais.Um grande nī umero produzida pelo seu próprio código é uma coisa, mas é o usuário permitido a entrada o número de sua própria escolha?Se assim for, eles podem ser capazes de criar ataques de temporização e DOSs usando o fato de que essa adição pode ser terrivelmente lento.Detectar este risco pode ser parte do seu trabalho.

Caso você perceba ou se preocupam com esta distinção no mundo real?

Praticamente falando:não.Não até que você dispostos correr para ele, e corrigir o problema na depuração.Python faz um monte de coisas que são "geralmente seguro," e são muito eficientes.É por isso que ele assumiu como uma das linguagens mais populares do mundo.

Para uma situação equivalente:o quão rápido é o x.y em Python?Nós pensamos nele como O(1), mas na verdade há uma pesquisa de hash de lá.Que pesquisa de hash utiliza um conhecido mecanismo de sondagem, e a resultante de pesquisa, na verdade, é O(n).Você nunca vai ver isso no código normal.Mas no código onde um adversário que chega a encher o seu dicionário com seu próprio conteúdo, eles podem, intencionalmente, artesanato em chaves, que colidem neste caminho.

Answer 7

Eu nunca encontrei um texto que tratava de "regular" operações com números inteiros como nada além de tempo constante, com o pressuposto implícito de que o tamanho tinha alguns razoável finito limite superior (por exemplo 64 bits).Talvez seria mais preciso afirmar a suposição, mas para um CS público, eu acho que está implícito.

Fazer isso seria introduzir um monte de complexidade nas discussões essencialmente de tópicos não relacionados.Bigint implementações normalmente não são implementadas, pouco a pouco, mas, na base(máquina de tamanho de palavra), de modo que S(b) > S(1) problema apenas nos chutes para fabulosamente grande número.

Pessoalmente, ao entrevistar alguém, eu poderia apreciar o rigor e amplitude de conhecimento associados a conhecer Python inteiros foram comprimento arbitrário, mas nada além informando o pressuposto de que toda a matemática é O(1), iria sentir-se extremamente pedante.Se a análise começou a ficar muito off-topic, com aritmética, e desperdício de tempo, eu consideraria isso um mau candidato.