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!
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
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)
Des listes… et en trichant un peu
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 (Ou tu pleures c’est selon).
