Sortiranje

[VolkD]

Pravzaprav nisem vedel kam bi tole uvrstil. Ne gre za programski jezik ampak za algoritme, ki pa se lahko aplicirajo v več različnih programskih jezikih, lahko pa se aplicirajo kar v resničnem življenju. Pri slednjem ne potrebujemo jezika, programa ali računalnika na sploh. V tej točki bo nadaljevanje sicer malo offtopic, a boljše rubrike za to ne najdem.
Da ne bom ljudi obremenjeval s kakim od jezikov in da se bomo bolj posvetili algoritmu samemu, bom zadeve pokazal na realnem problemu sortiranja tranzistorjev v TO-220 ohišju.

[VolkD]

Na zgornji fotografiji vidimo cel kup škatel z vrečkami. Pravzaprav škatel sploh nebi smeli gledati. V tej točki razlage je najbolje, da jih kar zanemarite, oziroma bomo rekli, da so tam zato, da se vrečke ne premikajo vse povsod in da se ne pomešajo med seboj. No to je celo res.
Imamo torej niz sortiranih vrečk z elementi. Na zgornji sliki je okrog 500 različnih vrečk.

500 vrečk je odločno preveč, da bi vam lahko razložil najbolj osnovne stvari o sortiranju. Je pa dovolj, da lahko trdimo, da je 500 vrečk preveč, da bi po njih iskali en določen element, če vrečke nebi bile sortirane.
Tudi če so posortirane, je iskanje nekega elementa v povprečju dolgo polovico števila vrečk, če iščemo po vrsti.

Kolikokrat pa pravzaprav potrebujemo iskanje po vrečkah. Ja, najmanj, ko iščemo nek določen element in to ne glede na to ali ga najdemo ali ne.
Je pa pri tem treba vedeti, da to funkcijo potrebujemo vsakič, ko hočemo v zbirko vstaviti nek element.

Sortiranje na tak način postane torej z večanjem števila elementov časovno zelo zahtevno. Pri takem tipu sortiranja se čas sortiranja s številom elementov povečuje s kvadratično funkcijo.

Temu sortiranju kot je prikazano tu, rečemo sortiranje z vstavljanjem.
Poznamo še precej drugih sortiranj, ki so bolj sofisticirana, imajo pa zato boljšo časovno odvisnost glede na število elementov, a čas sortiranja z naraščanjem števila elementov še vedno raste eksponencialno. Taki algoritmi so recimo sort vsak z vsakim, mehurčasto urejanje, urejanje s kopico.
Ta zadnji je pravzaprav izboljšan sort z vstavljanjem.

Vsem tem algoritmom je skupno to, se čas sortiranja definira na sledeč način:
t = K *n^2
Pri čemer je:
t - čas
n - število elementov
K neka konstanta, ki je lastna posameznim tipom sorta. Pri tem je treba vedeti, da je K lahko precej različen ne samo od danega algoritma ampak tudi od tega kakšno ( oziroma koliko ) posortirano množico elementov imamo za sortiranje.
Ravno zato je nemogoče reči kateri tip sorta je najboljši. Če k temu dodamo, da bomo algoritem uporabili na računalniku, pa je ta K odvisen še od lastnosti računalnika.

[VolkD]

Pasjansa!

Imam neko (ne preveliko) količino novih elementov, ki jih je treba dodati v našo zbirko.
Če bi te elemente dodali že obstoječi zbirki in to posortirali z enim od naših (kvadratičnim) že znanim algoritmom, bi to bilo časovno zelo potratno. Jasno saj bi bilo število vseh elementov (obe množici skupaj) zelo veliko, do zdaj opisani algoritmi pa imajo časovno odvisnost definirano z n^2.
Kako rešiti ta problem bolj elegantno ?
Najprej posortiramo nove elemente z enim od znanih algoritmov ( da ne kompliciramo lahko kar z vstavljanjem ). Temu delu jaz rečem pasjansa. Zlagam torej elemente na tak način, da so nekako urejeni. Točno kaj počnem bom opisal kasneje ( je pa to na sliki lep primer).
Tako dobim manjšo množico tranzistorjev, ki so urejeni. Ker je množica majhna gre tako sortiranje hitro.
Nato pa to množico združim z mojo prejšnjo veliko množico, ki je tudi že posortirana. Je kar nekaj načinov kako to narediti efikasno. Vsi pa temeljijo na zlitju dveh množic v eno. Angleško se temu reče merge. Po naše pa sortiranje z zlivanjem.

[VolkD]

Točno kaj počnem bom opisal kasneje ( je pa to na sliki lep primer).

V prejšnjem prispevku sem odprl dve temi o sortiranju. Bom najprej razložil tole, kasneje pa še eno obliko merge sorta.
Da bi razložil tole malo bolj, si še enkrat oglejte sliko:

V zgornji vrstici imamo pet tranzistorjev tipa 2SA, v naslednji vrstici so tranzistorji, katerih oznaka se začne z 2SB, v tretji vrstici je množica tranzistorjev tipa 2SC,.... in tako naprej vse do 2SK in desno zgoraj še skupina tranzistorjev katerih oznaka se začne z 2SJ.
Imamo torej 6 množic tranzistorjev. V vsako od teh množic vstavljamo nove elemente po sistemu sorta ki je tipa n^2. Brez da bi ogrozili časovno odvisnost si to lahko privoščimo, saj smo en velik problem razdelili na več majhnih. Majhni problemi pa so dokaj hitri četudi je sort tipa n^2.
Takemu sortiranju, kjer kreiramo več podmnožic rečemo sort z indeksom.

