Re: [Lazarus] A sort program in "rpsrt102.zip" (1).
Hello Mehmet, Tuesday, August 26, 2008, 7:35:00 AM, you wrote: MES> (A) MES> An "algorithm" ( http://en.wikipedia.org/wiki/Algorithm ) MES> and its "implementation" are different concepts , at least MES> in the sense that , for an algorithm there may be many MES> distinct implementations of it . Yes, you are right, but a good implementation of the same algorithm does not provide a big bunch of gain usually. Different algorithms are great for different sort tasks and QuickSort is, maybe, the best for the general case. MES> (B) MES> "RPSORT" program itself is written in 16-bit 8086 assembler MES> but its bit size is not related to the file size it sorts . Yes, but it matters in how it handle the data, as it can not deal with more than 64 KB in each bunch, also you should not mix 16 bit and 32 bit assembler if possible. Anyway porting it to 32 bits (the algorithm implementation, not the full code) should be quite easy. MES> (C) MES> Personally , I am not writing assembler programs , and MES> I do not know 32-bit assembly programming . MES> Therefore , I am not able to convert it to a 32-bit MES> assembly program . MES> I think a programmer fluent in assembly language programming MES> can do it . I am not able to evaluate its difficultyness but MES> it is my opinion that many statements may be converted by replace MES> operations . MES> After this it may be used as embedded into a Pascal procedure or MES> may be used as a spawned process to sort a file . The problem is that assembler is not portable. Also a 32 bit pure Pascal implementation should be even faster than RPSRT. MES> (D) MES> To make a proper reply to your question I prepared a simple program MES> compiled with FPC MES> to demonstrate its sorting speed as follows : Great, as both have the same computer ;) except that I have 1 GB. So I wrote a routine to sort it (the 10 000 000 lines file) with Lazarus using the already provided primitives, nothing special programmed. I had used your program to generate the test file. After 4 runs the average time to sort the file: Number of records File size TemporalTime required for as given for Mas MegaBytesdisk space sorting HH:MMM:SS --- -- - 10 000 000 220.0 0.00 00:03:18 5 000 000 110.0 0.00 00:01:23 -- procedure TForm1.Button1Click(Sender: TObject); var L: TStringList; StartTime: TDateTime; begin StartTime:=Now; L:=TStringList.Create; L.LoadFromFile('G:\RNumbers.txt'); L.Sort; L.SaveToFile('G:\sorted.txt'); L.Free; self.Caption:=TimeToStr(Now-StartTime); end; -- It does not beat RPSRT, so I decided to optimize it a bit, preparing the TStringList to receive 20 million lines at least, which preallocate 20 million pointer positions, and not freeing the memory as the OS will do it in one step. Number of records File size TemporalTime required for as given for Mas MegaBytesdisk space sorting HH:MMM:SS --- -- - 10 000 000 220.0 0.00 00:02:53 5 000 000 110.0 0.00 00:01:18 -- procedure TForm1.Button1Click(Sender: TObject); var L: TStringList; StartTime: TDateTime; begin StartTime:=Now; L:=TStringList.Create; L.Capacity:=2000; L.LoadFromFile('G:\RNumbers.txt'); Beep; L.Sort; Beep; L.SaveToFile('G:\sorted.txt'); Beep; self.Caption:=TimeToStr(Now-StartTime); L.Free; //Free time is not counted as RPSRT will not free 20 million pointers. end; -- Also disk write is not optimized in any way, so it could mean (not checked in the code) 5/10 million writes to disk. This code quite sure will explode with 2 Gigabytes file, and will take ages to complete MES> Number of records File size Time required for sorting MES> as given for Mas MegaBytesas Hour : Minute : Second . MES> --- --- MES> only + Command Prompt working : MES> 5 000 000 110.0 00 : 01 : 11.24 MES> 10 000 000 220.0 00 : 02 : 28.41 MES> 25 000 000 550.0 00 : 06 : 29.47 MES>100 000 000 2200.0 Locked : MES> I think file size should be less than 2147.0 MES> MegaBytes , MES> because of 32-bit MaxInt size ( 2 147 ... ... ) . MES> It is locked after 2053 MegaBytes of its MES> temporary file MES> left behind after its locking . MES>90 000 000 1980.0 01 : 32 : 45.98 Yes, 2 gigabytes will be a serious pr
Re: [Lazarus] A sort program in "rpsrt102.zip" (1).
On Mon, 25 Aug 2008 22:35:00 -0700 Mehmet Erol Sanliturk <[EMAIL PROTECTED]> wrote: > (C) > Personally , I am not writing assembler programs , and > I do not know 32-bit assembly programming . > Therefore , I am not able to convert it to a 32-bit > assembly program . If you really need the speed you should learn assembler programming. It is not that hard (at least for small programs like this sort). > I think a programmer fluent in assembly language programming > can do it . I am not able to evaluate its difficultyness but > it is my opinion that many statements may be converted by replace > operations . > > After this it may be used as embedded into a Pascal procedure or > may be used as a spawned process to sort a file . Assembler is not portable. So you need a different implementation for every plattform that fpc supports. If you just need x86 support then the sort programm should be part of your project and not of fpc in general. IMHO there is not much gain by including an assembly code sort in fpc. ___ Lazarus mailing list Lazarus@lazarus.freepascal.org http://www.lazarus.freepascal.org/mailman/listinfo/lazarus
[Lazarus] A sort program in "rpsrt102.zip" (1).
Dear JoshyFun , (A) An "algorithm" ( http://en.wikipedia.org/wiki/Algorithm ) and its "implementation" are different concepts , at least in the sense that , for an algorithm there may be many distinct implementations of it . (B) "RPSORT" program itself is written in 16-bit 8086 assembler but its bit size is not related to the file size it sorts . (C) Personally , I am not writing assembler programs , and I do not know 32-bit assembly programming . Therefore , I am not able to convert it to a 32-bit assembly program . I think a programmer fluent in assembly language programming can do it . I am not able to evaluate its difficultyness but it is my opinion that many statements may be converted by replace operations . After this it may be used as embedded into a Pascal procedure or may be used as a spawned process to sort a file . (D) To make a proper reply to your question I prepared a simple program compiled with FPC to demonstrate its sorting speed as follows : Program Numbers ; Var T : Text ; Var M : LongInt ; Var i : LongInt ; Var p : Int64 ; Var q : Int64 ; Begin M := 0 ; Writeln ( 'Give number of values to generate :' ) ; Readln ( M ) ; If ( M > 0 ) Then Begin Assign ( T , 'RNumbers.TXT' ) ; ReWrite ( T ) ; p := 9223372036854775807 ; For i := 1 to M Do Begin q := Random ( p ) ; Writeln ( T , q : 20 ) ; End ; Close ( T ) ; End Else Begin Writeln ( 'Given value : ' , M , ' is NOT greater than zero .' ) ; End ; End . Times are obtained in a PC with Intel Pentium 4 CPU 3.00 GHz 2 GB Memeory and Windows XP Home Edition . (E) For each value of M as number of records , the following command has been applied : > rpsort < rnumbers.txt > snumbers.txt The RPSORT.COM is reporting the time used for sorting which I checked by an actual clock and I have found them to be correct . The results are as follows : Number of records File size Time required for sorting as given for Mas MegaBytesas Hour : Minute : Second . --- --- 10 000 0.214 00 : 00 : 00.11 ( + Six program working ) 100 000 2.2 00 : 00 : 01.43 ( + Six program working ) 1 000 00022.0 00 : 00 : 17.19 ( + Six program working ) 5 000 000 110.0 00 : 01 : 36.61 ( + Six program working ) 10 000 000 220.0 00 : 03 : 21.41 ( + Six program working ) only + Command Prompt working : 5 000 000 110.0 00 : 01 : 11.24 10 000 000 220.0 00 : 02 : 28.41 25 000 000 550.0 00 : 06 : 29.47 100 000 000 2200.0 Locked : I think file size should be less than 2147.0 MegaBytes , because of 32-bit MaxInt size ( 2 147 ... ... ) . It is locked after 2053 MegaBytes of its temporary file left behind after its locking . 90 000 000 1980.0 01 : 32 : 45.98 When M = 10 000 000 : snumbers.txt which is already sorted is sorted as > rpsort < snumbers.txt > tnumbers.txt in time 00 : 01 : 50.84 . snumbers.txt which is already sorted in ascending order is sorted in descending order as > rpsort /R < snumbers.txt > tnumbers.txt in time 00 : 01 : 50.35 . (F) It is possible to generate multiple column files and test it for multiple sort keys . Details may be found in its documentation . Thank you very much , Mehmet Erol Sanliturk ___ Lazarus mailing list Lazarus@lazarus.freepascal.org http://www.lazarus.freepascal.org/mailman/listinfo/lazarus
Re: [Lazarus] A sort program in "rpsrt102.zip" .
Hello Mehmet, Sunday, August 24, 2008, 10:07:12 PM, you wrote: MES> It is "UNBELIEVABLY" fast . MES> My suggestion is that it can be incorporated into a unit MES> ( for example , MES> as a procedure with a parameter MES> ( containing giving definition of sort like its command-line parameter MES> string ) ). MES> My opinion is that it may be useful to study it . Which is special in this software ? It is using the well known QuickSort algorithm, as it is assembler it should run a faster than a pure Pascal implementation, also it is 16 bits asm code. It will be quite difficult to compare in speed with a FPC implementation as the binary of RPSRT is .com file of 18KBs ;) and will be loaded very fast (no rellocation needed), compared to a FPC .exe binary. Maybe you saw something that I was not aware about it :-? -- Best regards, JoshyFun ___ Lazarus mailing list Lazarus@lazarus.freepascal.org http://www.lazarus.freepascal.org/mailman/listinfo/lazarus
[Lazarus] A sort program in "rpsrt102.zip" .
Dear Sirs , There is a program named as "rpsort.com" with its related sources in "rpsrt102.zip" which may be found in the following address : http://www.simtel.net/product.php?url_fb_product_page=51643 or by an internet search with name rpsrt102.zip . The following is a part from its "readme" : -- This is being mailed to all those who either registered or inquired about RPSORT, written by my brother, Robert Pirko. Robert Pirko, the author of RPSORT, passed away on February 15, 1992. He had not been ill , but just suddenly collapsed and died. You never know ... RPSORT is now free for all to use, no payment is asked. Also the assembly language source code is free. The file RPSRT101.ZIP has been uploaded to a local (New York City) BBS: NYACC 718 539-3064 (free access) This file contains version 1.01 of RPSORT and its documentation plus the commented source code written in 8086 assembler for the Borland Turbo Assembler 2.5. It is also available by mail for a payment of $5.00 to: Alex Pirko 3881 Sedgwick Ave Apt.6D Bronx, NY 10463 -- rpsort.com is working perfectly under Windows XP ( with 8.3 format file names ( because its file name variable ( I think , due to "IpNameExt DB 13 Dup (?)" in its assembler source ) ) ) . It is "UNBELIEVABLY" fast . My suggestion is that it can be incorporated into a unit ( for example , as a procedure with a parameter ( containing giving definition of sort like its command-line parameter string ) ). My opinion is that it may be useful to study it . Thank you very much , Mehmet Erol Sanliturk ___ Lazarus mailing list Lazarus@lazarus.freepascal.org http://www.lazarus.freepascal.org/mailman/listinfo/lazarus