Samojen stringien poisto stringlistista

Voihan sen järjestyksen ensin tallentaa, sitten tehdä järjestystavalla ja lopuksi järjestää uudelleen tallennetun järjestyksen avulla.

Anonyymi kirjoitti:

Voihan sen järjestyksen ensin tallentaa, sitten tehdä järjestystavalla ja lopuksi järjestää uudelleen tallennetun järjestyksen avulla.

No se on totta.

Sellainen lisähuomio vielä, että yleensä kannattaa miettiä myös pidemmällä tähtäimellä, mitä haluaa ohjelmissaan tehdä. Jos poimit kolmasosan string-listastasi toiseen listaan ja haluat poistaa ne sitten alkuperäisestä listasta, niin nuo molemmat kannattaa tehdä samalla kertaa (ellei ole jotain syytä, miksi niin ei voisi tehdä). Eli samalla kun lisäät stringlist2:een stringin, poista se stringlist1:stä. Silloin et joudu käymään listoja läpi yhtäkään ylimääräistä kertaa.

Anonyymi kirjoitti:

No se on totta.

Ei ubuntussa tarvitse stringlistissa, se toimii ilmankin.

Ei tässä haettu samaa asiaa jonkun toisen koodaamana, vaan tehokkaampaa tapaa tehdä se.

meld tekee yhdistelmä listoja, ei mitään apua tässä tehtävässä.

diff on meld työkaluun nähden käänteinen, ja siitä olisi apua, mutta tulostus täytyisi siistiä.

Ehdottomasti kaikki ylimääräinen grafiikka kannattaa riisua, ja sillä voi olla yllättävänkin suuri vaikutus. Riittävän isolla datamäärällä (miljoona riviä on jo varsin paljon) algoritmin valinta on kuitenkin ylivoimaisesti merkittävin tekijä.

Jos n = 1 000 000, niin O(n^2)-algoritmi, vie noin biljoona aikayksikköä, kun taas O(n*log(n)) vie vain kymmenen miljoonaa aikayksikköä, eli aikavaativuus putoaa sadastuhannesosaan vaihtamalla tehokkaampaan algoritmiin.

Esimerkkinä lajittelusta, jossa 559 610 (yli puoli miljoonaa) merkkijonoa lajitella pituusjärjestykseen (pisin viimeiseksi), vie hiukan yli puoli sekuntia (real 0,630s).

Tulos saavutetaan kun lajittelu ulkoistetaan cat, awk, sort ja cut komentojen yhteiseksi tehtäväksi.

Anonyymi kirjoitti:

Esimerkkinä lajittelusta, jossa 559 610 (yli puoli miljoonaa) merkkijonoa lajitella pituusjärjestykseen (pisin viimeiseksi), vie hiukan yli puoli sekuntia (real 0,630s).

Tulos saavutetaan kun lajittelu ulkoistetaan cat, awk, sort ja cut komentojen yhteiseksi tehtäväksi.

Lue lisää

Aivan riippumatta siitä, miten sen käytännössä toteutat (itse koodaten vai muiden palikoilla leikkien), algoritmi on se, millä on väliä. Jos käsittelet miljoonan rivin datan O(n^2)-algoritmilla, se vie (noin) sata tuhatta kertaa kauemmin kuin O(n*log(n))-algoritmilla.

Keksin että yksi avainsana oli binary search. En ole vielä tarkastanut toimiiko se oikein mutta Delphin TStringList.Find käyttää binääristä hakua kun IndexOf käytti lineaarista. Ensin TStringList.sort niin StringList sortataan (en tiedä miten se konekielitasolla menee kuin 15 merkin jono sortataan). Tämän jälkeen Find funktio palauttaa index-parametrina poistettavan stringin indeksin toisella listilla jotta se voidaan deletoita. Näyttää tunnin algoritmi putoavan muutamaan minuuttiin.

Muita vaihtoehtoja voisi olla kuulemma järjestysluvullinne array. Pitäisi päästä vertailemaan järjestyslukuja, jolloin se olisi yksi komento tai yksi kohta muistissa, ei vertailemaan 15 merkin merkkijonona. Joku hash list, dictionary tai joku. Tehostuisi ehkä vielä suhteessa binäärihakuun.

Anonyymi kirjoitti:

Keksin että yksi avainsana oli binary search. En ole vielä tarkastanut toimiiko se oikein mutta Delphin TStringList.Find käyttää binääristä hakua kun IndexOf käytti lineaarista. Ensin TStringList.sort niin StringList sortataan (en tiedä miten se konekielitasolla menee kuin 15 merkin jono sortataan). Tämän jälkeen Find funktio palauttaa index-parametrina poistettavan stringin indeksin toisella listilla jotta se voidaan deletoita. Näyttää tunnin algoritmi putoavan muutamaan minuuttiin.

Muita vaihtoehtoja voisi olla kuulemma järjestysluvullinne array. Pitäisi päästä vertailemaan järjestyslukuja, jolloin se olisi yksi komento tai yksi kohta muistissa, ei vertailemaan 15 merkin merkkijonona. Joku hash list, dictionary tai joku. Tehostuisi ehkä vielä suhteessa binäärihakuun.

Lue lisää

Mitkään hakualgoritmit, lajittelualgoritmit tai valinta-algoritmit eivät ole varteen otettavia vaihtoehtoja, huippuunsa viritetylle ja juuri tätä tehtävää varten luodulle ulkoiselle komennolle.