Moja pasjansa na fotografiji, pa je seveda samo ena podmnožica vseh tranzistorjev in je indeksirana z indeksom 2S, razdeljena pa na A, B, C, D, K, J.

[VolkD]

..., kasneje pa še eno obliko merge sorta.

Rezultat moje pasjanse je torej množica japonskih sortiranih tranzistorjev 2S skupine. Ampak najbolj bistveno je, da so elementi sortirani.
Da bi končno dobili samo eno množico posortiranih elementov (tranzistorjev) moramo že posortirano množico vseh tranzistorjev na pravi način zmešati z to novo 2S množico.
To kar bom zdaj opisal je ena od možnih variant merge sorta.
Recimo, da se lotimo od elementov (oznak tranzistorjev) z najnižjimi vrednostmi in to v obeh skupinah.
■ Vzamemo torej najnižji element iz skupine 2S in najnižji element iz skupine VSEH. Elementa primerjamo med seboj. Nižjega vzamemo in uvrstimo v novo množico (v stari ga ni več), za naslednjo primerjavo pa vzamemo prvi višji element iz te iste množice. Potem postopek ponovimo v točki ■.
Pri tem početju imamo lahko dve različni izjemni situaciji.
1 - oba elementa sta enaka. Pri računalniškem sortiranju se v tem primeru vzame za manjšega enega od obeh. Poenostavljeno gledano je vseeno katerega, podrobne analize so prinesle v določenih primerih prednost, če vzamemo tistega iz večje množice. Pri sortiranju tranzistorjev pa v takem primeru odpremo ustrezno vrečko in vanjo vstavimo tranzistor, ki ima enako oznako, kot napisa na vrečki.
2 - v eni od množic je zmanjkalo elementov. Iz preostale množice prepišemo vse elemente v novo nastalo množico.

Nakazal bom še na drugo možnost merge sorta. Stvari se lahko lotimo z drugega konca. Torej vzamemo največje elemente obeh množic in jih primerjamo med seboj. Vse ostalo je recipročno enako kot pri merge sort-u, kjer začnemo z najmanjšimi elementi.

Postavi se vprašanje, če sta obe obliki ekvivalentni. Torej glede na časovno odvisnost / število elementov, ekvivalentni ? odgovor je JA in NE.
Vse je namreč odvisno od podatkov. Vsi vemo, da traja primerjanje + prepisovanje dlje kot samo prepisovanje. Želja torej je, da v eni od množic čim prej zmanjka podatkov.
Izboljšani merge sort se naslanja ravno na to dejstvo. V odvisnosti kako velika je nova množica podatkov, ki jo je treba "zmešati" v staro množico, se naredi "sondiranje" podatkov v stari množici. Z upoštevanjem najvišjega in najnižjega elementa v novi množici in z sondiranimi podatki se lahko potem odločimo za en ali drug tip merge sorta.
Pri peš sortiranju tranzistorjev nam je hitro jasno kako je s tem, saj te tranzistorje valjamo po rokah in se čudimo kako veliko japonskih je med njimi. japonski se skoraj vsi začno z 2S, taki in podobni pa so stari posortirani množici na začetku. Torej se splača začeti z manjšimi vrednostmi.
Računalniški program, medtem ko sortira nič ne gleda lastnosti podatkov. Torej mora s "sondiranjem" ugotoviti kaj se izplača.

[VolkD]

Pri vsakem primerjanju elementov ugotavljamo ali je prvi element večji, enak ali manjši od drugega. Računalnik s tem nima problemov, vse je točno definirano in jasno.
Človek ima drugačen način razmišljanja; zelo hitro bomo ugotovili, da je ljudem naravno normalno eno, računalniku pa nekaj povsem drugega.
In če smo že pri japonskih tranzistorjih, bi bilo prav, da damo en primer s tega področja.
Imamo množico desetih tranzistorjev tipa 2SB in sicer(vpisujem tako kot jemljem s predalčka): 2SB824, 2SB712, 2SB1375, 2SB834, 2SB1273, 2SB1344, 2SB857, 2SB1340, 2SB799.

Takole sem tranzistorje posortiral jaz:

Vendar se računalnik sploh ne strinja z menoj !
V čem je problem ?

[VolkD]

Mimogrede, a ste opazili, da je največ zelenih ohišij ravno v skupini 2SB tranzistorjev ?
No računalnika to ne briga, ima drugačen razlog, da se ne strinja z menoj!

[ivor]

V čem je problem ?

Kot da računalnik gleda samo številke, črke ga sploh ne brigajo.

Mimogrede, a ste opazili, da je največ zelenih ohišij ravno v skupini 2SB tranzistorjev ?

Japonci so pameten narod. Tranzistorje NPN in PNP takoj ločijo že po barvi. NPN (2SD...) so navadno črni, PNP (2SB...) pa zeleni. Tudi drugi se včasih držijo tega sistema, kar veliko olajša delo s takimi tranzistorji.

[DusanK]

Računalnik je prepameten, ker med 2SB najde 2SD799 vsiljivca... pasjansa karte se premešajo ponovno.

[VolkD]

Oba imata prav.
Računalnik dela narobe samo, če dobi napačne podatke. Te podatke mu seveda da človek. In ta isti človek bo v glavi ločil številke od črk in bo po vsej verjetnosti hotel sortirati številke v rastočem vrstnem redu, brez da bi upošteval, da imajo nekatere številke samo tri mesta, druge pa štiri mesta.

