Matrix to string

New to FreeBASIC? Post your questions here.
Carlos Herrera
Posts: 82
Joined: Nov 28, 2011 13:29
Location: Dictatorship

Matrix to string

Post by Carlos Herrera »

Dear All,
The following simplistic procedure converts a double precision matrix to the string.

Code: Select all

sub clip_string_uni_matrix (Z() As Double)
    ' converts matrix to clips string variable, which is global
    ' terminate  with CRLF, also the last line
    Dim As Integer lbx, ubx, lby, uby, i, j, nx, ny, nxy, nzsize
    lbx = Lbound(Z,1)
    ubx = Ubound(Z,1)
    lby = Lbound(Z,2)
    uby = Ubound(Z,2)
    clips = ""
    For i = lby To uby
        For j = lbx to ubx-1
            clips = clips + Str(Z(i,j)) + Chr(9)
        next j
        clips = clips + Str(Z(i,ubx)) + Chr(13) + Chr(10)
    Next i
End sub
Matrix has 511 x 511 size. With clips dim shared as string, conversion takes 13.5 seconds.
If clips is dim shared as Zstring *5505024, it takes 4 times longer. Anyway, it is extremely
slow. How to make it faster?
Thank you,
Carlos
(win10, 1.05, 64)
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Matrix to string

Post by jj2007 »

Without a full testbed, the analysis of your problem is difficult. However, it is pretty clear that this part is very slow:

Code: Select all

        For j = lbx to ubx-1
            clips = clips + Str(Z(i,j)) + Chr(9)
        next j
Allocate one long line, then copy the 512 tiny strings into that line and trim it as needed.

P.S.: I gave it a quick try, see Creating a matrix of doubles and store it to a text file. On my Core i5, creating the strings takes less than 0.1 seconds. The text file is about 3MB.
Munair
Posts: 1286
Joined: Oct 19, 2017 15:00
Location: Netherlands
Contact:

Re: Matrix to string

Post by Munair »

It might help if you use a union instead of plain number to string conversion and also limit the string operations by using a line ending constant:

Code: Select all

const EndOfLine = chr(13)+chr(10)

type TDouble
	union
		char as string * 8
		value as double
	end union
end type

' ...

sub clip_string_uni_matrix (Z() As TDouble)
    ' converts matrix to clips string variable, which is global
    ' terminate  with CRLF, also the last line
    Dim As Integer lbx, ubx, lby, uby, i, j, nx, ny, nxy, nzsize
    lbx = Lbound(Z,1)
    ubx = Ubound(Z,1)
    lby = Lbound(Z,2)
    uby = Ubound(Z,2)
    clips = ""
    For i = lby To uby
        For j = lbx to ubx-1
            clips = clips + Z(i,j).char + Chr(9)
        next j
        clips = clips + Z(i,ubx).char + EndOfLine
    Next i
End sub
marpon
Posts: 342
Joined: Dec 28, 2012 13:31
Location: Paris - France

Re: Matrix to string

Post by marpon »

better to use pointers and memcpy!

