Sortering med STL
Sigurd Stenersen
til sortering.
Gitt at en relativt stor mengde data skal leses inn, og sorteres i en eller
flere rekkefølger... Går det an å si noe generelt (mer eller mindre
uavhengig av STL-implementasjon) om hva som er kjappest - å lese inn data og
sortere dem etterhvert, eller å lese inn alle data først og så sortere dem
etterpå ?
Når jeg sier "sortere etterhvert" mener jeg at man bruker en struktur som
f.eks. std::multiset<> og setter hvert nytt element inn i denne etterhvert
som man leser dem.
Sigurd
Thore B. Karlsen
Det er sannsynligvis raskere å sortere etterpå, siden multiset og
lignende containere er implementert som et tre med individuelt
allokerte noder. Men det er jo lett å teste begge. Bare ikke bruk
iostreams til å lese inn data, for da blir det tregt uansett. :)
--
Be seeing you.
Sigurd Stenersen
> On Sat, 7 Jul 2007 19:30:39 +0200, "Sigurd Stenersen"
> <sig...@utvikling.com> wrote:
>
>>Jeg fant omsider en datamengde som er stor nok til at jeg ønsker å bruke
>>STL
>>til sortering.
>>
>>Gitt at en relativt stor mengde data skal leses inn, og sorteres i en
>>eller
>>flere rekkefølger... Går det an å si noe generelt (mer eller mindre
>>uavhengig av STL-implementasjon) om hva som er kjappest - å lese inn data
>>og
>>sortere dem etterhvert, eller å lese inn alle data først og så sortere dem
>>etterpå ?
>>
>>Når jeg sier "sortere etterhvert" mener jeg at man bruker en struktur som
>>f.eks. std::multiset<> og setter hvert nytt element inn i denne etterhvert
>>som man leser dem.
>
> Det er sannsynligvis raskere å sortere etterpå, siden multiset og
> lignende containere er implementert som et tre med individuelt
> allokerte noder.
I dette tilfellet er det snakk om så mye data at det er aktuelt å tilby
diskbufring som en opsjon, så allokeringene bekymrer meg for en gangs skyld
ikke i det hele tatt. Mitt spørsmål går mere i retning av i hvilken grad de
STL-inkluderte algoritmene funker bedre med "sett-inn-etterhvert" enn med
"sorter-alt-sammen-nå".
> Men det er jo lett å teste begge.
Ja, og det kommer jeg nok til å gjøre. Men det er jo greit å få
"dokumentert" denne problemstillingen på et sted som er egnet for
gjenfinning, og det hadde også vært greit å vite om det går an å si noe mer
eller mindre generelt om dette.
> Bare ikke bruk iostreams til å lese inn data, for da blir det tregt
> uansett. :)
Øhm... Ja, hvis du sier det, så. Men hvordan skal jeg DA få lest inn ?
;o)
Sigurd
Thore B. Karlsen
<sig...@utvikling.com> wrote:
[...]
>>>Når jeg sier "sortere etterhvert" mener jeg at man bruker en struktur som
>>>f.eks. std::multiset<> og setter hvert nytt element inn i denne etterhvert
>>>som man leser dem.
>> Det er sannsynligvis raskere å sortere etterpå, siden multiset og
>> lignende containere er implementert som et tre med individuelt
>> allokerte noder.
>I dette tilfellet er det snakk om så mye data at det er aktuelt å tilby
>diskbufring som en opsjon, så allokeringene bekymrer meg for en gangs skyld
>ikke i det hele tatt. Mitt spørsmål går mere i retning av i hvilken grad de
>STL-inkluderte algoritmene funker bedre med "sett-inn-etterhvert" enn med
>"sorter-alt-sammen-nå".
Hvor mye data er det snakk om?
>> Men det er jo lett å teste begge.
>Ja, og det kommer jeg nok til å gjøre. Men det er jo greit å få
>"dokumentert" denne problemstillingen på et sted som er egnet for
>gjenfinning, og det hadde også vært greit å vite om det går an å si noe mer
>eller mindre generelt om dette.
std::sort() er O(N log(N)), mens multiset::insert() er O(log(N)), så i
teorien skulle de være like raske (siden du kaller multiset::insert()
N ganger.) I praksis må man tenke på effektiviteten til allokatorene
osv.
>> Bare ikke bruk iostreams til å lese inn data, for da blir det tregt
>> uansett. :)
>Øhm... Ja, hvis du sier det, så. Men hvordan skal jeg DA få lest inn ?
>;o)
Bruk fantasien. :)
--
Be seeing you.
Steinar H. Gunderson
> std::sort() er O(N log(N))
Strengt tatt er den vel O(n^2), men ja, den er O(n log(n)) i average-case.
std::stable_sort() er O(n log(n) log(log(n))) eller noe, selv i worst-case :-)
/* Steinar */
--
Homepage: http://www.sesse.net/
Erik Naggum
>> std::sort() er O(N log(N))
> Strengt tatt er den vel O(n^2), men ja, den er O(n log(n)) i
> average-case. std::stable_sort() er O(n log(n) log(log(n))) eller
> noe, selv i worst-case :-)
Du bør antagelig lese <http://en.wikipedia.org/wiki/Big_O_notation> og
gjerne noen artikler eller lærebøker om algoritmer og kompleksitet. Det
ville nok også være lurt å droppe smileys når du uttaler deg om slike ting.
Det høres forøvrig ut som om du holder på å finne opp et sort-program.
Dette er (svært) sjelden god bruk av en programmerers tid. Det finnes
allerede en rekke meget, meget gode fiks ferdige programmer som kan
sortere meget, meget store datasett etter vilkårlig kompliserte
kriterier. Har du f eks behov for å drive med mellomlagring på disk skal
det skrekkelig mye til for at det du sier du vil gjøre nå vil være god
bruk av din tid og ende opp med noe som er god bruk av datamaskinens
tid. Folk har forøvrig installert databasemaskiner som gjør lite annet
enn å kjøre ferdige databasemotorer bare for å slippe å sortere store
datasett. Det skal overraskende lite til før det lønner seg.
Erik Naggum
--
Member of AAAS ACM AMS APS ASA ASL EMS IEEE IMS MAA NMF NYAS PSA
Probability is not about the odds. It is about the belief in the
existence of an alternative outcome, cause, or motive. -- Taleb
ID: 2007-188-75804 http://erik.naggum.no/sources-and-resources/
Sigurd Stenersen
> <sig...@utvikling.com> wrote:
>
>>I dette tilfellet er det snakk om så mye data at det er aktuelt å tilby
>>diskbufring som en opsjon, så allokeringene bekymrer meg for en gangs
>>skyld
>>ikke i det hele tatt. Mitt spørsmål går mere i retning av i hvilken grad
>>de
>>STL-inkluderte algoritmene funker bedre med "sett-inn-etterhvert" enn med
>>"sorter-alt-sammen-nå".
>
> Hvor mye data er det snakk om?
Det kan komme til å dreie seg om noen GB om gangen.
> std::sort() er O(N log(N)), mens multiset::insert() er O(log(N)), så i
> teorien skulle de være like raske (siden du kaller multiset::insert()
> N ganger.) I praksis må man tenke på effektiviteten til allokatorene
> osv.
Jeg antar at det du her refererer til er at vector<> er et "billigere"
alternativ enn andre containere ? I så fall dukker det jo opp andre
problemstillinger, f.eks. reallokeringer ved innsetting når man ikke på
forhånd vet hvor mange elementer det dreier seg om.
Sigurd
Sigurd Stenersen
>* Steinar H. Gunderson @2007-07-07 20:16Z -> Thore B. Karlsen
>>> std::sort() er O(N log(N))
>> Strengt tatt er den vel O(n^2), men ja, den er O(n log(n)) i
>> average-case. std::stable_sort() er O(n log(n) log(log(n))) eller
>> noe, selv i worst-case :-)
>
> Du bør antagelig lese <http://en.wikipedia.org/wiki/Big_O_notation> og
> gjerne noen artikler eller lærebøker om algoritmer og kompleksitet. Det
> ville nok også være lurt å droppe smileys når du uttaler deg om slike
> ting.
Jeg forstår ikke helt hvorfor du går til angrep på det Steinar sier, men det
ville nok være lurt å droppe kritikken av andres smileys inntil du har lært
deg å oppfatte hvem som skriver hva.
> Det høres forøvrig ut som om du holder på å finne opp et sort-program.
Hvem er det du snakker til her ? Så vidt jeg kan se er det ingen av de
andre bidragsyterne som indikerer at de holder på å lage noe, så da er det
kanskje meg du snakker til ? I så fall - nei, det er feil. Jeg holder ikke
på med å finne opp noe som helst. Jeg lager en elegant løsning på et lite
problem i et stort system.
> Dette er (svært) sjelden god bruk av en programmerers tid.
Det er mye dårligere bruk av tid å argumentere for feilaktige konklusjoner,
basert på en mangelfull forståelse av problemstillingen.
> Det finnes
> allerede en rekke meget, meget gode fiks ferdige programmer som kan
> sortere meget, meget store datasett etter vilkårlig kompliserte
> kriterier.
Kan det tenkes at det finnes meget, meget store datasett i sammenhenger der
det ikke er hensiktsmessig å bruke "fiks ferdige programmer" ?
Sigurd
HL
>> Hvor mye data er det snakk om?
>
>Det kan komme til å dreie seg om noen GB om gangen.
GB? Dette blir vel en merkelig benevning på datamengden som skal
sorteres. Det interessante må jo være hvor mange elementer som skal
sorteres.
>> std::sort() er O(N log(N)), mens multiset::insert() er O(log(N)), så i
>> teorien skulle de være like raske (siden du kaller multiset::insert()
>> N ganger.) I praksis må man tenke på effektiviteten til allokatorene
>> osv.
>
>Jeg antar at det du her refererer til er at vector<> er et "billigere"
>alternativ enn andre containere ? I så fall dukker det jo opp andre
>problemstillinger, f.eks. reallokeringer ved innsetting når man ikke på
>forhånd vet hvor mange elementer det dreier seg om.
Vet du noe om sorteringsnøklene på forhånd? Dvs. vil verdiene generelt
komme inn i tilfeldig rekkefølge, eller er det en viss orden i
utgangspunktet?
________
HL
Sigurd Stenersen
> "Sigurd Stenersen" <sig...@utvikling.com> wrote:
>
>>> Hvor mye data er det snakk om?
>>
>>Det kan komme til å dreie seg om noen GB om gangen.
>
> GB? Dette blir vel en merkelig benevning på datamengden som skal
> sorteres. Det interessante må jo være hvor mange elementer som skal
> sorteres.
Hva er det som er merkelig med det ? Jeg skal lese inn noen GB med data og
skrive dem ut i en eller flere sorterte rekkefølger. Som sagt er det
aktuelt å mellombufre på disk for å spare minne, og sorteringsnøklene kan
uten problemer foreligge i minne hele tiden.
Hvis du tenker deg at dataene ligger på et sekvensielt medium til å begynne
med, og skal skrives til et tilsvarende medium så er du i nærheten av det
jeg har å forholde meg til. Det er kanskje antall nøkler som bestemmer
hastigheten på sorteringsalgoritmen, men størrelsen på de aktuelle dataene
er i høyeste grad noe jeg må ta hensyn til...
>>> std::sort() er O(N log(N)), mens multiset::insert() er O(log(N)), så i
>>> teorien skulle de være like raske (siden du kaller multiset::insert()
>>> N ganger.) I praksis må man tenke på effektiviteten til allokatorene
>>> osv.
>>
>>Jeg antar at det du her refererer til er at vector<> er et "billigere"
>>alternativ enn andre containere ? I så fall dukker det jo opp andre
>>problemstillinger, f.eks. reallokeringer ved innsetting når man ikke på
>>forhånd vet hvor mange elementer det dreier seg om.
>
> Vet du noe om sorteringsnøklene på forhånd?
Ikke noe særlig, nei. Data kommer sannsynligvis inn i sortert rekkefølge,
men det er en annen rekkefølge enn de skal ut i. Ellers hadde det ikke vært
mye poeng i å sortere.
> Dvs. vil verdiene generelt
> komme inn i tilfeldig rekkefølge, eller er det en viss orden i
> utgangspunktet?
De kommer inn i en viss orden, den er ikke tilfeldig, men i hvilken grad den
stemmer med de ønskede "ut-rekkefølger" er ikke gitt på forhånd.
Sigurd
Erik Naggum
> Jeg forstår ikke helt hvorfor du går til angrep på det Steinar sier,
> men det ville nok være lurt å droppe kritikken av andres smileys
> inntil du har lært deg å oppfatte hvem som skriver hva.
Du beviser her at du mangler evne til å skille virkeligheten fra dine
forstyrrede fantaseringer om andre mennesker. Du kan ikke heretter
forvente at du vil behandles som annet enn som idiot som bruker sine
egne fantasier om hva andre oppfatter og hva de bør lære seg som
beslutningsgrunnlag for sine idiotiske personangrep. Kort sagt: Når du
oppfører deg slik, behandles du deretter inntil du beviser at du ikke er
så hjernedød som du har vist nå.
>>Dette er (svært) sjelden god bruk av en programmerers tid.
> Det er mye dårligere bruk av tid å argumentere for feilaktige konklusjoner,
> basert på en mangelfull forståelse av problemstillingen.
Jeg noterer meg hvilklet sakligshetsnivå du foretrekker å bevege deg på,
og melder pass. Jeg har ingen interesse av å gjøre noe som helst for at
du skal kunne løse de problemene du har. Tvert imot: Du fortjener ikke å
få hjelp til noe som helst noensinne slik som du oppfører deg her.
> Kan det tenkes at det finnes meget, meget store datasett i
> sammenhenger der det ikke er hensiktsmessig å bruke "fiks ferdige
> programmer" ?
Du stiller tilbakestående, idiotiske retoriske spørsmål som du har vett
til, og du får det samme svaret som om du oppfører deg slik helt alene:
Stillhet.
Folk bør legge merke til deg og hvordan du oppfører deg slik at de ikke
gir deg noen hjelp til å løse problemene dine. Ditt fokus her på Usenet
er ikke å få hjelp til å løse noen problemer, men å drite deg loddrett
ut ved å drive et åndssvakt maktspill. Du er kort og godt ikke den typen
menneske som kan ta del i den type informasjons- og erfaringsutveksling
som Usenet var ment som.
Erik Naggum
--
Member of AAAS ACM AMS APS ASA ASL EMS IEEE IMS MAA NMF NYAS PSA
Probability is not about the odds. It is about the belief in the
existence of an alternative outcome, cause, or motive. -- Taleb
ID: 2007-189-82189 http://erik.naggum.no/sources-and-resources/
Sigurd Stenersen
>Stillhet.
Den stillheten var øredøvende, du...
God bedring !
Sigurd
Erik Naggum
> Den stillheten var øredøvende, du...
>
> God bedring !
Takk for at du beviser det jeg sa. Ditt fokus er ikke teknisk
problemløsning, men et eller annet forstemmende primitivt personlig
problem som du ikke har vett til å få løst før du prøver deg på tekniske
problemer som du kunne ha fått hjelp til her om du klarte å konsentrere
deg om det tekniske du spør om.
Erik Naggum
--
Member of AAAS ACM AMS APS ASA ASL EMS IEEE IMS MAA NMF NYAS PSA
Probability is not about the odds. It is about the belief in the
existence of an alternative outcome, cause, or motive. -- Taleb
ID: 2007-190-30336 http://erik.naggum.no/sources-and-resources/
Sigurd Stenersen
>
Jeg håper at den nordmora som forløste deg ikke fikk betalt for jobben, for
du er faen ikke rett navla...
Sigurd
Erik Naggum
> Jeg håper at den nordmora som forløste deg ikke fikk betalt for
> jobben, for du er faen ikke rett navla...
Herregud, du er jo blitt aldeles sinnssyk nå. Men takk for at du
/fortsetter/ å bevise alt jeg har sagt om deg og dertil beviser at du
ikke engang evner å konsentere deg om å få løst det tekniske problemet
du spurte om, men nå har gått helt over til sinnssyke anfall i
personangrepene dine. Det er noe /virkelig/ alvorlig galt med deg som
når du ber om hjelp fra et forum av flinkere folk enn deg, begynner med
den adferden du nå legger for dagen.
Det er følgelig bevist hinsides enhver tenkelig tvil at det du trenger
hjelp til, ikke har noe som har med C++ å gjøre, men de psykiske
problemene dine.
Folk som ber om hjelp, men ikke klarer å konsentere seg om det de
trenger hjelp til når de får respons de ikke forventer, men isteden
begynner med den typen frådende galskap som du gjør her, er så
mislykkede mennesker at det er viktig at man får dem til å oppføre seg
slik som deg. Deretter må folk minnes på adferden til sånt søppel som
deg neste gang du ber om hjelp.
Erik Naggum
--
Member of AAAS ACM AMS APS ASA ASL EMS IEEE IMS MAA NMF NYAS PSA
Probability is not about the odds. It is about the belief in the
existence of an alternative outcome, cause, or motive. -- Taleb
ID: 2007-190-73984 http://erik.naggum.no/sources-and-resources/
Sigurd Stenersen
Erik Naggum
> He he he ;o)
>
> Du er faen ikke rett navla.
Det må være et kompliment når det kommer fra noe sånt som deg.
Får du løst sorteringsproblemet ditt? Får du noe mer hjelp?
Erik Naggum
--
Member of AAAS ACM AMS APS ASA ASL EMS IEEE IMS MAA NMF NYAS PSA
Probability is not about the odds. It is about the belief in the
existence of an alternative outcome, cause, or motive. -- Taleb
ID: 2007-191-31633 http://erik.naggum.no/sources-and-resources/
Bjorn Borud
|
| GB? Dette blir vel en merkelig benevning på datamengden som skal
| sorteres. Det interessante må jo være hvor mange elementer som skal
| sorteres.
hvis du skal sortere veldig store datamengder har størrelsen som
oftest mer å si enn antallet elementer.
-Bjørn
--
There had better be cheese at the end of this maze!
Sigurd Stenersen
> Får du løst sorteringsproblemet ditt? Får du noe mer hjelp?
Jeg har ikke problemer. Jeg løser problemer.
Det aktuelle problemet var løst lenge før du meldte din interesse, men når
sant skal sies så har du jo en viss underholdningsverdi...
God bedring !
Sigurd
Erik Naggum
> Jeg har ikke problemer. Jeg løser problemer.
*LER* Fantastisk. Du har vel aldri løst et problem i ditt liv, men det
er klart en sånn stakkar som deg /tror/ han har ikke har problemer og
/tror/ han løser problemer. Det er nok slik du har blitt slik du har blitt.
> Det aktuelle problemet var løst lenge før du meldte din interesse,
> men når sant skal sies så har du jo en viss underholdningsverdi...
Er dette noe du synes er vondt å høre når noen sier det til deg? Det er
nemlig en ganske fantastisk avslørende ting å si. Underholdningen her er
det jo du som står for. Jeg har ikke sett noen drite seg så
ettertrykkelig ut på en programmeringsnewsgruppe siden, vel, sist gang
du dret deg loddrett ut. Jeg hadde dessverre glemt navnet ditt fra
forrige prestasjon du stod for, men ettersom du falt tilbake på den
samme tilbakestående, sinnssyke adferden, ble det jo nødvendig å sjekke
historien din. Du er sannelig ikke blitt friskere siden sist. Men det er
vel sånn det er for deg når du ikke har problemer...
> God bedring !
Du burde kanskje vurdere å slutte å bruke deg seg til å gjette deg til
hvordan andre har det. Bare et vennlig tips. Du ender opp så langt ute
på jordet at det er relativt alarmerende. Sånt som deg pleier å jo å dø
i en ulykke og nomineres til Darwin-prisen på grunn av åndssvak kløning.
Det er dessverre /svært/ tydelig at du er alvorlig mentalt syk med store
og varige problemer med å justere holdningene dine i forhold til den
virkelige verden, så disse «god bedring»-greiene dine er vel det du
håper at noen skal si til deg en dag, men da må du oppføre deg mindre
sykt. Jeg håper bare at du blir sykere og sykere, naturligvis, for da
blir du morsommere og morsommere.
Erik Naggum
--
Member of AAAS ACM AMS APS ASA ASL EMS IEEE IMS MAA NMF NYAS PSA
Probability is not about the odds. It is about the belief in the
existence of an alternative outcome, cause, or motive. -- Taleb
ID: 2007-191-75859 http://erik.naggum.no/sources-and-resources/
Sigurd Stenersen
>Jeg håper bare at du blir sykere og sykere, naturligvis, for da
>blir du morsommere og morsommere.
He he he ;o)
Du er faen ikke rett navla...
Sigurd
Erik Naggum
> He he he ;o)
>
> Du er faen ikke rett navla...
Hyggelig av deg å bevise hvor alvorlig sinnssyk du faktisk er. Men stå
på, wonderboy! Det finnes muligens noen igjen som ikke har forstått hvor
syk du er, og som trenger å se deg i aksjon over enda litt lengre tid,
der du har kjørt deg fast i det samme alvorlig mentalt syke sporet som
tidligere. Med litt innsats kan du sørge for at du aldri noensinne vil
få hjelp igjen, og dét er jo faktisk målet mitt. Sånt som deg må ikke
hjelpes, hverken med evt tekniske problemer eller med de svært morsomme
personlige problemene deres.
Erik Naggum
--
Member of AAAS ACM AMS APS ASA ASL EMS IEEE IMS MAA NMF NYAS PSA
Probability is not about the odds. It is about the belief in the
existence of an alternative outcome, cause, or motive. -- Taleb
ID: 2007-192-00183 http://erik.naggum.no/sources-and-resources/
Sigurd Stenersen
Erik Naggum
> [Ingenting.]
Det er så kult at nettopp en sånn sinnssyk stakkar som deg bruker C++.
Det er ikke det at man /må/ være en sinnssyk stakkar for å bruke C++,
men det er nå komisk at det nettopp er de som er sprudlende sinnssyke
som bruker C++, og som ikke engang klarer å konsentrere seg om sine
tekniske problemer, men må vise hele verden hvor ødelagt psyke de har.
Stå på, wonderboy! Du kan kanskje være en nyttig idiot for å vise at
normale mennesker bør bruke noe annet. Jeg håper du bruker perl, også.
Erik Naggum
--
Member of AAAS ACM AMS APS ASA ASL EMS IEEE IMS MAA NMF NYAS PSA
Probability is not about the odds. It is about the belief in the
existence of an alternative outcome, cause, or motive. -- Taleb
ID: 2007-192-73891 http://erik.naggum.no/sources-and-resources/
Sigurd Stenersen
Erik Naggum
> He he he ;o)
>
> Du er faen ikke rett navla...
Da er jeg fornøyd. Det er ikke lenger mulig å tro at du noensinne kommer
til å fungere noe bedre enn du gjør nå. Neste gang du ber om hjelp, blir
det viktig å minne folk på hvor alvorlig defekt du faktisk er, slik at
ingen begår den alvorlige feilen å gi et så mislykket menneske som deg
bistand.
Erik Naggum
--
Member of AAAS ACM AMS APS ASA ASL EMS IEEE IMS MAA NMF NYAS PSA
Probability is not about the odds. It is about the belief in the
existence of an alternative outcome, cause, or motive. -- Taleb
ID: 2007-193-00565 http://erik.naggum.no/sources-and-resources/