Controllo dell'uguaglianza dei numeri interi: o (1) in c ma o (log n) in Python 3?

https://cs.stackexchange.com/questions/127939

29-09-2020
|

Domanda

Considerare queste funzioni equivalenti in C e Python 3. La maggior parte dei dispositivi avrebbe immediatamente affermato che entrambi sono $ o (1) $ .

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

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

Ma considera cosa sta succedendo sotto la superficie. I numeri interi sono solo stringhe binarie e, per determinare l'uguaglianza, entrambe le lingue confronluranno le stringhe bit-by-bit. In entrambi i casi questa scansione è $ o (b) $ dove $ B $ è il numero di bit. Dal momento che i numeri interi hanno una dimensione costante in bit in C, questa è semplicemente $ o (1) $ .

modifica: c non confronta Bit-by-bit Vedi questa risposta

In Python 3 Tuttavia, i numeri interi non hanno dimensioni fisse e la scansione rimane $ o (b) $ per il numero di bit nell'ingresso o nell'input o $ o (\ log a) $ dove $ a $ è il valore del INPUT IN BASE 10.

Quindi se stai analizzando il codice in Python, ogni volta che confronti due numeri interi, stai intraprendendo un viaggio sorprendentemente complesso di $ o (\ log n) $ rispetto al valore di base 10 del numero.

Per me questo solleva diverse domande:

.
è corretto? Non ho visto nessun altro reclamare che Python confronta gli intersti nel tempo di registro.

Nel contesto di condurre un colloquio, se si nota o attento se un candidato chiama questa classe $ o (1) $ ?

Dovresti notare o curare questa distinzione nel mondo reale?

modifica: è facilmente verificato (e intuitivo) che Python non può confrontare gli intercetti arbitrariamente grandi in costante tempo. Quindi un modo migliore per porre la domanda 1 potrebbe essere "cosa (se presente) è la giustificazione per chiamare questa operazione $ o (1) $ ? Perché è pragmatico? Convenzionale ? Implicito dal modello RAM?

Soluzione 7

TL; DR: c'è una convenzione CS di descrivere questo tipo di funzionamento come $ o (1) $ che accade per abbattere in casi estremi per Python. Questi casi sono estremamente rari, in modo da rompere con la convenzione di $ o (1) $ ha un'utilità negativa. Questo tipo di pragmatismo è normale in Big $ o $ .

Ci sono molte risposte molto buone a questa domanda e ti incoraggio a leggerli. Ma non penso che nessuno di loro risponda pienamente alle mie domande. Quindi ecco una sintesi.

.
è corretto? Non ho visto nessun altro affermare che Python confronta gli interni nel tempo di registro.

Questo è sorprendentemente sfumato. È True che Python confronta gli interni molto grandi in $ o (\ log n) $ runtime. Ma è corretto per descrivere questa operazione come $ o (\ log n) $ ?

Alla fine sono più persuaso da questo prendi da @tomvanderzanden:

.
Se hai detto che la versione C o Python era $ o (1) $ qualsiasi intervistatore dovrebbe essere perfettamente felice. Se lo hai detto (la versione Python) era $ o (\ log n) $ probabilmente sarebbero ancora felici, ma pensa che tu sia una persona piuttosto pedante che non fa t Seguire le convenzioni normali.

e

.
Se fossi un intervistatore, mi interesserebbe se conosci le limitazioni del mondo reale di ciò che stai facendo e sappia quali preoccupazioni teoriche riguardano quando e che li porti se e solo se appropriato.

Tuttavia non sto accettandolo come risposta perché penso che il primo paragrafo sia attualmente fuorviante (felice di cambiare).

In definitiva questo argomento è pragmatico. Dalla rigida definizione di Big $ o $ Python Int Confronto è ancora verificabilmente $ o (\ log n) $ . Ma non è utile trattarlo in questo modo, quindi non dovresti. Avrei aggiungere che per essere rigoroso su Big $ o $ è perdere il punto di grande $ o $ Analisi.

Altri suggerimenti

