Springen naar inhoud

Het sorteren van een lijst bestaande uit m gesorteerde lijsten


  • Log in om te kunnen reageren

#1

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 22 augustus 2009 - 15:20

Stel ik heb een aantal (m) gesorteerde lijsten die elk een variabel aantal elementen hebben (ze zijn dus niet noodzakelijk even lang) en ik wil hiervan een nieuwe lijst maken met alle elementen in de nieuwe lijst uit de andere lijsten, bestaat er dan een algoritme die sneller de lijst sorteert dan gewoon eerst alle lijsten samenvoegen en QuickSort toepassen.

Een intuÔtief programma zou natuurlijk zijn, per lijst een index laten bijhouden over hoeveel elementen we ervan al gebruikt hebben, en per element dat we toevoegen gewoon het kleinste element nemen en dit toevoegen. Het nadeel hiervan is echter dat je een tijdscomplexiteit LaTeX terwijl wanneer ik de totale lijst sorteer met QuickSort ik een tijdscomplexiteit van LaTeX krijg en m kan makkelijk in mijn geval de 100 bereiken.

Ik vraag me dus af of gegeven dat je al gesorteerde lijsten hebt, het algoritme niet sneller kan, misschien niet in tijdscomplexiteit maar eerder in optimalisaties, zo gaat QuickSort meestal zo diep tot dat het een lijst van twee elementen sorteerd (deel van de lijst dus). Indien we nu weten dat deze alletwee deel uitmaken van dezelfde vooraf gesorteerde lijst is dat helemaal niet nodig. Mijn vraag is dus hoe ik QuickSort met deze gegevens wat sneller kan maken.
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Schwartz

    Schwartz


  • >250 berichten
  • 691 berichten
  • Verbannen

Geplaatst op 22 augustus 2009 - 23:42

Methode 1:
Volgens mij kun je zeg eerst de lengte van alle lijsten optellen en daarvan een geheugen maken.
Dan gaat men alle lijsten rijgen.

Methode 2:
Men telt lengte van lijst 1 en lijst 2 op, men maakt dan een passende buffer (buffer A).
Dan gaat men lijst 1 met lijst 2 rijgen naar deze buffer.
Dan maakt men buffer B aan met lengte van buffer A met lengte van lijst 3.
Dan rijgt men buffer A met lijst 3 naar buffer B.
Dan kan men buffer A opnieuw instellen met de lengte van buffer B en lijst 4 en dan weer rijgen naar buffer A.
En dan is men klaar als men alle lijsten heeft gedaan.
Het resultaat staat dan in buffer A of buffer B.
Men gooit dan de andere buffer weg.

Welke sneller is weet ik niet...
kan afhankelijk zijn van de inhoudt en hoeveel lijsten men heeft en de lengte ervan.
In ieder geval moet men proberen zo weinig mogelijk met memory te schuiven en in te stellen.
Bij meerdere lijsten dan 2 rijgen (methode 1) moet men gaan scannen per element wat ook tijd kost.
Bij 3 lijsten heeft men 3*maximale lengte*2 scans(testen) nodig voor alle elementen van alle lijsten.
Plus nog wat software...
De 2e methode heeft het aantal scans op ongeveer (lijstaantal-1) * (lengten).
Optie Alfa: Als men de lengte van de lijsten eerst scant en dan de kleinste lijsten eerst doet is men sneller.

Met 100 kleine lijsten van 100 elementen gemiddeld komt men op ongeveer 20000 scans voor methode 2.
Voor methode 1 hebben we dan 100*100*2 en is ook 20000.
Dus methode 2 en optie Alfa is men sneller....
Een computertaal is voor mensen, niet voor de computer.

#3

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 23 augustus 2009 - 01:06

Bedoel je iets als mergesort? Het 2e deel van het algoritme is basically wat jij vraagt, toch?
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#4

Schwartz

    Schwartz


  • >250 berichten
  • 691 berichten
  • Verbannen

Geplaatst op 23 augustus 2009 - 20:18

even wat snelheidstestjes gehouden
Het rijgen van 2 gesorteerdelijsten..
Bij twee lijsten van 1000 elementen haal ik met mijn routine een snelheid van 1/12 van de processor snelheid.
Bij twee lijsten van 1 element haal ik een snelheid van 1/355 van de processor snelheid.
Bij 10 en 15 elementen is de snelheid 1/43.5.

Tijdens de runs staat gewoon muziek,internet en norton anti-virus aan e.d..

Ik had niet verwacht dat de routine bij 1000 elementen zo snel kon zijn.
Een computertaal is voor mensen, niet voor de computer.

#5

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 24 augustus 2009 - 09:50

Als je m groot is maak je best gebruik van een loser tree merge algoritme (bv http://sandbox.mc.ed...ec/losedex.html). Bij kleine m (2 of 3 rijen) kies je best voor gewone mergesort. Snellere methodes ga je hier niet voor vinden.

Veranderd door Cycloon, 24 augustus 2009 - 09:51


#6

Aries

    Aries


  • >25 berichten
  • 83 berichten
  • Ervaren gebruiker

Geplaatst op 24 augustus 2009 - 12:02

Het is zoieso een aanrader om geen elementen te sorteren , maar de pointers NAAR de elementen...
dat scheelt nogal ;)

#7

virtlink

    virtlink


  • >100 berichten
  • 158 berichten
  • Ervaren gebruiker

Geplaatst op 25 augustus 2009 - 16:55

Stel ik heb een aantal (m) gesorteerde lijsten die elk een variabel aantal elementen hebben (ze zijn dus niet noodzakelijk even lang) en ik wil hiervan een nieuwe lijst maken met alle elementen in de nieuwe lijst uit de andere lijsten, bestaat er dan een algoritme die sneller de lijst sorteert dan gewoon eerst alle lijsten samenvoegen en QuickSort toepassen.

Wat dacht je van deze: (suggesties en verbeteringen welkom)
Elke stap:
  • Kopieer het element waar de indexpointer naar verwijst uit de volgende lijst naar de nieuwe lijst.
  • Is het nieuwe element kleiner dan het voorgaande, wissel ze dan om.
  • Is het verplaatste nieuwe element kleiner dan het voor-voorgaande, wissel die dan ook om. Etc... totdat het nieuwe element op de juiste plek staat.
In het beste geval, wanneer alle lijsten om-en-om of gelijk gesorteerd zijn (bijv. [1 3 5 7 9][2 4 6 8 10][3 4 7 8 11]) is dit een LaTeX operatie. In het slechte geval, wanneer alle lijsten volledig ongesorteerd zijn, moeten alle elementen verwisseld worden en is dit een LaTeX operatie.
"Niet gehinderd door enige kennis van zaken..."

#8

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 25 augustus 2009 - 21:29

Proficiat met heruitvinden van insertion sort ;)





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures