Fastest Array(Byte) Search Procedure

[cas]

The bigger problem is the time used to read the file, 33MB take about 1 Sec in exe mode and 9-12 Sec in debug mode.
How can I improve the read file speed? I'm reading one byte/time.Look:

Maybe this will help you: http://www.forums.purebasic.com/english ... 87#p336087

[Vitor_Boss®]

The bigger problem is the time used to read the file, 33MB take about 1 Sec in exe mode and 9-12 Sec in debug mode.
How can I improve the read file speed? I'm reading one byte/time.Look:

Maybe this will help you: http://www.forums.purebasic.com/english ... 87#p336087

Now this take > 360ms to read a 33MB file.

Code: Select all

Procedure.b GetByte(FileName.s,Array Output.a(1), Size.l=0, START.l=0)
  Protected Status.a, i.l, length.l
  Protected Temp.s
  Define *MemoryID
  If FileSize(FileName)
    Status = OpenFile(1,FileName)
    If Status <> 0
      If Size = 0      
        Size = FileSize(FileName)
      EndIf    
      ReDim Output(Size)
      FileSeek(1,START)
      *MemoryID = @Output(0)
      If *MemoryID
        ReadData(1, *MemoryID, Size)
      EndIf
      CloseFile(1)
      ProcedureReturn Status
    Else
      ProcedureReturn Status
    EndIf
  EndIf  
EndProcedure

[cas]

You are doing it wrong, this code needs at least 66MB of RAM (ReDim + AllocateMemory()) to read complete 33MB file. Replace *MemoryID = AllocateMemory(Size) line with *MemoryID = @Output(0) so you won't do same thing twice. Look at code that i posted in other thread, i thought it would be perfect for your needs and it doesn't need so much RAM, it could probably run on computer with 32MB RAM+Windows 95 and do its job on 1GB file without crashing, which, with your code would crash immediately because it would need 2GB (1GB if you remove AllocateMemory()) of free RAM. If computer runs out of memory then your application will crash because you are not testing if ReDim failed or succedded with ArraySize(). And 360ms to read a 33MB file - that is relative and it doesn't mean anything, except if you have SSD and you are testing it with debugger disabled - in that case we could say it is slow.

[Vitor_Boss®]

Thank you very much for tell me how improve my code. Look the results:

Code: Select all

Advanced Patches Auto Porter v1.5.0.0
© 2010 Vitor_Boss®

Loaded Original Firmware (34MB) in 47ms
Loaded Destination Firmware (34MB) in 47ms

My notebook has a HD not a SSD.

[blueznl]

Perhaps you want to read it directly into a memory block with ReadData()?

[Vitor_Boss®]

Yes, I'm trying build the fastest algorithm possible. Any idea to improve this code?

Code: Select all

Procedure.b GetByte(FileName.s,Array Output.a(1), Size.l=0, START.l=0)
  Protected Status.a, i.l, length.l
  Protected Temp.s
  Define *MemoryID
  If FileSize(FileName)
    Status = OpenFile(1,FileName)
    If Status <> 0
      If Size = 0
        Size = FileSize(FileName)
      EndIf
      ReDim Output(Size)
      FileSeek(1,START)
      *MemoryID = @Output(0)
      If *MemoryID
        ReadData(1, *MemoryID, Size)
      EndIf
      CloseFile(1)
      ProcedureReturn Status
    EndIf
  EndIf
  ProcedureReturn 0
EndProcedure

[cas]

Here i corrected your code (added check if ReDim failed) and removed unnecessary variables, but you could also add some checks to test if start position is not greater than length of file if you want.
You can't get any faster code than this one to read whole file to array. And i would never do it that way because of, previously mentioned, high RAM usage.

Code: Select all

Procedure GetByte(FileName.s,Array Output.a(1), Size=0, START=0)
  Protected FileHandle, Result
  If FileSize(FileName) > 0
    FileHandle = OpenFile(#PB_Any,FileName)
    If FileHandle <> 0
      If Size = 0
        Size = Lof(FileHandle)
      EndIf
      ReDim Output(Size)
      If ArraySize(Output.a()) <> -1
        FileSeek(FileHandle, START)
        ReadData(FileHandle, @Output(0), Size)
        Result=#True
      EndIf
      CloseFile(FileHandle)
    EndIf
  EndIf
  ProcedureReturn Result
EndProcedure

[Vitor_Boss®]

Thank you, about RAM usage, I think don't need more RAM than the specified size.

[Vitor_Boss®]

There is a new version of Tuned Boyer-Moore algorithm.

Code: Select all

Procedure TUNEDBM(Start.l,Array Source.a(1), Array Pattern.a(1))
   Protected.i i, j, m, n, k, match, shift
   Protected.i Dim bmBc(255)   
   m = ArraySize(Pattern())
   n = ArraySize(Source()) 
   ; Preprocessing 
   preBmBc(Pattern(), bmBc())
   shift = Max(bmBc(Pattern(m - 1)),1)
   bmBc(Pattern(m - 1)) = 0
   ; Searching
   j = Max(0,Start-1)
   While j < n
	  While j + m < n And bmBc(Source(j + m -1)) <> 0
	    j + bmBc(Source(j + m -1))
	    If j + m >= n : Break : EndIf
		  j + bmBc(Source(j + m -1))
	    If j + m >= n : Break : EndIf
		  j + bmBc(Source(j + m -1))
	    If j + m >= n : Break : EndIf
	  Wend
	  If CompareMemory(@Source(j), @Pattern(), ArraySize(Pattern()))
	    ProcedureReturn j
	  EndIf 	  
	  j + shift
	Wend
	ProcedureReturn 0
EndProcedure

[Vitor_Boss®]

Fastest string find procedure.

Code: Select all

Removed

[Michael Vogel]

What have to be done to do a fast string find? The following code needs times more execution time for the new routine...

Code: Select all

#FSText="llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllliiillllllllll"
#FSNumber=999999
x-ElapsedMilliseconds()
For i=0 To #FSNumber
    a=FindString(#FSText,"iii",1)
Next i
x+ElapsedMilliseconds()

y-ElapsedMilliseconds()
For i=0 To #FSNumber
    a=TunedFind(#FSText,"iii",1)
Next i
y+ElapsedMilliseconds()

MessageRequester("-",Str(x)+" vs. "+Str(y))