.
I numeri interi sono solo stringhe binarie e, per determinare l'uguaglianza, entrambe le lingue confronluranno le stringhe bit-by-bit.

Non proprio. C ints sono di dimensioni della macchina e confrontate con un'istruzione a macchina singola; Python ints sono rappresentati in base $ 2 ^ {30} $ (vedi ad esempio https://rushter.com/blog/python-integer-implementation / ) e confrontato la cifra di cifre in quella base. Quindi la base rilevante del logaritmo è $ 2 ^ {30} $ .

Se almeno un di numeri può essere limitato da $ 2 ^ {30d} $ per qualsiasi fisso $ d $ , il confronto è $ o (1) $ (perché il numero di cifre viene confrontato per primo ), e se non possono, altre operazioni sono probabilmente di molte più preoccupazioni del confronto della parità. Quindi, in pratica direi che è molto improbabile che sia importante e se lo saprete sarai (e userete non usare non ints ma qualcosa come il GNU Biblioteca aritmetica di precisione multipla in c pure).

La complessità è definita relativa a un modello di calcolo.P e NP, ad esempio, sono definiti in termini di macchine Turing.

Per il confronto, considera il modello di RAM di parole.In questo modello, la memoria è divisa in parole, è possibile accedere alle parole in tempo costante e la dimensione del problema può essere rappresentata utilizzando $ o (1) $ parole.

Quindi, ad esempio, durante l'analisi di un'operazione di ordinamento basata sul confronto, assumiamo che il numero di elementi $ N $ può essere memorizzato in $ o (1) $ parole, quindi richiede tempo costante per leggere o scrivere un numero tra $ 1 $ e $ N $ .

.
è corretto? Non ho visto nessun altro affermare che Python confronta gli interni nel tempo di registro.

No (e un po 'sì). Considerare il seguente rivendicazione del pensiero (ma non veramente vero): un computer può avere solo una quantità finita di memoria (limitata dal numero di atomi nell'universo), quindi la versione Python è anche $ O (1) $ .

