Verktyg Visningsval
2012-04-25, 22:57   #1

Isildur79

Medlem

Registrerad: apr 2012

Java - tidskomplexitet - SkipList


Hej!

Jag har fastnat med en uppgift som går utt på att mäta effektiviteten hos ConcurrentSkipList. Enligt manualen ska den prestera log(n).
Jag skapar 10 olika SkipList i storleksordningen 100 000, 200 000, 300 000 upp till 1000 000. Vare lista fylls med tal 1,3,6,9...o.s.v..
Därefter söker jag i varje skiplsita efter 10 000 slumpmässiga tal. Se kodexempel nedan.
Jag kör varje klockning ca 100 gånger och räknar sedan ut snittiden. Tyvärr får jag fel resultat och jag vet inte vad jag gör för fel.
Räknar man ut log(100000) på miniräknaren så blir det 5 och log(1000000) blir 6. Alltså ska resultaten för varje testning hamna ganska nära varandra.
Mitt resultat blir ungefär ett spann från 5-15 vilket inte är rätt! Tacksam för alla tips och ideer jag kan få angående detta.

ConcurrentSkipListSet skiplista1 = new ConcurrentSkipListSet();

long start = System.currentTimeMillis(); //klocka starttid

for (int i = 0; i < 10000; i++) {

skiplista.contains(mylist.get(i));
}

long end = System.currentTimeMillis(); //klocka sluttid
long resultat = (end - start);
Isildur79 är inte uppkopplad
2012-04-25, 23:15   #2

MrMadMan

Medlem

Plats: Umeå

Registrerad: maj 2003

Jag gissar att man med tidskomplexitet menar Stora Ordo?
Om så är fallet, så är du inne på helt fel spår och du sitter och mäter med klocka. Mitt tips är att läsa på om stora Ordo.

Om jag missförstår något så får du gärna posta hela uppgiften här.

För övrigt tycker jag resultaten verkar stämma in med O(log n)
MrMadMan är inte uppkopplad
2012-04-25, 23:44   #3

Mikael07

Medlem

Mikael07s avatar

Plats: Göteborg

Registrerad: mar 2011

Tänk på att det är skillnad på Ordo och Ordo med en godtycklig faktor. Alltså 11029484 * O(log n) = O(log n).
Tidsserierna 1 2 3 4 och 300 600 900 1200 är alltså ekvivalenta ur ett tidskomplexitetsperspektiv.
__________________
.:: Linux Mint :: i5 2500k :: Gainward GTX580 Phantom :: XMS3 8Gb :: Seagate 2Tb ::.
Mikael07 är inte uppkopplad
2012-04-26, 00:39   #4

tufflax

Medlem

tufflaxs avatar

Plats: Stockholm

Registrerad: jan 2010

Citat:
Ursprungligen inskrivet av MrMadMan Visa inlägg
Jag gissar att man med tidskomplexitet menar Stora Ordo?
Om så är fallet, så är du inne på helt fel spår och du sitter och mäter med klocka. Mitt tips är att läsa på om stora Ordo.
Varför är det så konstigt att mäta med klocka?

Citat:
Ursprungligen inskrivet av MrMadMan Visa inlägg

Om jag missförstår något så får du gärna posta hela uppgiften här.

För övrigt tycker jag resultaten verkar stämma in med O(log n)
log(10^6)/log(10^5) = 1.2 så hur verkar det stämma?

Citat:
Ursprungligen inskrivet av Mikael07 Visa inlägg
Tänk på att det är skillnad på Ordo och Ordo med en godtycklig faktor. Alltså 11029484 * O(log n) = O(log n).
Tidsserierna 1 2 3 4 och 300 600 900 1200 är alltså ekvivalenta ur ett tidskomplexitetsperspektiv.
Det borde inte vara olika faktorer när man använder exakt samma klass.

Jag kan tänka mig tre saker. Den första (inte så trolig kanske) är att skiplisten blir dålig på nått sätt om du lägger till talen i ordning. Det andra är att en riktig dator är mer komplex än de modeller man burkar tänka på i datalogi, och att saker som cachemissar och annat blir vanligare med större listor. Eller så kanske du bara gjort nått konstigt. Pastea hela koden kanske?

Senast redigerad av tufflax 2012-04-26 klockan 01:07.
tufflax är inte uppkopplad
2012-04-26, 00:55   #5

MrMadMan

Medlem

Plats: Umeå

Registrerad: maj 2003

Citat:
Ursprungligen inskrivet av tufflax Visa inlägg
Varför är det så konstigt att mäta med klocka?
För att tidskomplexitet inte mäts. Den beräknas genom att analysera algoritmen.
Beräkningarna kan i vissa fall backas upp av mätstatistik, men då behövs mycket större variation i in-datat.

