Forum Mjukvara Programmering och digitalt skapande Tråd

Glesa datastrukturer och hashing

1 2
Skriv svar
Permalänk
Medlem ★
●

Glesa datastrukturer och hashing

Jag har ett återkommande problem, vilket har att göra med åtkomst till glesa datastrukturer.

Givet en volym (eller generell hyperrymd) med diskreta koordinater 0 <= x,y,z < N, vill jag spara data (i en array) associerad till vissa koordinater. Exempelvis kan element 0 innehålla data associerad till koordinat (x,y,z) = (2,18,12), element 1 till en helt annan koordinat, etc. Givet ett element i (den glesa) arrayen, kan jag enkelt veta vilken koordinat det handlar om genom att införa en till array som innehåller koordinaterna för respektive index.

Min fråga är, hur i hela friden bär jag mig åt för att åstadkomma det omvända? Dvs jag har en given koordinat (x,y,z) som jag vet finns representerad i den glesa arrayen, men jag vet inte dess index. Hur hittar man indexet? Ett krav är att en kompakt datastruktur (dvs N^3 element) inte får användas då det tar för mycket minne, samt vill jag heller inte söka i den glesa listan. Däremot är det ok att ta lite extra minne. Upp till O(N²) är ok.

Jag vill alltså åt en metod att, givet en koordinat jag vet finns representerad i den glesa listan, kunna beräkna rätt index direkt med bara en liten minnespenalty och hög beräkningseffektivitet. Är detta ens möjligt?

Har försökt söka upp en lösning på nätet, men är osäker på terminologin så har inte hittat något.

(den enda lösningen jag kommit på är att sortera de glesa värdena baserat på det "icke-glesa" indexet av koordinaterna enligt z*N*N + y*N + x. Då bör man kunna hitta sitt värde efter O(logN) sökningar, men jag vill helst undvika att söka.)

Redigera
Citera flera Citera
Permalänk
Medlem
●

