Posts: 1,407
Threads: 117
Joined: Dec 2002
BigD , I'm having all kind of problems in running PDS in Win 2000 so I can't test your program.
I will try to get a copy of VBDOS, I recall it was more Windows-friendly.
Antoni
Posts: 6
Threads: 0
Joined: May 2006
Ok, well these old dos programs tend to be unpredictable at times, I'm running XP SP2 myself and have no issues at all running PDS.
If you have trouble finding VB for DOS i believe it can be found at this page: http://www.phatcode.net/downloads.php?sub=compilers
Posts: 1,407
Threads: 117
Joined: Dec 2002
BigD , you win in the QB4.5 category!
I compiled your and my entry both in VBDOS, no optimizations. Your program did 37 seconds, mine did 65 seconds.
Congratulations!
Antoni
Posts: 6
Threads: 0
Joined: May 2006
Thanks!
It was a fun challenge.
Posts: 1,407
Threads: 117
Joined: Dec 2002
After reading your code I liked your couple of tricks to coerce GET and PUT to handle a full array in a single operation.
And you use strings for the sort buckets to avoid one tally pass...Why did'nt you use MKL$ instead of 4 PEEKS?. Something like
Code: tempstr(a)=tempstr(a)+MKL$(tmp)
Not so bad!
EDITED: I tried the mkl$ trick and the time goes down to 16 seconds!!
Antoni
Posts: 1,845
Threads: 44
Joined: Aug 2002
I made something this evening that sorts the 400MB of UIntegers in about 180 seconds on my pc, using up 99 MB (eek) of memory.
Since it sorts UIntegers I wasn't certain if it fitted in your categories.
Also, I dont know anything about sorting (I just know bubblesort and insertion sort, that's all), but I made it this afternoon, just tell me if you're interested
- Neo
P.S., here's the program output from my comp:
Quote:Preparing index... 100%.
Creating index... 100%. Took 69 seconds
Converting index... 100%. Took 118 seconds
Destroying index... 100%.
Process completed. Took 188 seconds.
P.S.2. It's very unoptimized, uncommented code, as I dont have much time
Posts: 6
Threads: 0
Joined: May 2006
Yeah, well to be honest it as kind of a rush job and I wanted to post some code before the deadline.
I don't have a lot of spare time where I can spend my time optimizing, and i simply didn't think of mkl$.
Great improvement of my code though
Posts: 1,407
Threads: 117
Joined: Dec 2002
Neo, please post your code somewhere!
Antoni
Posts: 1,845
Threads: 44
Joined: Aug 2002
Alright... if by "somewhere" you mean here, then here it is.
Code: 'NDEM Sort
'Sorts files internally on UIntegers, with filesizes up to the maximum file size of your file system.
'24 May 2006
'No-Comment version
'No-Optimization version
'Hideously bugged version
Option Dynamic
Option Explicit
Declare Sub PrepareIndex()
Declare Sub DestroyIndex()
Declare Sub CreateIndex()
Declare Sub ConvertIndex()
#include "crt.bi"
#define BUFFERSIZE_STD 131072
#define INTEGERSIZE_STD (BUFFERSIZE_STD\4)
#define WRITEBUFFER_STD 512
Type BufferType
size As Integer
data As UInteger Ptr
End Type
Dim Shared FileAccess As Integer
Dim Shared length As UInteger
Dim Shared Buffers(255) As BufferType
Dim timestarted As Single
timestarted = Timer
Cls
Call PrepareIndex()
Call CreateIndex()
Call ConvertIndex()
Call DestroyIndex()
Print "Process completed. Took "; Int(Timer - timestarted); " seconds."
'Sleep
End
Private Sub ConvertIndex()
Print "Converting index... ";
Dim starttime As Single
starttime = Timer
Dim i As UInteger, j As Integer, k As Integer, l As Integer, z As UInteger
Dim buffer(INTEGERSIZE_STD-1) As UInteger, got As UInteger = 0, buffersiz As Integer = BUFFERSIZE_STD, length As UInteger
Dim MasterIndexArray(16777215) As UInteger
For i = 0 To 255
j = FreeFile
Open ".\Index\" + Str$(i) + ".index" For Binary As #j
length = LoF(j)
got = 0
buffersiz = BUFFERSIZE_STD
ReDim buffer(INTEGERSIZE_STD-1) As UInteger
Do Until got >= length
If got + buffersiz > length Then
buffersiz = length - got
ReDim buffer(buffersiz\4-1) As UInteger
End If
Get #j, , buffer()
z = UBound(buffer)
For k = 0 To z
MasterIndexArray(buffer(k)) += 1
Next k
got += buffersiz
Loop
Close #j
Open "sort.dat" For Binary As #j
Seek #j, LoF(j)+1
For k = 0 To 16777215&
If MasterIndexArray(k) > 0 Then
z = k Xor (i Shl 24)
For got = 1 To MasterIndexArray(k)
Put #j, , z
Next got
MasterIndexArray(k) = 0
End If
Next k
Close #j
Locate 3,1: Print "Converting index... "; Int(i/255*1000)/10; "% "
Next i
Locate 3,1: Print "Converting index... 100%. Took "; Int(Timer - starttime); " seconds"
End Sub
Private Sub CreateIndex()
Print "Creating index... ";
Dim starttime As Single, lasttimed As Single
starttime = Timer
lasttimed = Timer
length = LoF(FileAccess)
Dim got As UInteger = 0, buffersiz As Integer = BUFFERSIZE_STD, i As Integer, z As UInteger
Dim buffer(INTEGERSIZE_STD-1) As UInteger, relevantbyte As UByte, lessrelevantbytes As UInteger
Dim writebuffer(INTEGERSIZE_STD-1) As UInteger, j As Integer
Do Until got >= length
If got + buffersiz > length Then
buffersiz = length - got
ReDim buffer(buffersiz\4-1) As UInteger
End If
Get #FileAccess, , buffer()
z = UBound(buffer)
For i = 0 To z
relevantbyte = ((buffer(i) And &HFF000000) Shr 24)
lessrelevantbytes = (buffer(i) And &HFFFFFF)
Buffers(relevantbyte).data[Buffers(relevantbyte).size] = lessrelevantbytes
Buffers(relevantbyte).size += 1
If Buffers(relevantbyte).size = INTEGERSIZE_STD Then
MemCpy(@writebuffer(0), Buffers(relevantbyte).data, BUFFERSIZE_STD)
j = FreeFile
Open ".\Index\" + Str$(relevantbyte) + ".index" For Binary As #j
Put #j, LoF(j)+1, writebuffer()
Close #j
Buffers(relevantbyte).size = 0
End If
Next i
got += buffersiz
If (Timer - lasttimed > 2.5) Then Locate 2,1: Print "Creating index... "; Str$(Int(got/length*1000)/10); "% ": lasttimed = Timer
Loop
For i = 0 To 255
If Buffers(i).size > 0 Then
ReDim writebuffer(Buffers(i).size - 1) As UInteger
MemCpy(@writebuffer(0), Buffers(i).data, Buffers(i).size * 4)
j = FreeFile
Open ".\Index\" + Str$(i) + ".index" For Binary As #j
Put #j, LoF(j)+1, writebuffer()
Close #j
Buffers(i).size = 0
End If
Next i
Close #FileAccess
Locate 2,1: Print "Creating index... 100%. Took "; Int(Timer - starttime); " seconds"
End Sub
Private Sub PrepareIndex()
Print "Preparing index... ";
MkDir "Index"
Dim i As Integer, j As Integer
j = FreeFile
For i = 0 To 255
Open ".\Index\" + Str$(i) + ".index" For Output As #j
Close #j
Buffers(i).data = CAllocate(BUFFERSIZE_STD)
Buffers(i).size = 0
Next i
j = FreeFile
Open "sort.dat" For Output As #j
Close #j
j = FreeFile
FileAccess = j
Open "unsortfb.dat" For Binary As #j
Print "100%."
End Sub
Private Sub DestroyIndex()
Print "Destroying index... ";
Dim i As Integer
For i = 0 To 255
Kill ".\Index\" + Str$(i) + ".index"
Deallocate Buffers(i).data
Buffers(i).size = 0
Next i
RmDir "Index"
Print "100%."
End Sub
As I said, the code is highly unoptimized, uncommented, and looks hideous
Anyway, as you might've noticed it doesn't really use a conventional sorting algorithm like bubble sort or so. And to be able to run it quickly, I hope you have a fast disk cache... ^^
The algorithm itself is probably really sucky, but I wanted to demonstrate another "unconventional" solution to the problem. It also works with files up to 2GB (didn't test though, dont have enough free space).
Hope it's at least worth 1 word (I'm so noobish! ),
- Neo
Posts: 1,845
Threads: 44
Joined: Aug 2002
As I thought, I guess it's worth nothing >.>
|