Il problema è che stiamo cercando di fare una dichiarazione su Asintotica (pertinente a ciò che accade all'infinito) su una macchina da stato finita (un computer). Quando stiamo analizzando la complessità del codice, non analizziamo effettivamente il codice in quanto eseguirebbe su un computer, stiamo analizzando un modello idealizzato del codice.

Supponiamo di avermi chiesto di analizzare un algoritmo di ordinamento scritto in C. Potresti indicare che utilizza gli interni per indicizzare l'array, quindi potrebbe solo ordinare una serie di dimensioni fino a $ 2 ^ {31} -1 $ . Eppure, quando analizziamo un tale pezzo di codice, fingiamo che potessimo gestire array arbitrariamente grandi. Chiaramente, non stiamo dicendo che il confronto intero è $ o (1) $ perché può solo gestire i numeri a 32 bit. .

Nel contesto di condurre un colloquio, dovresti notare o curare se un candidato chiama questo o (1)?

di solito, no. Supponiamo che sto conducendo un'intervista e ti chiedo di scrivere un programma di computer C o Python che conta il numero di dipendenti femminili che appaiono nel database dei dipendenti.

sarebbe incredibilmente pedante se mi sono lamentato del tuo programma C non è stato corretto perché potrebbe solo contare fino a $ 2 ^ {31} -1 $ .

Generalmente assumiamo che i numeri siano abbastanza piccoli che possono adattarsi all'interno di una parola / numero intero. Assumiamo aggiunta (o qualsiasi altra operazione numerica) può essere eseguita in $ o (1) $ , perché sarebbe molto fastidioso dover scrivere $ o (\ log n) $ ovunque e renderebbe tutto illeggibile anche se $ \ log n $ è così piccolo Non importa comunque.

Se hai detto che la versione C o Python era $ o (1) $ qualsiasi intervistatore dovrebbe essere perfettamente felice. Se lo hai detto (la versione Python) era $ o (\ log n) $ probabilmente sarebbero ancora felici, ma pensa che tu sia una persona piuttosto pedante che non fa t Seguire le convenzioni normali.

.
Dovresti notare o curare questa distinzione nel mondo reale?

Sì! Inizia alla materia quando i numeri diventano così grandi l'ipotesi che sono piccoli è violato. Diciamo che stai intervistando per Google e ti hanno chiesto di calcolare il numero di query di ricerca effettuate dagli utenti femminili nell'ultimo anno. L'intervistatore sarebbe stato giustificato di lamentarti se hai scritto un programma C usando gli ints.

È possibile passare all'utilizzo di lunghi ed essere ancora giustificato nel chiamarlo $ o (1) $ , e allo stesso modo, chiamando la versione Python $ o (1) $ è anche giustificato. La $ O (1) $ V.S. $ o (\ log n) $ La cosa inizia solo alla materia quando i numeri vengono molto lunghi. Ad esempio, se il tuo compito è scrivere un programma che calcola le cifre di $ \ PI $ o qualche compito simile. Se hai scritto un programma Python per questo compito e non hai menzionato le peculiarità della complessità quando viene chiesto, l'intervistatore si sarebbe curato.

Se fossi un intervistatore, mi interesserebbe se conosci le limitazioni del mondo reale di ciò che stai facendo e sappia quali preoccupazioni teoriche riguardano quando e che li porti se e solo se appropriato.

Quando dovresti preoccuparti?

Finora, sono stato un po 'vago sui numeri "grandi" e "piccoli". Nel modello RAM comunemente utilizzato, ti è permesso presumere che le operazioni interetiche possano essere eseguite in $ o (1) $ sui numeri che hanno al massimo $ O (\ log n) $ bit (dove $ N $ è la lunghezza dell'ingresso). La giustificazione per questa ipotesi è che se abbiamo un ingresso di lunghezza $ N $ , i puntatori / indici nel nostro linguaggio di programmazione dovrebbero essere abbastanza a lungo da poter affrontare il intero spazio di input. Quindi, nel modello RAM, se l'input è il numero binario di $ N $ cifre (binarie), la complessità del controllo dell'uguaglianza è $ O (\ frac {n} {\ log n}) $ Poiché possiamo verificare l'uguaglianza di un gruppo di $ o (\ log n) $ < / span> bit in una $ o (1) $ funzionamento.

Sebbene questo possa sembrare un punto banale, la tua prima frase non è corretta. Le funzioni non sono equivalenti . Per renderli equivalenti, la funzione C dovrebbe utilizzare GMP (o simile) per implementare l'aritmetica arbitale-precisione. Ora, la ragione per cui questa osservazione non è banale, è che la misura in cui è ragionevole dire che i due sono equivalenti, è proprio la misura in cui è ragionevole dire che il codice Python è costante! Cioè, se ignoreremo che i numeri interi di Python sono Bignums, possiamo (e dovremmo) trattandosi costantemente come dimensioni fisse.

Analogamente, considera la funzione C int is_equal(char a, char b) { return a == b; } e la funzione Python def is_equal(a: str, b: str) -> bool: return a == b. È più ovvio ora che le funzioni non sono equivalenti, ma la ragione per cui è esattamente la stessa della ragione per cui il tuo non è. Ci aspettiamo solo di vedere le forme enormi in Python tutto il tempo, ma non aspettarci davvero strumenti enormi anche se ovviamente sappiamo che sono possibili. Quindi, la maggior parte delle volte ignoriamo il fatto che i numeri interi di Python sono grandi, e analizziamo come se fossero dimensioni fisse. Nei rari casi in cui ci preoccupiamo dei tempi delle operazioni Bignm, puoi usare le complessità "reali". E, naturalmente, usa anche GMP nel tuo codice C.

Tutto questo è da dire: Anche se non l'hai capito, conosci già la risposta alla tua versione riformulata alla tua domanda alla fine, e la risposta è, "la stessa giustificazione con cui hai descritto quelle funzioni come equivalenti ". Python è insolito nel non avere un tipo di numero intero a misura fissa (beh, non uno che la gente usa comunemente: è possibile scrivere una naturalmente, e ce n'è uno in numpy). Ma come una questione di pragmatismo, non vogliamo che questo ti impedisca di fare la "solita" analisi della complessità degli algoritmi che crunch interi e ottenere le risposte "usuali". È raramente necessario fornire il cavernatore che se lo passiamo un paio di numeri interi da 10 GB che sono quasi uguali, potrebbe richiedere un po 'di tempo per confrontarli.

