Qu'est-ce qui est le plus rapide: Saisie de données appropriée ou structure de données appropriée?

Question

J'ai un ensemble de données dont les colonnes ressembler à ceci:

Consumer ID | Product ID | Time Period | Product Score 
1   | 1   | 1   | 2 
2   | 1   | 2   | 3 

et ainsi de suite.

Dans le cadre d'un programme (écrit en C), j'ai besoin de traiter les scores de produits donnés par tous les consommateurs pour une combinaison de produit et de période donnée pour toutes les combinaisons possibles. Supposons qu'il y ait 3 produits et 2 périodes de temps. Ensuite, je dois traiter les scores de produits pour toutes les combinaisons possibles, comme indiqué ci-dessous:

Product ID | Time Period 
1   | 1 
1   | 2 
2   | 1 
2   | 2 
3   | 1 
3   | 2 

je vais devoir traiter les données le long des lignes au-dessus de nombreuses fois (> 10k) et l'ensemble de données est assez grand (par exemple, 48k consommateurs, 100 produits, 24 périodes de temps, etc.). Donc, la vitesse est un problème.

J'ai trouvé deux façons de traiter les données et je me demande quelle est l'approche la plus rapide ou peut-être peu importe? (Questions de vitesse, mais pas au coût de l'entretien/lisibilité excessive):

1. Trier les données identifiant du produit et la période de temps et ensuite en boucle à travers les données pour extraire des données pour toutes les combinaisons possibles.

2. Conservez les identifiants de consommateurs de tous les consommateurs qui ont fourni des scores de produit pour une combinaison particulière d'ID de produit et de période et traitez les données en conséquence.

Des pensées? Un autre moyen d'accélérer le traitement? Merci

Answer 1

Comme pour de nombreuses questions liées à la performance, la seule réponse réelle et définitive est d'écrire un benchmark. La vitesse dépendra de beaucoup de choses, et il ne semble pas que vous parlez d'un cas simple d'un algorithme linéaire par rapport à un algorithme quadratique (et même cela aurait une dépendance supplémentaire sur la taille d'entrée).

Implémentez donc les deux méthodes, exécutez-les sur des exemples de données et chronométrez les résultats. Ce sera beaucoup plus rapide et plus concluant que nous essayons de le résoudre dans nos têtes avec des informations limitées.

Answer 2

Je suggère de filtrer les données, comme dans la deuxième étape, puis les processus selon la première étape. Si votre performance est inacceptable, syntonisez la performance. Définissez des repères pour votre base de référence, puis essayez différentes approches.

Dans la plupart des situations du monde réel, je déconseille de mettre en œuvre des méthodes multiples simplement pour le benchmarking. La performance est susceptible d'être similaire. Si ce n'est pas similaire, son fonctionnement probablement mal et sera dans le besoin évident de réglage. Votre temps est probablement mieux passé à implémenter d'autres fonctionnalités.

Answer 3

Cela donnerait une table de base de données plus petite. Il s'agit d'environ 0,4 Go de données si la matrice complète des consommateurs/produits/temps existe. Avez-vous envisagé de tout faire en SQL? Même si vous ne nous avez pas une base de données complète; pour cette taille de données, il serait pratique de générer une table complète pour chacun des ordres de tri possibles et de les vider dans un fichier. Vous pouvez ensuite charger n'importe quel fichier dont vous avez besoin pour le parcourir dans l'ordre de votre choix. En outre, si vous pouvez exécuter les passes complètes de 10 Ko en parallèle ou au moins quelques douzaines par passage, vous pourriez être en avance pour le faire car cela pourrait réduire considérablement vos attentes d'E/S et/ou vos échecs de cache.

Answer 4

En fait, les deux méthodes me semblent très similaires. Afin de stocker l'identifiant client de tous les clients ayant fourni un score pour une combinaison spécifique, vous devez trier les données ou effectuer une opération plus coûteuse.

Pouvez-vous échanger de l'espace pour le temps? Si oui, ne pas pré-traiter quoi que ce soit, mais créer un tableau de toutes les combinaisons (10x24) pour stocker les scores. Traiter les données comme elles viennent et mettre à jour le score de la combinaison spécifique. Si vous avez besoin du score moyen, stockez à la fois la somme et le nombre de clients ayant fourni le score.