Vai mitä olet mieltä, kun suoritamme "kai" -merkkijono haun, tiedostosta, joka sisältää yli puoli miljoonaa erilaista merkkijonoa, ja suoritus vie vain 0,017s, tuottaen tiedoston jossa on 5 917 löytynyttä.

Ei tätä voi nopeuttaa millään, siispä opettelemme ulkoistamaan tehtäviä tausta suorituksena. Ellet vielä osaa, nyt on korkea aika opetella.

Anonyymi kirjoitti:

Mitkään hakualgoritmit, lajittelualgoritmit tai valinta-algoritmit eivät ole varteen otettavia vaihtoehtoja, huippuunsa viritetylle ja juuri tätä tehtävää varten luodulle ulkoiselle komennolle.

Vai mitä olet mieltä, kun suoritamme "kai" -merkkijono haun, tiedostosta, joka sisältää yli puoli miljoonaa erilaista merkkijonoa, ja suoritus vie vain 0,017s, tuottaen tiedoston jossa on 5 917 löytynyttä.

Ei tätä voi nopeuttaa millään, siispä opettelemme ulkoistamaan tehtäviä tausta suorituksena. Ellet vielä osaa, nyt on korkea aika opetella.

Lue lisää

Millä taikuudella sinä luulet niiden komentojen toimivan? Algoritmi on siellä taustalla joka tapauksessa, ja toki sellainen komento johon on käytetty järkevää algoritmia, kannattaa valita, mutta kyse on silti täsmälleen samasta asiasta: haluatko käyttää tehokkaampaa vai vähemmän tehokasta algoritmia.

Jos et itse osaa ajatella asiaa, joudut luottamaan sokeasti siihen, että juuri se sinun valitsemasi komento on sattumalta tehty tähän nimenomaiseen tapaukseen järkevällä algoritmilla. Jos osaat ajatella, voit toki käyttää satunnaista komentoa jos laiskottaa, tai sitten voit miettiä, mikä algoritmi on kyseiseen tehtävään paras, ja käyttää sitä, joko itse koodattuna tai jostain valmiista paketista löydettynä.

Anonyymi kirjoitti:

Ehdottomasti kaikki ylimääräinen grafiikka kannattaa riisua, ja sillä voi olla yllättävänkin suuri vaikutus. Riittävän isolla datamäärällä (miljoona riviä on jo varsin paljon) algoritmin valinta on kuitenkin ylivoimaisesti merkittävin tekijä.

Jos n = 1 000 000, niin O(n^2)-algoritmi, vie noin biljoona aikayksikköä, kun taas O(n*log(n)) vie vain kymmenen miljoonaa aikayksikköä, eli aikavaativuus putoaa sadastuhannesosaan vaihtamalla tehokkaampaan algoritmiin.

Lue lisää

Poistin ruudulle tulostettan laskurin arvon joka siis käy yhdestä puoleentoistamiljoonaan ja nyt ei tulostu mitään tietoa missä mennään niin ohjelma nopeutui 40 minuutista 4 minuuttiin. Näyttäs toimivan. Mietityttää vaan voiko sillä olla niin iso ero ettei kirjoiteta tuota ruudulle? Vai pakko olla bugi? Mut toistaalta laitoin vain kommenttimerkit yhden rivin eteen.

Anonyymi kirjoitti:

Millä taikuudella sinä luulet niiden komentojen toimivan? Algoritmi on siellä taustalla joka tapauksessa, ja toki sellainen komento johon on käytetty järkevää algoritmia, kannattaa valita, mutta kyse on silti täsmälleen samasta asiasta: haluatko käyttää tehokkaampaa vai vähemmän tehokasta algoritmia.

Jos et itse osaa ajatella asiaa, joudut luottamaan sokeasti siihen, että juuri se sinun valitsemasi komento on sattumalta tehty tähän nimenomaiseen tapaukseen järkevällä algoritmilla. Jos osaat ajatella, voit toki käyttää satunnaista komentoa jos laiskottaa, tai sitten voit miettiä, mikä algoritmi on kyseiseen tehtävään paras, ja käyttää sitä, joko itse koodattuna tai jostain valmiista paketista löydettynä.

Lue lisää

Käyttöjärjestelmän komennot (grep) kuten tuossa edellisessä oli on vuosien työn tulos, jota hiotaan aina vain paremmaksi. Minä en luota omiin enkä sinun kykyihin tuottaa tehokkaampaa kuin olemassa olevat komennot jo on.

Myöskään itse komennon käyttämä algoritmi ei kiinnosta, riittää että on tehokas ja toimii. On erittäin tyhmää keksiä pyörä joka kerta uudestaan, kun vielä ottaa huomioon se tosiasian että itse tehtynä siitä tulisi merkittävästi huonompi, ja toteuttaminen veisi useita vuosia.

Anonyymi kirjoitti:

Käyttöjärjestelmän komennot (grep) kuten tuossa edellisessä oli on vuosien työn tulos, jota hiotaan aina vain paremmaksi. Minä en luota omiin enkä sinun kykyihin tuottaa tehokkaampaa kuin olemassa olevat komennot jo on.

Myöskään itse komennon käyttämä algoritmi ei kiinnosta, riittää että on tehokas ja toimii. On erittäin tyhmää keksiä pyörä joka kerta uudestaan, kun vielä ottaa huomioon se tosiasian että itse tehtynä siitä tulisi merkittävästi huonompi, ja toteuttaminen veisi useita vuosia.

