Trova k max interi di un array - Min Heap contro selezione Algo vs Selezione Ordina

3

Ho una matrice con un gran numero di elementi, e ho bisogno di trovare gli k elementi più grandi.

Per un'idea di scala, supponiamo un array intero di lunghezza 10.000.000, e k è 1.000.

Vedo tre potenziali soluzioni:

  1. Questa risposta a questa domanda su Stack Overflow suggerisce l'algoritmo di selezione per trovare il k più grande intero, quindi eseguire un partizione per trovare tutti gli elementi più grandi di quel valore.

  2. Potrebbe anche essere utilizzato un heap min con una dimensione massima di 1000. Se l'heap è pieno quando tenti di inserirlo, rimuovi il min e aggiungi il tuo nuovo elemento. Fare questo per un elemento sarebbe O medio di 1 per l'inserto e O di log (n) per la rimozione (se necessario). Quindi immagino che il caso peggiore sarebbe qualcosa come O (n log k). Qual è il caso medio?

  3. Potrei usare un algoritmo sort sort per trovare il massimo k volte e metterlo a destra dell'array. Questa soluzione sembra avere il peggior caso di O (n * k).

Quale di queste soluzioni ti aspetteresti per ottenere il miglior rendimento sul mio set di dati?

    
posta user3795202 22.12.2016 - 22:53
fonte

1 risposta

4

Ci sono alcune domande da porsi quando si tratta di grandi quantità di dati (lascio "grandi" intenzionalmente vaghe).

  • Tutti i dati possono essere caricati contemporaneamente nella memoria?

  • La quantità di dati è nota in anticipo? Oppure potrebbe entrare di più mentre l'algoritmo è in fase di elaborazione?

  • È possibile ordinare i dati prima di analizzarli?

La maggior parte degli esercizi a livello universitario tendono a gestire piccole quantità di dati, quindi queste domande non contano. Tuttavia, considera Google: hanno enormi quantità di dati e il caricamento dell'intero indice di ricerca in memoria e l'ordinamento non è affatto vicino possibile.

Anche quando la quantità di dati potrebbe entrare in memoria, a volte le soluzioni migliori sono quelle che funzionano nel caso più ampio. Ad esempio, potrebbe non essere necessario ordinare questo array per trovare gli elementi più grandi. Da una prospettiva teorica, la notazione Big-O è grande: tuttavia, nel mondo reale, a volte il fatto che O (n + n log n) si semplifichi a O (n log n) non è una grande rassicurazione. Potrebbe tradursi in minuti o ore di tempo di esecuzione extra.

Analisi Big-O:

  1. Mentre il link che hai postato afferma che è O (n), così come Wikipedia , non sono d'accordo . Big-O riguarda la complessità di worst-case , che in realtà è O (n 2 ). Mentre il caso medio è n (non c'è una lettera per quello), il caso peggiore è un enorme killer del tempo.

  2. L'array viene ripetuto una volta, che è O (n). La modifica dell'heap binario è O (log 2 k), ma viene eseguita (caso peggiore) n volte. Questo rende il tutto O (n + n log 2 k) = O (n log 2 k). Tieni inoltre presente che k è piccolo rispetto a n e che log 2 k è ancora più piccolo.

  3. L'ordinamento della selezione parziale in questa istanza è O (kn).

La prima opzione potrebbe in teoria comportarsi bene la maggior parte del tempo, con alcuni set di dati che funzionano male.

La seconda opzione funzionerà molto bene tutto il tempo. Nel peggiore dei casi, è molto meglio del primo algoritmo. Tuttavia, il primo algoritmo potrebbe sovraperformare questo tempo.

La terza opzione è praticamente costante per un dato n : il contenuto dell'array non ha importanza, solo la sua dimensione.

Vorrei puntare a me stesso verso l'heap binario, ma potrebbe valere la pena analizzare se i dati darebbero l'algoritmo Quickselect un momento difficile e forse implementarli entrambi e misurare la loro velocità reale.

    
risposta data 23.12.2016 - 01:08
fonte

Leggi altre domande sui tag