Randomly sort structured array

marcoagpinto · **Posted:** Thu Nov 28, 2019 7:03 am

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!

wilbert · **Posted:** Thu Nov 28, 2019 7:55 am

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 ?

marcoagpinto · **Posted:** Thu Nov 28, 2019 9:07 am

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!

wilbert · **Posted:** Thu Nov 28, 2019 11:05 am

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

skywalk · **Posted:** Thu Nov 28, 2019 4:36 pm

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

marcoagpinto · **Posted:** Thu Nov 28, 2019 4:45 pm

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.

marcoagpinto · **Posted:** Fri Nov 29, 2019 11:37 am

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!

wilbert · **Posted:** Fri Nov 29, 2019 11:42 am

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.

skywalk · **Posted:** Fri Nov 29, 2019 2:26 pm

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.

marcoagpinto · **Posted:** Fri Nov 29, 2019 2:33 pm

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.

PureBasic Forum

Randomly sort structured array

Who is online