Algoritmusok

Idén is indul az Advent of Code "karácsonyváró játék". Hajrá! :) 

 

Indítottam egy HUP leaderboard-ot: 2567216-8c01cc3b

?

 

(a privát leaderboard-ok csak login után látszanak)

Egy új, forradalmi nyelv van születőben, a Unison.

A forradalmi ötlet az, hogy az egyes definíciókat nem névvel azonosítjuk, hanem az absztrakt szintaxis fájuk hash-ével.

Ennek nagyon érdekes következményei vannak:

• Az elosztott rendszerek létrehozása és kezelése rendkívüli módon egyszerűsödik. A microservice architektúra számos hátránya eltűnik.
• Nincs build idő, vagyis gyakorlatilag nulla. Az erősen statikusan típusolt nyelveknél elég sokáig tart egy nagyobb alkalmazás buildelése. Itt gyakorlatilag nincs build, mivel az egyes definíciók ellenőrzés és átalakítás után, egyből bekerülnek a közös kódbázisba, ahol azonnal használhatóvá válnak.
• Nincs függőségi konfliktus. Egy-egy definíciónak tetszőleges sok verziója létezhet és futhat egymás mellett.
• Típusolt, tartós tárolás. Ha adatot el akarunk tárolni, akkor nem szükséges oda-vissza alakítani, gyakorlatilag az adott adat közvetlenül tárolható, akár elosztott rendszerben is.
• Gazdagabb kódbázis eszközök. A Unison kódbázis egy megfelelő adatbázis, amely ismeri minden tárolt dolog típusát, tökéletes fordítási gyorsítótárral, tökéletes tudással rendelkezik a függőségekről, a típusalapú keresés indexeiről és még sok másról. Ez lehetővé teszi számunkra, hogy egyszerűen készítsünk sokkal gazdagabb eszközöket a böngészéshez és a kóddal való interakcióhoz. Gyakorlatilag nem szükséges IDE, egy egyszerű szövegszerkesztővel is az IDE szolgáltatások elérhetőek, sőt még annál többek is.
• Struktúrált refaktorálás. Mivel a kódbázisban eltárolva van az összes függőség, strukturált módon, így segítséget kapunk a refaktorálás folyamatán, hogy mikor mit módosítsunk. Plusz előny, hogy a kódbázisunk folyamatosan futtatható állapotban van, sosincs törött állapotban.

Ui.: 

Ebből a videóból sokkal jobban megérthető az ötlet és a működése: 

"Unison: a new distributed programming language" by Paul Chiusano

