Profiloin oman ohjelmani ja se viettää aikaansa aivan liikaa etsiessään linkitetystä listasta tietoa.
Aloin kokeilemaan josko sinne voisi oikopolkuja rakentaa. Keskimmäisestä mentäisiin isommalle ja pienemmälle puolelle puoleen väliin jne. Eli temppuun riittäisi kaksi osoitinta lisää.
Yrtän selittää vähän paremmin.
Leikitään että listassa on 16 alkiota. silloin puusta tulisi tämän näköinen:
8/16
4/16 12/16
2/16 6/16 10/16 14/16
1/16 3/16 5/16 7/16 9/16 11/16 13/16 15/16Oikeasti noita huomattavasti enemmän.
Intoa puhkuen hakkasin näppäimistöä viimeyön ja en saanut aikaiseksi mitään toimivaa. Olen myös ihan varma, että joku muukin on tämän tehnyt.
Kiusallinen huomio tuosta on, että jos alkioita on vain kymmenen, tarvitsee puulle tapahtua jotain. Silloinhan 12/16 ei ole olemassa ja 10/16 tarvis nousta ylemmäs ja ja.. Toisaalta jollain hienolla väännöllä tuon 8/16 saisi varmasti puoleen väliin, josta sitten tulisi tasapainoinen puu.
Puuhunhan kiivetään listan ensimmäisestä alkion isosta haarasta.
Onko joku miettinyt tai törmännyt koodiin tai muuhun vastaavaan neuvoon miten tälläinen tehdään?
Binäärihakupuu tai mieluiten tasapainoitettu sellainen on mitä haet.
Tästä voit lähteä liikkeelle: http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
Sitä kautta pitäisi löytyä opastusta myös itse koodin suuntaan.
Minkälaista tietoa tallennat linkittyyn listaan?
Kohtuullisen helppo harjoite binäärihakupuun toiminnan ymmärtämiseen on toteuttaa vaikka morsekoodin tulkkaus binääripuun avulla. Voin auttaa tuossa tarvittaessa, jos et pääse alkuun...
jalski kirjoitti:
Kohtuullisen helppo harjoite binäärihakupuun toiminnan ymmärtämiseen on toteuttaa vaikka morsekoodin tulkkaus binääripuun avulla. Voin auttaa tuossa tarvittaessa, jos et pääse alkuun...
Oma C osaamiseni on hiukan ruosteessa, mutta alla kuitenkin PL/I-toteutus esimerkkinä. Ehkäpä joku minua fiksumpi kuitenkin tuon kääntää nopeasti C-kielelle...
morse: package;
start: procedure options (main);
put list (translate_morse('.- -... -.-.'));
end start;
translate_morse: procedure (morse_sentence)
returns (char (100) var);
dcl morse_sentence char (*);
dcl 1 node based,
2 left ptr init (null()),
2 right ptr init (null()),
2 character char init ('?');
dcl morse_code(26) char(4) var init
('.-', '-...', '-.-.', '-..', '.', '..-.',
'--.', '....', '..', '.---', '-.-', '.-..',
'--', '-.', '---', '.--.', '--.-', '.-.',
'...', '-', '..-', '...-', '.--', '-..-',
'-.--', '--..') static;
dcl alphabet(26) char init
('A', 'B', 'C', 'D', 'E', 'F', 'G',
'H', 'I', 'J', 'K', 'L', 'M', 'N',
'O', 'P', 'Q', 'R', 'S', 'T', 'U',
'V', 'W', 'X', 'Y', 'Z') static;
dcl root ptr static init (null());
dcl (i, k) fixed bin;
dcl p ptr;
dcl sentence char (100) var init ('');
dcl preliminary_character char;
dcl (dim, length, null, substr) builtin;
/* If this is the first call, then setup the binary tree: */
if root = null() then do;
allocate node set (root);
do k = 1 to dim(morse_code);
p = root;
do i = 1 to length(morse_code(k));
select (substr(morse_code(k), i, 1));
when ('.') do;
if p->left = null() then
allocate node set (p->left);
p = p->left;
end;
when ('-') do;
if p->right = null() then
allocate node set (p->right);
p = p->right;
end;
end;
end;
p->character = alphabet(k);
end;
end;
/* Translate morse code: */
p = root;
do i = 1 to length(morse_sentence);
select (substr(morse_sentence,i,1));
when ('.')
p = p->left;
when ('-')
p = p->right;
when (' ') if p ^= root then do;
sentence = sentence || p->character;
p = root;
end;
other /* invalid character */
signal error;
end;
if p = null() then signal error; /* too long */
if p ^= root then preliminary_character = p->character;
end;
if p ^= root then sentence = sentence || preliminary_character;
return (sentence);
end translate_morse;
end morse;EDIT: Korjattu PL/I-koodi. Pitäisi näköjään aina tarkistaa ja kokeilla toiminta ennen viestin lähettämistä.
Et tarvitse linkitettyä listaa, vaan binäärihakupuun. Ei-tasapainottuvan binäärihakupuun koodaaminen (lisäys & poisto -operaatiot) on suht helppoa ja hyvä harjoitus. Puun tasapainon vääristyminen on kuitenkin ikävä ongelma. Esimerkiksi lisättäessä puuhun luvut järjestyksessä 1 3 5 4 7 9 11, voidaan saada seuraavanlainen puu:
1
\
3
\
5
/ \
4 7
\
9
\
11Tästä hakeminen ei ole juurikaan linkitetystä listasta hakemista nopeampaa. Ongelman ratkaisemiseksi on olemassa tietorakenteita, joita kutsutaan tasapainoitetuiksi binäärihakupuiksi. Yleisimmät näistä on AVL-puu ja punamustapuu. Molempien aikavaatimukset haulle, lisäykselle ja poistolle on O(log n). C++:n standardikirjastosta löytyy hakupuiden kaltaiset containerit std::set ja std::map. Useimmissa ympäristöissä ne on toteutettu juurikin punamustapuulla.
Jos käytät C:tä, niin oot kusessa. Etsi netistä jokin valmis koodi/kirjasto ja käytä sitä. Sille on nimittäin hyvä syy, miksi tietorakenteiden peruskursseilla jätetään käsittelemättä (tai kotitehtäväksi) solmun poisto punamustapuusta. Se on nimittäin ihan helvetin vaikea operaatio. AVL-puun koodaaminen on ehkä hieman helpompaa, mutta ei kivaa sekään.
Oma C-implementaatio punamustapuulle löytyy täältä:
http://www.niksula.cs.hut.fi/~hirvolt1/koodia/
Implementaatiossani kahdella solmulla ei saa olla samaa avainta. Lisäykset ja poistot toimivat iteratiivisesti. Katsele netistä myös muiden toteutuksia.
edit. joihinkin tarkoituksiin binäärikeko on riittävä tietorakenne.
Hajautustaulu saattaisi olla sopiva tietorakenne tarkoitukseen. Sen toteuttaminen C:llä on helppoa ja se on tavallisesti hyvin tehokas.
Tosiaan data on linkitetyssä listassa järjestyksessä. Ohjelma kuitenkin viettää aikaansa 85% hakien tuosta listata tietoa. Siksi olisi varmaan fiksua optimoida tuota hakua.
Kun listaan lisätään tai poistetaan harvoin dataa, voisi koko puun tehdä vaikka uudestaan. Silloin on aikaa pomputella bittejä.
Katselin vikipediaa ja siellä oli hienoon javahäkkyrään linkki, jossa scapegoat tree luotiin. Jostain kauniista toteutuksesta voisi lainata ajatusta, koska puu tasapainoitetaan linkitetyn listan kautta.
Tällöin hakualgoritmia tarvitsisi vain muuttaa ja lisäyksen ja poiston yhteydessä luoda puu uudelleen. Lisäksi linkitetty lista jäisi paikoilleen, jotta ketjua indeksoiva maailma toimii.
Tietorakenteet kannattaa valita sen mukaan, mitkä operaatiot ovat tärkeitä. Jos haetaan usein ja muokataan harvoin, taulukko on varsin hyvä vaihtoehto. Silloin binaarihaku onnistuu aivan suoraan mutta uuden tiedon lisääminen esimerkiksi taulukon alkuun vaatii koko taulukon loppuosan siirtämistä.
Indeksointi ja linkitetty lista eivät kuulu yhteen. Taulukon kohdalla indeksoinnin voisi vielä ymmärtää. Hyvä ratkaisu voisi kuitenkin olla se, että korvaisit indeksoinnin osoittimilla ja säilyttäisit taulukossa vain niitä osoittimia.
vuokkosetae kirjoitti:
Tällöin hakualgoritmia tarvitsisi vain muuttaa ja lisäyksen ja poiston yhteydessä luoda puu uudelleen. Lisäksi linkitetty lista jäisi paikoilleen, jotta ketjua indeksoiva maailma toimii.
Myös skiplistissä lista jää paikoilleen.
Skip list oli se mitä kaipasin.
Nyt homma toimii nopeasti. Puu olisi ollut nopea aina, mutta voittoa tulee hyppäämiselläkin tarpeeksi. Yritin ajatella asiaa vain liian vaikeasti miettien, mikä olisi nopein tapa löytää jotain.
Ymmärrän Matabolixin huomion. On vain niin, että nuo on käytävä kaikki järjestyksessä läpi ja tarkkaa määrää en tiedä. Niitä voi olla kymmenistä kymmeniin tuhansiin riippuen annetusta datasta. Lisäksi ne riippuvat toisistaan niin on järkevä saada läpikäynti järjestyksessä, jota tehdään paljon ohjelmassa, nopeaksi helpolla rakenteella ja sitten kun haetaan satunnaista alkiota niin sekin on nopeaa.
Pullonkaula oli siis tuo haku. Ja tuossa listan alkiossa on tosiaan kymmenkunta osoitinta eri muuttujiin ja toisiin alkioihin. Sekä numero tunnistamista varten.
Kiitoksia.
Oman tietokantani suunnitteluvaiheessa lähdin siitä, että nopeus ja tiiveys ovat ratkaisevia. Niinpä alkuolioksi hash-olio, joka muodosti haettavasta avaimen alusta sopivanmittaisen indeksiavaimen, josta oli linkki ensimmäiseen sivuolioon.
Kullakin sivulla sisäisesti langoitettu puu ja avaimista indeksit linkkeihin. alasivuille, jotka olivat per taso aina ylempää tasoa pienempiä (mod 64=0).
Frekvenssien kirjaus kelvollisten löydettyjen avaintietojen osalta auttaa sittemmin balansoimaan puut sivuttain ja tarvittaessa koko hakemistosivuston.
Mitä pidempi on hash-avain, sitä nopeampi on tiedonhaku. Mikäli avainta vastaa useampi kuin yksi referenssitieto, referenssi viittaa listaolioon, johon on taltioitu sama-avaimisten tietojen referenssiosoitteet. Koodaus on simppeliä ja puiden käpistelyssä voi käyttää rekursiivisia proseduureja ja mielivaltaista sekundääriavainten määrää per tietue.
Nopein mahdollinen tapa kannan kyselykielen And/Or/Not ym. soveltamiseksi on binäärivektorien käyttö, jolloin tietokannan tietueen indeksiä vastaava bitti on asetettu tiedon osalta silloin, kun se täyttää tietyn ominaisuuden.
Kun kahta vektoria käsitellään 16 tai 32 bittiä kerrallaan (and,or,ym) saadaan näistä helposti tulosvektoriksi niiden keskinäiset ehdot täyttävä tulosvektori, joka indeksoituna antaa niiden tietueiden osoitteet, jotka vastaavat annettua hakua. 32 indeksin käsittely yhdellä operaatiolla on varsin nopeaa ainakin assembleria käyttämällä.
Vektorioperaatioiden rinnakkainen säikeistys tekee hausta ylivoimaisen nopean.
Esimerkkinä asiakastietokanta, jossa haetaan kaikki 01-alkuiset postinumerot, jotka eivät ole postilokero-osoitteita, voidaan tarvittaessa haun jälkeen nimetä halutuksi hakutermiksi, joka viittaa bittivektoriin. Esimerkiksi 8000 tälläisen osoitteen bittivektori vie tilaa vain 1000 byteä.
Korjaus edelliseen: 1000 * 2/4 = 2000..4000 byteä ja vektori on indeksivektori.
(suom.huom)
Aihe on jo aika vanha, joten et voi enää vastata siihen.