[VolkD]

Računalnik nam teh naših 10 tranzistorjev ( elementov) vrne posortirano tako kot je na fotografiji.
Deluje nekako čudno, saj so taki tranzistorji, ki imajo številke 1000 in več, prej od tistih, ki imajo številko manjšo od 1000. Ampak na četrtem mestu oznake je enica, ki je manjša od recimo sedmice. In prav je tako, le mi se moramo naučiti, da je vse skupaj ena sama oznaka.
Še bolj nerazumljivo za človeško glavo je, ko imamo recimo tranzistorje z oznako BD161, BD162, BDX53, BDW53.
Če človeku zelo hitro postane jasno, da so najprej številke potem pa črke, potem je treba reči, da so mnogim črke, ki jih niso vajeni kar problematične. Velika večina ljudi bo rekla, pa saj je zgornji niz že posortiran.
No računalnik bo to razvrstil drugače BD161, BD162, BDW53, BDX53.

Ta razlaga je pomembna. To pa zato, ker se bomo v resničnem življenju srečali z resničnimi tranzistorji, ki jih bo treba poiskati v povsem resničnem svetu. In če so naša pričakovanja drugačna od tega kar nam ponudi računalnik, potem imamo problem in to kljub temu, da je v resnici vse korektno sortirano.

[VolkD]

Računalnik je prepameten, ker med 2SB najde 2SD799 vsiljivca... pasjansa karte se premešajo ponovno.

Prav ima seveda računalnik, ampak to, da je vsiljivec prišel v naše območje ni nič hudega, saj bo zdaj pravilno sortiran.

Nam pa ta primer razkrije še eno skrivnost merge sorta. Merge sort predvideva, da sta obe množici, tako stara (velika) in nova (manjša) ( to kar je v oklepajih ni nujno res, sort deluje vseeno) že posortirani. Torej je vsak naslednji element iz posamezne množice enak ali večji prejšnjemu. Če temu ni tako, potem je nekaj narobe. Na ta način se odkrivajo napake v sortiranju.
In te napake se odkrivajo v obeh svetovih (virtualnem in fizičnem). Če je v fizičnem svetu jasno kako do napake pride, je to za virtualni svet malo težje razložiti. No v okolju, kjer stalno lahko podatke vzdržuje in spreminja veliko ljudi, se lahko zgodi, da nekdo spremeni recimo B v D v neki oznaki, ravno v trenutku, ko sort deluje.
Vem, zdaj bo nekdo takoj rekel, da to ni mogoče, saj računalnik ve kaj je kje in kakšno je. To sicer drži, a le za algoritme, ki ne porabijo praktično nič dodatnega prostora (en trenutni element). Zamenjava dveh elementov med seboj zahteva nek delovni prostor, sicer bi se podatek prekril. Tovrstni algoritmi pa so vsi glede na število elementov časovno zelo slabi.
Algoritmi, ki delujejo hitreje potrebujejo več delovnega prostora za urejanje. Pri računalniku je ta prostor večinoma niz pointerjev, ki kažejo na podatke. Pointerji so po sortiranju urejeni v vrstnem redu, ki ustreza sortu. Manj potratno je namreč prepisovati in spreminjati tabelo pointerjev, kot pa celotne zapise z vsemi podatki. Ampak zadnja faza nekega sorta je seveda prepis celotnega zapisa v novo tabelo, ki je urejena glede na kriterij sorta, torej po vrstnem redu pointerjev. Če po začetku sorta in tik pred to fazo nekdo drug spremeni v nekem zapisu B v D bomo imeli problem v obliki napačno posortirane tabele. Te in seveda tudi druge probleme se rešuje z nadzorom dostopa do podatkov. Najenostavnejši nadzor je, če posege v tabelo, ki jo sortiramo za čas sorta prepovemo. Če je podatkov malo in so sorti hitri ( beri trajajo malo časa ) potem je rešitev čisto v redu. Če pa nedosegljivost podatkov traje dlje časa ( lahko uro ali več; v današnjih časih nekaj minut) potem bodo ostali uporabniki znoreli. Sodobne baze podatkov poznajo nedosegljivost na nivoju vpisa enega stavka ( Record locking ), a ta ne reši našega problema sortiranja, saj ne vemo kateri stavek zakleniti, ker so na udaru vsi. Naslednji nivo je ( Field locking) ta ne dovoljuje spreminjanja posameznih polj v bazi podatkov. To problem sorta sicer reši, a ne povsem v celoti. Je pa to problem, ki je že izven domene sortiranja in ga lahko obdelujemo kdaj drugič, kje drugje.
Če se vrnemo na moje tranzistorje na mizi, naj povem, da se napaka zgodi, če nekdo poskuša sortirati stvari časovno paralelno z menoj. Lahko pa se zgodi preprosto zato, ker je D podoben B, če je zapis malo slabše čitljiv.
Zgoraj smo omenili porabo prostora, ki ga naše sortiranje zahteva. K temu se bomo še vrnili.

[DusanK]

IMG_20230304_091218.jpg

