Bygga kd-träd

Instiktivt känns det som att det är sorteringen som tar tid. Då du kommer sortera listan väldigt många gånger. Pröva med en effektivare algoritm?

Vid närmare eftertanke, måste du verkligen sortera i varje anrop?

Om det som ligger i arrayen är hyfsat osorterat kommer den ta O(n^2) tid att sortera, dvs för 100k blir det ~10 miljarder operationer som ska göras, och för 1M blir det 1000 miljarder operationer. Även om vi tänker idealfallet att din processor klarar att göra ett steg i sorteringen i varje klockcykel (vilket vore ofantligt bra) skulle det ta 5 minuter bara att sortera arrayen med photonerna första gången.

edit: tänkte kanske fel så tog bort lite text, får fundera lite mer på det

edit2: Blir inte bara log(n) sorteringar som jag tänkte först såklart, varje gång ökar ju antalet som ska göras. Däremot blir dom billigare och billigare eftersom varje sortering har ju bara hälften mot föregående att sortera. Ett exempel när n = 16 visar det ganska bra: 16^2 + 2*8^2 + 4*4^2 + 8*2^2 + 16 = 496. Men bara 16^2 = 256, alltså blir det inte ens dubbelt så mycket att göra trots omsorteringen.

Jo, O() säger ju bara hur snabbt den växer, inte exakt vad konstanterna är. 10 miljarder och 5 miljarder är samma sak, det intressanta är hur mycket det växt när indatan blev 10ggr större. Om två olika personer implementerar en insertion-sort kommer konstant-tiden nästan säkert bli olika, kanske 2 gånger, eller 10 gånger snabbare för en av dom. Men när indatan är stor, som tex 1M spelar det ingen roll vilken av dom man använder, 10 gånger snabbare är ingenting jämfört med hur mycket snabbare en sorteringsalgoritm som merge-sort är även om den måste göra mer grejer i varje steg.

Djupet i sig är nog inte farligt, du delar ju listan i 2 varje gång, så det blir bara 20 djupt som djupast med 1M photoner och det är ingenting. Däremot blir det ju ganska många funktionsanrop såklart eftersom bredden ökar. Jag är inte så vass på C++ så jag har någon bra uppfattning om exakt hur mycket olika saker kostar men jag kan ge lite förslag ändå:

Det ser ut som du har två dyra grejer som det görs mycket av förutom sorteringen, dels funktionsanropen (dvs rekursionen, 1Mst), och dels minnesalokeringen för ett Tree som sker lite i taget varje runda. Sen är förståss din nya sorteringsmetod säkert lite dyr oxå, kan vara så att den är dyrare än resten oavsett så att det är där du ska lägga tid att optimera (antagligen är det så?).

Att testa om funktionsanropen kostar något är lätt, först skriver du om den så att du har en if (n==2) oxå istället för att göra rekursionen. Eftersom du blir av med hälften av alla funktionsanrop då borde körtiden förbättras betydligt om det är anropen som är dyra.

Allokeringen av trädet kan du oxå testa på liknande sätt, när du skrivit om den med en if(n==2) så testa att allokera hela det delträdet i ett svep då och se ifall det hjälper. På samma sätt blir du nu av med hälften av allokeringarna.

Om det är sorteringen som fortfarande är dyr kan du testa genom att helt enkelt ta bort den och se hur lång tid koden tar att köra då

apro på sorterings algoritm så rekumenderar jag quiksort, den teoretiskt snabaste sorterings algorimen...

och det där med funktions anrop kan man med tur avärja med static inline...

Det är inte "den teoretiskt snabbaste sorteringsalgoritmen", det finns många algoritmer som går på n*log(n). Quicksort har dessutom worst-case performance n^2, vilket är sämre än både Heapsort, Mergesort, Binary tree sort, Introsort, Tournament sort, Smoothsort, Patience sorting och Shellsort. Att Quicksort sedan är lätt att implementera och lätt att optimera på många maskiner (med cachemissar och dyl.) är en annan sak.

En ordentlig lista på algoritmer finns på Wikipedia: Sorting algorithm - Wikipedia, the free encyclopedia

moflon: Hur ska kompilatorn kunna inlinea en rekursiv funktion? I teorin går det om man vet rekursionsdjupet på förhand iof, men i praktiken? Nej, det klarar ingen kompilator.

perost: Det är värre, en double är ju 64bit stor, och dessutom har han ju 3 dimensioner, så 1G*8*3 blir det, alltså 24GB..

Notera att i många fall kan man sortera snabbare än n*log(n). Teoretiskt är begränsningen n*log(n) om man måste göra sin sortering med enbart jämförelser (<, == osv) utan att kunna använda annan information om det som sorteras. Finns förklarat på wikipedia-sidan om sortering som You länkade. En kortlek kan t.o.m. ett barn sortera på O(n) tid lätt som en plätt