In alcuni casi potresti formalizzare questo (se hai davvero bisogno) dicendo che stai limitando la tua analisi a piccoli numeri interi. Quindi, potresti prendere in considerazione la complessità di alcuni algoritmi in termini di dimensioni di qualche gamma di numeri interi, trattando tutte le operazioni aritmetiche come O (1). Se stai considerando gli algoritmi che sono veramente lineari o peggio nella grandezza del numero intero, allora potresti formalizzarlo dicendo che ignorarai il fattore di registro, dal momento che tutti voi ti interessa è se la complessità è più vicina lineare o quadratico, perché o (n log n) è buono come lineare per i tuoi scopi. Quasi tutto il tempo, però, non è necessario formalizzare la complessità degli algoritmi in Python . Se hai raggiunto il punto di specificare un linguaggio di programmazione, non stai ancora facendo più Abstract Computer Science; -)

.
Nel contesto di condurre un colloquio, dovresti notare o curare Se un candidato chiama questa classe $ o (1) $ ?

Dipende dall'intervista per cosa, suppongo, ma come professionista del software, lavorando principalmente in Python per gli ultimi 10 anni, non lo chiederei in un'intervista. Se avessi fatto una domanda che aveva la complessità del confronto intero nascosto dentro di esso (come, non so, "qual è la complessità di questo tipo di algoritmo?"), Allora accetterei una risposta che ha ignorato l'intero problema. Avrei anche accettato uno che lo ha affrontato. Penso che valga la pena di comprendere e calcolare la complessità come parte della programmazione pratica, non lo considero così importante per la programmazione per essere molto attento a dichiarare formalmente che stai parlando di dimensioni ragionevoli interi.

