Cherche algorithme

On a un ensemble L1 d’éléments indexés.

Il s’agit de déplacer des éléments de L1 vers un ensemble L2

  • en respectant la relation d’ordre total
  • Sachant que les déplacement se font par blocs d’éléments consécutifs (par exemple, déplacements des éléments 31,32,33,…,44
  • Certains éléments marqués * ne peuvent pas être déplacé (lockés)
  • L’insertion et la recherche dans l’ensemble L1 et L2 doit rester rapide.

Exemple:
Déplacement des éléments de 23 à 27 avec
1, 2, 3, 4 … 22, 23, 24, 25*, 26, 27, 28, 28 …
Vers L2

Ou alors, insertion de l’élément 34 dans L1 sans perte de donnée, avec L1
1, 2, … 32, 33, 34, 35, 36… (Donc il faut décaler les éléments existants!):
1, 2, … 32, 33, 34, 35, 36, 37 …

Si vous avez des idées…
Les réponses simples sont en O(n) pour le déplacement et O(n²) pour l’insertion, je cherche en ln(n)…
PS: il y a quelques contraintes sur la mémoire!

J’ai. log n (recherche) n*log(n) (insertion) … Pffff :confused:

les écarts entre 2 valeurs consécutives sont relativement proches ?
ex : c est plus du genre 1 50 300 450 ou 2 4 7 9 10 11 12 14 ?

L’écart entre 2 valeurs à un max ? genre on peut avoir 12 14 17 (écart max 3) mais pas 12 18 29 ?

Et utiliser un mécanisme à la ‘B-arbres’ c est possible ?
Ex : 1 3 4 5 7 8 9 12 13 14 associé à un tableau 1 5 9 (rang 3 dans mon exemple), ainsi tu sais tu veux inserer 7, tu sais que c est apres l’index qui contient 5 (rang * indice de 5 = 3)
Mais ca suppose une construction et une modif de ce tableau a chaque insertion, c est peut etre un peu lourd.

Heu…rapidement, je ne vois pas comment on peut faire mieux que n*log(n) en insertion…Après, ça dépend bcp du nombre d’éléments lockés…bref, j’ai peur qu’une analyse brutale “en 0(truc)” ne soit pas suffisante dans ce cas. Il faudrait regarder la complexité dans le pire des cas.

axel.azerty: oui, l’écart est généralement proche. Ou plutôt, statistiquement proche car rien n’empêche que ces écarts soit importants. Il s’agits de listes de pages mémoires de fichier, dans divers états (default, dirty, commit…).
Statistiquement les pages contigües sont écrites sur le disque, mais pour des gros fichiers, tu peux avoir des écritures (et donc des pages) n’importe ou dans le fichier.

En fait je résouds le poblèmes des locks en stockant les éléments lockés dans une autre liste, on peut considéré qu’il n’y en a pas.

Par contre je n’arrive pas a sélectionner des blocs. Si je pouvais déplacer simplement un bloc de m éléments dans un arbre à n élément la complexité pour le déplacement passerai de m*log(n) à log(n), ce qui est vraiment mieux.

Les tableaux de mémoires contigüs sont de tailles fixes, il me faut avoir recours à des listes chaînées ou des arbres :confused:

Heu…Peux tu stp récapituler exactement ce que tu veux que l’algo fasse et quelles sont les contraintes.

Fakbill, qui n’est peut être pas très bien réveillé et qui voudrais être sûr de bien comprendre le pb.

Pour faire simple:
Insertion/suppression d’1 élément dans une ‘liste’ (arbre… )
Insertion/suppression d’un bloc d’éléments (ie: plusieurs éléments d’index consécutifs croissants)

Contraintes : rapide :stuck_out_tongue:

Y a une section dédiée à la prog dans le forum, tu trouverais sûrement des personnes plus à l’aise avec les maths. Pour ma part, j’ai rin capté.

Ok, je vais poster là bas.

La bible absolue pour ce genre de question :

INTRODUCTION ALGORITHMIQUE
Auteur(s) : Cormen Thomas , Leiserson Charles , Rivest Ronald
Date de parution : 01/12/1994

Je vais y jeter un oeil de suite!
Merci :wink:

Rivest Ronald

arrf !! le R de RSA ! ya des chances que tu trouve des infos solides :slight_smile:

sinon… chui comme dumbledore :stuck_out_tongue:

Un lien sympa:
http://www.nist.gov/dads/

ben en fait “tout le monde” connait ce bouquin sous le nom “le cormen”. pas de bol pour les autres auteurs :wink:

Il est assez théorique (des maths…) et solide comme un rock!

sT0ne : superbe lien!!

:jap: merci beaucoup

Heu…merci pourquoi? Tu as trouvé ton bonheur dans le lien et/ou dans le bouquin?

Je pense avoir trouvé, (reste à faire le code et à le tester) mais les liens sont interressants!

“Je pense avoir trouvé” : En utilisant quelle struture de données?

Des listes… et en trichant un peu :slight_smile:
Formellement c’est du n², en pratique c’est du … constante!

Grosso modo j’anticipe que les écritures du fichiers sont contigues, (statistiquement tu écris un fichier depuis le début jusqu’à la fin…).
Ce qui fait que je place un pointeur à la dernière position atteinte, et ça devrait exploser les benchs.

Bien sûr si tu fais une insertion au milieu du fichier, tu es grillé, l’algo sera en 0(n)

Ton heuristique est très bonne! La complexité théorique, parfois, on s’en tape. Si tu demandes à qlqn ce que signifie la phrase “Un tri ne peut pas être plus rapide que O(nLog(n)”, tu rigoles souvent en entendant la réponse :wink: (Ou tu pleures c’est selon).

Question bête : Actuellement, c’est fait comment?