Qbasicnews.com
October 22, 2019, 02:48:31 AM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: 1 ... 4 5 [6]
  Print  
Author Topic: External sort compo?  (Read 32616 times)
Neo
Na_th_an
*****
Posts: 2150



« Reply #75 on: May 24, 2006, 06:47:01 PM »

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 Wink

- 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 Smiley
Logged
BigD
New Member

Posts: 7


« Reply #76 on: May 25, 2006, 01:40:13 AM »

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 Cheesy
Logged
Antoni Gual
Na_th_an
*****
Posts: 1434



WWW
« Reply #77 on: May 25, 2006, 02:51:12 PM »

Neo, please post your code somewhere!
Logged

Antoni
Neo
Na_th_an
*****
Posts: 2150



« Reply #78 on: May 25, 2006, 03:04:32 PM »

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 Sad
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! Sad),

- Neo
Logged
Neo
Na_th_an
*****
Posts: 2150



« Reply #79 on: May 29, 2006, 02:07:25 PM »

As I thought, I guess it's worth nothing >.>
Logged
Antoni Gual
Na_th_an
*****
Posts: 1434



WWW
« Reply #80 on: May 29, 2006, 05:06:19 PM »

Excuse the delay, I can only do significant tests 90 minutes after starting my computer, that's what my crappy free antivirus takes to scan my disks. I have'nt had the PC connected that many time this weekend.

Your program ran in 677 seconds in my computer.
That makes yetifoot the winer!
Logged

Antoni
Neo
Na_th_an
*****
Posts: 2150



« Reply #81 on: May 29, 2006, 06:29:08 PM »

That was not the answer I was looking for...

Have you changed Antoni?  :lol:
Logged
Anonymous
Guest
« Reply #82 on: May 29, 2006, 09:15:06 PM »

Neo, are you feeling alright? Your posts have been quite odd lately...
Logged
Neo
Na_th_an
*****
Posts: 2150



« Reply #83 on: May 30, 2006, 04:23:03 AM »

Oh yeah... I'm feeling alright...

I'm just extremely noobie in programming again, with 0 motivation, and seeing people shove everything I made off the table just like that doesn't really help.

So yeah... I'm dumb, and feeling alright I guess ^^
Logged
Anonymous
Guest
« Reply #84 on: May 30, 2006, 04:40:00 AM »

that's why some of us didn't post in this thread. doesn't make you a noobie, people have different areas of specialty ;p

don't beso hard on yourself buddy.
Logged
yetifoot
Ancient Guru
****
Posts: 575



« Reply #85 on: May 31, 2006, 10:49:35 PM »

I may have won, but i am still scratching my head over that radix sort..
Logged

EVEN MEN OF STEEL RUST.
Moneo
Na_th_an
*****
Posts: 1971


« Reply #86 on: May 31, 2006, 11:08:36 PM »

Quote from: "yetifoot"
I may have won, but i am still scratching my head over that radix sort..


Well, congratulations are in order. You worked hard, and you earned it.

*****
Logged
Antoni Gual
Na_th_an
*****
Posts: 1434



WWW
« Reply #87 on: June 01, 2006, 07:22:15 AM »

And I have written a  radix sort combined with a multi-phase merge I will post when I have time to debug it.
Logged

Antoni
Pages: 1 ... 4 5 [6]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!