Come trovare i primi valori diversi da un array?

Question

Ho una serie di valori float e desidero il valore e, soprattutto, la posizione dei massimi quattro valori.

Ho originariamente creato il sistema per percorrere l'array e trovare il massimo nel solito modo, confrontando il valore nella posizione corrente con un massimo finora registrato e aggiornando una variabile di posizione quando il massimo finora i cambiamenti. Funzionava bene, un O (n) algo che era molto semplice. In seguito ho appreso che devo mantenere non solo il valore massimo, ma i primi tre o quattro. Ho esteso la stessa procedura e complicato il max-so-finora in un array di quattro max-so-fars e ora il codice è brutto.

Funziona ancora ed è ancora sufficientemente veloce perché alla procedura è stata aggiunta solo una quantità banale di calcoli. attraversa ancora efficacemente l'array e controlla ogni valore una volta.

Faccio questo in MATLAB con una funzione di ordinamento che restituisce due array, l'elenco ordinato e l'elenco delle posizioni originale di accompagnamento. Osservando i primi valori ho esattamente ciò di cui ho bisogno. Sto replicando questa funzionalità in un programma C # .NET 2.0.

So che potrei fare qualcosa di simile con un oggetto List e che l'oggetto List ha una routine di ordinamento integrata, ma non credo che possa dirmi le posizioni originali, e quelle sono davvero ciò che sto cercando .

Sta funzionando bene, ma ora mi trovo a desiderare il quinto valore massimo e vedo che riscrivere il correttore max-finora-che è attualmente un brutto pasticcio se le dichiarazioni aggraverebbero solo la bruttezza. Funzionerebbe bene e non sarebbe più lento aggiungere un quinto livello, ma voglio chiedere alla comunità SO se esiste un modo migliore.

L'ordinamento dell'intero elenco richiede molti più calcoli rispetto al mio metodo attuale, ma non credo che sarebbe un problema, poiché l'elenco è "solo" uno o duemila float; quindi se esiste una sorta di routine che può restituire le posizioni originali, sarebbe l'ideale.

Come sfondo, questo array è il risultato di una trasformata di Fourier su un kilobyte di file wave, quindi le posizioni dei valori massimi corrispondono alle frequenze di picco dei dati del campione. Mi sono accontentato dei primi quattro, ma vedo la necessità di raccogliere davvero i primi cinque o sei per una classificazione del campione più accurata.

Answer 1

Posso suggerire un algoritmo alternativo che dovrai codificare :)

Usa un mucchio di dimensioni K in cui K indica il conteggio degli elementi principali che desideri salvare. Inizializza questo sui primi K elementi dell'array originale. Per tutti gli elementi N - K, cammina l'array, inserendolo come e quando richiesto.

proc top_k (array<n>, heap<k>)
heap <- array<1..k-1>
for each (array<k..n-1>) 
  if array[i] > heap.min
     heap.erase(heap.min)
     heap.insert(array[i])
  end if
end for

Answer 2

Potresti comunque usare la tua idea di lista - gli elementi che inserisci nella lista potrebbero essere una struttura che memorizza sia l'indice che il valore; ma ordina solo sul valore, ad esempio:

class IndexAndValue : IComparable<IndexAndValue>
{
    public int index;
    public double value;

    public int CompareTo(IndexAndValue other)
    {
        return value.CompareTo(other.value);
    }
}

Quindi puoi inserirli nell'elenco, mantenendo le informazioni sull'indice. Se mantieni solo le voci m più grandi nell'elenco, la tua efficienza dovrebbe essere O (mn).

Answer 3

Non so quale algoritmo stai attualmente utilizzando, ma te ne suggerirò uno semplice. Ammettendo di avere una serie di float f e un massimo di capacità numeri, potresti fare quanto segue:

int capacity = 4; // number of floats you want to retrieve
float [] f; // your float list
float [] max_so_far = new float[capacity]; // max so far

// say that the first 'capacity' elements are the biggest, for now
for (int i = 0; i < capacity; i++)
  max_so_far[i] = i;

// for each number not processed
for (int i = capacity; i < f.length; i++)
{
  // find out the smallest 'max so far' number
  int m = 0;
  for (int j = 0; j < capacity; j++)
    if (f[max_so_far[j]] < f[max_so_far[m]])
      m = j;

  // if our current number is bigger than the smallest stored, replace it
  if (f[i] > f[max_so_far[m]])
    max_so_far[m] = i;
}

Alla fine dell'algoritmo, avrai gli indici dei più grandi elementi memorizzati in max_so_far .

Tieni presente che se il valore capacity aumenta, diventerà leggermente più lento di alternativa, che sta ordinando l'elenco tenendo traccia delle posizioni iniziali. Ricorda che l'ordinamento richiede confronti O (n log n), mentre questo algoritmo accetta O (n capacità).

Answer 4

Un'altra opzione è utilizzare la selezione rapida. Selezione rapida restituisce la posizione dell'elemento k-esima in un elenco. Dopo aver ottenuto la posizione e il valore dell'elemento k-esimo, vai sull'elenco e prendi ogni elemento il cui valore è più piccolo / più grande dell'elemento k-esimo.

Ho trovato l'implementazione ac # di selezione rapida qui: testo del link

Pro:

1. O (n + k) tempo di esecuzione medio.

Contro:

1. Gli elementi k trovati non sono ordinati. Se li ordini, il tempo di esecuzione è O (n + logk)
2. Non l'ho verificato, ma penso che per un k molto piccolo l'opzione migliore sia fare k gira sull'array, trovando ogni volta l'elemento successivo più piccolo / più grande.