Računalnik nam teh naših 10 tranzistorjev ( elementov) vrne posortirano tako kot je na fotografiji.
Deluje nekako čudno, saj so taki tranzistorji, ki imajo številke 1000 in več, prej od tistih, ki imajo številko manjšo od 1000. Ampak na četrtem mestu oznake je enica, ki je manjša od recimo sedmice. In prav je tako, le mi se moramo naučiti, da je vse skupaj ena sama oznaka.
Še bolj nerazumljivo za človeško glavo je, ko imamo recimo tranzistorje z oznako BD161, BD162, BDW53, BDX53.
Če človeku zelo hitro postane jasno, da so najprej številke potem pa črke, potem je treba reči, da so mnogim črke, ki jih niso vajeni kar problematične. Velika večina ljudi bo rekla, pa saj je zgornji niz že posortiran.
No računalnik bo to razvrstil drugačeBD161, BD162, BDX53, BDW53.

Ta razlaga je pomembna. To pa zato, ker se bomo v resničnem življenju srečali z resničnimi tranzistorji, ki jih bo treba poiskati v povsem resničnem svetu. In če so naša pričakovanja drugačna od tega kar nam ponudi računalnik, potem imamo problem in to kljub temu, da je v resnici vse korektno sortirano.

Kdor je vsaj malo delal sortiranje z npr. MS Excel-om mu je tako sortiranje jasno in nič neobičajno.
Moj računalnik v Excelu (SLO-2010) drugače posortira kot tvoj ali pa si se zatipkal:
Tvoj sort: BD161, BD162, BDX53, BDW53
Moj sort: BD161, BD162, BDW53, BDX53

Sortira po mešanici angleško-slovenskem razporedu v sledečem zaporedju:
BDQ53
BDŠ53
BDV53
BDW53
BDX53
BDY53
BDZ53
BDŽ53

[VolkD]

Moj računalnik v Excelu (SLO-2010) drugače posortira kot tvoj ali pa si se zatipkal:

Zatipkal sem se. Pravzaprav ne zatipkal, ampak sem naredil copy/paste napačnih vrstic.
Hvala za opozorilo in prispevek.

[VolkD]

Na zgornji fotografiji vidimo cel kup škatel z vrečkami. Pravzaprav škatel sploh nebi smeli gledati.

Naj ponovno pokažem za katero fotografijo se gre:

Mislim, da smo v točki, ko je treba upoštevati škatle. Razložil bom namreč sort z indeksom.
Ko postane množica elementov velika in 500 vrečk je za človeka gotovo veliko, je sort z vstavljanjem časovno potraten, saj je treba pravo pozicijo za vstavljanje iskati preko vseh 500 vrečk. Stvar naključja (predpostavljam, da je element, ki ga dodajamo naključen) je, kje jo najdemo. V povprečju pa moramo pregledati vsaj 250 vrečk.
Če opazujemo kako to ljudje običajno delajo, bomo videli, da v resnici ne gledajo vsake vrečke posebej, ampak malo preskakujejo in če so šli preko se vrnejo nazaj.
Boljša rešitev od tega je, da imamo v vsaki škatli tranzistorje z oznakami od do za eno škatlo. Pri meni je recimo škatla s številko 6 in vsebuje elemente, ki se začno recimo na BU in končajo z BY.
Tole lahko pogledate na http://material.volkd.si/PREGLED.ASPX . V polje Skatla vpišite C27. Dobili boste vse kar naj bi bilo v predalu z oznako C27. Če sedaj sortirate po Skatli, bo program stvari posortiral tako, bo razen po Skatli ( kar je neumnost, ker imamo izbrano le C27) posortiral še po polju polica (no to polje sem tukaj malo zloarbil, ampak predstavljajte si, da je znotraj predalnika C27 nekaj kar ima police). V resnici so te police pravzaprav škatle na naši fotografiji, v katerih so vrečke z elementi.
Tako boste lahko odkrili, da je v polici/škatli 0 natanko nič elementov, a že v škatli/polici 1 imamo nekaj tega. No ta 1 je izjema. V njej so vse vrečke, kjer je količina zelo velika. Ampak že od 2 dalje imamo pravila, ki se nekako držijo abecednega reda.
2 - od 0 do 9
3 - od A do BD798
4 - od BD799 do BD
5 - od BDX do BTB
6 - od BU do BUK
...
...
18 - 2N do 2N

[VolkD]

Primer take škatle/police:

Nalepka ima oznako SO in indeks škatle.

Pri vstavljanju ( del sorta ) mi torej ni treba iskati povprečno 250 vrečk, ampak preko mej poiščem index škatle/police in iščem samo znotraj tega kar je v škatli. Tak način je seveda mnogo hitrejši. Imenuje se sortiranje z indexom.
Ima pa zadeva tudi svojo slabo plat.
Ker ne moreš predvideti kakšne oznake tranzistorjev (kakšni podatki na računalniku) bodo prihajali, se lahko zgodi, da v eno tako škatlo pride več elementov, kot jih škatla/polica fizično zmore. Tudi pri računalniku postane to problem -> če je podmnožica, ki je v tem indeksnem delu, prevelika se časovna odvisnost precej poveča.
Rešitev tega problema je reindeksiranje. Računalnik naredi to za šalo, v naravi je to malo bolj zapleteno, saj je treba prelagati cele skupine vrečk iz škatle v škatlo. Potrebna je torej dobra ocena kaj se splača.
V realnem svetu sem tole reindeksiral že štirikrat in računam, da bom še vsaj ene trikrat.

[VolkD]

Preden grem naprej, naj povem, da je sort z indeksom, dokaj uporabna zadeva, saj razen prostora, ki ga zavzema indeks, ne zahteva dodatnega delovnega prostora. No vsaj osnovna verzija tovrstnega sorta ne.

[VolkD]