Egyesek fejében hatalmas káosz és sötétség kavarog ennek kapcsán, ezért úgy gondoltam, írok egy mini fejtágítót. Előrebocsátom, hogy az alábbi definíciók NEM teljesek, szándékosan hiányosak és leegyszerűsítettek, csupán azokat az aspetusokat emeltem ki belőlük, melyek a többszálúság kapcsán relevánsak. Multithreading A végrehajtás úgy történik, hogy a processzorban van ún. utasításszámláló regiszter, ez tárolja a soronkövetkező gépi kódú utasítás memóriabeli címét. Ezt a regisztert szokás PC-nek hívni (Program Counter, Motorola, ARM, stb. processzorokon) vagy IP-nek (Instruction Pointer, x86-on). Ha ennek a regiszternek az értéke elmentődik a memóriába, és egy, a normál programfolyamtól eltérő érték kerül helyette bele, akkor többszálú programvégrehajtásról beszélünk. Multitasking Ellőbbitől független dolog, de az előfeltétele ennek, többszálúság nélkül nincs multitasking se. Ilyenkor jellemzően az összes többi regiszter is mentődik az utasításszámlálóval együtt, emiatt címtérváltás is bekövetkezhet. Három fajtája létezik: - Szekvenciális az, ha az új szál lefutása után kerül csak vissza a vezérlés a megszakított szálra. - Ko-operatív az, ha létezik egy ún. yield hívás, aminek hatására visszaadódik a vezérlés a megszakított szálra (vagy egy bármilyen másik szálra). - Pre-emptív az, ha egy időzítő segítségével akkor is átatódik a vezérlés egy másik szálra, ha az éppen végrehajtott szál nem hív yield-et és nem is fejeződött még be. Régi szép időkben egyértelmű volt ez a dolog, mert a processzek közti kapcsolás a kernelben történt és címteret is váltott, a pthread-ek közti kapcsolás pedig egy processzen és egy címtéren belül történt, és a kernel nem is tudott róla. A mai kernelekben már kicsit összetettebb dolog amióta léteznek a SYS_set_tid_address, SYS_sched_setscheduler stb. rendszerhívások; azóta a kernel nemcsak a különböző címterű processzekről tud, hanem az egy címtéren belüli szálakról is, és azok kapcsolását is ő végzi (ez egyébként a multicore miatt szükséges, lásd alább). Ez a megoldás egyébként a Solaris kernelből eredeztethető, ahol LightWeight Process-nek hívták az ilyen közös címtéren belüli szálakat. Multicore (hyperthreading, SMP) Ezt sajnos helytelenül hívják néha multithreading-nek, de ennek semmi köze az első pontban leírthoz. A többmagvas processzor azt jelenti, hogy egyszerre több utasításszámláló regiszterrel is gazdálkodhatunk. De mégyegyszer, ennek semmi, de semmi köze a fenti kettőhöz, egy egymagvas processzoron is simán megvalósítható a multithreading és a multitasking, ezért jobb ezt multicore-nak, hyperthreading-nek (vagy esetleg SMP-nek, Symmetric Multi Processing-nek hívni). - Ha a szálak száma meghaladja a processzormagok számát, akkor látszólagos párhuzamosságról beszélünk. Ilyenkor időosztásos (time sharing) módon több szál hajtódik végre és osztozik egy adott processzormag utasításszámláló regiszterén (ehhez mindenképp kell multitasking). - Valós párhuzamosságról akkor beszélünk, ha a szálak száma kevesebb vagy egyenlő, mint a rendelkezésre álló processzormagok száma. Ilyenkor minden szál saját processzormagot, és azzal saját dedikált utasításszámláló regisztert kap (ekkor nem előfeltétel a multitasking). Ps: teljesség kevéért van még a nem szimmeltrikus multicore is, de abba most ne menjünk bele, mert a többszálúság elmagyarázáshoz nincs rá szükség. Ps2.: vegyük észre, mikor előfeltétel a multitasking és mikor nem. Szerevereken, asztali gépeken mindig rengeteg a processz és a szál, több, mint a mag, ezért mindig van multitasking is. Olyan, hogy multitasking nélkül létezik multithreading, jellemzően csak ipari PLC-ken meg néhány embedded IOT eszközön fordul elő, máshol nem. Blokkoló IO Ez azt jelenti, hogy az IO hívás blokkolja a hívót, és annak a következő utasítása nem hajtódik végre, amíg az IO művelet be nem fejeződik. Nem-blokkoló IO Ez csak annyit jelent, hogy az IO hívás egyből visszatér, azonban SEMMIT, de SEMMIT nem jelent arra nézve, hogy aztán a későbbiekben hogyan értesül a hívó az IO művelet befejeztéről. Jellemzően két fajtája van: ami többször is hívható és kóddal tér vissza (nem multithreadinges O_NONBLOCK read/write), és a callback alapú (multithreadinges, alacsony szinten csakis a POSIX szignálok ilyenek, semmi más, pl. SIGINT, SIGIO vagy stílusosan SIGHUP :-) ). Szekvenciális IO Ez azt jelenti, hogy egyszerre csak egyetlen IO kéréssel foglalkozhat a hívó. FIGYELEM! Nem arról van szó, blokkol-e vagy sem, hanem hogy hány IO kéréssel tud foglalkozni egyszerre. Aszinkron IO Aszinkron IO-ról abban az esetben beszélhetünk, ha az IO kérések feldolgozása NEM SZEKVENCIÁLIS, hanem párhuzamos, azaz az egyik IO kérésnek nem kell várnia egy másik IO kérés feldolgozására. Ismét nem arról van szó, hogy blokkol-e vagy sem, multithreading esetén simán lehet blokkoló is aszinkron, mert csak az adott IO művelethez tartozó szál blokkolódik, a többi vígan futkorászik tovább. Multiplexing Multiplexing az, ha több nem-blokkoló IO kontextussal rendelkezünk, és ezeket egyetlen szálon AKTÍVAN pollozuk. Multiplexer nem lehet aszinkron, mert hiába a több IO kontextus, a feldolgozásuk mindenképp szekvenciális, azaz egyszerre csak egy IO kéréssel tud foglalkozni, a többinek várakoznia kell. Összefoglalva: - minden multitask egyben kötelezően multithread is, de nem minden multithread multitask - minden multicore egyben kötelezően multithread is, de nem minden multithread multicore - minden aszinkron egyben kötelezően multithread is, de nem minden multithread aszinkron - szekvenciális (és a multiplexing) nem multithreading - blokkoló IO hívás lehet szekvenciális (POSIX alapeset) és aszinkron is (multithreading esetén, IO-ként egy-egy szál blokkolt vagy sem) - nem-blokkoló IO hívás lehet szekvenciális (ha nem multithreading, azaz multiplexing) és aszinkron is (ha multithreading)

