algo fuer listenvergleich

Meep Meep

hola leute

ich bastel grad an ner ordner-synchronisation. kennt jemand nen halbwegs verueftigen algo zum vergleichen von listen ?
damit ich weiß welche objekte in der liste gleich sind und welche nicht

Meep Meep

mata

liste sortiert anlegen und dann binäre suche sollte ganz gut gehen

volkard

Meep Meep schrieb:

hola leute
ich bastel grad an ner ordner-synchronisation. kennt jemand nen halbwegs verueftigen algo zum vergleichen von listen ?
damit ich weiß welche objekte in der liste gleich sind und welche nicht

um genau zu sein, braucht für ein sync-programm du die infos, welche in der einben liste sind aber nicht in der anderen und welche in der anderen sind aber nicht in der einen.

also günstig hat sich bei meinen experimenten erwiesen, die kompletten relativen pfade in zwei listen (naja, vector, weil schneller) zu halten. beim vergleich sortiere ich zuerst beide listen. dann gehe ich so vor:

while(beide listen noch nicht fertig)
   if(src.peek()<dst.peek())
      upload src.peek()
      src.pop()
   else if(dst.peek()<src.peek())
      del dst.peek()
      dst.pop()
   else
      src.pop()
      dst.pop()
if(!dst.isEmpty())
   foreach i in dst
      del i
if(!src.isEmpty())
   foreach i in src
      upload i

oder so ähnlich. hoffe, der plan wird klar dabei. nach dem sortieren, was O(n*log(n)) dauert, ist das durchrasen duch die listen in O(n) eine freude.

beim synchronisieren haste noch das priblem, daß verzeichnisse angelegt werden müssen vor den unterverzeichnissen/dateien und daß verzeichnisse gelöscht werden müssen nach den unterverzeichnissen/dateien. das hab ich gelöst, indem ich nicht direkt del oder upload ausführe, sondern alle jobs nur in eine liste stopfe. die wird dann so sortiert, daß auf jeden fall zuerst gelöscht wird und dann erst geuploaded und daß beim del zuerst die längeren kommen und beim upload zuerst die kürzeren.

netter nebeneffekt war (es ist ein uploader für ftp), daß ich auch noch mehrere threads ansetzen konnte, die job-liste zu leeren und auszuführen.

Meep Meep

re
danke mal fuer die ansaetze.
habs jetz ne fuer mich zufriedene und recht einfache loesung gefunden.

2 list<fileobject*> objekte von den sortierten listen erstellt und dann die listen gegenseitig nach dem alphabet abgleiche.
wenn eine datei beidseitig vorhanden ist, wird sie in beiden listen herausgenommen, eine davon geloescht und die andere in eine neue liste eingehaengt, falls die pruefsumme unterschiedlich ist. am schluss hab ich dann die differenzen.

Meep Meep