Lue lisää

Näistä tehoja vaativien tehtävien ulkoistamisesta, graafisen liittymän ulkopuolelle, on sekin hyöty että prosessien suoritus säikeisettään ja silloin tehtävä annetaan ytimelle, jolla sillä hetkellä on vähiten kuormaa.

Anonyymi kirjoitti:

Käyttöjärjestelmän komennot (grep) kuten tuossa edellisessä oli on vuosien työn tulos, jota hiotaan aina vain paremmaksi. Minä en luota omiin enkä sinun kykyihin tuottaa tehokkaampaa kuin olemassa olevat komennot jo on.

Myöskään itse komennon käyttämä algoritmi ei kiinnosta, riittää että on tehokas ja toimii. On erittäin tyhmää keksiä pyörä joka kerta uudestaan, kun vielä ottaa huomioon se tosiasian että itse tehtynä siitä tulisi merkittävästi huonompi, ja toteuttaminen veisi useita vuosia.

Lue lisää

Totta kai yksittäinen komento on (yleensä) optimoitu suurin piirtein niin tehokkaaksi kuin mahdollista. Jos sellainen on tarjolla siihen tehtävään, joka sinun pitäisi saada aikaan, se on todennäköisesti paras vaihtoehto.

Mutta tosiasia on kuitenkin se ettei joka ikiselle asialle, minkä joku joskus voisi kuvitella haluavansa tietokoneella tehdä, ole olemassa omaa yksittäistä komentoa, ja heti kun ketjutat edes kaksi (saati sitten useampia) komentoa, sinä luot uuden algoritmin, jonka palaset kyllä ovat tehokkaita, mutta kokonaisuus voi olla äärimmäisen typerä ja tehoton jos et yhtään osaa ajatella algoritmisesti. Jos valikoit nuo tehokkaat komennot niin, että lopputulos on O(n^2)-algoritmi, se on riittävän isolla datalla väistämättä huonompi ratkaisu kuin tehottomalla tavalla itse koodattu O(n*log(n))-algoritmi. Toki vielä parempi on jos osaat miettiä tehokkaiden komentojen käytön niin, että saat niillä toteutettua sen O(n*log(n))-algoritmin.

Anonyymi kirjoitti:

Ehdottomasti kaikki ylimääräinen grafiikka kannattaa riisua, ja sillä voi olla yllättävänkin suuri vaikutus. Riittävän isolla datamäärällä (miljoona riviä on jo varsin paljon) algoritmin valinta on kuitenkin ylivoimaisesti merkittävin tekijä.

Jos n = 1 000 000, niin O(n^2)-algoritmi, vie noin biljoona aikayksikköä, kun taas O(n*log(n)) vie vain kymmenen miljoonaa aikayksikköä, eli aikavaativuus putoaa sadastuhannesosaan vaihtamalla tehokkaampaan algoritmiin.

Lue lisää

Koska kysymys on "yleistä ohjelmoinnista" -palstalla, se ei ota kantaa ohjelmointikieleen.

Delphissä:

Kannattaa huomata:

type
TStringList = class(TStrings)
...
end;

ja myös:

TMemoStrings = class(TStrings)
...
end;

TListBoxStrings = class(TStrings)
...
end;

nuo TMemoStrings ja TListBoxStrings ovat siis sinänsä ihan oikeita tyyppejä, mutta referenssit noihin ovat usein tyy ppiä TStrings .

siis esim:

var
SL : TStrings;

SL := Memo1.Strings;

ShowMessage(SL.Classname); // tulostaa "TMemoStrings"

SL := ListBox1.Items;

ShowMessage(SL.Classname); // tulostaa "TListBoxStrings"

Mitään hitaita operaatioita EI PIDÄ koskaan suorittaa suoraan TMemoStrings eikä TListBoxStrings -luokkien objekteille !

Jos hitaita operaatioita tarvitaan, suorita ne aina TStringList -luokan ilmentymälle eli objektille.

Lisäksi:

delete() on periaatteessa hidas operaatio, ja mitä lähempänä listan alkua poistettava merkkijono on, sitä hitaampi operaatio.

siis kannattaa mieluummin tehdä for i := SL.Count-1 downto 0 -silmukka.

Myös Sort() -operaatio muuttuu hitaaksi, jos listassa on satoja tuhansia merkkijonoja (tai jopa yli miljoona),

Jos listassa on vaikkapa katuosoitteita (siis alkaa kadun nimellä) niin kannattaa jakaa kukin alkukirjain erikseen ja tehdä useita TStringList -objekteja, yksi kullekin alkukirjaimelle. Kannattaa samalla harkita, kuinka haluaa käsitellä isot/pienet kirjaimet.

Olisi muuten testaamisen arvoinen asia:
Onko delete() tai insert() -operaatio nopeampi "linked list" -toteutuksessa verrattuna Delphin TStringList -luokan käyttämään toteutukseen ?

Muistioperaationa on nopeampi, mutta tietyn kohdan etsiminen muuttuu samalla hitaammaksi.

Onkohan kukaan keksinyt hybriditietorakennetta, jolla saataisiin taulukon ja "linked LIST" -ratkaisujen parhaat puolety yhdistettyä ?

Anonyymi kirjoitti:

