maison
Top.Mail.Ru Yandeks.Metrika
Forum: "Débutants";
Archive actuelle: 2013.08.04;
Télécharger: [xml.tar.bz2];

vers le bas

Algorithmes rapides pour les opérations avec des tableaux Trouver des branches similaires


cls   (2012-12-02 12:36) [0]

Camarades, pouvez-vous me dire s'il existe des algorithmes rapides pour les opérations avec des tableaux de comparaison d'éléments et d'autres opérations arithmétiques avec eux (par condition). Tout ce que j'ai trouvé ne s'applique qu'à différentes sortes. Et, par exemple, pour convertir les éléments du tableau d’une manière donnée, il ne reste que l’énumération séquentielle de tous les éléments. Avec un volume de centaines d’éléments - c’est rapide, quelques secondes et si cent mille - pendant une longue période (comptez les minutes, parfois des dizaines de minutes). Est-il possible d'accélérer de telles opérations, m. décrit dans n'importe quelle littérature?



Авоськ   (2012-12-02 12:57) [1]


> seulement énumération séquentielle de tous les éléments

peut être à travers un. peut-être qu'ils ne le remarqueront pas.



RWolf   (2012-12-02 13:01) [2]

bien sûr il y a un GPU.



DVM   (2012-12-02 13:09) [3]


> Avec un volume de centaines d’éléments, c’est rapide, en quelques secondes,
> et si cent mille-pour une longue période (facture pour minutes, parfois
> des dizaines de minutes).

Cent mille, c'est un montant ridicule sans GPU. Une image FullHD contient des éléments 2 000 0000, mais elle est néanmoins affichée plusieurs fois par seconde et même sans GPU. Bien sûr, tout dépend du type de transformation que vous devez effectuer, mais ici, vous devez vraiment optimiser les algorithmes eux-mêmes. GPU - il s'agit d'un cas extrême, lorsque les autres options d'optimisation ont été épuisées. Bien entendu, le processeur graphique traite rapidement les données. Si vous pouvez paralléliser la tâche, vous devez d’abord pouvoir le faire et, d’autre part, le processeur graphique a également besoin de transférer des données. C’est le bon moment.



cls   (2012-12-02 13:11) [4]


> bien sur il y a un GPU.


Comment Si, par exemple, vous devez comparer des éléments avec une valeur donnée et entrer le résultat dans un autre tableau.



Юрий Зотов   (2012-12-02 13:13) [5]


> cls (02.12.12 12: 36)
> transformer les éléments du tableau d'une manière donnée reste
> énumération séquentielle de tous les éléments. Avec un volume de centaines
> éléments - c'est rapide, en secondes, et si cent mille - déjà
> long (facture pour minutes, parfois des dizaines de minutes). Est-il possible d'accélérer
> de telles opérations

