It is currently Sat Mar 06, 2021 3:53 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 10 posts ] 
Author Message
 Post subject: Randomly sort structured array
PostPosted: Thu Nov 28, 2019 7:03 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sun Mar 10, 2013 3:01 pm
Posts: 704
Location: Portugal
Hello!

I have a structured array in my code which I need to randomly sort between a given interval.

For example:
structure house
name.s
x.l
y.l
endstructure

dim house.house(3,10)
interval_start=2
interval_end_5

then, I give values to name, x and y.

Imagine I want to RANDOMLY sort by index 1 between the given interval.

For example, random sort index 1=1,2 or 3.

What I have been doing is to create a one index buffer array, copy the data to it USING A FOR LOOP, sort the buffer array and copy back to the structured array, but it is too slow.

How do I do it directly in the structured array?

Thank you!


Top
 Profile  
Reply with quote  
 Post subject: Re: Randomly sort structured array
PostPosted: Thu Nov 28, 2019 7:55 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3712
Location: Netherlands
SortStructuredArray has the ability to specify the index of the first and last element in the array that should be sorted.
Is that what you are trying to do ?

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: Randomly sort structured array
PostPosted: Thu Nov 28, 2019 9:07 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sun Mar 10, 2013 3:01 pm
Posts: 704
Location: Portugal
wilbert wrote:
SortStructuredArray has the ability to specify the index of the first and last element in the array that should be sorted.
Is that what you are trying to do ?


Hello!

dim house.house(3,100000)
interval_start=2
interval_end_5

For example, I wanted:
SortRandomArray(house(1,),interval_start, interval_end)
OR
SortRandomArray(house(2,),interval_start, interval_end)
OR
SortRandomArray(house(3,),interval_start, interval_end)

I want to randomize a structured array based on the first index and between an interval.

Thanks!


Top
 Profile  
Reply with quote  
 Post subject: Re: Randomly sort structured array
PostPosted: Thu Nov 28, 2019 11:05 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3712
Location: Netherlands
You could try to shuffle the items yourself by swapping memory.
https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

If it still isn't fast enough and a pseudo random is good enough, the whole procedure could be done with asm.

Code:
DeclareModule SwapMemory
 
  Declare SwapMemory(*m1, *m2, size)
 
EndDeclareModule

Module SwapMemory
 
  DisableDebugger
  EnableASM
 
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    Macro rax : eax : EndMacro
    Macro rcx : ecx : EndMacro
    Macro rdx : edx : EndMacro
    Macro rdi : edi : EndMacro
    Macro rsi : esi : EndMacro   
  CompilerEndIf
 
  Procedure SwapMemory(*m1, *m2, size)
    mov rax, [p.p_m1]
    mov rdx, [p.p_m2]
    mov ecx, [p.v_size]
    push rsi
    push rdi
    mov rsi, rax
    mov rdi, rdx
    sub ecx, 4
    !jc .l1
    !.l0:
    mov eax, [rsi + rcx]
    mov edx, [rdi + rcx]
    mov [rdi + rcx], eax
    mov [rsi + rcx], edx
    sub ecx, 4
    !jnc .l0
    !.l1:
    add ecx, 3
    !jnc .l3
    !.l2:
    movzx eax, byte [rsi + rcx]
    movzx edx, byte [rdi + rcx]
    mov [rdi + rcx], al
    mov [rsi + rcx], dl
    sub ecx, 1
    !jnc .l2
    !.l3:
    pop rdi
    pop rsi
  EndProcedure
 
EndModule





Structure house
  name.s
  x.l
  y.l
EndStructure

Dim house.house(3, 10)

; Generate sorted array

For x = 0 To 3
  For y = 0 To 10
    With house (x, y)
      \name = "house " + Str(x) + "," + Str(y)
      \x = x
      \y = y
    EndWith
  Next
Next

; Randomize house 2, 2 - 7

interval_start = 2
interval_end = 7

For i = interval_start To interval_end - 1
  j = Random(interval_end, i)
  SwapMemory::SwapMemory(@house(2, i), @house(2, j), SizeOf(house))
Next

; Show results for house 2

For y = 0 To 10
  Debug house(2, y)\name