Answer 5

La partie la plus lente sur laquelle vous avez une influence serait probablement la copie de morceaux de mémoire. Ainsi, la première technique à appliquer serait de placer les valeurs de chaque ligne dans une structure et de s'y référer uniquement par pointeur jusqu'à ce que tout le traitement soit terminé. Les structures seraient quelque chose comme:

typedef struct { 
int consumer; 
int product; 
int time; 
int score; 
} rowData; 

bâtiment sur que je pense que vous seriez mieux en boucle à travers les lignes d'entrée et de construire un arbre binaire (ou une autre structure triée) des structures qui sont identifiées par le consommateur et le produit, et contiennent une table de pointeurs vers tous rowData correspondant:

typedef struct { 
int consumer; 
int product; 
rowData * matches; 
} matchLut; 

une fois que toutes les lignes ont été placés dans des tables de consultation sur l'arbre puis chaque paquet peut être traité.

Answer 6

Si la mémoire le permet, stockez vos données dans un tableau 2d (vraiment 3D, mais j'y reviendrai plus tard). Ce tableau sera indexé par (product_id, time_period). Si votre traitement des données le permet, chaque élément du tableau 2D peut être un accumulateur des nouvelles données, de sorte que vous lisez dans un élément de données, puis ajustez l'élément correspondant du tableau 2D pour le refléter. Si cette méthode fonctionne, vos données seront traitées lorsque vous finirez de les lire.

Si votre traitement nécessite que vous ayez des données de chaque élément de données présentes à la fois, vous pouvez faire de chaque élément de votre tableau 2D une liste (ceci est le 3ème D). Il peut s'agir d'une liste de longueur variable si vous ne savez pas combien d'entrées client seront présentes pour chaque (product_id, time_period). Après avoir lu vos données, vous devrez revoir chaque élément du tableau 2D pour traiter chaque liste. La façon dont vous organisez votre tableau et la façon dont vous visitez les éléments auront une incidence sur la performance. Vous voudrez probablement déclarer dynamiquement, mais pour cet exemple

struct element_t element[NUMBER_OF_PRODUCTS][NUMBER_OF_TIME_PERIODS]; 
// don't forget to initialize these elements to empty 
... 
for (p = max_product_id; p >= 0; p--) { 
    for (t = max_time_period; t >= 0; t--) { 
     process(element[p][t]); 
    } 
} 

fonctionnera mieux si vous voulez traiter chaque produit avant de passer à l'autre parce que. Vous pouvez échanger la ligne, la colonne et les boucles de la déclaration pour obtenir de meilleurs résultats en cache si vous souhaitez traiter chaque période (pour tous les produits) avant de passer à la suivante.

Vous devriez noter que ceci fait le tri pour vous sans dire "trier ces données". Si la mémoire ne le permet pas, vous voudrez probablement stocker des parties de vos données dans les fichiers au fur et à mesure que vous les lisez. Cela aura les mêmes problèmes que l'optimisation tableau/boucle/sera amplifié plusieurs fois. À la fin de la lecture dans vos données principales, vous voudrez être en mesure de traiter toutes les données d'un fichier temporaire particulier (contenant éventuellement toutes les données pour un produit donné (xOR pour une période donnée)) avant de passer à la suivante. Le principal inconvénient d'essayer de faire cela est que lorsque vous lisez dans les données, il est très probable que vous aurez à faire face à ne pas être en mesure d'avoir tous les fichiers temporaires ouverts en même temps.Cela peut vous obliger à trouver un moyen de faire un échange de fichiers ouvert (identique à l'échange de mémoire, sauf que vous échangez des fichiers ouverts plutôt que des pages de mémoire). Ce serait un tout autre problème, cependant.

Answer 7

Je vous suggère de réorganiser vos données en fonction des processus les plus fréquemment utilisés. Les données les plus fréquemment consultées devraient être les plus faciles et les plus rapides à accéder.

En outre, jetez un oeil à Database Normalization. C'est un concept d'organisation des données pour le moins de duplication possible, et qui rend également l'accès aux données plus efficace.

Une autre idée consiste à utiliser des indices pour des recherches de données moins populaires.