preallocate zstring ptr with a big size ex 10000 or more
check if enough space to copy
if yes : memcpy the strptr( Str(Z(i,j)) to the rigth position and length,in that zstring ptr
if not : the allocated size is not enougth, reallocate the zstring ptr with the double size before memcpy
, add (9) or (13,10) be sure to always verify if enough space allocated
finish adding 0 to close the zstring

then dim as string result = *(the zstring ptr you have)

et voila
Munair
Posts: 1286
Joined: Oct 19, 2017 15:00
Location: Netherlands
Contact:

Re: Matrix to string

Post by Munair »

Yes, marpon's suggestion will be a great speed improvement too, but it requires administering the string position and size.
marcov
Posts: 3455
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: Matrix to string

Post by marcov »

If the string type separates size from length, simply set the size very high before starting. Adding then doesn't force constant reallocations.

Otherwise you need to do what Marpon says, do manual appending in a block of memory. If such a procedure is generalized to a class it is often called a stringbuilder. (it is a common problem for e.g. webpage or xml file generation, where every piece of a DOM tree adds a tag).
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Matrix to string

Post by fxm »

marpon wrote:... if yes : memcpy the strptr( Str(Z(i,j)) to the rigth position and length,in that zstring ptr...
'Str()' is a temporary variable, so you can not directly access to the address of its character data (you must first copy it in a declared string before calling memcpy).
grindstone
Posts: 862
Joined: May 05, 2015 5:35
Location: Germany

Re: Matrix to string

Post by grindstone »

The sub is that awfully slow, because with every extension the whole existing string is copied to an other memory location. Better once create an empty string of spaces of the necessary length an then replace the spaces with the converted doubles (maybe even faster with indexed strings instead of MID):

Code: Select all

Sub clip_string_uni_matrix (Z() As Double)
	' converts matrix to clips string variable, which is global
	' terminate  with CRLF, also the last line
	Dim As Integer lbx, ubx, lby, uby, i, j, nx, ny, nxy, nzsize, dpos, cnt
	Dim As String g
	lbx = LBound(Z,1)
	ubx = UBound(Z,1)
	lby = LBound(Z,2)
	uby = UBound(Z,2)

	'calculate necessary string length
	For i = lby To uby
		For j = lbx To ubx-1
			cnt += Len(Str(Z(i,j))) + 1
		Next
		cnt += Len(Str(Z(i,ubx))) + 2
	Next
	
	clips = Space(cnt) 'create empty string
	dpos = 1
	
	For i = lby To uby
		For j = lbx To ubx-1
			g = Str(Z(i,j)) + Chr(9)
			Mid(clips, dpos, Len(g)) = g 'replace spaces with "double" string
			dpos += Len(g)
		Next j
		g = Str(Z(i,ubx)) + Chr(13) + Chr(10)
		Mid(clips, dpos, Len(g)) = g
		dpos += Len(g)
	Next i
End Sub
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Matrix to string

Post by dodicat »

Straight to file is fast.

Code: Select all

 

#include "file.bi"
dim shared clips as string
dim shared mfile as string
mfile="matrixdata.txt"
sub clip_string_uni_matrix (Z() As Double)
    ' converts matrix to clips string variable, which is global
    ' terminate  with CRLF, also the last line
    Dim As Integer lbx, ubx, lby, uby, i, j, nx, ny, nxy, nzsize
    lbx = Lbound(Z,1)
    ubx = Ubound(Z,1)
    lby = Lbound(Z,2)
    uby = Ubound(Z,2)
    clips = ""
    open mfile for output as #1
    For i = lby To uby
        For j = lbx to ubx-1
            print #1,str(Z(i,j))+ chr(9);
           ' clips = clips + Str(Z(i,j)) + Chr(9)
        next j
        print #1,Str(Z(i,ubx)) + Chr(13) + Chr(10)
        'clips = clips + Str(Z(i,ubx)) + Chr(13) + Chr(10)
    Next i
    close #1
End sub


Function loadfile(file as string) as String
	If FileExists(file)=0 Then Print file;" not found":Sleep:end
   var  f=freefile
    Open file For Binary Access Read As #f
    Dim As String text
    If Lof(f) > 0 Then
      text = String(Lof(f), 0)
      Get #f, , text
    End If
    Close #f
    return text
end Function

redim as double d(1 to 511,1 to 511)

for n as long=1 to ubound(d,1)
    for m as long=1 to ubound(d,2)
        d(n,m)=rnd
    next
next

dim as double t=timer
clip_string_uni_matrix(d())
 clips=loadfile("matrixdata.txt")
print "Time  ";timer-t
print mid(clips,1,1000)
print "..."

print "done"
''kill mfile
sleep



     
marpon
Posts: 342
Joined: Dec 28, 2012 13:31
Location: Paris - France

Re: Matrix to string

Post by marpon »

elaborated solution with pointer

i put it in a function to return the needed string dont need shared string inside, if you want a sub convert it and use the shared string.

Code: Select all

#include "crt/string.bi"       'needed for memcpy function

#define K_VALUE     10000     'can be increased for more speed

function clip_string_uni_matrix(z() as double) as string
    ' converts matrix to clips string variable, which is global
    ' terminate with crlf, also the last line
    dim as integer lbx, ubx, lby, uby, i, j /' , nx, ny, nxy, nzsize '/ 
    lbx = lbound(z , 1)
    ubx = ubound(z , 1)
    lby = lbound(z , 2)
    uby = ubound(z , 2)
     /' clips = "" '/ 
    
    dim as zstring ptr ps1 = allocate( K_VALUE)
    dim as integer k = K_VALUE
    dim as integer max1 = 0
    dim as integer ilen
    dim as string temp
    
    for i = lby to uby
        for j = lbx to ubx
            temp = str(z(i , j))
            ilen = len(temp)
            if k < max1 + 3  + ilen then  'corrected here
                k *= 2
                ps1 = reallocate(ps1 , k)
            end if
            memcpy(ps1 + max1 , strptr(temp) , ilen)
            max1 += ilen
            if j = ubx then
                ps1[max1] = 13
                ps1[max1 + 1] = 10
                max1 += 2
            else
                ps1[max1] = 9
                max1 += 1
            end if
        next j
    next i
    ps1[max1] = 0
    return *ps1
end function
marpon
Posts: 342
Joined: Dec 28, 2012 13:31
Location: Paris - France

Re: Matrix to string

Post by marpon »

made a test to check speed

Code: Select all

#include "crt/string.bi" 'needed for memcpy



#define K_VALUE 10000  'can be increased for more speed

function clip_string_uni_matrix(z() as double) as string
    ' converts matrix to clips string variable, which is global
    ' terminate with crlf, also the last line
    dim as integer lbx, ubx, lby, uby, i, j /' , nx, ny, nxy, nzsize '/ 
    lbx = lbound(z , 1)
    ubx = ubound(z , 1)
    lby = lbound(z , 2)
    uby = ubound(z , 2)
     /' clips = "" '/ 
    
    dim as zstring ptr ps1 = allocate(K_VALUE)
    dim as integer k = K_VALUE
    dim as integer max1 = 0
    dim as integer ilen
    dim as string temp
    
    for i = lby to uby
        for j = lbx to ubx
            temp = str(z(i , j))
            ilen = len(temp)
            if k < max1 + 3  + ilen then
                k *= 2
                ps1 = reallocate(ps1 , k)
            end if
            memcpy(ps1 + max1 , strptr(temp) , ilen)
            max1 += ilen
            if j = ubx then
                ps1[max1] = 13
                ps1[max1 + 1] = 10
                max1 += 2
            else
                ps1[max1] = 9
                max1 += 1
            end if
        next j
    next i
    ps1[max1] = 0
    return * ps1
end function



redim z1(511, 511) as double
dim as integer i, j

for i = 0 to 511
	for j = 0 to 511
		z1(i,j) = rnd() * 2145787
	next
next
	

dim as double d1 = timer()
dim as string s1= clip_string_uni_matrix(z1())
d1 = timer() - d1 

print "done in" , d1 ; " secondes"  : print
print "len = " ;len(s1) : print : print
print left(s1, 1000): print : print

print "Any key to close"
sleep
result from my pc arround 0.26 ... secondes win 10 compiled 32bits
result from my pc arround 0.23 ... secondes win 10 compiled 64bits
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Matrix to string

Post by dodicat »

Double check.
view end of the string this time.

Code: Select all

#include "crt/string.bi" 'needed for memcpy
#include "file.bi"
dim shared mfile as string
mfile="matrixdata.txt"

#define K_VALUE 10000  'can be increased for more speed

function clip_string_uni_matrix(z() as double) as string
    ' converts matrix to clips string variable, which is global
    ' terminate with crlf, also the last line
    dim as integer lbx, ubx, lby, uby, i, j /' , nx, ny, nxy, nzsize '/ 
    lbx = lbound(z , 1)
    ubx = ubound(z , 1)
    lby = lbound(z , 2)
    uby = ubound(z , 2)
     /' clips = "" '/ 
   
    dim as zstring ptr ps1 = allocate(K_VALUE)
    dim as integer k = K_VALUE
    dim as integer max1 = 0
    dim as integer ilen
    dim as string temp
    
    for i = lby to uby
        for j = lbx to ubx
            temp = str(z(i , j))
            ilen = len(temp)
            if k < max1 + 3  + ilen then
                k *= 2
                ps1 = reallocate(ps1 , k)
            end if
            memcpy(ps1 + max1 , strptr(temp) , ilen)
            max1 += ilen
            if j = ubx then
                ps1[max1] = 13
                ps1[max1 + 1] = 10
                max1 += 2
            else
                ps1[max1] = 9
                max1 += 1
            end if
        next j
    next i
    ps1[max1] = 0
    return * ps1
end function

sub clip_string_uni_matrix2 (Z() As Double)
    ' converts matrix to clips string variable, which is global
    ' terminate  with CRLF, also the last line
    var f=freefile
    Dim As Integer lbx, ubx, lby, uby, i, j, nx, ny, nxy, nzsize
    lbx = Lbound(Z,1)
    ubx = Ubound(Z,1)
    lby = Lbound(Z,2)
    uby = Ubound(Z,2)
    open mfile for output as #f
    For i = lby To uby
        For j = lbx to ubx-1
            print #1,str(Z(i,j))+ chr(9);
        next j
        print #1,Str(Z(i,ubx))
    Next i
    close #f
End sub

Function loadfile(file as string) as String
	If FileExists(file)=0 Then Print file;" not found":Sleep:end
   var  f=freefile
    Open file For Binary Access Read As #f
    Dim As String text
    If Lof(f) > 0 Then
      text = String(Lof(f), 0)
      Get #f, , text
    End If
    Close #f
    return text
end Function
randomize 1


dim as long lim=511

redim z1(lim, lim) as double
dim as integer i, j

for i = 0 to lim
   for j = 0 to lim
      z1(i,j) = rnd() * 2145787
   next
next
   

dim as double d1 = timer()
dim as string s1= clip_string_uni_matrix(z1())
d1 = timer() - d1 

print "done in" , d1 ; " secondes"  : print
print "len = " ;len(s1) : print : print
print "line endings ";instr(s1,chr(13,10))
print right(s1, 1000): print : print


print
print


d1=timer
dim as string s2
clip_string_uni_matrix2(z1())
s2=loadfile(mfile)
d1 = timer() - d1 
print "done in" , d1 ; " secondes"  : print
print "len = " ;len(s2) : print : print
print "line endings ";instr(s2,chr(13,10))
print right(s2, 1000): print : print
print iif(s2<>s1,"disagreement","OK")
print "Any key to close"
sleep
kill mfile  
Carlos Herrera
Posts: 82
Joined: Nov 28, 2011 13:29
Location: Dictatorship

Re: Matrix to string

Post by Carlos Herrera »

Thank you all for the rapid and extremely helpful responses.
Carlos
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Matrix to string

Post by jj2007 »

marpon wrote:made a test to check speed
...
result from my pc arround 0.26 ... secondes win 10 compiled 32bits
result from my pc arround 0.23 ... secondes win 10 compiled 64bits
Good job - 0.34/0.27 on my machine. Only Assembly can beat that.
counting_pine
Site Admin
Posts: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: Matrix to string

Post by counting_pine »

jj2007 wrote:Without a full testbed, the analysis of your problem is difficult. However, it is pretty clear that this part is very slow:

Code: Select all

        For j = lbx to ubx-1
            clips = clips + Str(Z(i,j)) + Chr(9)
        next j
Allocate one long line, then copy the 512 tiny strings into that line and trim it as needed.

P.S.: I gave it a quick try, see Creating a matrix of doubles and store it to a text file. On my Core i5, creating the strings takes less than 0.1 seconds. The text file is about 3MB.
Good catch.
FB can append to strings pretty quickly, but it doesn't detect this as an append operation, probably because two strings are being added onto it.

It is much faster if you use:

Code: Select all

clips += Str(Z(i,j)) + Chr(9)
Or if for whatever reason you want to avoid the '+=' operator, this should do the same thing, but still be faster:

Code: Select all

clips = clips + (Str(Z(i,j)) + Chr(9))
Post Reply