Domanda Perché utilizzare un ciclo per iterare dall'inizio dell'array alla fine più veloce dell'iterazione dall'inizio alla fine e alla fine dell'avvio?


Dato un array avente .length  100 contenente elementi con valori 0 a 99 ai rispettivi indici, dove il requisito è trovare un elemento di matrice uguale a n : 51.

Perché utilizzare un ciclo per iterare dall'inizio dell'array alla fine più veloce dell'iterazione dall'inizio alla fine e alla fine dell'avvio?

const arr = Array.from({length: 100}, (_, i) => i);
const n = 51;
const len = arr.length;

console.time("iterate from start");
for (let i = 0; i < len; i++) {
  if (arr[i] === n) break;
}
console.timeEnd("iterate from start");

const arr = Array.from({length: 100}, (_, i) => i);
const n = 51;
const len = arr.length;

console.time("iterate from start and end");
for (let i = 0, k = len - 1; i < len && k >= 0; i++, k--) {
  if (arr[i] === n || arr[k] === n) break;
}
console.timeEnd("iterate from start and end");

jsperf https://jsperf.com/iterate-from-start-iterate-from-start-and-end/1


21
2017-11-01 05:52


origine


risposte:


La risposta è abbastanza ovvia:

Più operazioni richiedono più tempo.

Quando si giudica la velocità del codice, si osservano quante operazioni eseguirà. Basta attraversarli e contarli. Ogni istruzione richiederà uno o più cicli della CPU, e più ci sarà tanto più tempo ci vorrà per correre. Che le diverse istruzioni richiedano una quantità differente di cicli non ha importanza, mentre una ricerca di array potrebbe essere più costosa dell'aritmetica dei numeri interi, entrambi richiedono sostanzialmente un tempo costante e se ce ne sono troppi, domina il costo del nostro algoritmo.

Nel tuo esempio, ci sono alcuni diversi tipi di operazioni che potresti voler contare individualmente:

  • i confronti
  • incrementi / decrementi
  • ricerca di array
  • salti condizionali

(potremmo essere più granulari, come il conteggio delle operazioni di recupero e memorizzazione variabili, ma questi non hanno importanza - tutto è comunque in registri - e il loro numero è fondamentalmente lineare rispetto agli altri).

Ora entrambi i tuoi codici eseguono un'iterazione di circa 50 volte - l'elemento su cui interrompono il ciclo si trova nel mezzo dell'array. Ignorando alcuni errori, quelli sono i numeri:

               |  forwards  | forwards and backwards
---------------+------------+------------------------
>=/===/<       |       100  |                   200
++/--          |        50  |                   100
a[b]           |        50  |                   100
&&/||/if/for   |       100  |                   200

Detto questo, lo è non inaspettato fare il doppio delle opere richiede molto più tempo.

Risponderò anche ad alcune domande dei tuoi commenti:

È necessario ulteriore tempo per la seconda ricerca dell'oggetto?

Sì, ogni singola ricerca conta. Non è come potrebbero essere eseguiti contemporaneamente, o ottimizzati in una singola ricerca (immaginabile se avessero cercato lo stesso indice).

Dovrebbero esserci due circuiti separati per ogni inizio e fine per iniziare?

Non importa per il numero di operazioni, solo per il loro ordine.

Oppure, mettere ancora in modo diverso, qual è l'approccio più veloce per trovare un elemento in un array?

Non esiste un "più veloce" per quanto riguarda l'ordine, se non sai dove si trova l'elemento (e sono distribuiti uniformemente) devi provare ogni indice. Qualsiasi ordine, anche casuale, avrebbe funzionato allo stesso modo. Nota comunque che il tuo codice è strettamente peggiore, poiché guarda ogni indice due volte quando l'elemento non viene trovato - non si ferma nel mezzo.

Tuttavia, ci sono alcuni approcci diversi per micro-ottimizzare questo tipo di controllo questi parametri di riferimento.


39
2017-11-08 06:56



@Bergi è corretto. Più operazioni è più tempo. Perché? Più cicli di clock della CPU. Il tempo è davvero un riferimento a quanti cicli di clock ci vogliono per eseguire il codice. Per arrivare al nocciolo di ciò è necessario guardare il codice di livello della macchina (come il codice del livello di assemblaggio) per trovare la prova vera. Ogni ciclo di clock della CPU (core?) Può eseguire un'istruzione, quindi quante istruzioni stai eseguendo?

Non ho contato i cicli di clock da molto tempo da quando ho programmato le CPU Motorola per applicazioni embedded. Se il tuo codice impiega più tempo, in effetti genera un set di istruzioni più ampio di codice macchina, anche se il ciclo è più breve o esegue una quantità uguale di volte.

