mboost-dp1
Forkortelse af 5 variabler med primtal?
Jeg har brug for at forkorte nogle variabler, på den hurtigste måde i python.
EKS:
x: kan have 5 tilstande.
y: kan have 4 tilstande.
z: kan have 7 tilstande.
t: kan have 5 tilstande.
s: kan have 3 tilstande.
Jeg skal finde den hurtigste måde at omregne x y z t s til en variable A der er unik for den samlede tilstand. Det er ikke nødvendig at jeg kan komme tilbage til de oprindelige tilstande, bare A har samme resultat hvis xyzts har de samme tilstande.
En måde at gøre det på er ved at tage en Int eller dobbel og tildele alle tilstande en fortløbende numerisk værdi, og hvis de forekommer sætte deres tilhørende bit. Simpelt med formentlig meget langsomt.
En anden måde som jeg tror vil virke, er at tildele alle mulige tilstande fortløbende numerisk værdi, omregne dem til primtal og multiplicere værdierne. Simpelt EKS:
x = 3
y = 2
z= 1
x kan være 2,3,5,7,11 og er her 5
y kan være 13,17,19,23 og er her 17
z kan være 29,31,37 osv... og er her 29
resultat = 2465
Jeg vil tro at denne metode er langt hurtige end den første, men er meget usikker på om resultatet er unikt.
Er der en venlig sjæl der kan be/afkræfte om metode 2 virker, eller kan give et bedre metode. Hele denne problem stilling er lidt vigtig, da den bliver brugt meget i koden til programmet. Så kan man jo altid diskutere hvor hurtig python er, men alt er relativt :-)
EKS:
x: kan have 5 tilstande.
y: kan have 4 tilstande.
z: kan have 7 tilstande.
t: kan have 5 tilstande.
s: kan have 3 tilstande.
Jeg skal finde den hurtigste måde at omregne x y z t s til en variable A der er unik for den samlede tilstand. Det er ikke nødvendig at jeg kan komme tilbage til de oprindelige tilstande, bare A har samme resultat hvis xyzts har de samme tilstande.
En måde at gøre det på er ved at tage en Int eller dobbel og tildele alle tilstande en fortløbende numerisk værdi, og hvis de forekommer sætte deres tilhørende bit. Simpelt med formentlig meget langsomt.
En anden måde som jeg tror vil virke, er at tildele alle mulige tilstande fortløbende numerisk værdi, omregne dem til primtal og multiplicere værdierne. Simpelt EKS:
x = 3
y = 2
z= 1
x kan være 2,3,5,7,11 og er her 5
y kan være 13,17,19,23 og er her 17
z kan være 29,31,37 osv... og er her 29
resultat = 2465
Jeg vil tro at denne metode er langt hurtige end den første, men er meget usikker på om resultatet er unikt.
Er der en venlig sjæl der kan be/afkræfte om metode 2 virker, eller kan give et bedre metode. Hele denne problem stilling er lidt vigtig, da den bliver brugt meget i koden til programmet. Så kan man jo altid diskutere hvor hurtig python er, men alt er relativt :-)
da du har under 10 tilstande, kan du jo bare bruge index-tallet.
Så hvis:
x: tilstand 3
y: tilstand 2
z: tilstand 6
t: tilstand 4
s: tilstand 1
så får du tallet:
21540 (hvis vi regner med 0-indexeret)
Hvis du endelig kommer i en situation hvor du skal bruge mere end 10 tilstand kan du jo køre 0-9a-z
Så hvis:
x: tilstand 3
y: tilstand 2
z: tilstand 6
t: tilstand 4
s: tilstand 1
så får du tallet:
21540 (hvis vi regner med 0-indexeret)
Hvis du endelig kommer i en situation hvor du skal bruge mere end 10 tilstand kan du jo køre 0-9a-z
x: kan have 5 tilstande.
y: kan have 4 tilstande.
z: kan have 7 tilstande.
t: kan have 5 tilstande.
s: kan have 3 tilstande.
w = x + 5*y + 5*4*z + 5*4*7*t + 5*4*7*5*s
Vil du have fat i x?
x = w % 5
y = (w / 5) % 4
z = (w / 5 / 4) % 7
t = (w / 5 / 4 / 7) % 5
s = (w / 5 / 4 / 7 / 5) % 3
EDIT: og det er vigtigt at det er integers og at du runder ned når du dividerer. Og indekser tilstandene fra 0
y: kan have 4 tilstande.
z: kan have 7 tilstande.
t: kan have 5 tilstande.
s: kan have 3 tilstande.
w = x + 5*y + 5*4*z + 5*4*7*t + 5*4*7*5*s
Vil du have fat i x?
x = w % 5
y = (w / 5) % 4
z = (w / 5 / 4) % 7
t = (w / 5 / 4 / 7) % 5
s = (w / 5 / 4 / 7 / 5) % 3
EDIT: og det er vigtigt at det er integers og at du runder ned når du dividerer. Og indekser tilstandene fra 0
#2
God ide, desværre har nogle af variablerne over 10 tilstande, og resultatet skulle meget gerne være en Int eller Dobble.
#3
Super ide... Jeg forudser dog at man vil få et markant større resultat end hvis man gør det med primtal. du vil i dit eks kunne komme til at multiplicere med 2100 i variable s, hvor man med primtals ideen, kun vil komme til at multiplicere med 89.
Er der ikke en der kan bekræfte om onetreehell's metode er den rigtige, så er det den jeg bruger...
God ide, desværre har nogle af variablerne over 10 tilstande, og resultatet skulle meget gerne være en Int eller Dobble.
#3
Super ide... Jeg forudser dog at man vil få et markant større resultat end hvis man gør det med primtal. du vil i dit eks kunne komme til at multiplicere med 2100 i variable s, hvor man med primtals ideen, kun vil komme til at multiplicere med 89.
Er der ikke en der kan bekræfte om onetreehell's metode er den rigtige, så er det den jeg bruger...
Wolly (4) skrev:#3
Super ide... Jeg forudser dog at man vil få et markant større resultat end hvis man gør det med primtal. du vil i dit eks kunne komme til at multiplicere med 2100 i variable s, hvor man med primtals ideen, kun vil komme til at multiplicere med 89.
Huh? Hvis du skal have oversat eks. tilstand 3 til et bestemt tal, så hav et dictionary til at slå op hvad de forskellige tilstande har af værdier.
Med min metode kan du repræsentere alle mulige kombinationer af tilstande og hverken mere eller mindre. Jeg kunne nok godt lave et ~matematisk bevis, hvis det er. Jeg vil dog helst undgå det, da jeg har bedre at lave :)
Held og lykke m. dit program
#4 jeg tror du forudser forket.
En lille fejl der har sneget sig ind i din tekst (eller mig der læser hvad du skriver forkert): det er kun 700 der vil blive multipliceret med og ikke 2100.
#3 foreslår at bruge indexet i et det implicitte multidimensionale tilstandsrum. Hvor stort er dette tilstandsrum er det så relevant at spørge? Almindelig kombinatorik giver 5 * 4 * 7 * 5 * 3 = 2100.
Hvert eneste tal mellem 0 og 2100 svarer så til en unik tilstand, (eller lokation i tilstandsrummet).
Da du kun har en representation for hvert sted, og bruger alle tal mellem 0 og 2100, har du dermed ikke noget "spild" af små tal.
Da der ikke er noget spild, kan det afvises at primtals metoden er mere optimal mht. talstørrelser.
Modulo operatoren er en langsom fætter!
Hvis det VIRKELIGT er vigtigt for dig at have små tal, vil jeg foreslå dig at kigge på frekvensen af hver tilstand. Dvs. hvis x er i tilstand 2 90% af tiden, vil det være fordelagtigt at have tilstand 2 som den første, da dette giver et lavere tal.
Derudover giver det også mening at variabler der varierer meget, dvs. hvor frekvensen af alle tilstande er nogenlunde den samme, op forrest, da svingninger her generelt medfører mindre penalty i form af tal størrelse.
Slutteligt er det hele fra min vinkel et møghack. Tvivler på at læsbarheden er særligt høj, at du sparer nok plads, fremfor bare at bruge en mindre størrelse såsom byte. Der kan også opstå sjove problemer når du prøver at udvide det, og din representation overstiger en ints max værdi. :)
En lille fejl der har sneget sig ind i din tekst (eller mig der læser hvad du skriver forkert): det er kun 700 der vil blive multipliceret med og ikke 2100.
#3 foreslår at bruge indexet i et det implicitte multidimensionale tilstandsrum. Hvor stort er dette tilstandsrum er det så relevant at spørge? Almindelig kombinatorik giver 5 * 4 * 7 * 5 * 3 = 2100.
Hvert eneste tal mellem 0 og 2100 svarer så til en unik tilstand, (eller lokation i tilstandsrummet).
Da du kun har en representation for hvert sted, og bruger alle tal mellem 0 og 2100, har du dermed ikke noget "spild" af små tal.
Da der ikke er noget spild, kan det afvises at primtals metoden er mere optimal mht. talstørrelser.
Modulo operatoren er en langsom fætter!
Hvis det VIRKELIGT er vigtigt for dig at have små tal, vil jeg foreslå dig at kigge på frekvensen af hver tilstand. Dvs. hvis x er i tilstand 2 90% af tiden, vil det være fordelagtigt at have tilstand 2 som den første, da dette giver et lavere tal.
Derudover giver det også mening at variabler der varierer meget, dvs. hvor frekvensen af alle tilstande er nogenlunde den samme, op forrest, da svingninger her generelt medfører mindre penalty i form af tal størrelse.
Slutteligt er det hele fra min vinkel et møghack. Tvivler på at læsbarheden er særligt høj, at du sparer nok plads, fremfor bare at bruge en mindre størrelse såsom byte. Der kan også opstå sjove problemer når du prøver at udvide det, og din representation overstiger en ints max værdi. :)
#5+6
Woops.. Regnefejl i mit hoved... Det er naturligvis 700 der bliver multipliceret med.. (overså at hver variabels tilstandsnummer bliver lagt sammen) Som Benjamin ganske rigtigt skriver svare alle tal mellem 0 og 2100 til en tilstand, og metoden må derfor naturligvis være den mest optimale.. Jeg takker jer alle for at oplyse mig i min uvidenhed :-)
onetreehill's metode er den eneste rigtige.. Tak for hjælpen :-)
Woops.. Regnefejl i mit hoved... Det er naturligvis 700 der bliver multipliceret med.. (overså at hver variabels tilstandsnummer bliver lagt sammen) Som Benjamin ganske rigtigt skriver svare alle tal mellem 0 og 2100 til en tilstand, og metoden må derfor naturligvis være den mest optimale.. Jeg takker jer alle for at oplyse mig i min uvidenhed :-)
onetreehill's metode er den eneste rigtige.. Tak for hjælpen :-)
#6
Ellers kan man bruge det nærmeste 2-talspotens der er større end-lig #tilstande og bruge bitvis-shift + bitmasking.
Jeg vil påstå at det ikke gør nogen forskel om tallet er større 90% af tiden end de resterende 10 % :)
huffman codes?
Ellers kan man bruge det nærmeste 2-talspotens der er større end-lig #tilstande og bruge bitvis-shift + bitmasking.
Hvis det VIRKELIGT er vigtigt for dig at have små tal, vil jeg foreslå dig at kigge på frekvensen af hver tilstand. Dvs. hvis x er i tilstand 2 90% af tiden, vil det være fordelagtigt at have tilstand 2 som den første, da dette giver et lavere tal.
Jeg vil påstå at det ikke gør nogen forskel om tallet er større 90% af tiden end de resterende 10 % :)
huffman codes?
#10
Faktisk er der både en int og en long int (hvor long int er 'ubegrænset'), men da det er dynamisk typed lægger man ikke mærke til om det er en int eller long int*. Men ja, jeg tvivler på at han kun vil begrænse sig til (small) int. :)
* medmindre man bruger python <2.4.?, for der bliver der sat et L bagefter long ints :)
Faktisk er der både en int og en long int (hvor long int er 'ubegrænset'), men da det er dynamisk typed lægger man ikke mærke til om det er en int eller long int*. Men ja, jeg tvivler på at han kun vil begrænse sig til (small) int. :)
* medmindre man bruger python <2.4.?, for der bliver der sat et L bagefter long ints :)
Resultatet skal nok blive unikt (hvis ikke ud laver fejl i koden). Men den metode er jeg sikker på vil blive både langsom og kompliceret. Hold dig til en fortløbende nummerering af mulighederne. Se kommentar nummer tre for et eksempel på hvordan koden for det kunne se ud.Wolly (1) skrev:En anden måde som jeg tror vil virke, er at tildele alle mulige tilstande fortløbende numerisk værdi, omregne dem til primtal og multiplicere værdierne. Simpelt EKS:
x = 3
y = 2
z= 1
x kan være 2,3,5,7,11 og er her 5
y kan være 13,17,19,23 og er her 17
z kan være 29,31,37 osv... og er her 29
resultat = 2465
Jeg vil tro at denne metode er langt hurtige end den første, men er meget usikker på om resultatet er unikt.
Hold dig til integers. Hvis du begynder at afrunde talene vil resultaterne ikke mere være unikke.Wolly (4) skrev:God ide, desværre har nogle af variablerne over 10 tilstande, og resultatet skulle meget gerne være en Int eller Dobble.
Super ide... Jeg forudser dog at man vil få et markant større resultat end hvis man gør det med primtal.Der tager du fejl. Metoden der blev foreslået i kommentar nummer tre er optimal.
Læsbarheden bliver ikke noget problem hvis blot man definerer en funktion til at kombinere værdierne til et enkelt tal. Hver gang du skal kombinere et sæt tal er det blot et enkelt funktionskald, som vil være læseligt nok.Benjamin Krogh (6) skrev:Slutteligt er det hele fra min vinkel et møghack. Tvivler på at læsbarheden er særligt høj, at du sparer nok plads
Funktionen i sig selv vil kun være nogle få linier, så den kan også sagtens være læselig. Ydermere kunne man i den funktion checke at alle værdierne er indenfor de gyldige intervaller. Sådan check vil naturligvis gøre koden langsommere, men det vil uden tvivl fange nogle fejl tidligt som ellers vil tage lang tid at identificiere bagefter.
Om pladsbesparelsen er af betydning kommer meget an på hvad de tal skal bruges til. Skal de bruges som indeks i et array vil kombinationen fungere fint nok. Men det kan alligevel bedre betale sig at bruge et multidimensionelt array, for det vil foretage nøjagtigt de samme udregninger uden at man selv skal til at skrive koden (og rette alle de fejl man laver i den).
Hvis derimod det er fordi man har brug for at gemme tuplerne, så er der plads at spare ved at kombinere dem. I så fald er der egentlig tale om en komprimeringsalgoritme. I nogle tilfælde kan man konstruere en komprimering der er mere velegnet til det specifikke formål, men i mange tilfælde kan det bedre betale sig at blot anvende standard komprimeringer. Den standard algoritme der kommer tættest på det beskrevne er nok range coding. Men hvis man bruger en standard komprimering kan man i princippet være ligeglad med hvilken algoritme der anvendes.
Slutteligt vil jeg lige bring et enkelt citat: "premature optimization is the root of all evil".
Kort sagt lad være med at prøve at optimere på din kode før du har lavet noget der virker og du kan se hvor performance problemerne ligger. Ofte viser det sig at det man troede ville blive et problem slet ikke er det, og det er noget helt andet der er behov for at optimere på.
Hvis man optimerer for tidligt har man ikke blot spildt tid på optimeringerne, man gør også fremtidig udvikling mere besværligt.
Tak for alle jeres svar... Som i måske kan se ud fra mine posts, er jeg sq ikke den store kode-guro :-) Jeg mente naturligvis longint alle de steder jeg skrev dobble :-)
Fortryder stadig jeg droppede ud af DTU efter 2 år :-)
Jeg skal gemme en masse situationer i en dict, det er som sådan ikke noget problem, men jeg er meget i tvivl om hvordan jeg gør det hurtigst, og samtidig frygter jeg at min dict bliver for stor til at den kan tilgås funktionelt. Det er her forkortelserne kommer ind i billedet.
Jeg er dog kommet lidt i tvivl om det overhovedet er en god ide, efter alle jeres posts...
Forestil jer at jeg har 50 variabler (for nemhedens skyld kalder jeg dem index-variabler) i stedet for 5 og de alle har gennemsnitligt 8 tilstande. For hvert unikke samlede tilstand har jeg 12 variabler jeg skal have adgang til og ændre løbende.
Ved at samle nogle af index-variablerne hvor det ikke er vigtigt at have de 12 separate variabler , vil jeg mindske min dict's størrelse drastisk til fordel for performens... tror jeg :-)
Hvis jeg f.eks samlede index-variablerne i nye index af 5 stk vil jeg kun have 10 index, hvilket vil give mit dict færre dimentioner , på den anden side vil mit dict have markant flere indgange den skal søge igennem for hver gang den skal gå til næste index-var.
Min plan var at lave begge typer dict, og se hvad der var hurtigst.
Er der nogen der har et bud på vinderen, eller en bedre måde at gøre det på... Husk lige at jeg er kode-noob så vi skal gerne holde os til python :-)
Fortryder stadig jeg droppede ud af DTU efter 2 år :-)
Jeg skal gemme en masse situationer i en dict, det er som sådan ikke noget problem, men jeg er meget i tvivl om hvordan jeg gør det hurtigst, og samtidig frygter jeg at min dict bliver for stor til at den kan tilgås funktionelt. Det er her forkortelserne kommer ind i billedet.
Jeg er dog kommet lidt i tvivl om det overhovedet er en god ide, efter alle jeres posts...
Forestil jer at jeg har 50 variabler (for nemhedens skyld kalder jeg dem index-variabler) i stedet for 5 og de alle har gennemsnitligt 8 tilstande. For hvert unikke samlede tilstand har jeg 12 variabler jeg skal have adgang til og ændre løbende.
Ved at samle nogle af index-variablerne hvor det ikke er vigtigt at have de 12 separate variabler , vil jeg mindske min dict's størrelse drastisk til fordel for performens... tror jeg :-)
Hvis jeg f.eks samlede index-variablerne i nye index af 5 stk vil jeg kun have 10 index, hvilket vil give mit dict færre dimentioner , på den anden side vil mit dict have markant flere indgange den skal søge igennem for hver gang den skal gå til næste index-var.
Min plan var at lave begge typer dict, og se hvad der var hurtigst.
Er der nogen der har et bud på vinderen, eller en bedre måde at gøre det på... Husk lige at jeg er kode-noob så vi skal gerne holde os til python :-)
woops glemte lige at skrive at inden dict'et bliver fyldt ud med erfaringer, vil det have de 12 variabler for hver index, i tilfældet af at vi endnu ikke har opdaget hvordan den næste index er... en slags fall back i tilfælde af manglende informationer...
ellers ville de to beskrevne dict's være næsten ens...
ellers ville de to beskrevne dict's være næsten ens...
Gå til top
Opret dig som bruger i dag
Det er gratis, og du binder dig ikke til noget.
Når du er oprettet som bruger, får du adgang til en lang række af sidens andre muligheder, såsom at udforme siden efter eget ønske og deltage i diskussionerne.
- Forside
- ⟨
- Forum
- ⟨
- Programmering
Gå til bund