Re: The eternal sorting debate. Where to do sorting


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 12 of 12

Thread: Re: The eternal sorting debate. Where to do sorting

  1. #1
    Willy Van den Driessche Guest

    Re: The eternal sorting debate. Where to do sorting



    "Joe "Nuke Me Xemu" Foster" <joe@bftsi0.UUCP> wrote in message
    news:3ca94fa6@10.1.10.29...
    > "willy van den Driessche" <Willy.van.den.driessche@skynet.be> wrote in

    message <news:3c9f0322$1@10.1.10.29>...
    >
    > > "Michael Culley" <mike@vbdotcom.com> wrote:
    > > >Should sorting be done in the business layer or in the GUI?
    > > >
    > > >Say I am using a custom written grid to display data from a custom
    > > >collection. I have the choice to add the sorting to the business

    objects
    > > or
    > > >the grid, which should I do? I don't think it should be in the SQL

    string
    > > as
    > > >the user may chose to resort the list and it shouldn't need to run

    another
    > > >query for this.
    > > >

    > >
    > > I will add my own humble opinion to the debate.
    > > In our first version, we loaded all Business Objects at once (also in a

    custom
    > > collection). The custom collection did the sorting. The sorting

    process
    > > itself was quite speedy but the loading was too slow.

    (the -controversial-
    > > sorting code we used is at

    http://users.skynet.be/wvdd2/Sorting/sorting.html
    > > - I will one day modify it so that performance goes up and some

    controversial
    > > functions (like varassign) are modified)

    >
    > It's not "controversial", it's *broken*, and you know it. You've
    > known it for a month now, you dastard. A month in which, at the
    > bare minimum, to /remove/ just four lines so that objects having
    > default properties which might, just might, return Empty are not
    > mutilated when VarAssign is misused to swap elements. As if that
    > alone wasn't enough, you continue to /recommend/ it. Despicable!


    There are many more reasons to recommend it than to try and break it and you
    know that too. The only thing despicable is your vocabulary. I've changed
    the varassign to the original version (which you put in you reply). That
    should solve the problem once and for all.
    (http://users.skynet.be/wvdd2/General...et_and_set.htm
    l). Remember that the orginal version *only* failed for default properties
    returning Empty values. I don't have such properties in my classes but you
    are right about the fix.

    As for the heapsort, I'll look it up again in "Programming pearls" once I
    get the book back.

    The reason I recommend it is - as often happens - that it took me quite some
    time to come up with these routines. I can't say I don't like them. The
    most important thing to remember about the exercise is that through 3
    abstractions (IComparer, ISortableContainer, ISortAlgortihm), you are able
    to reuse code in an - IMHO- elegant way. All concepts in the sorting game
    are objects and you can combine any dimension to get a new result.
    You can decorate comparers (ex. to time them or to inverse the sorting
    order), build collections of them (to sort on multiple criteria). There are
    stock implementations for all standard VB types.
    You can do the same with sortablecontainers. There are stock
    implementations that let you sort collections (yes those things), arrays,
    strings and listboxes. It's plain easy to write one of your own for say a
    listview. There are some decorators to make the sortable container appear
    inversed (which might save you an inverse sort), sort only a subrange. Most
    important of all, there is the possibility to leave the original container
    untouched and return a permutation of indexes in the original container
    (allowing you to create indexes on the original container - possibly
    multiple of them) [Which explains why the ISortableCOntainer had to be
    assymmetrical]
    The objectification of sorting algorithms might be a little far-fetched but
    then again everybody should be able to have its pleasure.

    How many times have you seen questions about sorting in the newsgroups ? I
    have seen them a lot. Sorting a listbox happens this way, an array that way
    and a listview yet another way. There is nothing against these methods, but
    when you use the containeradapters in my component, then sorting a listbox,
    an array, a listview or heck, a collection is done in exactly the same way.

    All these features combined make me still recommend my little component.
    The article clearly states that it isn't a performance killer and also that
    that is not inherently so. I don't feel like beating any performance
    records. It's also exchange based sorting and O( n log n) at best. But I
    am not pushing it through anyone's throat. It's there if you like it or get
    some ideas from it. That's all.

    >
    > Here is a version of VarAssign which isn't completely brain-dead:
    >
    > Public Sub VarAssign(ByRef Target As Variant, ByRef Source As Variant)
    > If IsObject(Source) Then
    > Set Target = Source
    > Else
    > Let Target = Source
    > End If
    > End Sub



    >
    > If you feel that the Let does not help emphasize the difference
    > between copying a reference and copying a value, feel free to
    > mutilate the Let. Of course, you do realize, do you not, that
    > Matthew would find your sorting code perfectly cringe-worthy...
    >
    > > We therefore changed the approach to something much like
    > >

    http://users.skynet.be/wvdd2/PseudoP...ct_lists.html.
    > > (we stopped loading all objects and kept the recordset live - using

    interfaces
    > > we can change that strategy with just a few lines).

    >
    > Worry not - I will one day give this the full treatment as well.


    I will help you a little. Keeping a recordset open is a bad thing. The
    good thing - again - about the design is that you can have other decorators
    that solve these problems. Say I work over a wire. Then I probably won't
    read record by record. Instead, I'll probably read 50 or 100 records at a
    time. Writing a decorator that does this is peanuts - all this without
    changing a single line of UI code.

    >
    > > This approach had the benefit that the list screens came up almost

    immediately
    > > but we 'lost' our ability to sort the lists on demand. To re-add

    sorting,
    > > we extended the interface in the article with a sort method. Most of

    the
    > > time sorting is therefore done by the storage layer for one good reason

    :
    > > an "order by" is fast, it's available, tested and reliable.

    >
    > It imposes an additional, completely unnecessary burden on your
    > middle and data tiers and network, while wasting your clients'
    > capacity entirely! The initial fetch should specify an ORDER BY,
    > certainly, so that the clients do not need to wait for the entire
    > recordset to come across or to sort it before displaying so much
    > as a single field. However, saddling the servers with the burden
    > of doing *all* sorting is totally inexcusable. Just what exactly
    > is your major malfunction!?


    If you write an application that doesn't -logically - limit the amount of
    displayed records, then one day you might end up with a lot of records. If
    you read them all at once, you create a client-side bottleneck. If you
    order them on the server them the same might happen. (It's always something
    (Vlissides)). However, an order by clause doesn't force the server to sort
    on all occasions. Any decent implementation will use the indexes if and
    when available. In case of existing indexes there is no sorting to be done
    at all.
    BTW, I didn't say that our "default" doesn't use an order by. I just said
    that we don't read all records all the time. Our app was written for 100
    records max (the analysts told us). Until the first customer with 500 and
    2000 records where there with machines that weren't even decent enough to
    use as a typewriter. Our little trick solved that problem. Again, I'm not
    saying that anybody should use it. I'm just saying that it worked for us.

    And If you'll excuse me now, I have some diapers to change
    (http://users.skynet.be/wvdd2/Introdu...er/esther.html). I
    guess I'm better at that than at programming.
    --
    Van den Driessche Willy
    For a work in progress :
    http://users.skynet.be/wvdd2/index.html



  2. #2
    Joe \Nuke Me Xemu\ Foster Guest

    Re: The eternal sorting debate. Where to do sorting

    "Willy Van den Driessche" <Willy.Van.denDriessche@skynet.be> wrote in message <news:3caa1434@10.1.10.29>...

    > "Joe "Nuke Me Xemu" Foster" <joe@bftsi0.UUCP> wrote in message
    > news:3ca94fa6@10.1.10.29...


    > As for the heapsort, I'll look it up again in "Programming pearls" once I
    > get the book back.


    I already gave you everything you should have needed to fix that too:

    URL:http://groups.google.com/groups?selm...%40tkmsftngp05

    > The reason I recommend it is - as often happens - that it took me quite some
    > time to come up with these routines.


    <snicker/>

    > How many times have you seen questions about sorting in the newsgroups ? I
    > have seen them a lot. Sorting a listbox happens this way, an array that way
    > and a listview yet another way. There is nothing against these methods, but
    > when you use the containeradapters in my component, then sorting a listbox,
    > an array, a listview or heck, a collection is done in exactly the same way.


    The same broken way, you mean! Your sortable-containers have methods
    to swap elements, but comparing two elements /still/ requires that the
    elements be fetched separately, when you /could/ have added another
    method to the containers to support comparing elements, something most
    sorting algorithms tend to do quite a bit, hmmm? Fortunately, I also
    did this for you, weasel-boy, way back in February:

    URL:http://groups.google.com/groups?selm...%40tkmsftngp03

    > All these features combined make me still recommend my little component.


    Nevertheless, it's still a pig in a poke!

    > The article clearly states that it isn't a performance killer and also that
    > that is not inherently so. I don't feel like beating any performance
    > records. It's also exchange based sorting and O( n log n) at best.


    Wait a minute, weren't you bashing radix sorting a while back...? Do
    you change your tune according to whatever appears most convenient at
    that moment, or what? (Weasel)

    > If you write an application that doesn't -logically - limit the amount of
    > displayed records, then one day you might end up with a lot of records. If
    > you read them all at once, you create a client-side bottleneck. If you
    > order them on the server them the same might happen. (It's always something
    > (Vlissides)). However, an order by clause doesn't force the server to sort
    > on all occasions. Any decent implementation will use the indexes if and
    > when available. In case of existing indexes there is no sorting to be done
    > at all.


    What's wrong, haven't you thought of adaptive row-fetchers yet? The
    factory pattern makes it easy to create one type of rowset wrapper if
    a query returns only a little sip and another type if the query looks
    instead like it just broke open a fire-hydrant!

    --
    Joe Foster <mailto:jlfoster%40znet.com> On the cans? <http://www.xenu.net/>
    WARNING: I cannot be held responsible for the above They're coming to
    because my cats have apparently learned to type. take me away, ha ha!



  3. #3
    Willy Van den Driessche Guest

    Re: The eternal sorting debate. Where to do sorting

    "Joe "Nuke Me Xemu" Foster" <joe@bftsi0.UUCP> wrote in message
    news:3caa2d54@10.1.10.29...
    > "Willy Van den Driessche" <Willy.Van.denDriessche@skynet.be> wrote in

    message <news:3caa1434@10.1.10.29>...
    >
    > > "Joe "Nuke Me Xemu" Foster" <joe@bftsi0.UUCP> wrote in message
    > > news:3ca94fa6@10.1.10.29...

    >
    > > As for the heapsort, I'll look it up again in "Programming pearls" once

    I
    > > get the book back.

    >
    > I already gave you everything you should have needed to fix that too:
    >
    > URL:http://groups.google.com/groups?selm...%40tkmsftngp05
    >
    > > The reason I recommend it is - as often happens - that it took me quite

    some
    > > time to come up with these routines.

    >
    > <snicker/>
    >
    > > How many times have you seen questions about sorting in the newsgroups ?

    I
    > > have seen them a lot. Sorting a listbox happens this way, an array that

    way
    > > and a listview yet another way. There is nothing against these methods,

    but
    > > when you use the containeradapters in my component, then sorting a

    listbox,
    > > an array, a listview or heck, a collection is done in exactly the same

    way.
    >
    > The same broken way, you mean! Your sortable-containers have methods
    > to swap elements, but comparing two elements /still/ requires that the
    > elements be fetched separately, when you /could/ have added another
    > method to the containers to support comparing elements, something most
    > sorting algorithms tend to do quite a bit, hmmm? Fortunately, I also
    > did this for you, weasel-boy, way back in February:
    >
    > URL:http://groups.google.com/groups?selm...%40tkmsftngp03


    Adding the "comparison capability" to the containers is a possible design
    option. For what I had in mind it is inferior. If you add the "compareto"
    method to the sortablecontainer, you might just as well add the sort method
    to it as well. There would be no need for icomparers, isortablecontainers
    nor isortAlgorithms.
    The interfaces didn't come out of nowhere. They where carefully planned and
    thought out. The major reason for having a separate ISortableContainer and
    IComparer is reuse. No more, no less. Adding the compareto method directly
    to containers could buy you performance(a little I guess but yet to be
    benchmarked - my bet would be less than 5% on average).
    Here are my counter-arguments:
    1) Decoration is harder when compareto is in the container
    Our imaginary ISortableContainer2 interface would now look like this (you
    might probably want to skip some more methods but that's irrelevant)
    <code>
    interface ISortableContainer2:
    public enum eCompareResult
    eSmaller = -1
    eEqual = 0
    eLarger = 1
    end enum

    Public Property Get Count () As Long
    Public Property Get Item (ByVal nPos As Long) As Variant
    Public Sub Swap (ByVal nPosFrom As Long, ByVal nPosTo as Long)
    public function CompareElements (byval nPosFirst as long, byval nPosSecond
    as long) as eCompareResult
    </code>

    Remember that in my original design there where some "decorating" comparers.
    If you could sort a collection ascending with this statement :

    <code>
    call SortCollection (new myComparer)
    </code>

    then you could sort it in reverse order with this statement

    <code>
    call SortCollection CreateInverseComparer(new myComparer)
    </code>

    The trick behind this was that an inverse comparer was coded like this :
    <code>
    (private) class cInverseComparer

    Implements iComparer
    Private mBase As iComparer
    Public Property Set BaseComparer(objVal As iComparer)
    Set mBase = objVal
    End Property
    Private Function iComparer_Compare(ByVal Source As Variant, ByVal
    Destination As Variant) As Long
    iComparer_Compare = -mBase.Compare(Source, Destination)
    End Function

    </code>

    There is no doubt in my mind that a similar "decoration" trick could be
    performed on ISortableContainer2. Only, you would have to delegate 3
    methods to reimplement only the fourth one. Decoration is (IMHO) essential
    if you want to keep the number of classes low. If not you will need an
    CAscendingIntegerCOmparer and a CDescendingIntegerComparer - two comparers
    for every element type you which to handle.

    2) You need more classes for the same result.
    For sorting arrays and collections of strings and integers I need 4 classes
    : cSortableArray, cSortableCollection and cIntegerComparer, cStringComparer

    If the compareto method is part of the container, then you actually need to
    write 4 classes too :
    cSortable2ArrayWithIntegers,cSortable2ArrayWithStrings,
    cSortable2CollectionWithIntegers, cSortable2CollectionWithStrings.

    Seems like the same thing at first (4 classes in either approach), but we're
    only getting started. Add the capability to sort dates and longs. My
    approach demands the addition of 2 classes (cDateComparer and
    cLongComparer), for a total of 4 + 2 = 6 classes.

    Your approach calls for 4 additional classes :
    cSortable2ArrayWithDates,cSortable2ArrayWithLongs,
    cSortable2CollectionWithDates, cSortable2CollectionWithLongs.

    The thing is : for M container types and N element types, I need M + N
    classes, your approach needs M x N. [ decorators and compositions require
    the same amount of classes but yours with more "empty" methods (methods that
    just forward a call to the delegee). When decorators get used a lot, your
    approach might actually loose its appeal of added performance quickly but -
    again - those things have to be benchmarked.

    BTW. I know that ISortableContainer2 could be easily be mapped to a couple
    of (ISortableContainer, iComparer). In that case you loose two points :
    ISortableContainer2 doesn't need to be an interface (because there is only
    one implementation) and performance will be worse than the basic
    ISortableContainer, iComparer approach I advocated in the first place.

    As you might have noticed, argument 2 is essentially Ockham's razor. ( he
    never actually wrote that sentence :
    http://www.elon.edu/daspra/scirel%5Cdas9.pdf page 11 at the bottom)


    The thing is : if you keep containers and comparers separate you don't have
    all these problems.


    Some additional remarks:
    These don't come from you but while I'm at it, I might just let myself go.
    The funny thing about iSortableContainer is that it's asymmetric:
    <code>
    interface iSortableContainer
    Public Property Get Item(ByVal nPos As Long) As Variant
    Public Sub Swap(ByVal nPos1 As Long, ByVal nPos2 As Long)
    Public Property Get Count() As Long

    <\code>

    A more obvious definition would have been :
    <code>
    interface iSortableContainer3
    Public Property Get Item(ByVal nPos As Long) As Variant
    Public Property let Item(ByVal nPos As Long, byval aVal As Variant)
    Public Property Set Item(ByVal nPos As Long, byval aVal As Variant)
    Public Property Get Count() As Long

    <\code>

    The thing is that the Let/Set thing in itself is enough to drive you away
    from it. More importantly is that iSortableContainer3 doesn't let you
    "decorate" an existing ISortableContainer3 to leave the original container
    untouched and create a permutation of indices into the original container.
    I found this last ability to be very handy : it let's you "index" the
    container in as many ways as you wish.

    Of course, there is nothing against ISortableContainer3 an sich. In this
    case it just needs a different name : ISimpleContainer or so. It would
    allow for a CopyContainer, PartitionContainer, ... methods etc...
    In some cases you have to make design decisions. I chose
    ISortableCOntainer, but the ISimpleCOntainer would have worked just as well.
    --
    Van den Driessche Willy
    For a work in progress :
    http://users.skynet.be/wvdd2/index.html



  4. #4
    Joe \Nuke Me Xemu\ Foster Guest

    Re: The eternal sorting debate. Where to do sorting

    "Willy Van den Driessche" <Willy.Van.denDriessche@skynet.be> wrote in message <news:3cacc2d6@10.1.10.29>...

    > "Joe "Nuke Me Xemu" Foster" <joe@bftsi0.UUCP> wrote in message
    > news:3caa2d54@10.1.10.29...


    > > The same broken way, you mean! Your sortable-containers have methods
    > > to swap elements, but comparing two elements /still/ requires that the
    > > elements be fetched separately, when you /could/ have added another
    > > method to the containers to support comparing elements, something most
    > > sorting algorithms tend to do quite a bit, hmmm? Fortunately, I also
    > > did this for you, weasel-boy, way back in February:
    > >
    > > URL:http://groups.google.com/groups?selm...%40tkmsftngp03

    >
    > Adding the "comparison capability" to the containers is a possible design
    > option. For what I had in mind it is inferior. If you add the "compareto"
    > method to the sortablecontainer, you might just as well add the sort method
    > to it as well. There would be no need for icomparers, isortablecontainers
    > nor isortAlgorithms.
    > The interfaces didn't come out of nowhere. They where carefully planned and
    > thought out. The major reason for having a separate ISortableContainer and
    > IComparer is reuse. No more, no less. Adding the compareto method directly
    > to containers could buy you performance(a little I guess but yet to be
    > benchmarked - my bet would be less than 5% on average).
    > Here are my counter-arguments:
    > 1) Decoration is harder when compareto is in the container
    > Our imaginary ISortableContainer2 interface would now look like this (you
    > might probably want to skip some more methods but that's irrelevant)
    > <code>
    > interface ISortableContainer2:
    > public enum eCompareResult
    > eSmaller = -1
    > eEqual = 0
    > eLarger = 1
    > end enum
    >
    > Public Property Get Count () As Long
    > Public Property Get Item (ByVal nPos As Long) As Variant
    > Public Sub Swap (ByVal nPosFrom As Long, ByVal nPosTo as Long)
    > public function CompareElements (byval nPosFirst as long, byval nPosSecond
    > as long) as eCompareResult
    > </code>


    Wrong, moron. Did you conveniently "forget" about my example
    iSortableContainer_Compare function? (If so, you /should/ have
    thought to at least snip the link, above!)

    Private Function iSortableContainer_Compare(ByVal nPos1 As Long, _
    ByVal nPos2 As Long, ByVal Compare As iComparer) As Long

    nPos1 = nPos1 - 1 + LBound(mArray)
    nPos2 = nPos2 - 1 + LBound(mArray)

    iSortableContainerCompare = Compare.Compare(mArray(nPos1), mArray(nPos2))
    End Sub

    This way, the container isn't constantly having to copy elements
    back to the sorting code just so the sorting code can compare them.
    Duh.

    [rest of brainless strawman snipped]

    --
    Joe Foster <mailto:jlfoster%40znet.com> KrazyKookKultz! <http://www.xenu.net/>
    WARNING: I cannot be held responsible for the above They're coming to
    because my cats have apparently learned to type. take me away, ha ha!



  5. #5
    Willy Van den Driessche Guest

    Re: The eternal sorting debate. Where to do sorting

    I've posted a new benchmark on my site. The results more than surprise me
    Generating array 20 ticks (100000 random doubles)

    Component array quicksort (doubles)5518 ticks (non-optimized using
    varassign)
    Component array quicksort (doubles)2513 ticks (optimized without varassign)
    handcoded double array quicksort 80 ticks (no comparers or adapters
    involved)
    Joe array quicksort (doubles)3865 ticks (non optimized for swap using
    varassign)
    Joe array quicksort non object (doubles)3085 ticks (optimized without
    varassign)

    I can understand that "Joe" sort is faster than the na´ve implementation.
    However, I have a hard time figuring out why the optimized version of my
    component is still faster than an optimized Joe sort. (Maybe it's the
    refcounting on the comparer being passed around all the time ?)

    (Byref and Byval are the same for both)

    Seems like someone out there is trying to make a point that there is
    generally a bit of truth in both camps.
    --
    Van den Driessche Willy
    For a work in progress :
    http://users.skynet.be/wvdd2/index.html



  6. #6
    Joe \Nuke Me Xemu\ Foster Guest

    Re: The eternal sorting debate. Where to do sorting

    "Willy Van den Driessche" <Willy.Van.denDriessche@skynet.be> wrote in message <news:3cad9cf4@10.1.10.29>...

    > I can understand that "Joe" sort is faster than the na´ve implementation.
    > However, I have a hard time figuring out why the optimized version of my
    > component is still faster than an optimized Joe sort. (Maybe it's the
    > refcounting on the comparer being passed around all the time ?)


    Hardly: You "forgot" a few things in your zeal to find some way to
    "prove" that my version is "actually" slower, such as switching to
    sorting arrays of Doubles and having to copy the entire array twice.
    You aren't using my Quicksort either, but instead your Cretinsort.
    I also wonder if your components were compiled using some of the
    "Advanced Optimizations" you "forgot" to select in BenchSorting.VBP.
    Exactly whom do you think you're fooling, anyway?

    > (Byref and Byval are the same for both)


    Especially when it comes to iComparer, hmmm? I see you also "forgot"
    about the following change to iComparer.Compare's signature, which I
    had mentioned as well in that same February post I already cited:

    URL:http://groups.google.com/groups?selm...%40tkmsftngp03

    Function Compare(ByRef Value1 As Variant, ByRef Value2 As Variant) As Long

    This /easy/ fix makes sorting over 13% faster, on average. No wonder
    you "forgot"! Did you really think I wouldn't check? Imbecile...

    > Seems like someone out there is trying to make a point that there is
    > generally a bit of truth in both camps.


    It seems you /can/ be trusted after all -- to attempt to weasel out
    of your obvious benchmarking Agenda.NET however you possibly can!

    --
    Joe Foster <mailto:jlfoster%40znet.com> L. Ron Dullard <http://www.xenu.net/>
    WARNING: I cannot be held responsible for the above They're coming to
    because my cats have apparently learned to type. take me away, ha ha!



  7. #7
    Willy Van den Driessche Guest

    Re: The eternal sorting debate. Where to do sorting

    Ok Joe. From now on you're right all the time. Sell your crap to other
    people.
    --
    Van den Driessche Willy




  8. #8
    Joe \Nuke Me Xemu\ Foster Guest

    Re: The eternal sorting debate. Where to do sorting

    "Willy Van den Driessche" <Willy.Van.denDriessche@skynet.be> wrote in message <news:3cade49a@10.1.10.29.>..

    > Ok Joe. From now on you're right all the time. Sell your crap to other
    > people.


    Actually, there may be some benefit to passing the comparer ByRef to
    ISortableContainer2_Compare after all, at least in the VB5 EE SP3 IDE:

    Private Function ISortableContainer2_Compare(ByVal nPos1 As Long, ByVal nPos2 As Long, ByRef Comparer As iComparer) As Long
    nPos1 = nPos1 - 1 + LBound(mArray)
    nPos2 = nPos2 - 1 + LBound(mArray)
    ISortableContainer2_Compare = Comparer.Compare(mArray(nPos1), mArray(nPos2))
    End Function

    Oh yeah, about your straightqSort in cQuickSort2 -- it's b0rked d00d!
    Replace the last eight lines of cQuickSort2 with this to see it:

    If Low < UpperBound Then
    StraightqSort objContainer, Low, UpperBound, Compare
    End If

    'Exit Sub
    Dim i As Long: For i = LowerBound To UpperBound - 1
    If objContainer.Compare(i, i + 1, Compare) > 0 Then
    Debug.Print "item"; i; "="; objContainer.Item(i);
    Debug.Print ", item"; i + 1; "="; objContainer.Item(i + 1)
    Debug.Assert objContainer.Compare(i, i + 1, Compare) <= 0
    End If
    Next
    End Sub

    Private Sub iSortAlgorithm2_SortContainer(ByVal objContainer As ISortableContainer2, ByVal objComparer As iComparer)

    StraightqSort objContainer, 1, objContainer.Count, objComparer

    'Exit Sub
    Dim i As Long: For i = 1 To objContainer.Count - 1
    If objContainer.Compare(i, i + 1, objComparer) > 0 Then
    Debug.Print "item"; i; "="; objContainer.Item(i);
    Debug.Print ", item"; i + 1; "="; objContainer.Item(i + 1)
    Debug.Assert objContainer.Compare(i, i + 1, objComparer) <= 0
    End If
    Next
    End Sub

    I have to ask, have you ever heard of this concept called "testing"?
    Use the LBound, Luke...

    --
    Joe Foster <mailto:jlfoster%40znet.com> L. Ron Dullard <http://www.xenu.net/>
    WARNING: I cannot be held responsible for the above They're coming to
    because my cats have apparently learned to type. take me away, ha ha!



  9. #9
    Willy Van den Driessche Guest

    Re: The eternal sorting debate. Where to do sorting

    Oops, Fiddled with my newgroups settings. That last post was mine of
    course.
    --
    Van den Driessche Willy
    For a work in progress :
    http://users.skynet.be/wvdd2/index.html



  10. #10
    Joe \Nuke Me Xemu\ Foster Guest

    Re: The eternal sorting debate. Where to do sorting

    "Alfredo the pistolero" <wvddwebcomments@skynet.be> wrote in message <news:3cb2e634$1@10.1.10.29>...

    > OK, if you agree to continue (or rather start) the discussion in a civilized
    > way, then we might actually get somewhere.


    That depends, obviously, on what you're "forgetting" /this/ time.

    > I've added the IsContainerSorted function. You where correct to state that
    > my "JoeSort" implementation was incorrect. I didn't add the doubles test to
    > fool your sort or interfaces. Just to test the performance of both in both
    > cases. I was unable to find the bug in my implementation of the JoeSort.
    > If you know the problem, drop a line.


    The following change to Command5_Click and/or Command6_Click will
    help you see it:

    objArray.ArrayValue = Array(3, 4, 2, 4, 9, 8, 1, 6, 1, 9, 8) 'varDoubles

    What happens is that the pivot may be swapped with other elements.

    > I was so frustrated in my quest for that bug that I decided to take another
    > version for QuickSort (one from the practical programmer). I turns out to
    > be slower than the Delphi derivate but that is not my point.


    Are you using VBA.Rnd? It's rather slow, isn't it?

    > few data, but I'm working on that - that (optimized) JoeSort is faster than
    > (optimized) WillySort. This is most obvious for string arrays. However,
    > for a certain number, WillySort becomes faster than JoeSort (for the doubles
    > I took a 100000 double array; for strings even 115869 strings get sorted
    > faster with JoeSort than WillySort).


    What *exactly* are you claiming is "JoeSort" /this/ time?

    > BTW3. (political area). I like VB.NET. Not as one who comes from VB6


    YM "Religious"! After all, isn't even Microsoft finally admitting to
    their overzealous, dogmatic, unthinking, unjustifiable Evangelism.NET?

    URL:http://microsoft.com/presspass/press...DivisionPR.asp

    > because that generates lots of work. But as a new tool and language I like
    > it. I have never had the intention to promote it over VB6, however. They
    > are different things with different capabilities.


    Then you are indeed totally unique upon the face of the Earth, sirrah.
    For a much more typical example of VB6 vs. B# botchmarking, see:

    URL:http://devhood.com/tutorials/tutoria...utorial_id=203

    Gee, I wonder why the .VBP files contain the line:

    VersionCompanyName="Microsoft Research"

    The projects' Advanced Optimization settings are also very interesting.

    --
    Joe Foster <mailto:jlfoster%40znet.com> KrazyKookKultz! <http://www.xenu.net/>
    WARNING: I cannot be held responsible for the above They're coming to
    because my cats have apparently learned to type. take me away, ha ha!



  11. #11
    Willy Van den Driessche Guest

    Re: The eternal sorting debate. Where to do sorting

    I got the following (approximate) timing results. They speak for
    themselves. JoeSort is much better for strings (around 20%). WvddSort is
    better for doubles (around 20%) . I guess the byref in the comparer
    accounts for that. BenchProgram available within an hour from posting this.
    (tables show count of samples, ticks for joe and ticks for wvdd)
    ****Doubles****
    Size TimeJoe TimeWvdd
    1 0 80
    2 0 0
    3 0 0
    4 0 0
    5 0 0
    10 0 0
    20 0 0
    30 0 0
    40 0 0
    50 0 0
    100 10 0
    200 0 0
    300 0 10
    400 0 10
    500 10 10
    1000 20 20
    2000 50 40
    3000 70 60
    4000 110 91
    5000 130 110
    10000 270 231
    20000 621 530
    30000 1032 811
    40000 1352 1102
    50000 1672 1452
    100000 3635 2945
    200000 8412 6279
    300000 12788 9754
    400000 16443 14471
    500000 20690 17155
    1000000 46868 35761
    2000000 95026 77652
    3000000 158327 119813
    4000000 198606 162674
    5000000 253554 204835

    ****Strings****
    Size TimeJoe TimeWvdd
    1 0 10
    2 0 0
    3 0 0
    4 0 0
    5 0 0
    10 0 0
    20 0 0
    30 0 10
    40 0 0
    50 0 0
    100 10 0
    200 10 10
    300 10 20
    400 20 21
    500 20 20
    1000 50 60
    2000 130 160
    3000 231 300
    4000 350 481
    5000 561 631
    10000 1582 2013
    20000 5068 6679
    30000 10525 13981
    40000 18396 24115
    50000 30644 37454
    100000 108165 143336

    --
    Van den Driessche Willy
    For a work in progress :
    http://users.skynet.be/wvdd2/index.html



  12. #12
    Willy Van den Driessche Guest

    Re: The eternal sorting debate. Where to do sorting

    For those who are interested, there is sourcecode for the Array.Sort in .NET
    available at
    http://msdn.microsoft.com/downloads/.../sample.asp?ur
    l=/msdn-files/027/001/901/msdncompositedoc.xml

    It seems to use an object and non-object implementation too.

    The Quicksort implementation is much like the Borland Delphi Sorter Demo.
    --
    Van den Driessche Willy
    For a work in progress :
    http://users.skynet.be/wvdd2/index.html



Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center