Récupération de la valeur maximale d'une plage dans un tableau non trié

9

J'ai un tableau non trié . J'ai des requêtes dans lesquelles je donne une plage, puis la valeur maximale de cette plage doit être retournée. Par exemple:

array[]={23,17,9,45,78,2,4,6,90,1};
query(both inclusive): 2 6
answer: 78

Quel algorithme ou structure de données dois-je construire pour récupérer rapidement la valeur maximale de n'importe quelle plage. (Il y a beaucoup de requêtes)

EDIT: Ceci est en effet une version simple du problème réel. Je peux avoir la taille du tableau jusqu'à 100 000 et le nombre de requêtes jusqu'à 100 000. J'ai donc certainement besoin d'un prétraitement qui facilitera une réponse rapide aux requêtes.

sudeepdino008
la source
5
Pourquoi n'est-il pas trié? Le problème est trivial s'il est trié, donc l'approche évidente est de le trier.
1
@delnan Sans mécanisme supplémentaire, vous perdez la trace des valeurs qui étaient à l'origine dans la plage à interroger ...
Thijs van Dien
Spécifiez tout votre problème. Si ces connaissances (ou toute autre information) sont importantes, il faut savoir les prendre en compte dans la solution.
1
Suis-je en train de manquer quelque chose, ou s'agit-il simplement de visiter les éléments 2 à 6 et de trouver la valeur maximale de ces éléments?
Blrfl
@Blrfl: Je ne pense pas qu'il vous manque quelque chose, sauf peut-être la partie concernant de nombreuses requêtes. Il n'est pas vraiment clair s'il est utile de construire une structure qui rend les requêtes beaucoup moins chères qu'une recherche séquentielle. (Bien qu'il ne servirait à rien de poser la question ici si ce n'était pas l'idée.)
Mike Sherrill 'Cat Recall'

Réponses:

14

Je pense que vous pourriez construire une sorte d'arbre binaire où chaque nœud représente la valeur maximale de ses enfants:

            78           
     45            78     
  23    45     78      6  
23 17  9 45   78 2    4 6   

Ensuite, il vous suffit de trouver un moyen de déterminer les nœuds que vous devez vérifier au minimum pour trouver la valeur maximale dans la plage interrogée. Dans cet exemple, pour obtenir la valeur maximale dans la plage d'index [2, 6](incluse) que vous auriez à la max(45, 78, 4)place de max(9, 45, 78, 2, 4). À mesure que l'arbre grandit, le gain augmente.

Thijs van Dien
la source
1
Pour que cela fonctionne, il manque des informations dans votre exemple d'arbre: chaque nœud interne doit avoir à la fois le maximum et le nombre total de nœuds enfants qu'il possède. Sinon, la recherche n'a aucun moyen de savoir que (par exemple) elle n'a pas à regarder tous les enfants de 78(et ignorer le 2), car pour autant qu'elle sache, l'index se 6trouve dans ce sous-arbre.
Izkata
Sinon, +1 car je trouve cela plutôt inventif
Izkata
+1: Il s'agit d'une technique puissante pour répondre aux questions sur les sous-plages d'une liste en temps log (N), utilisable quelle que soit la donnée au nœud racine peut être calculée en temps constant à partir des données des enfants.
kevin cline
Cette idée est géniale. Il donne le temps de requête O (logn). Je pense que @Izkata a également fait valoir un bon point. Nous pouvons augmenter le nœud d'arbre avec des informations sur les plages gauche et droite qu'il couvre. Donc, étant donné une plage, il sait diviser le problème en deux. Côté espace, toutes les données sont stockées au niveau de la feuille. Il faut donc 2 * N d'espace, ce qui est O (N) pour stocker. Je ne sais pas ce qu'est un arbre de segment, mais est-ce l'idée derrière l'arbre de segment?
Kay
Et en termes de prétraitement, il faut O (n) pour construire l'arbre.
Kay
2

Pour compléter la réponse de ngoaho91.

La meilleure façon de résoudre ce problème est d'utiliser la structure de données de l'arborescence des segments. Cela vous permet de répondre à de telles requêtes dans O (log (n)), ce qui signifierait que la complexité totale de votre algorithme serait O (Q logn) où Q est le nombre de requêtes. Si vous utilisiez l'algorithme naïf, la complexité totale serait O (Q n) qui est évidemment plus lente.

Il y a cependant un inconvénient à l'utilisation des arbres de segments. Cela prend beaucoup de mémoire, mais souvent vous vous souciez moins de la mémoire que de la vitesse.

Je décrirai brièvement les algorithmes utilisés par ce DS:

L'arbre de segment n'est qu'un cas particulier d'un arbre de recherche binaire, où chaque nœud contient la valeur de la plage à laquelle il est affecté. Le nœud racine se voit attribuer la plage [0, n]. L'enfant gauche se voit attribuer la plage [0, (0 + n) / 2] et l'enfant droit [(0 + n) / 2 + 1, n]. De cette façon, l'arbre sera construit.

Créer un arbre :

/*
    A[] -> array of original values
    tree[] -> Segment Tree Data Structure.
    node -> the node we are actually in: remember left child is 2*node, right child is 2*node+1
    a, b -> The limits of the actual array. This is used because we are dealing
                with a recursive function.
*/

int tree[SIZE];

void build_tree(vector<int> A, int node, int a, int b) {
    if (a == b) { // We get to a simple element
        tree[node] = A[a]; // This node stores the only value
    }
    else {
        int leftChild, rightChild, middle;
        leftChild = 2*node;
        rightChild = 2*node+1; // Or leftChild+1
        middle = (a+b) / 2;
        build_tree(A, leftChild, a, middle); // Recursively build the tree in the left child
        build_tree(A, rightChild, middle+1, b); // Recursively build the tree in the right child

        tree[node] = max(tree[leftChild], tree[rightChild]); // The Value of the actual node, 
                                                            //is the max of both of the children.
    }
}

Arbre de requête

int query(int node, int a, int b, int p, int q) {
    if (b < p || a > q) // The actual range is outside this range
        return -INF; // Return a negative big number. Can you figure out why?
    else if (p >= a && b >= q) // Query inside the range
        return tree[node];
    int l, r, m;
    l = 2*node;
    r = l+1;
    m = (a+b) / 2;
    return max(query(l, a, m, p, q), query(r, m+1, b, p, q)); // Return the max of querying both children.
}

Si vous avez besoin de plus d'explications, faites le moi savoir.

BTW, Segment Tree prend également en charge la mise à jour d'un seul élément ou d'une plage d'éléments dans O (log n)

Andrés
la source
quelle est la complexité de remplir l'arbre?
Pieter B
Vous devez parcourir tous les éléments, et il faut O(log(n))que chaque élément soit ajouté à l'arborescence. Par conséquent, la complexité totale estO(nlog(n))
Andrés
1

Le meilleur algorithme serait en temps O (n) comme ci-dessous, commençons, fin soit l'indice des limites de la plage

int findMax(int[] a, start, end) {
   max = Integer.MIN; // initialize to minimum Integer

   for(int i=start; i <= end; i++) 
      if ( a[i] > max )
         max = a[i];

   return max; 
}
Tarun
la source
4
-1 pour avoir simplement répété l'algorithme que l'OP tentait d'améliorer.
kevin cline
1
+1 pour avoir publié une solution au problème mentionné. C'est vraiment la seule façon de le faire si vous avez un tableau et que vous ne savez pas quelles seront les limites a priori . (Bien que j'initialiser maxpour a[i]et démarrer la forboucle à i+1.)
Blrfl
@kevincline Ce n'est pas seulement une reformulation - c'est aussi dire "Oui, vous avez déjà le meilleur algorithme pour cette tâche", avec une amélioration mineure (passer à start, s'arrêter à end). Et je suis d'accord, c'est le meilleur pour une recherche unique. La réponse de @ ThijsvanDien n'est meilleure que si la recherche doit se produire plusieurs fois, car elle prend plus de temps à configurer initialement.
Izkata
Certes, au moment de publier cette réponse, la question ne comprenait pas la modification confirmant qu'il ferait de nombreuses requêtes sur les mêmes données.
Izkata
1

Les solutions d'arbre binaire / segment d'arbre pointent en effet dans la bonne direction. On pourrait cependant objecter qu'ils nécessitent beaucoup de mémoire supplémentaire. Il existe deux solutions à ces problèmes:

  1. Utiliser une structure de données implicite au lieu d'un arbre binaire
  2. Utilisez un arbre M-aire au lieu d'un arbre binaire

Le premier point est que parce que l'arbre est très structuré, vous pouvez utiliser une structure semblable à un tas pour définir implicitement l'arbre plutôt que de représenter l'arbre avec des nœuds, des pointeurs gauche et droit, des intervalles, etc. Cela économise beaucoup de mémoire avec essentiellement aucun impact sur les performances - vous devez effectuer un peu plus d'arithmétique de pointeur.

Le deuxième point est que, au prix d'un peu plus de travail pendant l'évaluation, vous pouvez utiliser un arbre M-aire plutôt qu'un arbre binaire. Par exemple, si vous utilisez un arbre à 3 aires, vous calculerez le maximum de 3 éléments à la fois, puis 9 éléments à la fois, puis 27, etc. Le stockage supplémentaire requis est alors N / (M-1) - vous pouvez prouver en utilisant la formule de la série géométrique. Si vous choisissez M = 11, par exemple, vous aurez besoin de 1 / 10ème du stockage de la méthode de l'arbre binaire.

Vous pouvez vérifier que ces implémentations naïves et optimisées en Python donnent les mêmes résultats:

class RangeQuerier(object):
    #The naive way
    def __init__(self):
        pass

    def set_array(self,arr):
        #Set, and preprocess
        self.arr = arr

    def query(self,l,r):
        try:
            return max(self.arr[l:r])
        except ValueError:
            return None

contre.

class RangeQuerierMultiLevel(object):
    def __init__(self):
        self.arrs = []
        self.sub_factor = 3
        self.len_ = 0

    def set_array(self,arr):
        #Set, and preprocess
        tgt = arr
        self.len_ = len(tgt)
        self.arrs.append(arr)
        while len(tgt) > 1:
            tgt = self.maxify_one_array(tgt)
            self.arrs.append(tgt)

    def maxify_one_array(self,arr):
        sub_arr = []
        themax = float('-inf')
        for i,el in enumerate(arr):
            themax = max(el,themax)
            if i % self.sub_factor == self.sub_factor - 1:
                sub_arr.append(themax)
                themax = float('-inf')
        return sub_arr

    def query(self,l,r,level=None):
        if level is None:
            level = len(self.arrs)-1

        if r <= l:
            return None

        int_size = self.sub_factor ** level 

        lhs,mid,rhs = (float('-inf'),float('-inf'),float('-inf'))

        #Check if there's an imperfect match on the left hand side
        if l % int_size != 0:
            lnew = int(ceil(l/float(int_size)))*int_size
            lhs = self.query(l,min(lnew,r),level-1)
            l = lnew
        #Check if there's an imperfect match on the right hand side
        if r % int_size != 0:
            rnew = int(floor(r/float(int_size)))*int_size
            rhs = self.query(max(rnew,l),r,level-1)
            r = rnew

        if r > l:
            #Handle the middle elements
            mid = max(self.arrs[level][l/int_size:r/int_size])
        return max(max(lhs,mid),rhs)
Patrick Mineault
la source
0

essayez la structure de données "arbre de segment"
il y a 2 étapes
build_tree () O (n)
requête (int min, int max) O (nlogn)

http://en.wikipedia.org/wiki/Segment_tree

Éditer:

vous ne lisez pas le wiki que j'ai envoyé!

cet algorithme est:
- vous traversez le tableau 1 fois pour construire l'arborescence. O (n)
- 100000000+ fois où vous voulez connaître le maximum de n'importe quelle partie du tableau, appelez simplement la fonction de requête. O (logn) pour chaque requête
- implémentez c ++ ici geeksforgeeks.org/segment-tree-set-1-range-minimum-query/ l'
ancien algorithme est:
chaque requête, il suffit de parcourir la zone sélectionnée et de trouver.

donc, si vous allez utiliser cet algorithme pour traiter une fois, OK, il est plus lent que l'ancienne. mais si tu vas traiter grand nombre de requêtes (milliards), il est très efficace , vous pouvez générer un fichier texte comme celui - ci, pour le test en

ligne 1: 50000 nombre aléatoire 0-1000000, divisé par « (espace) » (c'est le tableau) en
ligne 2: 2 nombre aléatoire de 1 à 50000, divisé par '(espace)' (c'est la requête)
...
ligne 200000: aime la ligne 2, c'est aussi la requête aléatoire

c'est l'exemple du problème, désolé mais c'est en vietnamien
http://vn.spoj.com/problems/NKLINEUP/
si vous le résolvez à l'ancienne, vous ne passez jamais.

ngoaho91
la source
3
Je ne pense pas que ce soit pertinent. Un arbre d'intervalles contient des intervalles, pas des entiers, et les opérations qu'ils autorisent ne ressemblent en rien à ce que demande OP. Vous pouvez, bien sûr, générer tous les intervalles possibles et les stocker dans une arborescence d'intervalles, mais (1) il y en a de manière exponentielle, donc cela ne se met pas à l'échelle, et (2) les opérations ne ressemblent toujours pas à ce que OP demander.
mon erreur, je veux dire arbre de segment, pas d'arbre d'intervalle.
ngoaho91
Intéressant, je pense que je n'ai jamais croisé cet arbre! IIUC, cela nécessite cependant de stocker tous les intervalles possibles. Je pense qu'il y a O (n ^ 2) de ceux-ci, ce qui est assez cher. (De plus, la requête ne devrait-elle pas être O (log n + k) pour les résultats k?
oui, void build_tree () doit traverser le tableau. et stocker la valeur max (ou min) pour tous les nœuds. mais dans de nombreux cas, le coût de la mémoire n'est pas important que la vitesse.
ngoaho91
2
Je ne peux pas imaginer que cela soit plus rapide qu'une simple O(n)recherche dans le tableau, comme décrit dans la réponse de tarun_telang. Le premier instinct est que O(log n + k)c'est plus rapide que O(n), mais O(log n + k)c'est juste la récupération du sous-tableau - équivalent à l' O(1)accès au tableau étant donné les points de début et de fin. Vous auriez encore besoin de le parcourir pour trouver le maximum.
Izkata
0

Vous pouvez obtenir O (1) par requête (avec une construction O (n log n)) à l'aide d'une structure de données appelée table clairsemée. Pour chaque puissance de 2, économisons le maximum pour chaque segment de cette longueur. Maintenant, étant donné le segment [l, r), vous obtenez un maximum de maximum sur [l + 2 ^ k) et [r-2 ^ k, r) pour k approprié. Ils se chevauchent mais c'est OK

RiaD
la source