En soi, la boucle à travers des centaines de milliers d’éléments de tableau ne prend pas beaucoup de temps. Et voici la preuve (un million d'éléments):
type // TElementType = string; // 45..65 ms TElementType = entier; // 0..15 ms var A: tableau [1..1000000] de TElementType; N: TElementType; procedure TForm1.FormDblClick (Sender: TObject); var i: entier; T: cardinal; commencer T: = GetTickCount; pour i: = faible (A) à élevé (A) do N: = A [i]; Légende: = IntToStr (GetTickCount - T); fin
Le passage d'un million d'éléments de type Integer (et c'est l'un des types les plus rapides, si ce n'est le plus rapide) dure de 0 à 15 ms.

Le passage d'un million d'éléments de type String (et c'est l'un des types les plus lents, sinon le plus lent du tout) dure de ms à 45.

Pour les autres types d'éléments, le temps de transit devrait être approximativement entre ces estimations limites.

Par conséquent, si votre compte fonctionne pendant des minutes, voire des dizaines de minutes, il est évident que le problème ne réside pas dans la manière de passer à travers les éléments du tableau, mais dans l'algorithme permettant de les convertir. Par conséquent, il est nécessaire de commencer l'optimisation avec cet algorithme.

C'est tout ce qui peut être suggéré sans connaître l'algorithme lui-même.



cls   (2012-12-02 13:13) [6]


> mais ici il faut optimiser les algorithmes eux-mêmes.

à ce sujet et à la question - existe-t-il des ouvrages consacrés à ou concernant les algorithmes optimaux de traitement de tableaux?



DVM   (2012-12-02 13:27) [7]


> cls (02.12.12 13: 13) [6]

Il ne s'agit pas de tableaux. La chose est les algorithmes. Bien sûr, il y a de la littérature, le même whip, par exemple - vous y trouverez des réponses à toutes les questions. Mais il peut préciser la question, à savoir qu'ils disent qu'il existe un tel algorithme car il peut être accéléré.



Юрий Зотов   (2012-12-02 13:28) [8]


> cls (02.12.12 13: 13) [6]
> il existe une littérature sur ou relative aux algorithmes optimaux
> des matrices de traitement?

1. Pas des tableaux, mais leurs éléments. Le problème est, comme déjà mentionné.

2. Comment pouvons-nous conseiller la littérature sur l'optimisation du traitement de quelque chose si on ne sait pas de quel type de traitement il s'agit?



Авоськ   (2012-12-02 13:29) [9]

lisez [5] plusieurs fois, c’est peut-être appris.



cls   (2012-12-02 13:43) [10]


> Yuri Zotov


> dans l'algorithme pour leur conversion.

Par exemple, la transformation ci-dessus: compare les éléments du tableau A avec une valeur donnée et affiche le résultat (1 ou 0) dans le tableau B. Une énumération simple d'éléments avec une opération de comparaison dure avec un volume d'environ 250000 éléments de minutes 10. Que peut aider?



brother   (2012-12-02 13:45) [11]

ne confondez pas l'algorithme avec sa mise en œuvre.



RWolf   (2012-12-02 13:49) [12]

Je ne peux pas imaginer une combinaison de fer sur laquelle une recherche aussi exhaustive sera effectuée pendant les minutes 10. Même le BC-0010 se débrouillera plus vite. Une autre chose est qu’il n’a tout simplement pas de mémoire pour un tableau de milliers d’éléments 250.
Ce tableau est-il pompé à partir d'une base de données sur un autre continent, ou quoi?



DVM   (2012-12-02 14:00) [13]


> cls


> L'énumération simple des éléments avec une opération de comparaison dure
> volume d'environ 250000 éléments de minutes 10. Que peut aider?
>

écrivez l'algorithme ici



cls   (2012-12-02 14:05) [14]

Tapez TPointRecord X, Y, Z: simple; NClass: entier; fin var Data: tableau de TPointRecord; P: TPointRecord; ..... pour J: = 0 to Length (Data) -1 do // sur tout le tableau commencer P: = données [J]; // MidArifm déjà compté si (PZ - MidArifm) <0 alors P.NClass: = 0 sinon P.NClass: = 1; fin



Юрий Зотов   (2012-12-02 14:06) [15]


> cls (02.12.12 13: 43) [10]
> comparer les éléments du tableau A avec une valeur donnée et imprimer dans le tableau B
> résultat (1 ou 0). Énumération simple des éléments avec une opération de comparaison
> dure avec un volume d'environ 250000 éléments de minutes 10.

Dans la mise en œuvre normale, cela ne devrait pas être.
type TElementType = cardinal; const MinIndex = 1; MaxIndex = 250000; ValueToCompare = High (TElementType) div 2; var A: tableau [MinIndex..MaxIndex] de TElementType; B: tableau [MinIndex..MaxIndex] d'octet; procedure TForm1.FormDblClick (Sender: TObject); var i: entier; T: cardinal; commencer T: = GetTickCount; pour i: = faible (A) à élevé (A) do si A [i]> ValueToCompare alors B [i]: = 1 d'autre B [i]: = 0; Légende: = IntToStr (GetTickCount - T); fin
Ceci est fait instantanément. Donc, votre implémentation n'est pas normale. Montre le code.



DVM   (2012-12-02 14:08) [16]


> cls (02.12.12 14: 05) [14]

code sans signification, il ne fait rien.



RWolf   (2012-12-02 14:12) [17]


> [14]


sur i5, ce code est exécuté en moins de 1 ms.



DVM   (2012-12-02 14:13) [18]


> RWolf (02.12.12 14: 12) [17]

et même cela peut être accéléré, mais ce n’est pas le problème, l’auteur dissimule les détails



cls   (2012-12-02 14:17) [19]

En effet, la déclaration 1 est tombée
Tapez TPointRecord X, Y, Z: simple; NClass: entier; fin var Data: tableau de TPointRecord; P: TPointRecord; ..... pour J: = 0 to Length (Data) -1 do // sur tout le tableau commencer P: = données [J]; // MidArifm déjà compté si (PZ - MidArifm) <0 alors P.NClass: = 0 sinon P.NClass: = 1; Données [J]: = P; fin
seulement c'est une version simplifiée, mais l'essence est la même



Юрий Зотов   (2012-12-02 14:21) [20]


> cls (02.12.12 14: 17) [19]

Ce code est exécuté presque instantanément. Soit vous jouez la partisan pendant l'interrogatoire, soit vous vous livrez à un divorce bon marché.



DVM   (2012-12-02 14:25) [21]


> cls (02.12.12 14: 17) [19]

Ce code fonctionnera également en quelques millisecondes.

Mais que puis-je dire. Pourquoi aller ici et là pour piloter le contenu de chaque élément?

P: = données [J]; si (PZ - MidArifm) <0 alors P.NClass: = 0 sinon P.NClass: = 1; Données [J]: = P;

Remplacer par

if (Data [J]. Z - MidArifm) <0 alors Data [J] .NClass: = 0 sinon Data [J] .NClass: = 1;

Mieux encore:

Type
PPointRecord = ^ TPointRecord;

var P: PPointRecord; P: = @Data [J]; si (P ^ .Z - MidArifm) <0 alors P ^ .NClass: = 0 sinon P ^ .NClass: = 1;



cls   (2012-12-02 14:49) [22]


> si (Données [J]. Z - MidArifm) <0 alors Données [J] .NClass: = 0
> else Data [J] .NClass: = 1;

C'est ce que j'ai fait - j'ai eu une erreur: le côté gauche ne peut pas être assigné. Si nous prenons l'enregistrement de variable temporaire (lecteur), il n'y a pas d'erreur. Quelle est la différence?



cls   (2012-12-02 15:06) [23]


> Yuri Zotov (02.12.12 14: 21) [20]
>
>
>> cls (02.12.12 14: 17) [19]
>
> Ce code est exécuté presque instantanément. Soit vous jouez
> au partisan lors de l'interrogatoire, ou bien divorcer à bon marché.
>

Il n'y aurait pas de problème - je ne demanderais pas.



DVM   (2012-12-02 15:08) [24]


> cls (02.12.12 14: 49) [22]


> Quelle est la différence?

Le fait que tu caches quelque chose. Créez un projet vide, copiez le code du problème minimum nécessaire, assurez-vous qu'il y a un problème et UNIQUEMENT PAR CETTE POSITION posez une question et apportez le code.



Юрий Зотов   (2012-12-02 15:25) [25]


> cls (02.12.12 15: 06) [23]
> Il n'y aurait pas de problème, je ne demanderais pas.

Le code que vous affichez n’est pas le meilleur, mais il n’ya pas de problème de vitesse, ce qui a déjà été mentionné plus d’une fois.

Donc, vous montrez le mauvais code. La question est - pourquoi?

Un des deux - soit ne lis pas ce qu'ils vous écrivent, soit exprès.



Styx   (2012-12-02 15:38) [26]

Le téléporteur indique que, en plus des champs répertoriés, il y a quelque chose d'autre dans l'enregistrement, et il y en a tellement qu'il faut tout le temps pour copier d'avant en arrière ...



cls   (2012-12-02 16:41) [27]


> Styx

Autant que cela est écrit dans le compte rendu

> Yuri Zotov

Je lis tout ce que tous les participants à la discussion écrivent, même des blagues, sans rien cacher. C’est irréaliste de donner tout le code, c’est pourquoi je le cite sous une forme abrégée. Cela vous aidera si je donne une description complète de la classe:

//-------------------- Запись для одной точки ----------------------------------
     TPointRecord = record
      X: double;      // координаты X
      Y: double;      //            Y
      Z: single;      // параметр
      NClass: integer;// номер класса после классификации
     end;
//-------------------- TDataClass ----------------------------------------------
     TGridSize = record     //размер грида
      nX: integer;          // кол-во профилей (столбцов матрицы)
      nY: integer;          // кол-во пикетов (строк матрицы)
     end;

     TValueRecord = record   //пара значений "минимум-максимум"
      LoVal: double;         //минимум
      HiVal: double;         //максимум
     end;
     TDataClass = class
     private
      FName: string;
      FChecked: boolean;
      FGridSize: TGridSize;
      FXSize: TValueRecord;
      FYSize: TValueRecord;
      FZSize: TValueRecord;
      FRotation: double;
      FBlank: double;
      FData: array of TPointRecord;
      FFileName: TFileName;
     protected
      procedure PutItem(AIndex: integer; AValue: TPointRecord);
      function GetItem(AIndex: integer): TPointRecord;
      procedure SetName(AName: string);
      procedure SetState(AState: boolean);
      procedure SetGridSize(AGridSize: TGridSize);
      procedure SetXSize(AValueRecord: TValueRecord);
      procedure SetYSize(AValueRecord: TValueRecord);
      procedure SetZSize(AValueRecord: TValueRecord);
      function GetStepX: double;
      function GetStepY: double;
      procedure SetRotation(ARotation: double);
      procedure SetBlank(ABlank: double);
      function GetItemCount: integer;
      function GetNumberNoEmpty: integer;
      function CalcMidArifm: extended;
      function CalcDispersy: extended;
      function CalcStDeviation: extended;
      procedure SetFileName(AFileName: TFileName);
      function CalcIntStergess: double;
      function CalcIntSqrtRootN: double;
     public
      //SignClass: array of String;
      constructor Create(ASize: integer);
      procedure ReadGrid(AFileName: TFileName);
      procedure WriteGrid(AFileName: TFileNAme; AOption: TOption);
      function CalcHistogram(AInterval: TInterval): THistogramArray;
      function ShowInfo: TStrings;
      property Name: string read FName write SetName;
      property Checked: boolean read FChecked write SetState;
      property GridSize: TGridSize read FGridSize write SetGridSize;
      property XSize: TValueRecord read FXSize write SetXSize;
      property YSize: TValueRecord read FYSize write SetYSize;
      property ZSize: TValueRecord read FZSize write SetZSize;
      property StepX: double read GetStepX;
      property StepY: double read GetStepY;
      property Rotation: double read FRotation write SetRotation;
      property Blank: double read FBlank write SetBlank;
      property Data[IndexOf: integer]:TPointRecord read GetItem write PutItem;
      property Count: integer read GetItemCount;
      property MidArifm: extended read CalcMidArifm;
      property Dispersy: extended read CalcDispersy;
      property StDeviation: extended read CalcStDeviation;
      property FileName: TFileName read FFileName write SetFileName;
      property IntStergess: double read CalcIntStergess;
      property IntSqrtRootN: double read CalcIntSqrtRootN;
     end;

et plus loin, avec toutes les méthodes, et d'autres, et d'autres ...
Je viens de souligner le problème



icWasya   (2012-12-02 16:57) [28]

Le truc est probablement dans cette
property Data [IndexOf: integer]: TPointRecord read GetItem write PutItem;
Ce n'est pas un tableau, mais une propriété indexée.



Anatoly Podgoretsky   (2012-12-02 16:59) [29]

L'auteur a peur pour le code, ils le voleront et le donneront comme sien.
Mais qui a besoin de lui si lentement.



Авоськ   (2012-12-02 17:01) [30]


> Anatoly Podgoretsky (02.12.12 16: 59) [29]

au besoin. essayez de le faire lentement, l’autre jour, j’en ai assez d’insérer des nops.



Юрий Зотов ©   (2012-12-02 17:14) [31]


> cls (02.12.12 16: 41) [27]


Si vous avez tout lu, vous devriez avoir lu [24]. Et pour comprendre que tout n'est pas nécessaire, mais seulement le code du problème minimal. Et comment l'obtenir, il est également indiqué ici.

Au lieu de cela, vous citez la déclaration de classe et PAS UNE ligne de code exécutable. Et le code exécutable que vous avez déjà montré n'a pas de problèmes de vitesse. En conséquence, les informations nécessaires sont absentes encore et encore, rien ne peut être dit.

Faites déjà, enfin, ce que vous deviez faire tout de suite - montrez ce morceau de code REAL qui cause VRAIMENT le problème. AND REAL déclarations de TOUTES les variables qui participent à cette pièce.



cls   (2012-12-02 18:05) [32]

Mon code n'a besoin de personne d'autre que moi, avec toutes les lacunes. Désolé de vous déranger.



RWolf ©   (2012-12-02 18:23) [33]

Eh bien, pourquoi, par exemple, j'aimerais voir comment le code trivial a réussi à ralentir par inadvertance au moins un million de fois - également une sorte de réussite.



Styx   (2012-12-02 18:45) [34]


> RWolf © (02.12.12 18: 23) [33]
> pourquoi, par exemple, j'aimerais voir comment
> le code trivial a réussi à ralentir involontairement

Duc a en quelque sorte compris:

> icWasya (02.12.12 16: 57) [28]
> Le truc est probablement dans cette
> propriété Data [IndexOf: entier]: TPointRecord lit GetItem
> écrire PutItem;
> et ce n'est pas un tableau, mais une propriété indexée.



DVM ©   (2012-12-02 18:51) [35]


> Styx (02.12.12 18: 45) [34]


> Duc a en quelque sorte compris:
>

En raison de cela, il est peu probable qu'il existe deux fonctions, chacune ayant deux paramètres. Vous devriez voir ce qui se passe à l'intérieur, mais ralentissez pendant des dizaines de minutes ce qui devrait être fait 10 ms, cela devrait être essayé.



RWolf ©   (2012-12-02 18:54) [36]


> [34]

Eh bien, 200 ms sur i3, jusqu'à 10 minutes de toute façon oh combien loin.



RWolf ©   (2012-12-02 18:58) [37]

c'est-à-dire, 20ms, pas deux cents - j'ai déjà essayé d'insérer des tableaux de données dans la structure pour ralentir la copie et j'ai oublié de les supprimer.



Styx   (2012-12-02 20:02) [38]


> bien sûr il faudrait voir ce qui se passe à l'intérieur

Si le code "extérieur" est identique à celui que le TS l'a apporté - cela signifie qu'il ne reste plus qu'à chercher les freins ...



Palladin   (2012-12-02 23:11) [39]

Le questionneur résout un problème spécifique afin d'obtenir un financement spécifique, mais vous ne l'avez toujours pas aidé à l'obtenir. Posez des questions stupides et parlez des cycles sphériques dans le vide. Et aussi le maître.



Slym   (2012-12-03 08:38) [40]

en conséquence, tout repose dans
SetLength (Données, Longueur (Données) + 1); Data [Longueur (Data) -1]: = P;
:)



Авоськ   (2012-12-03 18:25) [41]


> Palladin (02.12.12 23: 11) [39]
>
> Et aussi le maître.


N'avez-vous pas entendu parler de la façon dont la femme d'un physicien a demandé à ce physicien de couper lui-même une branche d'un arbre dans le jardin qui l'empêchait?



Sapersky   (2012-12-03 20:32) [42]

Mon téléporteur dit: il existe une sortie pour le débogage dans un composant visuel, quelque chose comme Memo1.Lines.Add ...



Очень Злой   (2012-12-03 22:16) [43]


> Camarades, dites-moi s'il vous plaît, y at-il des algorithmes rapides
> pour les opérations avec des tableaux pour comparer les éléments et plus
> opérations arithmétiques avec eux (par condition). Tout ce que j'ai trouvé
> ne s'applique qu'à différentes sortes. Et, par exemple, convertir
> éléments de tableau d'une manière prédéterminée seulement les restes en série
> énumération de tous les éléments.


Des algorithmes "rapides" à mon humble avis existent pour les opérations dans lesquelles de nombreux tableaux sont utilisés, et qui existent afin de réduire le nombre d'appels à chacun des éléments du tableau, et si vous allez effectuer certaines opérations sur le contenu des cellules, où Étant donné que chaque cellule est utilisée à des moments 1 (pour récupérer sa valeur et éventuellement enregistrer une nouvelle valeur), il ne peut exister de tels algorithmes "rapides" pour cette définition.

Parfois, ces opérations peuvent être légèrement accélérées, mais cela se fait déjà par la mise en œuvre. Par exemple, si un tableau d'octets doit être mandaté avec le même nombre, il sera probablement plus rapide de prendre des valeurs du tableau non par octet, mais par exemple immédiatement par 4 octets sous forme d'entier.

Bien que ne sachant pas le vrai problème - il est peu probable que vous puissiez dire quelque chose sur le sujet ...



Pages: 1 2 branche entière

Forum: "Débutants";
Archive actuelle: 2013.08.04;
Télécharger: [xml.tar.bz2];

à l'étage





Mémoire: 0.75 MB
Heure: 0.04 c
15-1362670231
Dimka Maslov
2013-03-07 19:30
2013.08.04
Localisation de Venda


15-1362735718
Employé
2013-03-08 13:41
2013.08.04
Internet et nous


2-1354629104
ours vert
2012-12-04 17:51
2013.08.04
Aide ouvrir le fichier


15-1360144381
Sergey Masloff
2013-02-06 13:53
2013.08.04
Mais à qui le poste vacant Oraklista - Delphi (+ plus. NET) ;-)


15-1362938066
Dmitry S
2013-03-10 21:54
2013.08.04
Archivage





afrikaans albanais Arabic arménien azerbaïdjanais basque Biélorusse Bulgare catalan Chinois simplifié) Chinois (traditionnel) croate Tchèque Danois Néerlandais Anglais estonien Filipino Finlandais Française
galicien géorgien Allemand Grecque Créole haïtien hébreu Hindi Hongrois Islandais Indonesian irlandais Italienne Japonais Coréen letton lituanien macédonien Malay maltais Norvégienne
persan Polonais Portugais Roumain Russe serbe Slovaque Slovène Espagnol Swahili Suédois Thai turc ukrainien Urdu vietnamien gallois yiddish bengali bosniaque
Cebuano espéranto gujarati Hause hmong Igbo Javanais Kannada Khmer lao latin maori Marathi mongol népalais punjabi somali tamil telugu yoruba
zoulou
Английский Français Allemand Italien Португальский Русский Espagnol