Vsakokratno iskanje indeksa je seveda tudi zamudno opravilo. Razen tega je treba, ko je indeks že najden, znotraj te podmnožice poiskati element.
Na vprašanje ali se da to poenostaviti je odgovor seveda pritrdilen. Potrebujemo seveda nekaj več prostora na mizi, oziroma nekaj več RAM-a ali spomina na disku.
Pri meni in mojih TO-220 je tole videti nekako takole.

[ivor]

Pri meni in mojih TO-220 je tole videti nekako takole.

Kje si to poslikal, pri tebi doma ali lani v Pordenonu?

[RudiP]

Če slika ni iz Pordenona je pa iz Nemčije ( Frider..... je prekomplicirano za pisanje) !

[VolkD]

Je kar na moji mizi in to v tem trenutku,...

[VolkD]

Nazaj na temo.
V teh škatlicah so elementi, ki se začno na črke, ki so označene na škatlicah. Znotraj tega pravila pa so elementi v posamezni škatlici še pomešani.
Gre torej za nekakšno delno sortiranje po prvi ali prvih dveh črkah oznake elementa.

Iz množice novih nepoznanih elementov je dotok posameznih precej enostavno usmerjati v različne škatlice. Celo, ko bereš oznako, bereš le del - prva dva znaka in že gre roka k ustrezni škatlici.
Na ta način novo množico razdelimo na več podmnožic, ki so sicer neurejene a znotraj določenih mej.

[VolkD]

Nadaljujem s sortiranjem.
Izbral sem si škatlico z oznako 78 - 79. Naj takoj opozorim, da najbolj pogostih LDO v tej škatlici ni. Tako bomo tu zaman iskali 7805 in 7812. Te sem izločil že v predfazi, ker jih je preveč in bi vse skupaj samo ovirali.
Tudi v računalniškem sortu se mnogokrat poslužujejo takih trikov. Tovrstna metoda se imenuje sort z excludom. Zakaj je to dobro ?
Algoritmov, ki znajo sortirati majhne množice dovolj hitro je mnogo. Problem sortiranja lahko poenostavimo torej tako, da zmanjšamo število elementov. Če v neki analizi pred sortom ugotovimo da naša velika množica vsebuje, glede na kriterij sortiranja, veliko število enakih elementov, potem se veliki množici elementov lahko preprosto izognemo tako, da iz velike množice lahko naredimo dve ali več manjših.
V mojem primeru sem torej iz množice, ki jo imenujem 78-79 in je velika izločim dve vrednosti, ki se največkrat pojavljata in to je 7805 in 7812. Tako dobim dve množice v katerih ni več kaj sortirati in eno množico, kjer je sort še vedno potreben. Ampak ta množica je sedaj majhna.
Ta metoda je tudi v resničnem svetu zelo zanimiva, saj je robustna. Tudi če se v preostali množici pomotoma pojavi kakšen 7805 ali 7812, to ne bo bistveno vplivalo na hitrost sortiranja.

[VolkD]

Lotil se bom torej preostale še neurejene množice.

Na levi imam čist list papirja. To je moje delovno področje. Na desni strani pa imam relativno majhno množico LDO regulatorjev vseh vrednosti (razen 7805 in 7812). Fotografija je nastala tudi kot časovni marker, ki sliši na 08:51:51. To je torej začetek sortiranja. Uporabil bom sort z vstavljanjem (pasjansa).

[VolkD]

Tu vidimo igro vstavljanja na njenem koncu. Fotografija ima časovni marker 09:02:59.
S tole pasjanso sem se torej ukvarjal 11 minut in 8 sekund. Sliši se veliko, a v igri je 60 elementov. Za vsakega torej okrog 5 sekund. Kdo z boljšim vidom, bi tole verjetno naredil še hitreje.
Pri računalniku je podobno. Hitrejši procesor naredi prej.
Zdaj moramo te stvari spraviti v vrečke.

[VolkD]

Poiskati je torej treba ustrezno škatlo/polico. Program pravi, da je to škatla/polica 2. Zato sem to škatlo prinesel bližje.

Oznaka škatle je SO 2, a naj vas to ne moti, SO pomeni sort, 2 pa je številka škatle. Fotografija ima časovni marker na 09:05:06.

[VolkD]

Fotografija je tu zato, da se vidi, da so šli LDO-ji po vrečkah in jih ni več na papirju. Časovni marker na tej fotografiji je 09:12:42.
Za to, da bi teh 60 LDO-jev dal po vrečkah sem torej porabil 7 minut in 36 sekund, kar je v resnici precej hitro. Na ta način sem vse LDO-je, ki so bili v prvem predalčku, spravil v vrečke, ki so v celotni zbirki z oznako C27.
Na fotografiji se vidi, da je do konca množice v škatli/polici ostala le ena vrečka - zadnja. V to nisem dal nič, ker takega elementa v moji pasjansa množici ni bilo.
Je pa pri tem treba povedati eno zelo važno zadevo. V tem sortu z vstavljanjem sem imel samo take primere, kjer je oznaka posameznega elementa (LDO) že bila v osnovni zbirki. Torej sem elemente samo dodajal v vrečke. V zbirko torej nisem dodal nobenega novega, nobene nove vrečke ni bilo treba opremiti z nalepko in kar je najvažneje - nobenega pdf-ja ni bilo treba poiskati, nobenega novega recorda ni bilo treba dodati, le količino pri posameznih oznakah sem povečeval.

[VolkD]