Sziasztok!

Alábbi PHP kódot sikeresen használom egy ideje:

function getOtp($key) {

    $alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
    /* Base32 decoder */
    // Remove spaces from the given public key and converting to an array
    $key = str_split(str_replace(" ","",$key));

    $n = 0;
    $j = 0;
    $binary_key = "";
    // Decode public key's each character to base32 and save into binary chunks
    foreach($key as $char) {
        $n = $n << 5;
        $n = $n + stripos($alphabet, $char);
        $j += 5;

        if($j >= 8) {
            $j -= 8;
            $binary_key .= chr(($n & (0xFF << $j)) >> $j);
        }
    }
    /* End of Base32 decoder */
    // current unix time 30sec period as binary
    $binary_timestamp = pack('N*', 0) . pack('N*', floor(microtime(true)/30));
    // generate keyed hash
    $hash = hash_hmac('sha1', $binary_timestamp, $binary_key, true);

    // generate otp from hash
    $offset = ord($hash[19]) & 0xf;
    $otp = (
        ((ord($hash[$offset+0]) & 0x7f) << 24 ) |
        ((ord($hash[$offset+1]) & 0xff) << 16 ) |
        ((ord($hash[$offset+2]) & 0xff) << 8 ) |
        (ord($hash[$offset+3]) & 0xff)
    ) % pow(10, 6);

   return $otp;
}

Szeretném ugyanazt a funktionalitást elérni bash-ben, de nem tartok még ott.

#!/bin/bash

T=$(echo $(date +%s) / 30 | bc)
export T
TB=$(perl -e "print pack(\"N*\", 0).pack(\"N*\", $T)")
echo $TB | od
K="TITOK123"
keyhex=$(printf '%s' "$TB" | openssl dgst -sha1 -hmac $K | cut -d' ' -f2 )
echo $keyhex
dec=$(echo "ibase=16; $(echo $keyhex | tr '[:lower:]' '[:upper:]')" | bc)
echo $dec
key=$(echo "$dec % 1000000" | bc)
echo "$key"

Erre a soora gyanakszom a leginkább:

TB=$(perl -e "print pack(\"N*\", 0).pack(\"N*\", $T)")

Van egy csomó egyforma cellám (szoba), ezeknek O oldaluk van, a szomszédjaikkal 1-1 oldalon kapcsolódnak = 1 közös faluk van.
Az egyszerűség kedvéért a szomszéd szobába mindig át lehet menni, vagyis az ajtók nincsenek egyik irányból sem zárva.

A feladat azt kitalálni, hogy 2 random szoba milyen messze van egymástól, a távolságot mérjük mondjuk "ajtó"-ban, Hány ajtón kell minimálisan átmenni, hogy A-ból B-be jussunk.

A legegyszerűbb ilyen, ha négyzet alakú szobák vannak, 4-4 ajtóval, szépen, mint a füzetben. Erre gyorsan ki lehet találni egy magik képletet, ami a poziciójuk alapján megmondja.
De mondjuk általános esetben? Mondjuk 6 oldalú szobák esetén. Netán szélsőséges esetben, pl. Ha Voronoj-celláim vannak? 

Vagy ha nem egyformák a szobák?

- Bonyolítja kicsit, hogy kell majd hozzá vmi model is, jellemzően SQL-ben szeretném az egészet aszalni.
- Jó lenne, ha majd lehetne írni egy egyszerű, tömör, zárt query-t, ami 2 cella-ID alapján megmondja a tutit. Szóval geometriai megoldások egyelőre visszafogottan érdekelnek.

Lehet ezt még bonyolítani, pl. ha "lyukak" is vannak (mint a keresztrejtvényben), vagy nem minden ajtó nyitható. De ezeket most hagyjuk. 

Az mondjuk már félig megoldás, ha a tisztelt közösség nevesíteni tudja a problémát, olvasni tudok.

TIA.

Sziasztok!