Citat:
Ursprungligen inskrivet av tufflax Visa inlägg
log(10^6)/log(10^5) = 1.2 så hur verkar det stämma?
För att ökningen är logaritmisk, och inte linjär eller exponentiell.

Jag råder dig att läsa på om Ordo-begreppet. Du har inte förstått det rätt.
MrMadMan är inte uppkopplad
2012-04-26, 01:03   #6

tufflax

Medlem

tufflaxs avatar

Plats: Stockholm

Registrerad: jan 2010

Citat:
Ursprungligen inskrivet av MrMadMan Visa inlägg
För att tidskomplexitet inte mäts. Den beräknas genom att analysera algoritmen.
Beräkningarna kan i vissa fall backas upp av mätstatistik, men då behövs mycket större variation i in-datat.
"Jag har fastnat med en uppgift som går utt på att mäta effektiviteten hos ConcurrentSkipList" sa han/hon ju.

Citat:
Ursprungligen inskrivet av MrMadMan Visa inlägg
För att ökningen är logaritmisk, och inte linjär eller exponentiell.

Jag råder dig att läsa på om Ordo-begreppet. Du har inte förstått det rätt.
"5-15" (dvs en faktor 3, eller han/hon kanske t.o.m. menade en faktor 5 till 15) är inte en faktor 1.2, så det stämmer inte så bra.

Och jag kan begreppet fullständigt.
tufflax är inte uppkopplad
2012-04-26, 01:09   #7

Mikael07

Medlem

Mikael07s avatar

Plats: Göteborg

Registrerad: mar 2011

Citat:
Ursprungligen inskrivet av tufflax Visa inlägg
Det borde inte vara olika faktor när man använder exakt samma klass.
Stämmer, men TS verkar ha utgått från att faktorn skulle vara 1. Dessutom i log10 bas.
Tydligast är ju att göra en semi-log plot, då kan man även härleda vilken bas det är på logaritmen. Det är rätt stor skillnad på log2 och log10 t.ex. om man bara tittar på mätvärden i linjär bas, vilket kan vara förvillande.

För att servera det på ett fat för TS: Om du plottar problemstorleken över x-axeln, och tiden över y, så ska det se ut ungefär så här
http://algebra.freehomeworkmathhelp....tion_graph.PNG



Edit: men strunta i värdena på axlarna i bilden
__________________
.:: Linux Mint :: i5 2500k :: Gainward GTX580 Phantom :: XMS3 8Gb :: Seagate 2Tb ::.
Mikael07 är inte uppkopplad
2012-04-26, 01:12   #8

tufflax

Medlem

tufflaxs avatar

Plats: Stockholm

Registrerad: jan 2010

Citat:
Ursprungligen inskrivet av Mikael07 Visa inlägg
Stämmer, men TS verkar ha utgått från att faktorn skulle vara 1. Dessutom i log10 bas.
Tydligast är ju att göra en semi-log plot, då kan man även härleda vilken bas det är på logaritmen. Det är rätt stor skillnad på log2 och log10 t.ex. om man bara tittar på mätvärden i linjär bas, vilket kan vara förvillande.

För att servera det på ett fat för TS: Om du plottar problemstorleken över x-axeln, och tiden över y, så ska det se ut ungefär så här
http://algebra.freehomeworkmathhelp....tion_graph.PNG

Varför verkar TS ha utgått från att faktorn skulle vara 1? Jag förstår inte. Och det är ingen skillnad på log2 och log10 när man använder dem för att beskriva komplexitet "med Ordo".
tufflax är inte uppkopplad
2012-04-26, 01:19   #9

Mikael07

Medlem

Mikael07s avatar

Plats: Göteborg

Registrerad: mar 2011

Citat:
Ursprungligen inskrivet av tufflax Visa inlägg
Varför verkar TS ha utgått från att faktorn skulle vara 1? Jag förstår inte. Och det är ingen skillnad på log2 och log10 när man använder dem för att beskriva komplexitet "med Ordo".
Citerat från TS:
"Räknar man ut log(100000) på miniräknaren så blir det 5 och log(1000000) blir 6."

TS verkar anta att hans mätvärden ska bli exakt 5 och 6 för dessa storlekar, vilket motsvarar 1*log10(n)
Det är ingen skillnad för komplexitetsanalys, absolut, men som du själv antydde, han ska ju verifiera med mättider att algoritmen uppvisar logaritmisk komplexitet. Då kan det vara snurrigt om man får en mätserie i log2 bas men försöker verifiera numeriskt med log10 bas.
__________________
.:: Linux Mint :: i5 2500k :: Gainward GTX580 Phantom :: XMS3 8Gb :: Seagate 2Tb ::.
Mikael07 är inte uppkopplad
2012-04-26, 01:23   #10

MrMadMan

Medlem

Plats: Umeå

Registrerad: maj 2003

Citat:
Ursprungligen inskrivet av tufflax Visa inlägg
"Jag har fastnat med en uppgift som går utt på att mäta effektiviteten hos ConcurrentSkipList" sa han/hon ju.
Sant. Fel av mig.

"5-15" (dvs en faktor 3, eller han/hon kanske t.o.m. menade en faktor 5 till 15) är inte en faktor 1.2, så det stämmer inte så bra.

Och jag kan begreppet fullständigt.[/QUOTE]
Jag är tveksam till det.
Men om du gör det så vet du också att faktorn 3 är helt obetydlig. Det viktiga är hur lösningstiden växer tillsammans med problemrymden, och det behövs fler mätresultat om man ska kunna dra några slutsatser.
MrMadMan är inte uppkopplad
2012-04-26, 01:27   #11

tufflax

Medlem

tufflaxs avatar

Plats: Stockholm

Registrerad: jan 2010

Citat:
Ursprungligen inskrivet av Mikael07 Visa inlägg
Citerat från TS:
"Räknar man ut log(100000) på miniräknaren så blir det 5 och log(1000000) blir 6."

TS verkar anta att hans mätvärden ska bli exakt 5 och 6 för dessa storlekar, vilket motsvarar 1*log10(n)
Det är ingen skillnad för komplexitetsanalys, absolut, men som du själv antydde, han ska ju verifiera med mättider att algoritmen uppvisar logaritmisk komplexitet. Då kan det vara snurrigt om man får en mätserie i log2 bas men försöker verifiera numeriskt med log10 bas.
Jag fattar inte vad du menar med mätserie i log2. Hur får man en mätserie i någon speciell bas överhuvudtaget?
tufflax är inte uppkopplad
2012-04-26, 01:29   #12

tufflax

Medlem

tufflaxs avatar

Plats: Stockholm

Registrerad: jan 2010

Citat:
Ursprungligen inskrivet av MrMadMan Visa inlägg
Sant. Fel av mig.

Citat:
"5-15" (dvs en faktor 3, eller han/hon kanske t.o.m. menade en faktor 5 till 15) är inte en faktor 1.2, så det stämmer inte så bra.

Och jag kan begreppet fullständigt.
Jag är tveksam till det.
Men om du gör det så vet du också att faktorn 3 är helt obetydlig. Det viktiga är hur lösningstiden växer tillsammans med problemrymden, och det behövs fler mätresultat om man ska kunna dra några slutsatser.

Den faktorn 3 är ju själva mätresultatet, hur skulle det kunna vara helt obetydligt? Jag tror det är du som inte hänger med, eller tolkade TS inlägg på något annat sätt än jag gjorde.
tufflax är inte uppkopplad
2012-04-26, 02:01   #13

Mikael07

Medlem

Mikael07s avatar

Plats: Göteborg

Registrerad: mar 2011

Citat:
Ursprungligen inskrivet av tufflax Visa inlägg
Jag fattar inte vad du menar med mätserie i log2. Hur får man en mätserie i någon speciell bas överhuvudtaget?
Jag tänker mest ur praktisk synpunkt, eftersom vi har att göra med mätserier. Vad jag vill säga är att om du får en mätserie där du detaljkollar med en miniräknare kan det bli snurrigt om ett problem ökar 1s efter dubblering av problemstorleken, när man förväntar sig att den ska öka 1s efter 10ggr större problem. Bättre om du gör en semi-log plot. I vilken logaritmiskt beteende ju alltid kommer visa en linjär funktion (och ur lutningen kan du härleda log basen).

Edit: tog bort lite detaljtrams

Senast redigerad av Mikael07 2012-04-26 klockan 02:26.
__________________
.:: Linux Mint :: i5 2500k :: Gainward GTX580 Phantom :: XMS3 8Gb :: Seagate 2Tb ::.
Mikael07 är inte uppkopplad
2012-04-26, 05:02   #14

Triffid

Medlem

Triffids avatar

Plats: Lund

Registrerad: okt 2002