Utan att veta precis vad för begränsningar MarcusW har är det lite svårt o säga något smart, men om hans fotoner bara åker omkring i ett tomt rum med viss storlek skulle man kunna göra en bucketsort på mindre än n*log(n) ganska lätt tror jag. Även om dom får åka helt fritt begränsas dom av hur mycket som får plats i en double, så (teoretiskt) skulle man kunna göra 2^64 buckets man sorterade in dom i, och göra sin sort på O(n).

Men i det fallet krävs det inte att fotonerna är sorterade öht, så man kan skippa sorteringen helt och hållet. Hela poängen är ju att stoppa in dom i ett kd-träd, vilket kan ses som att hela bygg-kd-träd-funktionen är en sorteringsalgoritm Det du egentligen vill ha fram i varje del är ju att dela arrayen i 2 delar med alla element i ena delen mindre än dom i andra delen. Det går att göra på O(n) tid. Såhär i efterhand skulle jag väl skrivit det redan från början, men tänkte inte riktigt i dom banorna då

+1. Viktigt att tänka på när det gäller så här stora mängder data är också minneskomplexiteten (dvs. hur mycket extra minne som behövs, utöver det man redan allokerat).

Hur då?

Det man oftast missar när man jämför O(n) med O(n * log(n)) är att log(n) är nästan konstant.

2^64 >> log(n)

Den absolut största prestanda-dödaren här borde vara "pekare till pekare". Kan du inte lagra fotoner direkt i strukturen och skippa alt som har med OO att göra?

Weeblie: Sortera en kortlek kan man göra genom att lägga ut den på golvet i 4a långa rader. Och eftersom man vet att det finns 52 kort med vissa färger är det "lätt" att lägga rätt kort på rätt plats direkt. Sen samlar man in alla korten. (dvs 2n gånger behöver man gå igenom dom = O(n)).

Och jo, 2^64 är ju väldigt stort, såhär i efterhand kanske det var ett dumt exempel, man kommer ju aldrig komma upp i sådana siffror i praktiken, och det skulle kräva en maskin som indexerar i en sådan array på konstant tid, vilket är helt orimligt.

Och hur sorterar du dem individuella raderna?

D.v.s. ser till att klöver tre kommer före klöver sju?

Sorting Algorithm Animations

Och hur lokaliserar du den tredje positionen i klöverraden? Kan du direkt peka ut platsen eller måste du mer rimligt svepa över alla platser med synen?

Själva algoritmen är ju O(n), förutsatt att du har någon sorts ideal situation där du 1) direkt kan beräkna var elementet ska in och 2) insättningar är O(1) — vilket stämmer när man ska sortera en hel kortlek. Det går ju enkelt att skapa en sådan situation, även om det har konsekvensen att kräva O(n) extra minne. Pseudo-C-nånting-kod:

struct Kort{ int farg, valor; };
Kort* sortera(Kort[52] kortlek) {
  Kort* sorterad = malloc(52*sizeof(Kort));
  for(int i=0;i<52;i++) sorterad[kortlek[i].farg*13+kortlek[i].valor] = kortlek[i];
  return sorterad;
}

Edit: Det viktiga här är väl egentligen att varje element har en unik nyckel.

struct Kort{ int farg, valor; };
Kort* sortera(Kort[52] kortlek) {
  Kort* sorterad = malloc(52*sizeof(Kort));
  for(int i=0;i<52;i++) sorterad[kortlek[i].farg*13+kortlek[i].valor] = kortlek[i];
  return sorterad;
}

Jag vet mycket väl att du kan skriva ett program som på linjär tid sorterar en virtuell kortlek (eller egentligen konstant tid eftersom antalet kort är spikat).

Men scenariot här var "angående hur ett barn skulle sortera en kortlek". D.v.s. sortering av en kortlek i verkligheten/"fysiskt".

...och jag påstår att exakt samma metodik går att tillämpa i verkligheten: rita upp ett rutnät (allokera arrayen), för varje kort; beräkna vilken rad/kolonn kortet ska in på, lägg det där (for-loopen). Man behöver inte skanna över sitt rutnät om man har lite fingertoppskänsla och kan måtta hur långt från kanterna kortet ska ligga.

Låt nu "n" öka till 10 000 (100 x 100 cm). Kan din fingertoppskänsla fortfarande pricka in rutan? Öka då till 1 miljon (1000 x 1000 cm).

Jag tror att du ganska snabbt märker att du undermedvetet använder dig av divide-and-conquer vilket ger logaritmisk körtid för att lokalisera en enskild ruta.

Men nu handlade det ju om en kortlek. Får jag inte modifiera problemet så får du inte heller göra det