Non dimenticare mai che il tuo codice viene effettivamente compilato in una serie di comandi che la CPU sta per eseguire (puntatori di memoria, puntatori a livello di codice di istruzioni, interrupt, ecc.). È così che i computer funzionano e sono più facili da capire a livello di microcontrollore come un processore ARM o Motorola, ma lo stesso vale per le macchine sofisticate su cui stiamo lavorando oggi.

Il tuo codice semplicemente non funziona nel modo in cui lo scrivi (sembra folle, giusto?). Viene eseguito in quanto è compilato per essere eseguito come istruzioni a livello macchina (scrivere un compilatore non è divertente). L'espressione matematica e la logica possono essere compilate in un mucchio di assembly, codice di livello macchina e ciò dipende da come il compilatore sceglie di interpretarlo (è il bit shifting, ecc., Ricorda la matematica binaria chiunque?)

Riferimento: https://software.intel.com/en-us/articles/introduction-to-x64-assembly

La tua domanda è difficile da rispondere ma come @Bergi ha dichiarato che più operazioni sono più lunghe, ma perché? Più cicli di clock ci vogliono per eseguire il tuo codice. Dual core, quad core, threading, assembly (linguaggio macchina) è complesso. Ma nessun codice viene eseguito mentre lo hai scritto. C ++, C, Pascal, JavaScript, Java, a meno che non si stia scrivendo in assembly (anche se compila fino al codice macchina) ma è più vicino al codice di esecuzione effettivo.

Un master in CS e potrai contare su cicli di clock e tempi di ordinamento. Probabilmente farai la tua lingua incorniciata sui set di istruzioni della macchina.

La maggior parte della gente dice chi se ne importa? La memoria è a buon mercato oggi e le CPU stanno gridando velocemente e diventando più veloci.

Ma ci sono alcune applicazioni critiche in cui contano 10 ms, dove è necessario un interrupt immediato, ecc.

Il commercio, la NASA, una centrale nucleare, gli appaltatori della difesa, un po 'di robotica, avete capito l'idea. . .

Io voto lasciarlo guidare e continuare a muoversi.

Saluti, Wookie


2
2017-11-13 23:03



Poiché l'elemento che stai cercando è sempre approssimativamente nel mezzo dell'array, dovresti aspettarti che la versione che si avvicina sia dall'inizio che dalla fine dell'array richieda circa il doppio del tempo di una che inizia appena dall'inizio.

Ogni aggiornamento di variabile richiede tempo, ogni confronto richiede tempo e tu ne stai facendo il doppio. Poiché si sa che ci vorrà una o due iterazioni del ciclo per terminare in questa versione, si dovrebbe ragionare che costerà circa il doppio del tempo di CPU.

Questa strategia è ancora O(n) la complessità del tempo, dal momento che guarda una volta ogni elemento, è solo in modo peggiore quando l'oggetto è vicino al centro della lista. Se è vicino alla fine, questo approccio avrà un runtime previsto migliore. Prova ad esaminare l'elemento 90 in entrambi, ad esempio.


1
2017-11-13 02:14



La risposta selezionata è eccellente. Vorrei aggiungere un altro aspetto: Prova findIndex(), è 2-3 volte più veloce rispetto all'utilizzo di loop:

const arr = Array.from({length: 900}, (_, i) => i);
const n = 51;
const len = arr.length;

console.time("iterate from start");
for (let i = 0; i < len; i++) {
  if (arr[i] === n) break;
}
console.timeEnd("iterate from start");

console.time("iterate using findIndex");
var i = arr.findIndex(function(v) {
  return v === n;
});
console.timeEnd("iterate using findIndex");


1
2018-01-17 11:08



Le altre risposte coprono i motivi principali, ma penso che un'aggiunta interessante potrebbe essere menzionare la cache.

In generale, l'accesso sequenziale a un array sarà più efficiente, in particolare con array di grandi dimensioni. Quando la tua CPU legge un array dalla memoria, recupera anche le posizioni di memoria vicine nella cache. Ciò significa che quando si recupera l'elemento n, elemento n+1 è anche probabilmente caricato nella cache. Ora, la cache è relativamente grande in questi giorni, quindi il tuo array 100 int può probabilmente adattarsi comodamente nella cache. Tuttavia, su una matrice di dimensioni molto più grandi, la lettura sequenziale sarà più veloce del passaggio tra l'inizio e la fine dell'array.


0
2018-01-17 22:55