Bonjour,
 
'Petit' probleme explicite ^^, je recois pres de 100 Millions de points dans des fichiers de 700Mo +-.
Le probleme est qu`il ne sont absolument pas tries .  
 
Voulant travailler dessus par portion de surface, il me faut pour cela pouvoir les trie dans l`espace ^^.
Cependant 1000 Millions de points me prennent en ram si mes calculs sont bons (4*3*1000e6) (float*xyz*nb) --  
 
Enfin dans tout les cas, cela n`est pas gerable : )
Auriez vous une idee d`une maniere elegante de proceder ?

"acheter 16Go de RAM" est-il une réponse acceptable?

sinon, les injecter dans une base de données, pour pouvoir requêter des ensembles de points par coordonnées... mais je suis pas sur que ce soit plus simple...

Utilise un tri par fusion sans hésitation.

Quadtree si tu veux les traiter par portions 2D (dans un plan commun à tous les traitements).
Octree si 3D (traitement par volume d'intérêt).
 
Quelles relations de cohérence tu as entre tes points ?
Tu as une notion de connectivité (bouts de surfaces) ?
Quelle est la nature de tes traitements ?

J'utiliserais plutot des R-Tree.  J'ai l'impression qu'une partie du probleme de Kirua_sama est que ses donnees ne tiennent pas en memoire chez lui et les R-Tree sont plus adaptes a l'utilisation de fichiers (en gros, c'est un B-Tree adapte en structure d'acces spaciales - en passant, spatial access method est le mot cle a utilise pour chercher les infos sur ce sujet).

En supposant bien sur qu'une premiere passe de classification ne suffit pas pour repartir les donnees en des fichiers de tailles raisonnables.

Effectivement, LE probleme n`est pas comment subdiviser l`espace, mais bien de savoir comment trie un nombre de points qui de toute evidence ne tiens pas en memoire...
 
Le but serait a la maniere spacial d`un quadtree de decouper ces fichiers de 900MPts en plusieurs fichier de +-2MPts (chaque fichier representant la surface d`une feuille).
 
Je vais me renseigne au niveau des R-Tree et de la gestion des fichier qu`il peut en faire.  
 
Merci ^^.

Déjà a mon avis, un bon build 64bits sera utile.
A mon avis tu devras générer un fichier qui englobe les structures de divisions et les points, un memmap sur le fichier que tu parcours suivant des requêtes de zones.
Maintenant si tu veux pouvoir modifier ta collection de points et rebalancer les structures
 
Mais bon c'est quoi le contexte ?
Ta collection de points peut être modifiée ?
Tu est en 2D ou en 3D (vu que tu as un z ?) ?

En fait les R-Tree et algorithme de subdivision de l`espace ne sont pas ce que je cherche... Je cherche les moyen de lire un fichier et de jouer avec d`autres pour repartir mes points en les triant par zone : /.  
 
3D ^^, mais je parle d`un subdivision 2D car je ne souhaites recupere des points tries que selon x et y.
 
Je ne connais aucuns des composants de ta solution --> google.
 

Qu'est-ce que tu entends de jouer avec d'autres ?
Car c'est là que tout se joue. ( )

J`entends par la de trier a partir de ce gros fichier de 1KMPts d`en remplir d`autre de +-2Mpts.
 
J`imagine que l`unique solution consiste a remplir les fichier petit a petit et puis tranfere les points d`un fichiers a un autre pour effectue le tri selon la surface dans laquelle il est.
 
Si cela est trop complique je vais je pense, juste gride ma surface avec un rapport de proportion simple pour arrive a mes deux Mpts --> creer mes fichiers et relire le gros pour copier les points correspondant a cahque carre ^^.

En tout cas les grouper par localité c'est sûr que c'est nécessaire.
Maintenant quelle va être l'utilisation suivante ?

Traitement Lourd :
- classification -  
- reconstruction de surface -
- Triangulation -
Supression...

Ben c'est cool. Tu lis tes points et tu les répartis tranquillement dans tes N fichiers en fonction de (x, y).  Y'a pas de probème particulier. Le plus long, la-dedans, ce seront les accès fichiers, la lecture et l'écriture de ton milliard de points, donc l'algo, il n'a (pour l'instant) pas besoin d'être très sophistiqué.
Après, la 2e passe, c'est le tri de chacun des 450 fichiers pour optimiser les traitements ultérieurs, mais ça peut probablement être fait en RAM pour chacun d'eux.

Apres m`etre un petit peu renseigner sur les memap... Pareil niveau performances et complexite de mise en place ce serait pas super rentable : /.
 
So, tout compte fais, la solution de pataluc consistant a passer par les base de donnees me parait la plus interessante...
 
Qu`en pensew vous ?

A mon avis bcp trop lent, rien que pour l'insertion des données. Ceci dit, rien ne vaut un test. Et ma solution ?

 
Et quelle serait cette fonction f(x,y) ?
Je veux dire comment tu peux les repartirs en fonction de quelque chose dont tu n`as pas la connaissance prealable ?

Ben la fonction dépend de la façon dont tu veux répartir tes données, et donc de l'usage ultérieur. Le truc simple, c'est une répartition uniforme à 2D. Si tes données ne sont pas du tout uniformes, il va falloir faire une première passe avec lecture aléatoire de données sur un échantillon pour effectuer une statistique de répartition. Et après tu découpes en zones de façon à ce que les fichiers soient à peu près équivalents. Et ensuite, tu crées une fonction de répartition basée sur cette statistique...

 
Pas l`air super simple, vais m`y pencher (apres un petit test de perf sur BD   ).  
Mais la solution me plais.

C'est pas très compliqué, pourtant. Après, tu peux raffiner avec de la bisection pour la première passe (la répartition dans les N fichiers), tu peux diminuer la taille des fichiers (et donc augmenter leur nombre) pour augmenter la vitesse du tri (2e passe), faire du mmap comme le suggère bjone, etc.
A vue de nez, si on compte 2s pour la lecture, le tri et l'écriture de fichiers binaires de 2millions de points, il faut environ ~15 mn pour le total des opérations. Il y a sûrement mieux, mais là, je laisse la place aux autres.

Une piste peut être :
- chaque fichier faisant 700 mo, il doit être possible de trier chacun d'eux
- ensuite, ouvrir tous ces fichiers triés et les parcourir progressivement en prenant à chaque fois le point le plus "petit"
C'est pas extrèmement élégant mais ca devrait fonctionner sans nécessiter trop de RAM (juste le tri des 700 mo de chaque fichier)

Desole, mais tu as saute la conversation ^^.