Tud-e valaki veletlenul jo kis FIR algoritmust, ami akar meg gyors/hatekony is lehet? :) A win[] ablakfuggveny minden esetben lehet L + 1 = 2^N+1 elemszamu es szimmetrikus, ezt "er" kihasznalni. Azaz ahol L az mondjuk 32 ... 256 lenne a gyakorlatban mint ketto-hatvany, es win[n] = win[L-n] fennall. Nyilvan ha L az kisebb lenne mint az itteni ertekek (pl 4...8), akkor teljesen felesleges tultolni valami szofisztikalt eljarassal, ha pedig tul nagy, akkor mar ugyis inkabb konvolucionak hivnank mintsem FIR filteringnek. 

Egy naiv implementacio az kb ilyen most:

typedef struct
 {      int     fir_length;
        double  *fir_buffer;
        double  *fir_window;
        int     fir_index;
 } finite_impulse_response;

int fir_init(finite_impulse_response *fir,int len,double initial)
{
 int    i;
 fir->fir_length=len;
 fir->fir_buffer=(double *)malloc(sizeof(double)*len);
 for ( i=0; i<len; i++ )
  {     fir->fir_buffer[i]=initial;
  }
 fir->fir_window=(double *)malloc(sizeof(double)*(len+1));
 fir->fir_window= ...; /* computation of FIR window filter goes here */
 fir->fir_index=0;
 return(0);
}

double fir_apply(finite_impulse_response *fir,double in)
{
 double w;
 int    j,p;

 w=0.0;
 for ( j=0,p=fir->fir_index; j<fir->fir_length; j++ )
  {     w += fir->fir_buffer[p] * fir->fir_window[j];
        p=(p+1)%fir->fir_length;
  }
 w+=in*fir->fir_window[j];
 fir->fir_buffer[fir->fir_index]=in;
 fir->fir_index=(fir->fir_index+1)%fir->fir_length;

 return(w);
}

int fir_buffer(finite_impulse_response *fir,float *input,int ninput)
{
 int    i;
 for ( i=0; i<ninput ; i++ )
  {     input[i]=fir_apply(fir,input[i]);
  }
 return(0);
}

Lenyeg itt a legutolso fir_buffer() hivas, ami siman a fir_apply() hivason keresztul lekonvolvalja es a `fir` objektumban szepen tarolja az allapotgepet hogy kifele elrejtse az egesz hobelevancot. Szoval a feladat az a fir_apply() minel hatekonyabb, O(fir->fir_length) muveletigenynel jobban skalazo valtozata lenne. Nyilvan egy O(log(fir->fir_length)) lenne a legjobb :) Extrem hataresetekben, pl boxcar filterignel ugye O(1) muvelettel es O(length) memory footprinttel megoldhato, szoval csakcsak van valami a ketto kozott, kihasznalva hogy a length az ketto-hatvany es/vagy hogy a fir_window[] az szimmetrikus meg ilyesmi... 

thx, A.

Klaszterezés után az előálló klaszterek "minőségét" szeretném jellemezni mérőszámmal. A klaszterekben mondjuk betűk gyűlnek: AAA BBBBBCCE EEEEEF stb.

Ideális esetben a klaszterekben homogén lenne a tartalom, de az eset nem ideális, így alakulhat ki a fenti elrendezés.

Mivel többféle módszerrel történik ugyanazon adathalmaz klaszterezése, a létrejövő dendrogramokon pedig esetenként látszanak jobb elrendeződések (nagyobbak a homogén klaszterek, több homogén klaszter jön létre, mint más esetben), így valahogyan számszerűsíteni kéne ezeket a jobb elrendezéseket. Az nem elég, hogy "látszik". :-)

Ti hogyan oldanátok ezt meg?

Sziasztok!

Adott a következő probléma, amire algoritmust keresek. (Hobbi projekt, nem munkához kell.)

Adott egy téglalap oldalméretekkel meghatározva, ezen a téglalapon kell elhelyezni n darab kisebb téglalapot, a következő szabályok szerint:

• 2 <= n <= 50
• Az elhelyezendő téglalapoknak egybevágóaknak kell lenni 
  • Közülük pontosan 1 téglalap a referencia, ennek az oldalarányát tartani kell
  • Az összess többi téglalap (n -1 darab) egyforma méretű kell legyen
  • A referencia téglalapnak ugyanakkorának (n=2 esetén) vagy nagyobbnak (n>2 esetén) kell lennie mint a többinek
• Az elrendezésnek "mátrix jellegűnek" kell lennie, azaz pl
  • n = 2 esetén egy 1 x 2 es mátrixban lenne két egyforma téglalap
  • n = 3 esetén egy 2 x 3 as mátrixban a referencia téglalap lefoglalná az első két oszlopot teljesen, és a két kis téglalap lenne a 3. oszlop két sorában
  • n = 6 esetén egy 4 x 3 as mátrixban a referencia téglalap a bal felxő 2x2 cellát foglalná le, az 5 kis téglalap pedig a jobb oldali oszlopban, illetve a referencia téglalap alatt lennének
• A téglalapok között kimaradt területet (értsd. üres cellák számát) kell minimalizálni
• Eredményként a megoldásmátrix dimenziót kell kiadni, és hogy a referencia téglalap 1x1, 2x2, 3x3 stb cellát foglal e le az eredménymátrixból

Ha jól értelmezem, a probléma a 2D packing egy speciális alesete. Ezeket itt nézegettem, de szerintem minden ottani megoldás túl általános az én esetemre.

Use case: Fotózás, referencia fotóra szeretnék különféle effekteket (jelen esetben LUT-okat) applikálni, és szeretném egy képernyőn/képen nézegetni a variációkat.

Az algoritmust alighanem Rben vagy Pythonban fogom lekódolni, így ha valaki onnan tud libet vagy csomagot ajánlani, akkor extra megköszönöm.

(Nem kész szoftvert, hanem algoritmust keresek.)

Köszi előre is a tippeket,

 

Csaba

Disztichon Alfa - Első magyar versgenerátor

"Az első magyar automatikus versgenerátor program, a Disztichon Alfa bármelyik Apple Macintosh számítógépen automatikusan magyar verseket, nevezetesen disztichonokat ír ki a számítógép képernyőjére. A generált versek 1) nyelvileg hibátlanok; 2) értelmesek, 3) tökéletesen kielégítik a disztichon formai ismérveit."

Könyv + melléklet elérhető innen:
https://mek.oszk.hu/11700/11744/

Disztichon Alfa 2.0
A Disztichon Alfa, Papp Tibor 1994-ben megjelent műve az első magyar digitális versgenerátor volt, amely eredeti technikai keretrendszere miatt néhány éven belül gyakorlatilag hozzáférhetetlenné vált. A közelmúltban elkészült az eredetivel megjelenésében azonos, de platformfüggetlen változat, amelyet az Irodalomtudományi Intézet honlapján, digitális szolgáltatásaink között fogunk közzétenni. A művet bemutató előadások a játékos hagyománykezelésről, a digitális megőrzés technikai paradoxonairól szólnak.

https://abtk.hu/esemenynaptar/esem%C3%A9ny%20r%C3%A9szletei/353/-/mtu-2…

Sziasztok!

 

Volt valamikor egy Ericsson T28 nevű telefon. Ennek a nagy durranása az volt, hogy egy gomb lenyomásával képes volt élőszóban elmondott névjegyet felhívni.  Minden névjegyhez hozzá lehetett fűzni egy hangmintát, amivel ha nagyjából egyezett az élő szó, akkor tárcsázta. Röviden egy ilyet szeretnék csinálni, de minimum megérteni. Létező szolgáltatás volt ez, csak elment mindenki inkább a szövegértésre.

Általánosítva lennének hangmintáim, és egy sorszámot kellene visszaadni, hogy melyik hangzott el összességében mondjuk 10-20 szó felismerésére számítok. A végső cél hogy ez egy mikrovezérlős céleszközbe kerülhessen, szóval távlatok bizony vannak.

Namost. Általában nem vagyok analfabéta, de ez a terület maximálisan idegen számomra, és nem is tervezem hogy a szükségesnél jobban elmerüljek benne, csak amennyire ehhez az eszközhöz feltétlenül szükséges. Természetesen látom hogy nem lesz gyaloggalopp, és ingyen ebédre sem számítok.

Első gondolatom az lenne, hogy mint a hallásunk is, szűrés után (300Hz-3kHz) felbontanám frekvenciaösszetevőkre, és ebből valahogy gyártanék egy egyedi jellemzőt, mint egy ujjlenyomatot amit aztán eltárolva össze lehetne hasonlítani a mintával. Feltételezem hogy a frekvencia komponens időtartamát belekódolva megfelelő változatosságot lehet adni a mintáknak.

Ez csak az amit eddig agyaltam, de fogalmam sincs hogy egyáltalán az irány megfelelő-e.

Van valakinek bármilyen építő jellegű észrevétele, forrása, bármi? Lehetőleg minimális matekkal!