Om du skall mäta så borde du kanske kolla hur lång tid det tar att plocka ut ett värde om listan är 1000 stor och ett om listan är 100000 stor och sen jämföra den tiden. Detta måste göras väldigt många gånger för att få någon säkerhet i det dock. Är det då ordo N borde värdet hamna runt 500tidsenheter för den lilla och 50000tidsenheter för den stora, och om det är ordo log(n) borde/behöver värdet för det lilla och det stora inte skilja så värst mycket. osv..
__________________
Dator: BenQ BL3200PT | u2211 | Silverstone Fortress 2 | Topre realforce 45g | GTX680 DCII Top | Intel i5 3570k @ 4.5 | Intel X25-m | 12gb ram | Asus p8z77-v
Ljud: Swans M1 | hk6550 |Subwoofer: bk xls200 | xonar essence st | O2 | sennheiser hd650 | Shure srh1540 | Mr Speakers Alpha Dog | alessandro ms-1
Triffid är inte uppkopplad
2012-04-26, 09:18   #15

tufflax

Medlem

tufflaxs avatar

Plats: Stockholm

Registrerad: jan 2010

Citat:
Ursprungligen inskrivet av Mikael07 Visa inlägg
Jag tänker mest ur praktisk synpunkt, eftersom vi har att göra med mätserier. Vad jag vill säga är att om du får en mätserie där du detaljkollar med en miniräknare kan det bli snurrigt om ett problem ökar 1s efter dubblering av problemstorleken, när man förväntar sig att den ska öka 1s efter 10ggr större problem. Bättre om du gör en semi-log plot. I vilken logaritmiskt beteende ju alltid kommer visa en linjär funktion (och ur lutningen kan du härleda log basen).

Edit: tog bort lite detaljtrams
Varför just 1s? Det är ju helt godtyckligt. Det enda som spelar roll är hur tiden ökar (inte i någon speciell enhet) när n ökar. Om vi räknar på t.ex. n = 10^6 och n = 10^5 så kommer ju såklar log10 för de att bli 6 och 5. log2 blir 19.9316 och 16.6096. Tar vi kvoten av de första och andra talet i båda fallen blir det 6/5 = 1.2 och 19.9316/16.6096 = 1.2. Det ska alltså ta ca. 1.2 gånger längre tid att köra algoritmen för indata av storlek 10^6 som för indata av storlek 10^5. Det spelar ingen roll hur lång tid det faktiskt tar, vilken enhet man använder, eller vad för bas man har i logaritmen. Dock så skulle en kostant term t.ex. kunna göra att det inte riktigt blir så, och att tiden ökar med någonting mindre än en faktor 1.2, fast det känns lite onaturligt att det skulle finnas en konstant term i just detta fall. Att tiden ökar med en faktor 3 är dock lite oväntat, om man inte tar med saker som cachemissar o.s.v.
tufflax är inte uppkopplad
2012-04-26, 10:28   #16

Mikael07

Medlem

Mikael07s avatar

Plats: Göteborg

Registrerad: mar 2011

Citat:
Ursprungligen inskrivet av tufflax Visa inlägg
Varför just 1s? Det är ju helt godtyckligt. Det enda som spelar roll är hur tiden ökar (inte i någon speciell enhet) när n ökar. Om vi räknar på t.ex. n = 10^6 och n = 10^5 så kommer ju såklar log10 för de att bli 6 och 5. log2 blir 19.9316 och 16.6096. Tar vi kvoten av de första och andra talet i båda fallen blir det 6/5 = 1.2 och 19.9316/16.6096 = 1.2. Det ska alltså ta ca. 1.2 gånger längre tid att köra algoritmen för indata av storlek 10^6 som för indata av storlek 10^5. Det spelar ingen roll hur lång tid det faktiskt tar, vilken enhet man använder, eller vad för bas man har i logaritmen. Dock så skulle en kostant term t.ex. kunna göra att det inte riktigt blir så, och att tiden ökar med någonting mindre än en faktor 1.2, fast det känns lite onaturligt att det skulle finnas en konstant term i just detta fall. Att tiden ökar med en faktor 3 är dock lite oväntat, om man inte tar med saker som cachemissar o.s.v.
Instämmer. Jag ville bara poängtera att det fanns en skillnad mellan en serie värden log2(x) och log10(x), det kan underlätta att känna till. Vad som skiljer är ju bara en konstant faktor, vilken ju elimineras när man tar kvoten, som du säger. Men, som sagt, det jag mest ville ha fram var att tydligaste sätt att se samband (när man har med mätvärden att göra) är att göra en plot, då man enkelt kan identifiera enstaka avvikande värden och istället se en trend.
__________________
.:: Linux Mint :: i5 2500k :: Gainward GTX580 Phantom :: XMS3 8Gb :: Seagate 2Tb ::.
Mikael07 är inte uppkopplad
Senaste nyheterna

Redaktionens senaste nyhetsrubriker