Avrei mai portato mai una domanda in cui voglio che il candidato offrire le informazioni che i numeri interi di Python sono arbitrari-precisione, quando non è ovviamente rilevante per la domanda per qualche motivo per fare con i dati coinvolti. Se la domanda implica che i numeri coinvolti possano andare più in alto di 2 ^{64 allora in un colloquio C vorrei che il candidato si noti che questo è un problema di cui hanno bisogno per affrontare, e in un'intervista di Python Vorrei che il candidato sappia che non lo è, ma non mi aspetterei che loro finiscano di tutto per affermarlo. Non c'è tempo in un'intervista per dichiarare ogni piccolo fatto che fa qualcosa di non problema.}

Se volessi controllare la comprensione della complessità in un'intervista, quindi probabilmente probabilmente avrei iniziato a chiedere qualche codice per qualche problema in cui c'è una soluzione "ingenua" davvero semplice con scarsa complessità, e almeno una soluzione meno semplice Con una complessità decente utilizzando tecniche ben note. Se il candidato offre la soluzione ingenua, allora puoi chiedere qual è la complessità e come si modificano il codice per migliorarlo. Se il candidato offre una soluzione migliore, puoi descrivere la soluzione ingenua, indicare come poche righe di codice è, e chiedi cosa c'è che non va con esso (forse chiedendo: "Se stavi rivedendo qualcuno
Codice e ti hanno dato questo, cosa vorresti dire su di esso "?). Per scopi più pratici tutto ciò che ti interessa è se possono dire la differenza tra lineare, quadratico e peggiore-quadratico. o (n logn) appare anche, ma soprattutto a causa di smistamento o strutture di dati in cui stai parlando di complessità in termini di numero di confronti. Il costo di ogni confronto è solitamente considerato irrilevante, perché il progettista dell'algoritmo di solito non ha alcun controllo soprafornito dall'utente dell'algoritmo o della struttura dei dati).

nell'evento sorprendentemente improbabile che io sia stato l'intervistatore per una posizione come aritmetica arbitrarica arbitraria che copre la cs, quindi vorrei che vorrei candidati a conoscere le complessità di vari algoritmi per varie operazioni, e anzi per conoscere lo stato dil'arte per i non banale.

.
è corretto? Non ho visto nessun altro affermare che Python confronta gli interni nel tempo di registro. Python ha in effetti un formato intero arbitrario di precisione. Tuttavia, dobbiamo fare un confronto equo qui. Se consideriamo il sottoinsieme di numeri interi sul limite di $ [0,2 ^ {64}] $ , scopriamo che l'operazione Python è un tempo costante.
Quello che stai vedendo è uno dei limiti per misurare la complessità computazionale usando la notazione Big-oh. Descrive cosa succede quando n si avvicina all'infinito, ma non fa necessariamente un buon lavoro di confrontare il comportamento per numeri più piccoli. Vediamo questo notoriamente in Algoritmi di moltiplicazione della matrice . Ci sono alcuni algoritmi che sono più efficienti in un grande senso, ma sono in realtà più lenti in pratica finché non arrivi a matrici Gargantuan.

.
Nel contesto di condurre un colloquio, dovresti notare o curare se un candidato chiama questo o (1)?

dipende da ciò per cui stai assumendo. Per la stragrande maggioranza dei lavori, chiamandolo o (1) dovrebbe andare bene. In effetti, è come tendiamo ad insegnarlo a scuola. Se volessi trasformarlo in un'opportunità utile per conoscere il tuo candidato, potresti chiedere loro perché pensano che l'aggiunta sia un tempo costante (a cui la risposta è che il modello che usavano per determinare Big-oh presunto ... che è Una risposta valida)

Se stai assumendo qualcuno per cercare cose come gli exploit nel tuo codice, potresti voler spingere Vother. Un Bignum prodotto dal tuo codice è una cosa, ma l'utente è permesso inserire il numero di loro scelta? Se è così, potrebbero essere in grado di creare attacchi di temporizzazione e doss utilizzando il fatto che questa aggiunta può essere terribilmente lenta. Rilevamento di questo rischio potrebbe essere parte del loro lavoro.

.
Dovresti notare o curare questa distinzione nel mondo reale?

Praticamente parlando: no. Non finché non ci imbattiamo in modo acutabile e fissa il problema nel debug. Python fa un lotto di cose che sono "generalmente al sicuro" e sono molto efficienti. Questo è il motivo per cui ha rilevato una delle lingue più popolari del mondo.

Per una situazione equivalente: quanto è veloce x.y in Python? Lo pensiamo come o (1), ma in realtà c'è una ricerca di hash lì. Quella ricerca hash utilizza un meccanismo di sondaggio noto e la ricerca risultante è in realtà o (n). Non lo vedrai mai in codice normale. Ma nel codice in cui un avversario riempie il tuo dizionario con i propri contenuti, possono intenzionalmente craft chiavi che si scontrano in questo modo.

Non ho mai riscontrato un testo che ha trattato le operazioni intere "regolari" come qualsiasi cosa oltre a un tempo costante, con l'ipotesi implicita che le dimensioni avessero un po 'di tagliente finito ragionevole (ad esempio 64 bit).Forse sarebbe più accurato dichiarare l'ipotesi, ma a un pubblico CS, penso che sia implicito.

Fare ciò introdurrebbe molta complessità in discussioni su argomenti essenzialmente non correlati.Le implementazioni di Bigint in genere non sono implementate un po 'a bit, ma in base- (dimensioni della parola macchina), in modo che il problema o (b)> o (1) problema calci solo per numeri favolosamente grandi.

Personalmente mentre intervista qualcuno, potrei apprezzare il rigore e l'ampiezza della conoscenza associata a conoscere numeri interi di pitone erano lunghezze arbitrarie, ma qualsiasi cosa oltre ad affermare l'ipotesi che tutta la matematica è O (1) si sentirebbe estremamente pedante.Se l'analisi ha iniziato ad essere troppo lontano dall'argomento con aritmetico e il tempo sprecato, considererei un cattivo candidato.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a cs.stackexchange