Aivan riippumatta siitä, miten sen käytännössä toteutat (itse koodaten vai muiden palikoilla leikkien), algoritmi on se, millä on väliä. Jos käsittelet miljoonan rivin datan O(n^2)-algoritmilla, se vie (noin) sata tuhatta kertaa kauemmin kuin O(n*log(n))-algoritmilla.

Lue lisää

"Jos käsittelet miljoonan rivin datan O(n^2)-algoritmilla, se vie (noin) sata tuhatta kertaa kauemmin kuin O(n*log(n))-algoritmilla."

Peraatetasolla varmaan ihan totta.

Käytännön huomioina silti:

1. ONKO tuo log(n) millainen logaritmi? Siis 10-kantainen, 2-kantainen vai ns. luonnollinen logaritmi, jossa kantalukuna on ns. neperin luku, jota merkitään yleensä symbolilla e ?

2. QuickSort -algoritmia monet pitävät nopeana.
Mutta onko kyseinen algoritmi kuitenkaan se paras (ja jos on, onko siitä useita erilaisia toteutuksia, jotka eroavat huomattavasti nopeudeltaan) ?

2a) omia kokemuksia:
QuickSort -algoritmi on suhteellisen nopea, jos lajiteltavia alkioita on enintään 100.000 (sata tuhatta). Tätä suuremmilla määrillä QäuickSort -algoritmi voi osoittautua yllätt
vän hitaaksi !

2b) Netistä luettua: QuickSort -algoritmi on erityisen hidas silloin, jos lähtöaineisto on jo ennestään melkein lajiteltu, mutta siellä on muutamia yksittäisiä alkioita, jotka ovat väärässä järjestyksessä.

Voi hyvin olla, että USEIMMISSA tapauksissa QuickSort -algoritmi on nopein vaihtoehto.

ENTÄ, jos algoritmit pisteytetään nopeuden mukaan siten, että kullekin algoritmille annetaan lajiteltavaksi sellainen lähtöaineisto, että kukin algoritmi suoriutuu hitaimmalla mahdollisella tavalla?

Eli verrataan kutakin algoritmia vertaillaan nimenomaan kyseiselle algoritmille omin aisen ns. "worst case" -tapauksen mukaan.

Mikä on tällöin paras algoritmi lajitteluun (oletetaan aineiston kooksi 2 miljoonaa merkkijonoa ja jakaumaksi kullekin algoritmille sellainen, josta on tiedossa, että moinen järjestysjakauma erityisesti hidastaa ko. algoritmia) ?

Anonyymi kirjoitti:

Keksin että yksi avainsana oli binary search. En ole vielä tarkastanut toimiiko se oikein mutta Delphin TStringList.Find käyttää binääristä hakua kun IndexOf käytti lineaarista. Ensin TStringList.sort niin StringList sortataan (en tiedä miten se konekielitasolla menee kuin 15 merkin jono sortataan). Tämän jälkeen Find funktio palauttaa index-parametrina poistettavan stringin indeksin toisella listilla jotta se voidaan deletoita. Näyttää tunnin algoritmi putoavan muutamaan minuuttiin.

Muita vaihtoehtoja voisi olla kuulemma järjestysluvullinne array. Pitäisi päästä vertailemaan järjestyslukuja, jolloin se olisi yksi komento tai yksi kohta muistissa, ei vertailemaan 15 merkin merkkijonona. Joku hash list, dictionary tai joku. Tehostuisi ehkä vielä suhteessa binäärihakuun.

Lue lisää

Delphin TStringList:

Tuo binäärihakua käyttävä toimii oikein vain, jos Sorted = True.

Toisaalta esim. insert ja add saattavat olla hitaampia, jos Sorted = True.

Jouduin joskus itse lajittelemaan Delphin TStringList -luokan objektin, jossa oli satojatuhansia merkkijonoja (kukin alkoi kadun nimellä).

Delphin oma Sort -metodi (tai Sorted := True) olivat hyvin hitaita.

Päädyin jakamaan nuo kadun nimet 29 eri TStringList -luokan objektiksi, eli ensimmäiseen tuli "A" -kirjaimella alkavat kadunnimet ja viimeiseen "Ö" -kirjaimella alkavat kadunnimet.

Sitten kullekin TStringList -luokan objektille oma erillinen Sort -metodikutsu.

Tämä tapa oli huomattavasti nopeampi kuin koko pitkän listan lajittelu kerralla.

Anonyymi kirjoitti:

Poistin ruudulle tulostettan laskurin arvon joka siis käy yhdestä puoleentoistamiljoonaan ja nyt ei tulostu mitään tietoa missä mennään niin ohjelma nopeutui 40 minuutista 4 minuuttiin. Näyttäs toimivan. Mietityttää vaan voiko sillä olla niin iso ero ettei kirjoiteta tuota ruudulle? Vai pakko olla bugi? Mut toistaalta laitoin vain kommenttimerkit yhden rivin eteen.

Lue lisää

"voiko sillä olla niin iso ero ettei kirjoiteta tuota ruudulle"

Kyllä voi ja usein onkin !

Jos silti haluat tiedon ruudulle, tee se fiksusti !

esim näin:

Työsäie (periytetty TThread -luokasta)

päivittää muuttujaa, joka ilmaisee joko valmistumisasteen prosentteina, tai sitten (vieläkin nopeampi) läpikäydyn kappalemäärän ja kokonaiskappalemäärä toiseen muuttujaan.