Celoten sort iz enega posameznega predalčka v celotno zbirko je torej trajal 18 minut in 44 sekund. Je pa pri tem trreba vedeti, da sem se vmes ukvarjal še s fotografiranjem in zapisovanjem podatkov, ki sem jih uporabil tule.
Imam še natanko 17 predalčkov, pri tem pa je malo možnosti, da jo bom odnesel tako poceni kot tokrat, saj bo zagotovo treba dodajati nove oznake. Najmanj en dan torej.

[Jakey]

Ni direktno sortiranje, semizdi da pa paše v to temo: kolikšen delež elektronike si uspel že razdreti, posortirati in pospraviti? (predvidevam, da si se lotil pospravljanja tistih škatel PCBjev?)

[VolkD]

Ni direktno sortiranje, semizdi da pa paše v to temo: kolikšen delež elektronike si uspel že razdreti, posortirati in pospraviti?

V bistvu ne paše, le rahlo se naslanja na tole temo o sortiranju. Za tole bi moral novo temo odpreti. Če bi pa rad delež,... bom rekel, da upam, da bo ob koncu tega, kar imam zdaj na mizi, od elementov v TO-220 ohišju ostalo manj kot 5%. Govorim seveda o elementih, ki so po škatlah in ne tistih, ki so še na TIV.

(predvidevam, da si se lotil pospravljanja tistih škatel PCBjev?)

Ne. Tisto je še vse celo. Tako kot je bilo.


Mogoče bi res moral odpreti temo o tem. Temo, ki bi povezovala tole temo o sortiranju, pa temo o iskanju datasheetov, pa teme o vrečkah, škatlicah, nalepkah,...

[VolkD]

Da nekako nadaljujem temo o sortiranju.
Mogoče bo za nekoga vse tole nekako nepomembno. Ja razumem, tema obravnava razne tipe sortiranja. S stališča PC uporabnika/programerja je to lahko zanimivo, a se pri tem tudi konča.
V C# je sort le ena od funkcij objekta. Pokličemo ga načeloma kot Objekt.sort(); In pri tem ne razbijamo kaj mnogo z glavo katero od metod sortiranja bo ta klic uporabil. Zagotovo bo to nekaj kar je precej blizu idealnemu.
Ampak nekaj povsem drugega so majhni mlinčki s samo nekaj 10k RAM-a. Tu velja biti pazljiv in še kako dobro je poznati posamezne metode in algoritme sortiranja.
Sortiranje v realnem življenju je še bolj nerodno in mnogo bolj zahtevno. Poznavanje algoritmov in metod sortiranja lahko zelo, zelo olajša delo.
Prispevki so torej namenjeni tovrstnemu delu.

[VolkD]

Do sedaj smo že dodobra ugotovili, da je lažje sortirati več manjših množic, kot pa eno veliko.
Evo, dajem primer pri mojih tranzistorjih. Na vrsti so japonski tranzistorji, ki se začnejo z 2SB.
V tej skupini tranzistorjev je izjemno veliko število tanzistorjev, ki so zaliti v zeleno plastiko. Barva ohišja je zelo uočljiva in je torej lahko odličen kriterij za delitev enega velikega problema na dva manjša. No lahko si pomagamo s še enim, tudi dobro vidnim kriterijem. Ohišje je lahko v celoti palstično, ali pa ima kovinski tab.
Ta način delitve je bil v mojem primeru izjemno uspešen.

Na slikah vidimo obe pasjansi, torej pasjansa z zelenimi plastičnimi in pasjansa z zelenimi kovinskimi tab-i.

Taka delitev je seveda smiselna, le dokler velja pravilo, da imajo vsi tranzistorji iste oznake enako ohišje glede na barvo in glede na TAB.

[VolkD]

No zdaj pa imam.
Tranzistor 2sb857 je bil verjetno zelo popularen in je zanj zmanjkalo zelene plastike. Že desni zgoraj je malo temnejši.
Prej smo rekli, da bo barva razdelila problem na dva manjša dela, ki bosta lažje obvladljiva. Rekli smo tudi, da je pogoj, da bi zadeva funkcionirala, da ni enakih oznak za zeleno in črno plastiko.
Zdaj pa imam tole.

Za enako oznako imam tranzistorje v različnih barvah.

Saj posortiral sem vseeno in vse je v redu. Ampak zdaj je čas, da pogledam kakšna je časovna škoda, ker imamo tako neugodne podatke.
Če bi se za vse oznake izkazalo, da jih imamo v mešanih barvah, bi se čas sortiranja kar občutno podaljšal. Torej najmanj za čas iskanja, odpiranja in zapiranja vrečke pri vseh.
Ne ne, nisem picajzel, zelo dobro vem, da je to majhen čas, ampak če moraš to narediti za recimo 100 oznak, se pa kar pozna. In pri sortiranju šteje vsaka operacija. V realnem času je to vrečka,.. no vrečka gor, vrečka dol, ampak če tako zadevo vgradimo v nek sortirni algoritem, je ta "napaka" tam za večno. Napaka sem napisal v narekovajih, ker to v resnici ni napaka, saj bo izhod vseeno pravilen, le časovna odvisnost bo večja. Mogoče bi bil izraz "nerodnost" boljši.

