Matrix to string

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

Matrix to string

Postby Carlos Herrera » Feb 08, 2019 9:16

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: 1523
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Matrix to string

Postby jj2007 » Feb 08, 2019 9:54

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: 886
Joined: Oct 19, 2017 15:00
Location: 't Zand, NL
Contact:

Re: Matrix to string

Postby Munair » Feb 08, 2019 10:28

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

Postby marpon » Feb 08, 2019 10:33

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: 886
Joined: Oct 19, 2017 15:00
Location: 't Zand, NL
Contact:

Re: Matrix to string

Postby Munair » Feb 08, 2019 10:37

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

Re: Matrix to string

Postby marcov » Feb 08, 2019 10:39

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
Posts: 9698
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Matrix to string

Postby fxm » Feb 08, 2019 10:55

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: 726
Joined: May 05, 2015 5:35
Location: Germany

Re: Matrix to string

Postby grindstone » Feb 08, 2019 10:56

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: 6543
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Matrix to string

Postby dodicat » Feb 08, 2019 11:07

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

Postby marpon » Feb 08, 2019 11:18

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

Postby marpon » Feb 08, 2019 12:07

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: 6543
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Matrix to string

Postby dodicat » Feb 08, 2019 13:26

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: 81
Joined: Nov 28, 2011 13:29
Location: Dictatorship

Re: Matrix to string

Postby Carlos Herrera » Feb 08, 2019 13:45

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

Re: Matrix to string

Postby jj2007 » Feb 08, 2019 14:05

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: 6210
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: Matrix to string

Postby counting_pine » Feb 08, 2019 14:21

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))

Return to “Beginners”

Who is online

Users browsing this forum: No registered users and 6 guests