Jos muuttujat on määritelty globaalisti näin:

var
LapiKayty : Longword;
KokonaisKPLMaara : Longword;

niin silloin voi GUI -säikeeseen tehdä vaikkapa formilla olevalla TTimer -komponentilla (Interval = 250) OnTimer -käsittelijän, joka lukee molemmat muuttujat paikallisiin kopioihin näin:

var
A,B : Longword;
PerCent : Double;
S, S1 : String;

begin
A := LapiKayty;
B := KokonaisKPLMaara;

PerCent := LapiKayty * 100.0 / KokonaisKPLMaara;

Str(PerCent:5:1, S1);

S := S1 ' % läpikäyty';

lblProgress.Caption := S;
lblProgress.Repaint;

end;

Teoriassa tuossa kuuluisi lukita nuo muuttujat LapiKayty ja KokonaisKPLMaara (ks. TCriticalSection), mutta koska ne molemmat ovat CPU -rekisterin kokoisia (32 bit) ja ovat muistissa 4:LLÄ jaollisessa osoitteessa, niin tuosta syystä tuo lukitseminen ei ole ihan niin pakollista kuin moni luulee.

Jos haluaa olla ihan 100% varma, ettei eri säikeet aiheuta konfliktia keskenään, niin ks. myös:

InterlockedExchangeAdd ja InterlockedIncrement .

Siis työsäie voisi kasvattaa LapiKayty :
InterlockedIncrement (LapiKayty );

Ja GUI -säie voisi lisätä arvoon LapiKayty vakion nolla, ja napata tuloksen talteen:
InterlockedExchangeAdd (LapiKayty , 0)

JOS tuo viimeinen antaa käännösvirheen, niin korjaa näin:
InterlockedExchangeAdd (@LapiKayty , 0)

Tuolla tavalla hidas näytön päivitys tehdään vain 4 kertaa sekunnissa sensijaan, että se tehtäisiin jokaisen alkion kohdalla (mikä olisi todella hidasta).

Anonyymi kirjoitti:

"voiko sillä olla niin iso ero ettei kirjoiteta tuota ruudulle"

Kyllä voi ja usein onkin !

Jos silti haluat tiedon ruudulle, tee se fiksusti !

esim näin:

Työsäie (periytetty TThread -luokasta)

päivittää muuttujaa, joka ilmaisee joko valmistumisasteen prosentteina, tai sitten (vieläkin nopeampi) läpikäydyn kappalemäärän ja kokonaiskappalemäärä toiseen muuttujaan.

Jos muuttujat on määritelty globaalisti näin:

var
LapiKayty : Longword;
KokonaisKPLMaara : Longword;

niin silloin voi GUI -säikeeseen tehdä vaikkapa formilla olevalla TTimer -komponentilla (Interval = 250) OnTimer -käsittelijän, joka lukee molemmat muuttujat paikallisiin kopioihin näin:

var
A,B : Longword;
PerCent : Double;
S, S1 : String;

begin
A := LapiKayty;
B := KokonaisKPLMaara;

PerCent := LapiKayty * 100.0 / KokonaisKPLMaara;

Str(PerCent:5:1, S1);

S := S1 ' % läpikäyty';

lblProgress.Caption := S;
lblProgress.Repaint;

end;

Teoriassa tuossa kuuluisi lukita nuo muuttujat LapiKayty ja KokonaisKPLMaara (ks. TCriticalSection), mutta koska ne molemmat ovat CPU -rekisterin kokoisia (32 bit) ja ovat muistissa 4:LLÄ jaollisessa osoitteessa, niin tuosta syystä tuo lukitseminen ei ole ihan niin pakollista kuin moni luulee.

Jos haluaa olla ihan 100% varma, ettei eri säikeet aiheuta konfliktia keskenään, niin ks. myös:

InterlockedExchangeAdd ja InterlockedIncrement .

Siis työsäie voisi kasvattaa LapiKayty :
InterlockedIncrement (LapiKayty );

Ja GUI -säie voisi lisätä arvoon LapiKayty vakion nolla, ja napata tuloksen talteen:
InterlockedExchangeAdd (LapiKayty , 0)

JOS tuo viimeinen antaa käännösvirheen, niin korjaa näin:
InterlockedExchangeAdd (@LapiKayty , 0)

Tuolla tavalla hidas näytön päivitys tehdään vain 4 kertaa sekunnissa sensijaan, että se tehtäisiin jokaisen alkion kohdalla (mikä olisi todella hidasta).

Lue lisää

"PerCent := LapiKayty * 100.0 / KokonaisKPLMaara;"

siis piti olla:

PerCent := A* 100.0 / B;

Eli käytä laskemiseen paikallisia kopioita muuttujista !

Siinä mielessä totta, että:

Käytä tosiaan tiedon prosessoinnissa aitoa TStringList -tyyppiä.

Älä käytä tyyppiä, joka on näennäisesti TStrings, mutta tosiasiassa se voi olla esim:

TMemoStrings

tai

TListboxStrings!

Noiden käyttö voi olla todella hidasta, kun GUI -käyttöliittymää päivitetään samalla kun prosessoidaan tietoa!

Vinkki Delphin käyttäjälle:

var
SL : TStrings;

// lataa tässä SL -muuttuja osoittamaan haluamaasi stringlistaan.

// Todellinen tyyppi selviää näin:

