Comment trouver les premières valeurs d'un tableau?

Question

J'ai un tableau de valeurs flottantes et je veux la valeur et surtout la position des quatre valeurs maximales.

J'ai initialement construit le système pour parcourir le tableau et trouver le max de la manière habituelle, en comparant la valeur de la position actuelle à un max-so-far enregistré, et en mettant à jour une variable de position lorsque le max-so-far changements. Cela a bien fonctionné, un O (n) algo très simple. J'ai appris par la suite que je devais garder non seulement la valeur la plus élevée, mais également les trois ou quatre valeurs les plus élevées. J'ai étendu la même procédure et compliqué le max-so-far dans un tableau de quatre max-so-fars et maintenant le code est moche.

Cela fonctionne toujours et est suffisamment rapide, car seul un petit nombre de calculs a été ajouté à la procédure. il parcourt toujours efficacement le tableau et vérifie chaque valeur une fois.

Je le fais dans MATLAB avec une fonction de tri qui renvoie deux tableaux, la liste triée et la liste de positions d'origine qui les accompagne. En regardant les premières valeurs, j'ai exactement ce dont j'ai besoin. Je réplique cette fonctionnalité dans un programme C # .NET 2.0.

Je sais que je pourrais faire quelque chose de similaire avec un objet List et que cet objet a une routine de tri intégrée, mais je ne crois pas qu'il puisse me dire les positions d'origine et ce sont vraiment ce que je suis après. .

Cela a bien fonctionné, mais maintenant je me trouve à vouloir la cinquième valeur maximale et je vois que réécrire le vérificateur max-so-far qui est actuellement un foutoir si les déclarations ne feraient qu'aggraver la laideur. Cela fonctionnerait bien et ne serait pas plus lent d'ajouter un cinquième niveau, mais je voudrais demander à la communauté SO si il y a un meilleur moyen.

Le tri de la liste complète nécessite beaucoup plus de calculs que ma méthode actuelle, mais je ne pense pas que ce serait un problème, car la liste contient "seulement" un ou deux mille flottants; Donc, s’il existe une routine de tri capable de restituer les positions initiales, ce serait l’idéal.

En tant qu'arrière-plan, ce tableau est le résultat d'une transformation de Fourier sur un kilo-octet de fichier wave. Les positions des valeurs maximales correspondent donc aux fréquences de crête des données de l'échantillon. Je me suis contenté des quatre premiers, mais je constate qu’il est nécessaire de rassembler les cinq ou six premiers pour une classification plus précise des échantillons.

Answer 1

Je peux suggérer un algorithme alternatif que vous devrez coder:)

Utilisez un segment de taille K où K indique le nombre d'éléments supérieurs que vous souhaitez enregistrer. Initialisez cela aux K premiers éléments de votre tableau d'origine. Pour tous les éléments N - K, parcourez le tableau en insérant le cas échéant.

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

Vous pouvez toujours utiliser votre idée de liste - les éléments que vous avez mis dans la liste pourraient être une structure qui stocke à la fois l'index et la valeur; mais ne trie que sur la valeur, par exemple:

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

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

Ensuite, vous pouvez les coller dans la liste, tout en conservant les informations sur l'index. Si vous ne conservez que les m éléments les plus importants de la liste, votre efficacité devrait être de O (mn).

Answer 3

Je ne sais pas quel algorithme vous utilisez actuellement, mais je vais en proposer un simple. Admettre que vous avez un tableau de flottants f et un maximum de capacité chiffres, vous pouvez faire ce qui suit:

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;
}

À la fin de l'algorithme, vous aurez les indices des plus grands éléments stockés dans max_so_far .

Notez que si la valeur capacity augmente, elle sera légèrement plus lente que le alternative, qui consiste à trier la liste tout en gardant une trace des positions initiales. N'oubliez pas que le tri prend des comparaisons O (n log n), tandis que cet algorithme prend une capacité O (n ).

Answer 4

Une autre option consiste à utiliser la sélection rapide. La sélection rapide renvoie la position du k-ème élément dans une liste. Une fois que vous avez la position et la valeur du k-ème élément, parcourez la liste et prenez chaque élément dont la valeur est plus petite / plus grande que le k-ième élément.

J'ai trouvé une implémentation de la sélection rapide ici: texte du lien

Avantages:

1. O (n + k) durée moyenne.

Inconvénients:

1. Les k éléments trouvés ne sont pas triés. Si vous les triez, la durée d'exécution est O (n + logk)
2. Je n’ai pas vérifié cela, mais je pense que pour un très petit k, la meilleure option est de faire k exécute sur le tableau, en cherchant chaque fois le prochain élément le plus petit / le plus grand.