Če se vrnem na moje tranzistorje. Imel sem srečo, saj se je ta "nepravilnost" pojavila samo enkrat. Prihranek na času zaradi delitve problema na dva manjša, je vseeno krepko večji, kot pa čas, ki je šel po zlu zaradi te "nepravilnosti".
To da je čas sortiranja odvisen od tega kako so podatki razvrščeni, smo že prej ugotovili. Ampak v mojem konkretnem primeru smo zaradi izbire algoritma, ki upošteva barvo še vedno v prihranku s časom, le, da smo prihranili precej manj, kot je bilo pričakovano. Ampak lahko bi bili pa v minusu, če bi se to pojavilo pri večini oznak.

Jaz sem se za to odločil, takole "od oka". Računalniku ta danost ni dana. Za vse algoritme, ki imajo to lastnost, da je čas njihovega delovanja močno odvisen od podatkov, je treba pred njihovo uporabo narediti analizo vhodnih podatkov in se potem na podlagi te analize odločiti za katerega od teh kritičnih algoritmov. Analiza seveda ne sme biti časovno potratna, sicer se računica v nobenem primeru ne izide.
Nekoč, ko so računalniki imeli malo RAM-a (govorimo o kb) se take analize absolutno niso izšle, čas branja diska je bil namreč za kar nekaj faktorjev večji od kakršnega koli prihranka na račun premetavanja podatkov RAM-u.
V današnjih časih, ko je RAM-a dovolj, da je celotna naša zbirka podatkov v RAM-u, pa so analize podatkov dovolj hitre, da lahko prinesejo prihranek z izbiro pravega algoritma in še več, omogočajo uporabo algoritmov, ki smo jih v preteklosti zavrgli, ker so bili nestabilni, ali pa jih sploh nismo dovolj poznali, ker jih nihče ni raziskal.
Obstajajo celo rešitve, pri katerih se vhodne podatke, pred uporabo takega kritičnega algoritma najprej dodatno premeša.

[VolkD]

Skupina tranzistorjev, katerih oznaka se začne z 2SC. Recimo, da sledečemu ugotovljenemu dejstvu lahko rečemo analiza podatkov pred sortiranjem:
-2SC skupina je najobsežnejša skupina tranzistorjev, ki jih imam.
-Ta skupina obsega tranzistorje v TO-220 ohišju in to v izvedbi s plastičnim in kovinskim tab-om. Obsega tudi tranzistorje v TO-202 ohišju, oziroma izvedenkami tega ohišja.

Iz povedanega sledi, da je treba to skupino razdeliti na manjše skupine, ker bomo na ta način sortiranje pohitrili.
Torej, večja kot je množica, večja je potreba, da jo razdelimo na več manjših množic.
Na fotografiji vidimo, da sem skupino razdelil na tri dele. ( TO202, TO220 kovinski tab in TO220 plastika).
Bomo videli kako bo to šlo.

[VolkD]

Se mi je kar splačalo razdeliti celo skupino na tri podskupine. Zaenkrat sem rešil le to kar je v TO-202 ohišju.

Veliko število enakih/podobnih in samo 5 različnih, pomeni, da je bila izbira kako razdeliti tranzistorje dobra.

Še enkrat! Če se da, se vedno splača razdeliti eno veliko nesortirano mnžico elementov na več manjših množic.

[VolkD]

Na ZS sem dobil vprašanje:

Zakaj je tako pomembno, da je malo tranzistorjev v skupini

No tranzistorji so samo tranutno moj realni fizični problem, ki mi služi kot primer za razlago sortov, ki so ponavadi aplicirani kot algoritmi v računalniških programih.

Bom odgovoril na primeru.

Tole je moja pasjansa.
Imam množico tranzistorjev iz skupine 2SC. To je najbolj množična skupina tranzistorjev v moji zbirki (verjetno tudi na svetu).
Če pogledamo mojo pasijanso, potem bo jasno, da sem iz škatle jemal tranzistor po tranzistor in jih zlagal enega do drugega, pri čemer sem pazil, da je v prvem stolpcu podskupina tranzistorjev z oznako 2SC1xxx, v drugem si taki z oznako 2SC2xxx, v tretjem 2SC3xxx in tako naprej. Razen tega sem z vrivanjem v vsakem stolpcu dosegel, da gredo xxx po vrstnem redu. Tisti, ki imajo enako oznako pa so tesno skupaj v vodoravni smeri.
Zadeva je torej pripravljena, da vzamem ustrezno polico/škatlo in vanjo dodam tranzistorje, ali kot nove v novi vrečki, ali pa kot že obstoječe oznake, torej jih samo dodam v vrečko.
Ampak pred tem moram v pasjanso dodati še tole!

[VolkD]

Ja nerodno. V moji pasjansi je premalo prostora za dodajanje vsega tega. Tudi računalniki imajo probleme z dodajanjem novih elementov, ker s tem potrebujejo dodaten prostor. ( Resnica je, da ima pri tej količini podatkov računalnik dovolj prostora).
Razen tega bi z še več elementi v moji pasjansi postalo iskanje prostora kam spada nov element in vrivanje med ostale, precej komplicirano. Če si pa le malo neroden, se celotna pasjansa razsuje. Dovolj je, da ti en tranzistor z višine 10cm pade v to področje in iz pasjanse nastane kaos.

Če lahko tranzistorje razdelimo po nekem kriteriju, ki je tak, da za to delitev potrebuje malo časa, recimo po barvi ali ohišju, potem imamo dva manjša problema, ki sta lažje obvladljiva. Če je izbira kriterija taka, da zanesljivo loči oznake na tak način, da ni istih v obeh dveh skupinah, potem nam iste vrečke zagotovo ne bo treba iskati, odpirati in zapirati, dvakrat.