memLog.Lines.Add('SL:n Todellinen tyyppi on: ' + SL.ClassName);

Jos tuo tulostaa
TMemoStrings
tai
TListboxStrings

niin silloin ohjelmasi on väärin tehty ja kaipaa korjausta / uudelleensuunnittelua.

Ongelmaa voi muuten vähentää (mutta ei kokonaan poistaa) näin:

SL.BeginUpdate;
try

finally
SL.EndUpdate;
end;

Käytä aitoa TStringList -tyyppiä, se on vakiotyypeistä nopein.

Anonyymi kirjoitti:

Koska kysymys on "yleistä ohjelmoinnista" -palstalla, se ei ota kantaa ohjelmointikieleen.

Delphissä:

Kannattaa huomata:

type
TStringList = class(TStrings)
...
end;

ja myös:

TMemoStrings = class(TStrings)
...
end;

TListBoxStrings = class(TStrings)
...
end;

nuo TMemoStrings ja TListBoxStrings ovat siis sinänsä ihan oikeita tyyppejä, mutta referenssit noihin ovat usein tyy ppiä TStrings .

siis esim:

var
SL : TStrings;

SL := Memo1.Strings;

ShowMessage(SL.Classname); // tulostaa "TMemoStrings"

SL := ListBox1.Items;

ShowMessage(SL.Classname); // tulostaa "TListBoxStrings"

Mitään hitaita operaatioita EI PIDÄ koskaan suorittaa suoraan TMemoStrings eikä TListBoxStrings -luokkien objekteille !

Jos hitaita operaatioita tarvitaan, suorita ne aina TStringList -luokan ilmentymälle eli objektille.

Lisäksi:

delete() on periaatteessa hidas operaatio, ja mitä lähempänä listan alkua poistettava merkkijono on, sitä hitaampi operaatio.

siis kannattaa mieluummin tehdä for i := SL.Count-1 downto 0 -silmukka.

Myös Sort() -operaatio muuttuu hitaaksi, jos listassa on satoja tuhansia merkkijonoja (tai jopa yli miljoona),

Jos listassa on vaikkapa katuosoitteita (siis alkaa kadun nimellä) niin kannattaa jakaa kukin alkukirjain erikseen ja tehdä useita TStringList -objekteja, yksi kullekin alkukirjaimelle. Kannattaa samalla harkita, kuinka haluaa käsitellä isot/pienet kirjaimet.

Olisi muuten testaamisen arvoinen asia:
Onko delete() tai insert() -operaatio nopeampi "linked list" -toteutuksessa verrattuna Delphin TStringList -luokan käyttämään toteutukseen ?

Muistioperaationa on nopeampi, mutta tietyn kohdan etsiminen muuttuu samalla hitaammaksi.

Onkohan kukaan keksinyt hybriditietorakennetta, jolla saataisiin taulukon ja "linked LIST" -ratkaisujen parhaat puolety yhdistettyä ?

Lue lisää

"Onkohan kukaan keksinyt hybriditietorakennetta, jolla saataisiin taulukon ja "linked LIST" -ratkaisujen parhaat puolety yhdistettyä ?"

Onhan noita, jokin puurakenne esimerkiksi. Puurakenteessa haku, lisääminen ja poistaminen ovat erittäin tehokkaita. Ongelma on balansointi, jonka puuttuessa puun oksat saattavat kehittyä vaihtelevan mittaisiksi. Ääritapauksessa puurakenne pelkistyy linkitetyksi listaksi, jolloin tehokkuusetu katoaa kokonaan. Balansointi leikkaa tehokkuudesta hieman, mutta esimerkiksi Red-black-algoritmissa balansoinnin tuoma lisäkuorma on verrattain vähäinen.

Anonyymi kirjoitti:

"Jos käsittelet miljoonan rivin datan O(n^2)-algoritmilla, se vie (noin) sata tuhatta kertaa kauemmin kuin O(n*log(n))-algoritmilla."

Peraatetasolla varmaan ihan totta.

Käytännön huomioina silti:

1. ONKO tuo log(n) millainen logaritmi? Siis 10-kantainen, 2-kantainen vai ns. luonnollinen logaritmi, jossa kantalukuna on ns. neperin luku, jota merkitään yleensä symbolilla e ?

2. QuickSort -algoritmia monet pitävät nopeana.
Mutta onko kyseinen algoritmi kuitenkaan se paras (ja jos on, onko siitä useita erilaisia toteutuksia, jotka eroavat huomattavasti nopeudeltaan) ?

2a) omia kokemuksia:
QuickSort -algoritmi on suhteellisen nopea, jos lajiteltavia alkioita on enintään 100.000 (sata tuhatta). Tätä suuremmilla määrillä QäuickSort -algoritmi voi osoittautua yllätt
vän hitaaksi !

2b) Netistä luettua: QuickSort -algoritmi on erityisen hidas silloin, jos lähtöaineisto on jo ennestään melkein lajiteltu, mutta siellä on muutamia yksittäisiä alkioita, jotka ovat väärässä järjestyksessä.

Voi hyvin olla, että USEIMMISSA tapauksissa QuickSort -algoritmi on nopein vaihtoehto.

ENTÄ, jos algoritmit pisteytetään nopeuden mukaan siten, että kullekin algoritmille annetaan lajiteltavaksi sellainen lähtöaineisto, että kukin algoritmi suoriutuu hitaimmalla mahdollisella tavalla?

Eli verrataan kutakin algoritmia vertaillaan nimenomaan kyseiselle algoritmille omin aisen ns. "worst case" -tapauksen mukaan.

Mikä on tällöin paras algoritmi lajitteluun (oletetaan aineiston kooksi 2 miljoonaa merkkijonoa ja jakaumaksi kullekin algoritmille sellainen, josta on tiedossa, että moinen järjestysjakauma erityisesti hidastaa ko. algoritmia) ?

Lue lisää

Diplomi hönö.

Anonyymi kirjoitti:

Keksin että yksi avainsana oli binary search. En ole vielä tarkastanut toimiiko se oikein mutta Delphin TStringList.Find käyttää binääristä hakua kun IndexOf käytti lineaarista. Ensin TStringList.sort niin StringList sortataan (en tiedä miten se konekielitasolla menee kuin 15 merkin jono sortataan). Tämän jälkeen Find funktio palauttaa index-parametrina poistettavan stringin indeksin toisella listilla jotta se voidaan deletoita. Näyttää tunnin algoritmi putoavan muutamaan minuuttiin.

Muita vaihtoehtoja voisi olla kuulemma järjestysluvullinne array. Pitäisi päästä vertailemaan järjestyslukuja, jolloin se olisi yksi komento tai yksi kohta muistissa, ei vertailemaan 15 merkin merkkijonona. Joku hash list, dictionary tai joku. Tehostuisi ehkä vielä suhteessa binäärihakuun.

Lue lisää

Tosiaan, Delphissä:

TStringList on oikea tyyppi tuohon listaan.

Huomaa:

Käsiteltäessä TMemo ja TListBox -tyyppejä, niissä on sisäisesti:

Memo.Lines : TMemoStrings;

Listbox.Items : TListboxStrings;

Nuo TMemoStrings ja TListboxStrings ovat molemmat TStrings -luokasta periytettyjä tyyppejä, mutta ovat käsittääkseni määritelty unitin implementation -osassa, joten nuo tyypit eivät näy unitin ulkopuolelle, joten yritys käyttää niitä johtaa käännösvirheeseen tuntemattomasta tyypistä.

Tosiaan, älä koskaan tee noita operaatioita suoraan TMemo.Lines eikä TListBox.Items -propertyllä (jotka ulkoisesti on määritelty TStrings -tyypeiksi), koska graafisen liittymän jatkuva päivittely tekee hommasta superhidasta - BeginUpdate ja EndUpdate parantaa asiaa hieman, mutta en silti käyttäisi noita, vaan luo itse TStringList -tyyppinen objekti.

Huomaa:

TStringList -tyypissä on Sorted -property (Boolean)

Ainakin joissain kohdissa VCL -koodi tarkistaa, onko Sorted True, ja jos on, käyttää binäärihakua, mutta jos False, käytetään hitaampaa lineaarihakua.

QuickSortin väitetään olevan nopea (nopein ?).
Mutta vaikka asia usein noin onkin, ei aina.... jos listan alkuperäinen järjestys on QuickSortin kannalta "patologinen" niin siinä tapauksessa QuickSort on yllättävän hidas!

Olen itse havainnut:
Delphillä TStringList -luokan operaatioissa:

JOS listan pystyy jakamaan useaan pienempään listaan, ja käsittelemään yksi pikkulista kerrallaa yhden ison listan sijasta, ajoaika putoaa usein murto-osaan aiemmasta yhdellä isolla listalla tehdystä!

Jos merkkijonot sisältävät suomenkielistä tekstiä, vois tehdä näin:

var
Listat : Array[0..30] of TStringList;

Listat[0] = ennen A -kirjainta tulevat asiat
Listat[1] .. Listat[29] = Kirjaimilla "A" .. "Ö" alkavat asiat
Listat[30] Ö -kirjaimella alkavien asioiden jälkeen tulevat asiat.

Jos jaat molemmat listat alkukirjaimen mukaan 31 alalistaksi (osa niistä voi olla tyhjiä),
kokonaissuoritusaika todennäköisesti putoaa huomattavasti verrattuna yhteen jättikokoiseen listaan.

Huomaa1:
Toki voit periyttää oman luokkasi TStringList -tyypistä ja käyttää sitä.
Näin voit optimoida jonkin tietyn toiminnon, jos huomaat, että jokin TStringList -tyypin alkuperäinen metodi on vain liian hidas.


Huomaa2:
Ainakin Delphi7:n HLP -tiedostossa on virhe!
Koskee TStringList.CustomSort -metodia (tarkemmin sen käyttäjän määrittelemää Compare -funktiota joka EI voi olla luokan metodi, vaan sen on oltava itsenäinen funktio):

Dokumentointi dokumentoi juuri väärinpäin arvojen -1 ja +1 merkitykset... asia on juuri päinvastoin kuin Delphi7:n dokumentointi väittää.

Kokeile jollain pienellä muutaman merkkijonon TStringListalla ja kun käytät CustomSort -funktiota, huomaat kyllä, mistä on kyse.

Pienten listojen tulokset saa kätevästi näkyviin näin:

Memo1.Text := SL.Text; // Missä SL:TStringList;

Jumbokokoisten listojen osalta ylläolevaa EI suositella - jättilistojen tapauksessa tuo johtaa ongelmiin.

Minä olen ollut sitä jo 18 vuotta.

Anonyymi kirjoitti:

Minä olen ollut sitä jo 18 vuotta.

Niin, mutta, minä olen paras.

Eli siis stringit pois, ja häshimään!
#hashset

Anonyymi kirjoitti:

Eli siis stringit pois, ja häshimään!
#hashset

Thä häh, luulin sitä kirjoitusvirheeksi, perun puheeni, en ole paras, enkä käytä noita ollenkaan.

"Onko Delphissä valmiina joukko-tietorakennetta"

Kyllä on. ks. avainsana (Reserved Word): Set.

"Tee siitä listasta, josta kysytään onko stringi siellä, joukko."

Delphissä tuo ei onnistu.
Joukko on joukko asioita, joista kukin mahtuu joko tyyppiin BYTE tai muuhun sellaiseen tyyppiin, että SizeOf(tyyppi) = 1.

BYTEn lisäksi sallittuja ovat vakiotyypeistä ShortInt, AnsiChar sekä ne käyttäjän määrittelemät tyypit, joissa S SizeOf(tyyppi) = 1.

Eli vaikka Delphissä on joukot, ne eivät sovellu tapauksiin, joissa joukon alkiot ovat merkkijonoja.

Poikkeus:

Jos eivät ole mielivaltaisia merkkijonoja, vaan kukin merkkijono on vakio, ja noita vakiomerkkijonoja on enintään 256 erilaista, silloin voisi määritellä oman luetellun tyypin, ja laittaa sen eri arvot vastaamaan 256 erilaista vakiomerkkijonoa.

Mikä vertailu

CRC32 on toki nopea, mutta muuten väärä valinta tuohon!
Ongelma on varsin suuri todennäköisyys, että 2 tai useampi merkkijono tuottaa saman CRC-32 -arvon.

md5 on parempi, eräät uudemmat ns "Cryptographically Strong Hash" -funktiot ovat vieläkin parempia.

Esim. SHA-256.

Erityisesti, jos käytät 64 -bittistä (uudehkoa) versiota Delphistä, niin SipHash voisi olla houkutteleva vaihtoehto.

https://en.wikipedia.org/wiki/SipHash

Vaikka se on HASH -pituudeltaan md5:ttäkin lyhyempi (64-Bit versio) tai sama (128-Bit versio), on se uudempi ja ilmeisesti kryptografiselta vahvuudeltaan parempi.
md5:stä on löytynyt tiettyjä heikkouksia, sovelluksen tavasta käyttää md5:tä riippuu se onko noilla heikkouksilla ehkä hyvinkin vakava merkitys vai eikö ole.

Tätä olen aina ihmetellyt:
Miksi monet olettavat, että kun hyökkääjä yrittää arvata jonkin salaisen avaimen tai sitä käyttäen lasketun tiivisteen, niin ikään kuin väärät arvaukset eivät vaikuttaisi mitään tai niitä ei huomattaisi.

Usein ohjelman voi kirjoittaa niin, että se havaitsee tällaisen arvailun ja reagoi siihen jotenkin.

Yksi vaihtoehto voisi olla että kun pyyntöä epäillään häiriköinniksi, sen käsittelyyn lisätään viive ( esim. Windowsissa Sleep(N) ), jossa N >= 1 (N EI saa olla <= 0).

Toki tuossa täytyy miettiä, miten säikeitä käytetään oikein.

Huomaa myös:
Windowsissa, jos kutsut Sleep(1), niin viive on aina vähintään 1 ms mutta usein se on n. 15-16 ms. Toki, jos jokin käynnissä oleva ohjelma on kutsunut TimeBeginPeriod(1) niin sitten se todellakin on sen 1 ms.

GetTickCount:lla voi tarkistaa asian:

var
T1, T2, dT : Longword;

T1 := GetTickCount;
Sleep(1);
T2 := GetTickCount;
dT := T2 - T1; // RangeCheck ja OverFlowCheck OFF !!!

dT kertoo, montako millisekuntia meni Sleep(1) -suoritukseen.

Yllä esimerkki, miten GetTickCount -funktiota käytetään oikein.
Olen nähnyt paljon muiden kirjoittamaa koodia, jossa GetTickCount -funktiota käytetään väärin, ja harmejahan väärinkäytöstä seuraa.
Esim sellaisia, että kun ohjelma ( tai Windows )on ollut käynnissä 49-50 vrk, niin silloin ohjelma alkaa "mystisesti" toimia väärin tai menee jumiin.

Johtuu siitä, että 32- bittinen arvo pyörähtää ympäri, kun n. 49,71 vuorokautta on kulunut, koska silloin kuluneiden ms määrä vastaa arvoa 2**32.

Täällä on tarkemmin kerrottu, kuinka tuon oman joukko-tietorakenteen voi toteuttaa:

https://stackoverflow.com/questions/33529763/is-there-a-hashset-in-delphi/33530037#33530037

Voipi johtua muistimallin valinnasta eli rajoituksissa usein lukee, että allokoitavan muistin koko on maksimissaan megatavu/ohjelma? Esim. tiny-mallissa koko ohjelman maksimikoko on 64kt ja tuohon ei kovin paljoa dataa mahdu.

Tähän ketjuun kirjoittaneilla on aivan sama mikä käyttöjärjestelmä niillä on, ne ei ikinään opi käyttämään sitä, ovat niin saatanan typeriä elukoita.