Är O() verkligen viktigt? Rent spontant skulle jag göra en radix search på x, y och z i tur och ordning (dvs en hash indexerad array (av godtycklig storlek) med en lista i varje entry. Du får ju inte O(1) på uppslagningen men beroende på ditt indata och storleken på hash arrayerna så tror jag att du kan få ett riktigt bra average.

O(N^2) minne är ju ok så du borde kunna göra stora arrayer i varje sökning och man behöver ju inte allokera hash-arrayer för y och z när det inte finns nån träff för x.

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

Är O() verkligen viktigt? Rent spontant skulle jag göra en radix search på x, y och z i tur och ordning (dvs en hash indexerad array (av godtycklig storlek) med en lista i varje entry. Du får ju inte O(1) på uppslagningen men beroende på ditt indata och storleken på hash arrayerna så tror jag att du kan få ett riktigt bra average.

O(N^2) minne är ju ok så du borde kunna göra stora arrayer i varje sökning och man behöver ju inte allokera hash-arrayer för y och z när det inte finns nån träff för x.

Gå till inlägget

Menar du O() som i antalet sökningar? Isåfall är det extremt viktigt. Jag siktar på så hög beräkningseffektivitet som det bara går, och denna lookup är central i hela algoritmen. Jag kan säga som så att det finns ingen undre gräns som är snabb nog

Men jag ska kolla upp radix search. Har hört namnet, men är inte bekant med hur den fungerar. Tackar för tipset!

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

Menar du O() som i antalet sökningar?

Gå till inlägget

Nja jag menar O() som i ordo, dvs algoritmens värsta fall. Med en hashbaserad sökning så är ju värsta fallet ganska sunkigt (dvs allt data har samma hash och man måste (linjärt) söka igenom alla element).

Säg att vi kör med modulo 10 som hash. Då hamnar ju x=10, x=20 och x=30 alla på samma ställe i arrayen...

Men om man kan konstruera en hash funktion som fungerar bra i praktiken så kan det ju vara ok med ett dåligt värsta fall.

/Ivar

Redigera
Citera flera Citera
Permalänk
Medlem ★
●

Vad är det för fel på en enkel hashtabell?
$['x,y,z'] = array(x,y,z);
Sen är det ju naturligtvis upp till implementationen av hashtabellen hur effektiv den är, både minnesmässigt och snabbhet.

Eller om det rör sig om ett statiskt sammanhang (där man skapar datan en gång) så kan man väl sortera indexet för att sen köra binär sökning (iofs sökning som du ville undvika).

Möjligt att jag missar något fundamentalt här

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

Vad är det för fel på en enkel hashtabell?
$['x,y,z'] = array(x,y,z);
Sen är det ju naturligtvis upp till implementationen av hashtabellen hur effektiv den är, både minnesmässigt och snabbhet.

Eller om det rör sig om ett statiskt sammanhang (där man skapar datan en gång) så kan man väl sortera indexet för att sen köra binär sökning (iofs sökning som du ville undvika).

Möjligt att jag missar något fundamentalt här

Gå till inlägget

Ja det är väl själva implementationen som är intressant här. Det går inte att undvika sökning,dvs O(1), utan O(N^3) minne. En binärsökning är ju det snabbaste , O(log(n)), om man bara får använda O(n) minne. Men som jag förstod det så var O(N^2) minne ok och då tror jag att ett radix tree är bra.

n=antal element
N=max storlek i varje dimension

Naturligtvis så kan man ju peta in binary search trees i arrayerna och få ner worst case till O(log n).

btw, vilket språk är det som gäller? Blev lite sugen på en test implementation...

Redigera
Citera flera Citera
Permalänk
Medlem
●

Om jag inte har missuppfattat vad det är du är ute efter så är termen du letar efter Spatial Hash. Googlar man på det kommer många träffar som ser relevanta ut upp. (Vanligt i fysikmotorer, tex 2d-motorn chipmunk använder en sån)

Visa signatur

AK47s for everyone! - Angry mob
Since NaN /= NaN, I think, we should decipher 'NaN' as 'Not a NaN' - Miguel Mitrofanov
(Varför är människan så benägen att tro på Gud?) Antagligen har det lönat sig och evolutionen har drivit fram sådana hjärnor. - Anon

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

Om jag inte har missuppfattat vad det är du är ute efter så är termen du letar efter Spatial Hash. Googlar man på det kommer många träffar som ser relevanta ut upp. (Vanligt i fysikmotorer, tex 2d-motorn chipmunk använder en sån)

Gå till inlägget

Intressant, men är inte huvudpoängen med spatial hashes att hitta saker som är nära varandra? Rätta mig om jag har fel men jag fick inte uppattningen att det var ett krav...

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

Om jag inte har missuppfattat vad det är du är ute efter så är termen du letar efter Spatial Hash. Googlar man på det kommer många träffar som ser relevanta ut upp. (Vanligt i fysikmotorer, tex 2d-motorn chipmunk använder en sån)

Gå till inlägget

Spatial hashing kräver N^3 element för att resultera i en direkt lookup, som IvP säger. Och det är tyvärr uteslutet. Klart, man kan ju göra en grov spatial hashing, kanske bucketsize 4x4x4, och sedan binärsöka en indexsorterad array i varje hashbucket. Algoritmiskt är det fortfarande O(N^3) i minnesanvändning, men i praktiken skulle det nog fungera, minnesmässigt. Dock kvarstår ju sökningen som jag helst vill undvika. Men börjar inse att jag kanske för lätta lite på mina krav där.

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

Ja det är väl själva implementationen som är intressant här. Det går inte att undvika sökning,dvs O(1), utan O(N^3) minne. En binärsökning är ju det snabbaste , O(log(n)), om man bara får använda O(n) minne. Men som jag förstod det så var O(N^2) minne ok och då tror jag att ett radix tree är bra.

n=antal element
N=max storlek i varje dimension

Naturligtvis så kan man ju peta in binary search trees i arrayerna och få ner worst case till O(log n).

btw, vilket språk är det som gäller? Blev lite sugen på en test implementation...

Gå till inlägget

C/C++ till en början, kanske fortran om det visar sig vara snabbare, men tanken är att det ska över till GPU'n så småningom.
Hmm, om det är som du säger att det är omöjligt att få en direkt lookup utan N^3 minne så är det trist. Men som sagt, ska kolla radix search/sort. Det är väl en algoritm som även lämpar sig väl för GPU, alltså parallell implementering, om jag förstått saken rätt?

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

Vad är det för fel på en enkel hashtabell?
$['x,y,z'] = array(x,y,z);
Sen är det ju naturligtvis upp till implementationen av hashtabellen hur effektiv den är, både minnesmässigt och snabbhet.

Eller om det rör sig om ett statiskt sammanhang (där man skapar datan en gång) så kan man väl sortera indexet för att sen köra binär sökning (iofs sökning som du ville undvika).

Möjligt att jag missar något fundamentalt här

Gå till inlägget

Med en hashtabell måste jag väl söka? Om jag inte kör spatial hashing, men då använder jag alldeles för mycket minne.

Redigera
Citera flera Citera
Permalänk
Medlem ★
●

Hmm, det här pappret verkar innehålla vad jag söker:

"Perfect Spatial Hashing"

http://research.microsoft.com/en-us/um/people/hoppe/perfectha...

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

(den enda lösningen jag kommit på är att sortera de glesa värdena baserat på det "icke-glesa" indexet av koordinaterna enligt z*N*N + y*N + x. Då bör man kunna hitta sitt värde efter O(logN) sökningar, men jag vill helst undvika att söka.)

Gå till inlägget

Vore inte en enkel och snabb, forfarande O(log n) dock, lösning att hasha "z*N*N + y*N + x" till så många buckets du har plats med och lägga ett binary search tree i varje bucket?

Redigera
Citera flera Citera
Permalänk
Medlem ★
●

Vad ska applikationen göra i slutändan? Jag börjar bli nyfiken.

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

Vad ska applikationen göra i slutändan? Jag börjar bli nyfiken.

Gå till inlägget

Jag med...

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

Vore inte en enkel och snabb, forfarande O(log n) dock, lösning att hasha "z*N*N + y*N + x" till så många buckets du har plats med och lägga ett binary search tree i varje bucket?

Gå till inlägget

Du menar som jag skrev i inlägg #9 ? Har aldrig använt hashing innan (förutom spatial hashing med direkt lookup), så jag är lite oklar på hur det används, och terminologin kring det.

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

Vad ska applikationen göra i slutändan? Jag börjar bli nyfiken.

Gå till inlägget

Tänkte göra en enkel path-tracer, alltså en 3d-renderare som klarar global illumination, eller 'indirekt ljus'. Så jag måste göra ohemult många ray-intersections med geometrin och spara resultatet på något sätt. Så en intersection kommer ge mig en koordinat, och bidraget från den strålen sparar/läser jag i en spatial hash-bucket. Värdena, ljusbidragen, i dessa används för att integrera renderingsekvationen. Det är dessa buckets jag vill kunna spara glest, istället för att göra en full spatial hash när mycket av 'världen' kommer vara tomrum. Med gles struktur har jag råd att göra mina buckets mindre och få högre noggrannhet på ljusspridningen.
Lite löst förklarat, har inte tänkt igenom det helt och fullt.

Men det är alltså ett fall där det inte finns något sätt som är tillräckligt snabbt, man får vänta hursomhelst, så ju snabbare desto bättre!

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

Tänkte göra en enkel path-tracer, alltså en 3d-renderare som klarar global illumination, eller 'indirekt ljus'. Så jag måste göra ohemult många ray-intersections med geometrin och spara resultatet på något sätt. Så en intersection kommer ge mig en koordinat, och bidraget från den strålen sparar/läser jag i en spatial hash-bucket. Värdena, ljusbidragen, i dessa används för att integrera renderingsekvationen. Det är dessa buckets jag vill kunna spara glest, istället för att göra en full spatial hash när mycket av 'världen' kommer vara tomrum. Med gles struktur har jag råd att göra mina buckets mindre och få högre noggrannhet på ljusspridningen.
Lite löst förklarat, har inte tänkt igenom det helt och fullt.

Men det är alltså ett fall där det inte finns något sätt som är tillräckligt snabbt, man får vänta hursomhelst, så ju snabbare desto bättre!

Gå till inlägget

Coolers. Misstänkte nästan att det var något grafiskt.
Renderar du för att sen kunna visa scenen i realtid eller renderar du en enda statisk vy?
Jag såg en ganska intressant implementation av "radiosity" i OpenGL för lääänge sen. Det var en polygonscen där polygonern var uppdelade i en x*y-grid där han sedan interpolerade ljusvärderna. Det coola var att för ljustestningen satte han kameran (via glut) från varje punkt på polygonerna mot varje annan punkt på andra polygoner och på så sätt fick visibilitytestning. Ljusvärdena lagrades sen i texturer och det tog inte många pass för att tydligt se "color bleeding" och annat fränt. Skuggor fick man ju på köpet.

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

Coolers. Misstänkte nästan att det var något grafiskt.
Renderar du för att sen kunna visa scenen i realtid eller renderar du en enda statisk vy?
Jag såg en ganska intressant implementation av "radiosity" i OpenGL för lääänge sen. Det var en polygonscen där polygonern var uppdelade i en x*y-grid där han sedan interpolerade ljusvärderna. Det coola var att för ljustestningen satte han kameran (via glut) från varje punkt på polygonerna mot varje annan punkt på andra polygoner och på så sätt fick visibilitytestning. Ljusvärdena lagrades sen i texturer och det tog inte många pass för att tydligt se "color bleeding" och annat fränt. Skuggor fick man ju på köpet.

Gå till inlägget

Ha, smart trick! Ja, det är tunga beräkningar men man får som sagt mycket på köpet som man slipper specialkoda för, och snyggt blir det. Jag tänkte försöka mig på monte carlo approachen med importance sampling.
Får se vad det blir, om man gör någon adaptive refinement kanske man kan få det interaktivt. Hade bara tänkte implementera klotprimitiver till en början, så det bör vara rätt snabbt. Vill mest få kläm på algoritmen och metodiken.

Redigera
Citera flera Citera
Permalänk
Medlem
●

När jag skrev mitt inlägg tänkte jag främst inte på en perfekt hash-funktion likt artikeln från ms, utan en "vanlig" hash-funktion (tex http://stackoverflow.com/questions/5928725/hashing-2d-3d-and-...). Om det i enstaka fall finns fler än ett element i en hashbucket borde inte spela någon roll för ditt fall, det borde vara medel-hastigheten för att kolla en koordinat som är viktig?
Eventuellt om det behövs kan du ha varje bucket sorterad, jag har lite svårt att uppskatta om det är värt det eller bara loopa igenom den om den innehåller fler än 1 element... antar att det beror lite på om du mest kommer söka i hashen eller lägga till/ta bort från den.

Fast om det funkar med den perfekta hashen från artikeln kanske den blir snabbare.. bäst är nog att testa helt enkelt

Visa signatur

AK47s for everyone! - Angry mob
Since NaN /= NaN, I think, we should decipher 'NaN' as 'Not a NaN' - Miguel Mitrofanov
(Varför är människan så benägen att tro på Gud?) Antagligen har det lönat sig och evolutionen har drivit fram sådana hjärnor. - Anon

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

Ha, smart trick! Ja, det är tunga beräkningar men man får som sagt mycket på köpet som man slipper specialkoda för, och snyggt blir det. Jag tänkte försöka mig på monte carlo approachen med importance sampling.
Får se vad det blir, om man gör någon adaptive refinement kanske man kan få det interaktivt. Hade bara tänkte implementera klotprimitiver till en början, så det bör vara rätt snabbt. Vill mest få kläm på algoritmen och metodiken.

Gå till inlägget

Jag kräver att du visar screenshots så fort du har någonting(!) att visa.

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

Jag kräver att du visar screenshots så fort du har någonting(!) att visa.

Gå till inlägget

Will do, men det kan nog ta ett tag. Har dessvärre ett jobb att sköta vid sidan av mina hobbys
Men med lite flyt kan jag nog knåpa ihop Yet Another Cornell Box inom en rimlig framtid...

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

Jag kräver att du visar screenshots så fort du har någonting(!) att visa.

Gå till inlägget

Nu har jag roddat ihop något jag är hyfsat nöjd med! Gjorde en post med bild i 3D-forumet:

#13755273

Använde i slutändan inte någon gles datastruktur. Det är något som kallas irradiance caching där man behöver det. Jag gjorde brute force path tracing istället där man inte behöver hålla koll på någonting..

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

Nu har jag roddat ihop något jag är hyfsat nöjd med! Gjorde en post med bild i 3D-forumet:

#13755273

Använde i slutändan inte någon gles datastruktur. Det är något som kallas irradiance caching där man behöver det. Jag gjorde brute force path tracing istället där man inte behöver hålla koll på någonting..

Gå till inlägget

Kick MF ass!
Det enda jag kan klaga på är lite aliasing på ljuskällorna.

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

Kick MF ass!
Det enda jag kan klaga på är lite aliasing på ljuskällorna.

Gå till inlägget

Tackar
Ja den där aliasingen beror på att ljuskällorna har så pass höga värden (allt e float såklart innan rasteriseringen) så att de viktar stenhårt i pixel-subsamplingen. Om jag clippar värdet till vitt (istället för "supervitt") innan jag tar medelvärdet för subsamplingen så borde det försvinna.

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

Tackar
Ja den där aliasingen beror på att ljuskällorna har så pass höga värden (allt e float såklart innan rasteriseringen) så att de viktar stenhårt i pixel-subsamplingen. Om jag clippar värdet till vitt (istället för "supervitt") innan jag tar medelvärdet för subsamplingen så borde det försvinna.

Gå till inlägget

Vad jobbar du med? *nyfiken i en strut* Själv är jag sjukskriven utvecklare. Kan lite om allt och har får dålig koncentration att bli riktigt bra på något haha. Under hösten ska jag försöka bli vettig på C# för att jag har lite Windows-program som jag tänkte göra.
Petproject är bla DNSdigger.com där jag senast la till en fulltext sökmotor för robots.txt.

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

Vad jobbar du med? *nyfiken i en strut* Själv är jag sjukskriven utvecklare. Kan lite om allt och har får dålig koncentration att bli riktigt bra på något haha. Under hösten ska jag försöka bli vettig på C# för att jag har lite Windows-program som jag tänkte göra.
Petproject är bla DNSdigger.com där jag senast la till en fulltext sökmotor för robots.txt.

Gå till inlägget

Jo jag känner igen det där. Det är kul att köra på något spår tills att man känner att man fått kläm på vad det handlar om och löst problemet. Att fortsätta och göra det fullt ut brukar vara rätt boring..
Just nu jobbar jag som forskarassistent och utvecklar beräkningsmetodik och kod (CUDA) för ett fysikaliskt simuleringsverktyg. Men innan det jobbade jag med digital visual effects sedan länge.. Inte så konsekventa yrkesval kanske Gillar fysik, grafik och kod lika delar ungefär.. Men därav intresset för att skriva renderare!

Vad gör DNSdigger, och vad är robots.txt? Antar att du utvecklar för web/IT/nätverk etc.
Är sugen på att lära mig lite om hur man rotar runt på nätet och mobila enheter, med lämplig kodbas. Ska precis hämta hem android SDK och se om man kan göra en hello world iaf

Redigera
Citera flera Citera
Permalänk
Datavetare ★
●

Nu gick det ju bra ändå, men det du letade efter är något som kallas Patricia Trie då som är mer utrymmeseffektivt än en Radix Trie.

I ditt fall skulle faktiskt ett Radix Trie bli O(1). Anledningen är att värsta söktiden för ett Radix Trie är att du går ner i det djupaste trädet, men i ditt fall skulle alla nycklar vara av exakt samma längd: antal bitar som x+y+z tar.

Ett Radix Trie är däremot inte helt optimalt (trots O(1)) i ditt fall då du säger att koordinaterna inte klustrar sig speciellt mycket. Det man då kan göra är att "komprimera" sitt Radix Trie på höjden och bara lägga in de interna noder som krävs för att separerar existerande element.

Ex: där jag har följande element

  0: 0000-0000b
  1: 0000-0001b
100: 0110-0100b
200: 1100-1000b
255: 1111-1111b

ger följande Radix Trie

där höjden på trädet avgör vilken bit i din nyckel du ska titta på

Patricia Trie är också känt som "path-compressed Radix Trie" (finns även något som kallas level-compressed trie, något som är bra om värden tenderar att ligga nära varandra) och ser ut på följande sätt för exemplet

De interna noderna (diamanterna) innehåller alltid två barn och värdet av den interna noden är vilken bit man ska titta på för att avgöra om man ska gå till vänster (nolla) eller till höger (etta).

Utseendet på Radix och Patricia träd bestäms entydigt av dess element så man behöver inte (man kan inte heller) balansera dessa träd.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

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

Vad gör DNSdigger, och vad är robots.txt? Antar att du utvecklar för web/IT/nätverk etc.

Gå till inlägget

DNSDigger resolvar alla domännamn som jag kan få tag på och bygger upp ett index som gör att jag kan lista "alla" hosts som finns bakom ett IP/DNS/Adsense/Analytics.
Robots.txt (http://sv.wikipedia.org/wiki/Robots_Exclusion_Standard) är en hint till vilka sidor en HTTP-robot "får" ladda ner.
Här är Sweclockers robots.txt http://www.sweclockers.com/robots.txt

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

Nu har jag roddat ihop något jag är hyfsat nöjd med! Gjorde en post med bild i 3D-forumet:

#13755273

Använde i slutändan inte någon gles datastruktur. Det är något som kallas irradiance caching där man behöver det. Jag gjorde brute force path tracing istället där man inte behöver hålla koll på någonting..

Gå till inlägget

Det där ser riktigt ruskigt bra ut, imo. Jag är svårt imponerad och kraftigt avundsjuk.

Visa signatur

5950X, 3090

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