J'ai l'algorithme suivant qui scanne un grand tableau circulaire (données). À certains points de la matrice, je dois jeter un coup d'œil aux valeurs antérieures (0 = point de données le plus récent, n = point de données le plus ancien) et déterminer s'il y avait une valeur de 5% inférieure à la valeur actuelle. J'ai fini par écrire un algorithme O (n ^ 2) qui fonctionne correctement, mais cela ne fait pas échouer. N'importe quelle idée comment je pourrais transformer cela en une algue O (n) Algo? Merci!
9 Réponses :
Tout en itérant que la matrice stocke la valeur la plus basse. Cela nécessite de créer une variable min et d'effectuer une vérification de comparaison dans chaque étape. Au lieu de comparer toutes les valeurs précédentes avec le nouveau, comparez-la uniquement avec le plus bas.
Je pense que vous devez élaborer un peu plus. Je ne comprends pas comment vous créez un algorithme O (n) en faisant cela; Il semble que vous puissiez simplement différer la recherche jusqu'à ce qu'une insertion soit effectuée. Je le pire des cas (qui est ce que o mesure), vous êtes toujours O (n ^ 2).
Dépend de savoir si vous pouvez compter sur le minimum toujours dans la fenêtre ou non.
Je pense que c'est la bonne réponse .. Il n'y a plus de recherche nécessaire depuis tout élément inférieur à 95%.
@tomdemuyt ... mais seulement si vous ne "perdez" jamais "perdre" (c'est-à-dire aucune suppression, pas d'écrasement pour enregistrer la mémoire, aucune expiration de valeurs basée sur l'heure, etc.).
@San Jacinto: Je crois que l'algorithme proposé convertit avec succès le bloc de code affecté à O (n). Cela suppose que les données ne changent pas pendant l'analyse.
@San Jacinto: Aucun algorythm ne peut aborder que sans verrouillage, je ne sais pas quel est votre point?
@tomdemuyt pourquoi le verrouillage est-il nécessaire? OP n'a pas mentionné un besoin de concurrence. Si la concurrence est nécessaire, la nature de la manière dont il stocke les valeurs implique de verrouiller sur un tampon circulaire partagé. Avec due respect, je ne comprends pas votre point. Mon point était simplement que, si c'est désiré, votre algorithme exclut l'utilisation des suppressions pour une raison quelconque.
@ kgiannakakis mes excuses. Il semble qu'un problème ait mal compris le problème, afin que je puisse voir pourquoi on pensait que j'implique le verrouillage. Maintenant que je suis le problème, le vôtre semble le plus concis et correct, à condition que vous signiez itérer sur la liste une fois, puis effectuez votre recherche. +1.
Cela ne prend pas en compte la «fenêtre» de 1500 valeurs précédentes.
@Adrian et l'OP n'a pas déclaré que c'était nécessaire. C'est un peu ambigu et c'est un point soulevé par d'autres. Cependant, vous pouvez sûrement voir comment un petit tweak expliquerait cela?
Il l'a dit, dans son exemple de code 'NumberofDataproytsintHepsast'
Ça ne va pas marcher. Il ne prend pas en compte la fenêtre de 1500 points.
@Martin @adrian, il n'a pas fait explicitement claire. Certes, il y a une forte chanson qu'il a peut-être voulu dire que (si vous voyez mes commentaires précédents, je supposais de la même manière), mais ce n'est pas clairement indiqué.
@San Jacinto: Martin est l'affiche de la question! Je dirais donc qu'il l'a rendu parfaitement clair :-) Bien sûr, vous pouvez faire valoir que le contenu de la question est ce qui compte: D
@Moron haha, bon point. Désolé, Martin! J'aurais pu être libellé un peu mieux pour enlever toute ambiguïté :)
EDIT:
Après réflexion Somemore, un algorithme de temps O facile (n) est possible, sans la nécessité d'RMQ ou de l'arbre (voir partie précédente de ma réponse ci-dessous).
Étant donné un tableau A [1 ... n] et une fenêtre et la largeur W, vous devez trouver au minimum A [i, i ... + W], étant donné i.
Pour cela, vous effectuez les opérations suivantes.
Groupe A [1 ... n] dans des blocs contigus de taille W-1. B1, B2, ... B (W-1).
Pour chaque bloc B, maintenir deux autres bloc appelé BLancez et BEND.
BLancez [i] = minimum de B 1 , B [2], .. ., B [i].
BEND [i] = minimum de B [W-1], B [W-2], ..., B [W-i].
Cela peut être fait en O (W) pour chaque bloc, et ainsi de O (n) du temps total.
Maintenant, étant donné un i, la sous-matrice A [i ... i + W] aura une durée de deux blocs consécutifs, par exemple B1 et B2.
trouver le minimum de i à la fin du bloc B1 et B2 en début de séquence à i + w en utilisant B1End et B2Start respectivement.
Ceci est O (1) fois, de manière totale O (n).
Pour un réseau circulaire C [1 .... n], tout ce que vous devez faire est de lancer ci-dessus sur
A [1 .... 2n], qui est essentiellement deux copies de C concaténés-à-dire A [1 ... n] = C [1 ... n] et A [n + 1 ... 2n ] = C [1 ... n]
writeup précédent.
Ok. En supposant que je l'ai bien compris votre question cette fois-ci ...
Il est possible dans l'espace O (n) et S (n).
En fait, il est possible de changer la taille de la fenêtre à un numéro que vous le souhaitez, avoir différents pour différents éléments et ont encore fonctionner!
Etant donné un tableau a [1 ... n], il peut être prétraité en O (n) du temps et de l'espace O (n) pour les requêtes de réponse de la forme: Ceci est appelé Range Interrogation minimum problème.
En théorie, il est possible de le faire en O (n).
Juste en utilisant un arbre vous donnera O (nlogW) temps où W est la taille de la fenêtre et fonctionnera probablement beaucoup mieux que RMQ, dans la pratique, comme je l'attends les constantes cachées pourraient aggraver le RMQ.
Vous pouvez utiliser un arbre comme suit.
Début vers l'arrière et des éléments W insert. Trouvez le minimum et pousser sur une pile.
Maintenant, supprimer le premier élément et l'insert (W + 1) ième élément. Trouvez le minimum, appuyez sur la pile.
Continuez ainsi. Le temps total de traitement sera O (nlogW).
A la fin vous avez une pile de peines minimales, que vous pouvez juste garder sautaient que vous marchez maintenant le tableau une deuxième fois, cette fois-ci dans le bon ordre, la recherche de 0,95 cible *.
En outre, votre question n'est pas vraiment clair, vous dites qu'il est un tampon circulaire, mais vous ne semblez pas faire une opération de module avec la longueur. Et comme code, votre algorithme est O (n), et non O (n ^ 2) que votre taille de la fenêtre est une constante. Quelle est la position d'un élément de minimum le sous-tableau A [i ... j]? constante temps!
EMMM ... et quand vous trébuchez sur un très petit élément-dire zéro-il sera lié comme une tête de liste et restera là-bas pour toujours, même après sa sortie de NumberOdaPoinSInpast . Suis-je mal comprendre quelque chose?
@nailxx: Vous n'avez besoin que de savoir s'il y avait un élément précédent <= 0,95 * NewValue. Donc, avoir un zéro est génial! N'est-ce pas? Dans tous les cas, vous pouvez créer la liste liée à la date mouche in O (n), juste avant de commencer à rechercher, en marchant dans la matrice en arrière (dans l'ordre inverse de la commande dans la question).
@nailxx: la taille de la liste liée sera exactement la même que le nombre d'éléments (c'est-à-dire des valeurs dupicate), si c'est quelle est la confusion.
@nailxx: J'ai mal compris la question!
@nailxx, @Martin: J'ai maintenant changé ma réponse en fonction de ce que je comprends la question à être maintenant. Dites moi si ca marche...
@Martin: J'ai simplifié l'algorithme et c'est maintenant un simple algorithme de l'espace O (n) O (n).
@Martin: Les gens ont mis des efforts à essayer de répondre à vos questions. Moins que vous puissiez faire est de reconnaître. De toute façon bonne chance.
Je ne pense pas qu'il soit possible de le faire dans O (n) parce que en résolvant cela avec O (n), vous pouvez le trier avec O (n) et cela n'est pas possible. (Minimum, pour trier est O (nlogn)).
Supposons que l'on puisse dire pour chaque point combien de points dans le passé a une valeur inférieure à x% (ici X est 5 - mais X peut également être 0 que le nombre sera inférieur dans le passé).
Maintenant - supposons que vous souhaitiez trier un tableau d'éléments N. Corrigez-moi si je me trompe (il se peut que je ne comprenais pas le problème en premier lieu).
Si vous pouvez obtenir le nombre de points plus petits int tout le passé pour tous les éléments de O (n) si le point A a une plus grande valeur que le point B le compte pour le point A sera également grand que le comptage pour le point B (car le tableau est circulaire). Ce problème donne donc une fonction des valeurs au compte qui préserve la commande.
Maintenant, les nouvelles valeurs sont liées entre O et N et ceci peut être trié dans le temps n.
O (n) est possible, imo. Voir ma réponse.
Désolé, je dois donner à cela A -1: il y a 0,95 impliqué et o (n) est possible et cela n'a rien à voir avec le tri. Vous devez trouver s'il y a une certaine valeur <= 0,95 * NewValue. Vous n'êtes pas obligé de trouver la postition exacte, ce qui nécessite le tri.
@Aitay: Tout d'abord, vous devez le réduire dans l'autre moyen: le tri doit me réduire, pas l'inverse. Deuxièmement, O (n) est possible! Avez-vous lu ma réponse?
Mais vous supposez que vous devez trier les données pour accomplir la tâche. Ce n'est pas nécessairement le cas.
@Moron - Je l'ai fait - mais je n'ai pas compris ce que vous vouliez dire "seulement insérer", "Supprimer" ce que tout ce qui avait à faire avec le problème?
@San Jacinto - Je n'ai pas supposé que je dois trier. Ce que j'ai dit, c'est que si je veux trier, je peux le faire avec O (n) + O (résoudre ce problème).
@Aitay qu'est-ce que vous vouliez dire quand vous avez dit: «Je ne pense pas qu'il soit possible de le faire dans O (n) parce que, en résolvant cela avec O (n), vous pouvez le trier avec O (N) et cela n'est pas possible. (minimum, pour trier est O (nlogn)). " Votre point même est que ce n'est pas possible car vous ne pouvez pas trier les données dans O (n) heure. Ce que je dis, c'est que vous dites que ce n'est pas possible parce que____ mais votre hypothèse est fausse. Vous n'avez pas besoin de trier, donc il peut donc être possible avec une autre méthode.
@Aitay: Il n'y a pas de «trouver le nombre d'éléments». La question pose: Y a-t-il au moins un? ...
@San Jacinto - Je n'ai pas supposé que j'ai besoin de trier.
@Aitay: Le commentaire sur l'insertion était hors de propos. Oublie. Ce qui est plus pertinent est que une solution O (n) est possible et vous semblez l'ignorer :-)
@Moron - En effet, si le problème est de trouver F, il y en a au moins un, je suis d'accord avec vous :)
@Aitay ok, mes excuses. J'ai l'intention de penser que les gens veulent dire ce qu'ils disent / écrivent. J'ai mal compris ce que vous vouliez dire d'une manière ou d'une autre.
Depuis que j'ai mal compris la question moi-même, j'ai annulé le bowvote.
Vous pouvez prendre le premier numéros de téléchargement dans le passé, ce qui est N log (n). Ensuite, faites une recherche binaire, Journal (N), trouvez le point de données le plus bas qui transmet le test de 5%. Cela vous indiquera combien de points hors de la numéros de page d'accès au test de l'essai dans N Journal (n) heure à laquelle je crois.
Vous pouvez maintenir un tableau pour chaque itération:
Ce n'est pas O (n) comme je le comprends, mais certainement plus efficace que O (n ^ 2) puisque l'ajout et la suppression des éléments vers / à partir de la matrice triée est O (log n). Je soupçonne que l'efficacité finale est O (n journal (w)), où w est buffarray pour NumberofDataPoinSInpast contenant des éléments de "fenêtre" actuels triés par ordre croissant.
0.95 * buffarray [0] et exécutez les actions nécessaires si elle est.
i + numérosofdaproytsInpast 'th) à partir de buffarray .
i 'th) à buffarray Maintien de l'ordre de tri.
numberofdataproytsinpast .
Darn, vous avez fini de poster en premier.
Votre message est plus propre mais :) laissez-le choisir :)
C'est le pire cas O (NW) si vous utilisez un tableau. O (n logw) est inexact.
trouver des éléments dans une matrice triée est O (log n), l'ajout ou l'enlèvement est O (n)
Je pense que je comprends vos besoins ... Je vais reformuler le problème:
calcul : comptez le nombre de points j tels k <= j Ceci peut être accompli comme suit:
Trier les points {Data [0], Data [1], ... Données [K-1]} à l'aide d'une structure de données qui a au maximum O (log n) Coût d'insertion / retrait. < / p>
initialiser un compteur R à 0, initialiser j à k.
Vérifiez le tableau trié pour voir si le point le plus bas est <= DATA [J] * 0,95; Si oui, incrément r.
Supprimez les données [J-K] à partir du tableau trié et insérez des données [J] sur la matrice triée.
incrément j
si j La clé ici consiste à choisir la structure de données appropriée. Je suis à peu près sûr qu'un arbre binaire fonctionnerait. Si le coût d'insertion incrémentielle est O (log n), votre temps d'exécution total est O (N journal n).
Les itérations doivent commencer par le bas et l'incrément (garder la minute du passé). En ce moment, comme indiqué que l'algorithme revient toujours en arrière, au lieu d'aller de l'avant et de se souvenir du minimum passé.
Comme de nouveaux points sont ajoutés, la gamme de points de données ne peut augmenter que la limite supérieure ou inférieure. Comme la liaison inférieure diminue, la tenue de la limite inférieure est tout ce qu'elle est nécessaire. Tous les nouveaux points qui sont plus que la limite inférieure / 0,95 seront acceptables (car la limite inférieure est toujours dans le passé):
C'est la même solution présentée par une autre affiche.
Essayez ceci:
maintient toujours deux pointeurs sur des éléments de votre tampon. L'une est la valeur minimale rencontrée et l'autre est le prochain miumumum (c'est-à-dire le prochain arrière-sinistre par incrément). Rappelez-vous que ce sont À chaque étape de votre progression dans la mémoire tampon, déterminez si la valeur actuelle est inférieure ou égale à la valeur pointée par Min1 ou Min2, dans l'affirmative, mettez à jour Min1 ou Min2 pour pointer vers l'emplacement actuel.
Sinon, si par le pointeur arithmétique, la valeur de Min1 ou Min2 est de 1500 endroits dans la mémoire tampon, vous devez déterminer lequel il s'agit et réaffectant Min1 ou Min2 en conséquence, c'est-à-dire que Min1 points à Min2 et Min2 est réglé sur Emplacement actuel, ou Min2 est simplement défini sur le point à l'emplacement actuel.
Si la valeur pointée par Min1 ou Min2 est inférieure à 15% de la valeur actuelle peut alors être déterminée par une comparaison simple ...
Pas sûr de comprendre votre algorithme à droite ... Comment ça marche? Votre tableau est-il de 0 à 0 à 0 à 2N? (De votre code, il semble que cela doive être 2n)
Est-ce que ce devoir? Si tel est le cas, vous devriez envisager de le marquer en conséquence.
La description du problème et le code ne semblent pas décrire la même chose pour moi.
Non, ce n'est pas un devoir.
Est
numberOfdaPoinSInpast la taille de votre tableau?Vous écrivez
s'il y avait une valeur de 5% inférieure à la valeur actuelle mais dans votre code, vous comptez en réalité le nombre de points de données. Donc, il y a une divergence. En fait, votre code compte le nombre de points de données qui figurent parmi les N prédécesseurs des N Les derniers points de données et qui sont inférieurs de 5% au point de données de référence en cours.Les gars, c'est un tampon circulaire, c'est pourquoi le code est tel quel. J'aurais tendance à penser que pour un tampon circulaire, les itérateurs sont les meilleurs outils à utiliser ...
@Martin, quelle implémentation de la matrice circulaire utilisez-vous? Pouvez-vous fournir un échantillon ou un lien?