Next

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: Randomly sort structured array
PostPosted: Thu Nov 28, 2019 4:36 pm 
Offline
Addict
Addict
User avatar

Joined: Wed Dec 23, 2009 10:14 pm
Posts: 3413
Location: Boston, MA
Use a companion array without modifying your original structure.
Code:
Structure house
  name.s
  x.l
  y.l
EndStructure
Dim house.house(3, 10)
Dim arsort(10)
; Generate sorted array
For x = 0 To 3
  For y = 0 To 10
    With house (x, y)
      arsort(y) = y
      \name = "house " + Str(x) + "," + Str(y)
      \x = x
      \y = y
    EndWith
  Next
Next
; Randomize house 2, 2 - 7
interval_start = 2
interval_end = 7
RandomSeed(123) ;<-- REMOVE AFTER DEBUG
  RandomizeArray(arsort(), interval_start, interval_end)
; Show results for house 2
For y = 0 To 10
  Debug house(2, arsort(y))\name
Next

_________________
The nice thing about standards is there are so many to choose from. ~ Andrew Tanenbaum


Top
 Profile  
Reply with quote  
 Post subject: Re: Randomly sort structured array
PostPosted: Thu Nov 28, 2019 4:45 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sun Mar 10, 2013 3:01 pm
Posts: 704
Location: Portugal
Thank you for the tips and I already have a plan.

I will create a unidimensional array with the number of items in the multidimensional one, then
buffer(number_of_items)
for f=1 to number_of_items
buffer(f)=f
next f
randomize the buffer array, and then use swap,
for f=1 to number_of_items
swap multidimensional(3,f) with multidimensional(3,buffer(f))
next f

This is my basic concept.


Top
 Profile  
Reply with quote  
 Post subject: Re: Randomly sort structured array
PostPosted: Fri Nov 29, 2019 11:37 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sun Mar 10, 2013 3:01 pm
Posts: 704
Location: Portugal
Buaaaa... I can't swap values between structured arrays:
[10:24:43] [COMPILER] Line 26169: 'Swap' only works with 2 elements of the same native type (not structured).

Is there a workaround?

Thanks!


Top
 Profile  
Reply with quote  
 Post subject: Re: Randomly sort structured array
PostPosted: Fri Nov 29, 2019 11:42 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3712
Location: Netherlands
marcoagpinto wrote:
Buaaaa... I can't swap values between structured arrays:
[10:24:43] [COMPILER] Line 26169: 'Swap' only works with 2 elements of the same native type (not structured).

Is there a workaround?

You can swap two items by swapping the memory they occupy like I did.
That's why I used this approach. I also encountered the problem that Swap doesn't work in this case.

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: Randomly sort structured array
PostPosted: Fri Nov 29, 2019 2:26 pm 
Offline
Addict
Addict
User avatar

Joined: Wed Dec 23, 2009 10:14 pm
Posts: 3413
Location: Boston, MA
marcoagpinto wrote:
Buaaaa... I can't swap values between structured arrays:
[10:24:43] [COMPILER] Line 26169: 'Swap' only works with 2 elements of the same native type (not structured).
Is there a workaround?
Why waste time/code rearranging your data if you have a companion sorted array of indexes? Think how slow databases would be if every query forced a reorder of rows.
Anyway, you have to create a Procedure with a variable *pointer.mystructure.
Then use that as a temp variable to swap each entry in your array.

_________________
The nice thing about standards is there are so many to choose from. ~ Andrew Tanenbaum


Top
 Profile  
Reply with quote  
 Post subject: Re: Randomly sort structured array
PostPosted: Fri Nov 29, 2019 2:33 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sun Mar 10, 2013 3:01 pm
Posts: 704
Location: Portugal
skywalk wrote:
marcoagpinto wrote:
Buaaaa... I can't swap values between structured arrays:
[10:24:43] [COMPILER] Line 26169: 'Swap' only works with 2 elements of the same native type (not structured).
Is there a workaround?
Why waste time/code rearranging your data if you have a companion sorted array of indexes? Think how slow databases would be if every query forced a reorder of rows.
Anyway, you have to create a Procedure with a variable *pointer.mystructure.
Then use that as a temp variable to swap each entry in your array.


Thank you.

I have created a companion array.

It was the best solution found.


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 24 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye