inplace merge two sorted linked list

[casper_sky]

bonjour,
je viens d'un backgroud C/C++ , et je voudrai implémenter une fonction qui fait un inplace merge pour deux liste chainées déjà triées ( je veux pas utiliser la fonction SortLinkedList or SortStructredLinkedList car on veux un contrôle totale sur la liste afin de faire un multi threaded sorting algo).

En langage C ca marche tres bien . mais j'ai essayer de le refaire en purebasic avec la built-in linked list "NewList" fournit par l'API de pure basic.
mais le problème avec la NewList est que je peux pas changer le suiveur( successeur ou next in english) de chaque pointeur dans la liste chainee.
voici un pseudo code C que je voudrai savoir comment le faire en purebasic :

// "a" and "b" are two linked lists . and i want to achieve an inplace merge
// "it" is a temporary pointer .

while ( a != NULL && b != NULL ) {
if ( a->value < b->value ) {
it->next = a;
a = a->next;
}
else {
it->next = b;
b = b->next;
}
it = it->next;
}
donc en gros ma question est comment réaliser un inplace mege for two sorted lists avec purebasic ? est ce que c'est pas faisable avec NewList , doit je ré-implémenter ma propre liste chainée dans laquelle je peux changer le successeur de chaque élément comme je veux ? sinon, est ce qu'il ya d'autre moyens pour faire inplace merge ?
merci pour tout aide .

[Ollivier]

Salut,

Personnellement, je ne suis pas friand des listes liées natives de PB. C'est très bien dans l'approche générale et standard, mais dès que tu veux faire de l'exceptionnellement fiable (tant en gestion de mémoire, qu'en gestion de la prise de ressources du CPU), c'est évident que travailler des listes (ou tables, ou autres noms de tableaux lambda qu'on veut pouvoir déformer un peu dans tous les sens), il faut s'attacher aux tableaux.

