Fast solution to insert and shuffle data in an typed array?

Author

Message

Cliff Mellangard 3DEGS

Developer

18

Years of Service

User Offline

Joined: 20th Feb 2006

Location: Sweden

Posted: 1st May 2011 01:33

Link

Iam working on an z depth buffer for my engine and currently have this!

if Zbuffer(1,t).Size>0
for z=Zdepth to 2 step -1
Zbuffer(z,t).Size=Zbuffer(z-1,t).Size
Zbuffer(z,t).Texture=Zbuffer(z-1,t).Texture
next z
endif

Is there an faster way to simply insert my new data in to index 2 and shuffle the other data down?
This is extremely slow the way i do it

Back to top

Profile PM Website

mr_d

DBPro Tool Maker

17

Years of Service

User Offline

Joined: 26th Mar 2007

Location: Somewhere In Australia

Posted: 1st May 2011 10:53 Edited at: 1st May 2011 11:07

Link

you could maybe implement a linked list (LL)?
i.e. have an 3 extra values in your Zbuffer UDT like .ThisIndex, .NextIndex, and PrevIndex
this means that when you add entries to your array, you would need to manually manage these values as well.
i.e. first item would have .ThisIndex=1, .NextIndex=2, .PrevIndex=0; second item would have .ThisIndex=2, .NextIndex=3, .PrevIndex=1, etc.
Then when you what to insert an entry you just change the .NextIndex and .PrevIndex values of the current, next and previous items.

Note:The values for .ThisIndex, .NextIndex, and .PrevIndex are not really indexes but are really unique identifiers to uniquely identify each entry of the LL.
i.e. although it's easy to start at 1 and go 1,2,3,4,5 initially, when you start using the LL properly and add and delete entries, the actual sequential values may end up being for example 1,2,6,3,8,4,5, etc.

Hope this makes sense and helps you out.

Back to top

Profile PM Email

Grog Grueslayer

Valued Member

19

Years of Service

User Offline

Joined: 30th May 2005

Playing: Green Hell

Posted: 1st May 2011 11:48

Link

Quote: "Is there an faster way to simply insert my new data in to index 2 and shuffle the other data down?
This is extremely slow the way i do it "

Not with a 2D array like you have. If you used a 1D array you could use ARRAY INSERT AT ELEMENT to add a new element to the middle of the array.

+ Code Snippet

` Make random number picking more random
randomize timer()

` Make a UDT (User Defined Type)
type TestData
 TestName as string
 Test1 as integer
 Test2 as byte
endtype

` Dimensionalize the array
dim Test(5) as TestData

` Define the array
for t=0 to array count(Test(0))
 Test(t).TestName="Test #"+str$(t)
 Test(t).Test1=rnd(5000)
 Test(t).Test2=rnd(255)
next t

` Show the array
for t=0 to array count(Test(0))
 print "Test("+str$(t)+").TestName = "+Test(t).TestName
 print "Test("+str$(t)+").Test1 = "+str$(Test(t).Test1)
 print "Test("+str$(t)+").Test2 = "+str$(Test(t).Test2)
 print ""
next t

wait key

` Add a new element to the array at the 3rd element
array insert at element Test(0),3

cls

` Show the array again
for t=0 to array count(Test(0))
 print "Test("+str$(t)+").TestName = "+Test(t).TestName
 print "Test("+str$(t)+").Test1 = "+str$(Test(t).Test1)
 print "Test("+str$(t)+").Test2 = "+str$(Test(t).Test2)
 print ""
next t

wait key

Back to top

Profile PM Email

Cliff Mellangard 3DEGS

Developer

18

Years of Service

User Offline

Joined: 20th Feb 2006

Location: Sweden

Posted: 1st May 2011 12:03

Link

Quote: "Hope this makes sense and helps you out"

All input is good input

Quote: "Not with a 2D array like you have. If you used a 1D array you could use ARRAY INSERT AT ELEMENT to add a new element to the middle of the array."

Thanks iam going to test this as i simply nead to make two typed arrays so should it work the way i want it?
Time to try it!

Back to top

Profile PM Website

BatVink

Moderator

21

Years of Service

User Offline

Joined: 4th Apr 2003

Location: Gods own County, UK

Posted: 2nd May 2011 00:42

Link

ARRAY INSERT results in your entire array being shifted in memory. You save a bit of code, but not any time.

Linked Lists is a better way to go. You can combine this with a second array that holds a reference to all of your empty array elements in the main array. This way you can have a fairly constant array size and keep reusing elements as they become available.

Back to top

Profile PM Email

Sorry your browser is not supported!

Newcomers DBPro Corner / Fast solution to insert and shuffle data in an typed array?