Forum Mjukvara Programmering och digitalt skapande Tråd

Java - tidskomplexitet - SkipList

1
Skriv svar
Permalänk
Medlem
●

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);

Redigera
Citera flera Citera
Permalänk
Medlem
●

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)

Redigera
Citera flera Citera
Permalänk
Medlem ★
●

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.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av MrMadMan:

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.

Gå till inlägget

Varför är det så konstigt att mäta med klocka?

Skrivet av MrMadMan:

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)

Gå till inlägget

log(10^6)/log(10^5) = 1.2 så hur verkar det stämma?

Skrivet av Mikael07:

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.

Gå till inlägget

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 redigerat
Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av tufflax:

Varför är det så konstigt att mäta med klocka?

Gå till inlägget

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.

Skrivet av tufflax:

log(10^6)/log(10^5) = 1.2 så hur verkar det stämma?

Gå till inlägget

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.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av MrMadMan:

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.

Gå till inlägget

"Jag har fastnat med en uppgift som går utt på att mäta effektiviteten hos ConcurrentSkipList" sa han/hon ju.

Skrivet av MrMadMan:

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.

Gå till inlägget

"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.

Redigera
Citera flera Citera
Permalänk
Medlem ★
●
Skrivet av tufflax:

Det borde inte vara olika faktor när man använder exakt samma klass.

Gå till inlägget

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.com/Relations_and_Functio...

Edit: men strunta i värdena på axlarna i bilden

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av Mikael07:

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.com/Relations_and_Functio...

Gå till inlägget

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".

Redigera
Citera flera Citera
Permalänk
Medlem ★
●
Skrivet av tufflax:

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".

Gå till inlägget

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.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av tufflax:

"Jag har fastnat med en uppgift som går utt på att mäta effektiviteten hos ConcurrentSkipList" sa han/hon ju.

Gå till inlägget

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.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av Mikael07:

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.

Gå till inlägget

Jag fattar inte vad du menar med mätserie i log2. Hur får man en mätserie i någon speciell bas överhuvudtaget?

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av MrMadMan:

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.

Gå till inlägget

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.

Redigera
Citera flera Citera
Permalänk
Medlem ★
●
Skrivet av tufflax:

Jag fattar inte vad du menar med mätserie i log2. Hur får man en mätserie i någon speciell bas överhuvudtaget?

Gå till inlägget

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 redigerat
Redigera
Citera flera Citera
Permalänk
Medlem ★
●

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..

Visa signatur

“Every atom in your body came from a star that exploded. And, the atoms in your left hand probably came from a different star than your right hand. It really is the most poetic thing I know about physics: You are all stardust. ... The stars died so that you could be here today.” - Lawrence M. Krauss

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av Mikael07:

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

Gå till inlägget

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.

Redigera
Citera flera Citera
Permalänk
Medlem ★
●
Skrivet av tufflax:

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.

Gå till inlägget

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.

Redigera
Citera flera Citera
1
Skriv svar
Senaste nyheterna
Hårdvara
Mjukvara
Övrigt
Nytt i forumet
Datorkomponenter
System
Ljud, bild och kommunikation
Spel och mjukvara