Če zaradi prevelikega števila elementov, skupine ne moremo razdeliti s pomočjo kakega koristnega kriterija, potem se bodo enaki elementi pojavljali v obeh skupinah. Posledično bo treba nekatere vrečke poiskati vsaj dvakrat namesto enkrat.

Povsem enak problem je tudi pri računalniku, le da tam namesto o minutah, govorimo o ms, ali o še krajših časih. Ampak na koncu se vseeno nabere.

[VolkD]

V mojo pasjanso sem dodal komaj kaj več kot 10 tranzistorjev, pa poglejte kako se je skomplicirala. Marsikje je nemogoče dodati še kaj več. V posameznih skupinah je enakih elementov toliko, da je zadeva prerasla v 3D. Tranzistorje sem torej zložil v višino.
Če mi tu zdaj iz rok pade en tranzistor bo res katastrofa.
Če primerjam z računalnikom, potem se tam lahko zgodi recimo to, da zmanjka RAM-a, namenjenega delovnemu področju sorta.

[VolkD]

Nova pasjansa.
Zdaj je zadeva že tako natrpana, da sem si omislil vstavljanje z zamikom. Tako imam v navpični vrstici tranzistorje zamaknjene levo desno.
Skratka zadeva je postala nepregledna in zahteva rešitev.
Ena od rešitev je, da pasjanso pospravim po vrečkah in začnem novo. Ta rešitev že sama nakazuje na to, da bom moral veliko vrečk odpirati vsaj dvakrat. Dobra časovna odvisnost takega sortiranja bo torej šla po zlu.
Kakšna bi bila boljša rešitev ?
Recimo namesto A4 lista bi dali A3. Ampak potem bi se v taki pasjansi izgubili, pa še več prostora na mizi bi potrebovali. Napisano seveda lahko takoj prevedete tudi na računalnik. Prostor na mizi je RAM v računalniku. Ko rečem, da bi se v pasjansi izgubili pa za računalnik pomeni precej več primerjav elementov med seboj. Ta rešitev torej ni dobra.
Kaj pa če pasjanso rešimo tako, da le del elementov pospravimo v vrečke drug del pa pustimo in nadaljujemo z zlaganjem v pasjanso. To bi bilo precej bolje. Je pa sedaj vprašanje katere dele pustiti in katere zložiti v vrečke? No tole vprašanje je vprašanje za milion $.

Lahko od oka določimo kateri gredo v vrečke. Kakšen bo prihranek - pa od oka dober.
Ampak tale od oka ni kar tako, je povsem smiselen. Če od oka vidimo, da je napis lepo viden, potem bo s takimi manj problemov, če jih bomo morali ponovno uvrstiti v pasjanso.
Lahko si izberemo take, ki jih je veliko enakih. Smiselno, saj s tem razbremenimo veliko prostora v pasjansi. Po drugi strani pa ni smiselno, saj statistika pravi, da je velika verjetnost, da se bodo vrnili.
Zgornja trditev nas napelje na to, da lahko razmišljamo o tem, da odstranimo take, ki imajo po samo en element za oznako, saj je malo verjetnosti, da se bo tak pojavil znova.
Vsi argumenti so lahko dobri ali pa slabi. Vse je odvisno od podatkov. Edini resnično dober odgovor da predhodna analiza podatkov.

[VolkD]

V primeru mojih tranzistorjev je taka analiza kar malo odveč (vsaj meni). V primeru računalnika, pa je še kako smiselna.
Kako taka analiza sploh deluje. Mnogo načinov je. Eden enostavnejših in pogostih je en sam prelet vhodnih podatkov od začetka do konca. Rezultat tega preleta je, da računalnik naredi tabelo oznak in zraven doda vrednost, ki predstavlja število elementov za to oznako elementa.
Ko računalnik v pasjanso dodaja nov element, gre še pogledat koliko takih oznak cela množica sploh ima. Če ugotovi, da je v pasjanso dodal zadnji elemet, potem celotno skupino elementov z enako oznako premakne v posortirano množico. Na ta način se močno zmanjša potrebno delovno področje za sortiranje.
Slabost je, da je velikost potrebnega delovnega področja, močno odvisna od vrste podatkov.

Če se vrnem na tranzistorje.
Jaz bom tudi izločal posamezne elemente in jih umikal v vrečke/škatle. No moj kriterij je ta, da bom umaknil tiste, ki imajo v posortirani množici že narejeno vrečko. Torej mi zanje ne bo treba iskati pdf-ja, vpisovati vseh podatkov,... samo količino bom povečal.
Slabost tega je, da mi bodo na koncu ostali samo taki, ki jih v moji zbirki do sedaj še ni.

Posledično bom težil za pdf-je sporadično, vsake toliko, ko bo šla pasjansa k koncu. In zadnji elementi pasjanse so precej bolj zamudni kot tisti prej.

[VolkD]

Jaz bom tudi izločal posamezne elemente in jih umikal v vrečke/škatle. No moj kriterij je ta, da bom umaknil tiste, ki imajo v posortirani množici že narejeno vrečko. Torej mi zanje ne bo treba iskati pdf-ja, vpisovati vseh podatkov,... samo količino bom povečal.
Slabost tega je, da mi bodo na koncu ostali samo taki, ki jih v moji zbirki do sedaj še ni.

Tole je ostalo od moje pasianse, ki sem jo "obdelal" po gornjem kriteriju.
Imam torej ponovno pasianso z majhnim številom elementov, to kar sem iz pasjanse umaknil, pa je na svojem končnem mestu.