Maintenant, je peux me tromper, et d'autres ici pourront me remettre en cause à ce sujet mais j'aurai quelques anciens posts qui les combleront dans leur(s) contre-argumentaire(s). Le bonheur que PB offre pour TON problème (décider d'un type de tri, puis trier, et enfin transférer), c'est de disposer d'une syntaxe simplifiée par rapport au C++ pour traiter plus efficacement des tableaux. En plus, les tableaux sont déformables à volonté, (en global, en procédures, en DLL, etc...) avec une excellente fiabilité native au niveau de la mémoire. Donc les listes c'est vraiment quand on n'a pas que cela à faire avec le côté technique, ce qui n'est pas ton cas.

M'enfin, pour te faire plaisir, voici une entorse. La ligne 22 est critique puisqu'elle fait une copie des pointeurs de chaînes et non de leur gestion en mémoire. C'est aussi pour ça que je n'adore pas les listes chaînées.

Code : Tout sélectionner

;http://www.purebasic.fr/french/viewtopic.php?f=3&t=10492

#ListMaxSize = 65535

Structure ListInfo
  Item1.S
  Item2.S
  ; Etc...
EndStructure

Procedure MergeLists(List List1.ListInfo(), List List2.ListInfo() )
  Protected Index.I
  Global Dim *ListRef(#ListMaxSize)
    Index = 0
    ForEach List2()
     *ListRef(Index) = List2()
     Index + 1 
    Next
    Index = 0
    ForEach List1()
      AddElement(List1() )
      CopyMemory(*ListRef(Index), List1(), SizeOf(ListInfo) )
      Index + 1
    Next
  Global Dim *ListRef(0)
EndProcedure

NewList List1.ListInfo()
NewList List2.ListInfo()

AddElement(List1() )
List1()\Item1 = "Lundi"
AddElement(List1() )
List1()\Item1 = "Mardi"
AddElement(List1() )
List1()\Item1 = "Mercredi"

AddElement(List2() )
List2()\Item1 = "Pierre"
AddElement(List2() )
List2()\Item1 = "Paul"
AddElement(List2() )
List2()\Item1 = "Jacques"

MergeLists(List1(), List2() )

    ForEach List1()
      Debug List1()\Item1
    Next

[Ollivier]

Hop! Un exemple avec les tableaux (en espérant que j'ai compris ton histoire parce que c'est un peu hors norme ton algo... ):

Code : Tout sélectionner

;http://www.purebasic.fr/french/viewtopic.php?f=3&t=10492

#ListMaxSize = 65535

Global Dim A(#ListMaxSize)
Global Dim B(#ListMaxSize)
Global Dim C(#ListMaxSize)

Define pA, pB, pC ; pointeurs (ou plutôt index puisque c'est entre 0 et n dans des tableaux)
Define LastA, LastB, LastC ; (limites d'info pour chacun des 3 tableaux)

While (pA <= LastA And pB <= LastB)
  If A(pA) < B(pB)
    C(pC) = A(pA)
    pA + 1
  Else
    C(pC) = B(pB)
    pB + 1
  EndIf
  pC + 1
  LastC = pC ; (Si la limite n'est pas calculée d'une autre manière avant ou après cette boucle)
Wend

[Le Soldat Inconnu]

J'ai déjà vu une approche par modification de la liste en mémoire avec PeekL(@Maliste+index) et PokeL(@MaListe+index) mais je ne retrouve pas comment est gérer une liste chainée en mémoire, pourtant, j'ai déjà vu ça.

[casper_sky]

merci olivier "le soldat inconnu" pour vos réponses,

en effet , pour notre situation on est obligé de passer par une liste chainée , parce qu'on travaille sur des données statistiques de très grande dimension ( jusqu'au 50 Mb d'espace mémoires ), et pour telle situation on peut pas passer par des tableau continu en mémoire et surtout qu'on a des clients qui ont des machine limités en mémoire, du coup c'est pas garantie que l'OS nous reserve 50 mb d'espace mémoires continu.

autre chose, c'est que l'accès au listes chainées pour la suppression et l'ajout des éléments reste bcp plus rapides et même plus simple que supprimer et ajouter des éléments dans des tableaux .

puis en effet l'algo qu'on voudrai implémenter c'est un algo de merge sort mais inplace sur des liste chainee qui me parait pas hors norme, non ? surtout que SortStructredLinkedList utilise cet algo.

merci pour le premier algo, je trouve qu'il est pas mal comme point de départ( bien qu'il fait pas exactement ce que le vrai merge fait ...)

donc en résumé, c'est conseiller de coder ma propre liste chainee non ?

mais la question que je me pose tjs, comment SortStructredLinkedList implémente le merge ? est ce qu'il ya quelqu'un de purebasic team qui peut me repondre svp ?

[G-Rom]

@Lsi

Les LL suivent logiquement cette "logique" en mémoire :

[Pointeur de l'élément précédent]
[Pointeur de l'élément courant]
[Pointeur de l'élément Suivant]

aprioris , c'est pas forcement le cas dans le cadre d'une LL structuré sous PB.

Code : Tout sélectionner

Structure GrossierPersonnage
  Nom$
  Prenom$
  Age.l
EndStructure


Global NewList Personage.GrossierPersonnage()


Macro NouveauPersonnage(Nom_,Prenom_,Age_)
  AddElement(  Personage() )
  Personage()\Nom$      =  Nom_  
  Personage()\Prenom$   =  Prenom_
  Personage()\Age       =  Age_
  Debug "------------------------"
  Debug "Pointeur de l'élément = "+str(@Personage())
  Debug "------------------------"
EndMacro

NouveauPersonnage("Mickey","Mouse",82)
NouveauPersonnage("Donald","Duck",84)
NouveauPersonnage("Bayrou","Francois",52)
NouveauPersonnage("Royal","Segolène",72)

Debug ""
Debug ""
Debug ""



FirstElement(Personage())
*PointeurDeBase = @Personage()


For i = 1 To 4
   Debug "--------------------------------------------"
   Debug PeekS(PeekL(*PointeurDeBase))
   Debug PeekS(PeekL(*PointeurDeBase+4))
   Debug PeekL(*PointeurDeBase+8)
   Debug "--------------------------------------------"
     
   *PointeurDeBase + (SizeOf(GrossierPersonnage)+12)
Next 

[Ollivier]

J'ai déjà vu une approche par modification de la liste en mémoire avec PeekL(@Maliste+index) et PokeL(@MaListe+index) mais je ne retrouve pas comment est gérer une liste chainée en mémoire, pourtant, j'ai déjà vu ça.

Ben ouais, moi je veux bien, mais si une liste chaînée c'est un taureau et qu'un plantage mémoire c'est un coup de cornes, il est grandement préférable d'attacher les cornes d'Hannibal le taureau avant de lui titiller les c[ensuré]s.

Donc, 2ème version: « moi y'en a pas être friand listes chaénées! »