Greetings,
Ouch. That's...probably painfully expensive for large @children arrays.
Trying to understand, it looks like you're sorting on child.sequence, and
keeping each child with the same sequence in the same order as they are
initially in the @children array?
You could try something like this:
def sort_children2
@children = @children.sort_by.with_index { |child, index|
[child.sequence, index]}
end
One key to understanding this is that arrays elements ([child.sequence,
index] here) compare on each element when #<=> is used, so you're
essentially adding the elements index in the array as a secondary sort key.
The call of #sort_by and then #with_index is chaining enumerators.
(Hopefully I've gotten that basically right; it's not the simplest part of
Ruby, but it's fascinating...) This all allows us to use an unstable (but
fast!) sort, while essentially adding additional sort keys that keep it
stable.
A shorter version reads:
def sort_children2
@children = @children.sort_by.with_index { |*args| args}
end
Clever, perhaps, but a little obscure. This works because |*args| stuffs
all the arguments into an array, which coincidentally is exactly where we
want them.
Here's a fun little piece of code to demonstrate what I'm doing:
# This example is flawed, but hopefully useful for demonstration
purposes.
def test_stable_sorting
ary = (1..100).to_a.shuffle + (1..100).to_a.shuffle
# This associates an ordering with the randomized numbers
idx = 0
paired = ary.collect {|value| [value, idx += 1]}
puts "Now the numbers are paired; the first is the random number 1-100,"
puts "the second is its sequence within the 200 entries."
puts paired.inspect
puts
puts "#sort is unstable; you'll see many entries with equal first values"
puts "where the first of them has a higher second (sequence) number,
meaning"
puts "it's out of order now."
puts paired.sort {|x,y| x.first <=> y.first }.inspect
puts
puts "Now we sort exclusively on the value, while preserving ordering;"
puts "All entries with identical first values should have second values"
puts "that are also in numerical order."
puts paired.sort_by.with_index {|x, i| [x.first, i]}.inspect
end
-- Morgan
On Sun, Jan 30, 2011 at 5:22 PM, Robert Rice <rice.au...@pobox.com> wrote:
> Hi Morgan:
>
> Thanks for the info although I have to admit that I don't understand how
> your solutions work.
>
> I also needed my sort to return a modified flag to update the file if
> changed so I wrote my own bubble sort.
> I haven't test this yet:
>
> def sort_children # Don't trust Ruby sort to maintain sequence, also need
> set_modified
> return if @children.empty?
>
>
> arr = @children.map{ | child | [ child.sequence, child ]
> modified = false
>
>
> while true # bubble sort
> change = false
> new_arr = []
>
>
> arr.each_with_index do | new_child, index |
> if index.zero?
> prior_child = new_child
> new_arr[ 0 ] = new_child
>
>
> elsif new_child.first < prior_child.first # OOO
> change = true
> new_arr.insert( index - 1, new_child )
>
>
> else
> new_arr[ index ] = new_child
> prior_child = new_child
> end
> end
> break unless change
>
>
> modified = true
> arr = new_arr
> end
> return unless modified
>
>
> @children = arr.map{ | child | child.last }
> set_modified()
> end
>
> Thanks,
> Bob Rice
>
> On Jan 30, 2011, at 7:19 PM, Morgan Schweers wrote:
>
> Greetings,
> Ruby's sort algorithm is quicksort, last I checked, and quicksort is not
> stable (which is the property you're looking for in a sort). There are a
> bunch of ways around this, including writing your own, but one cute, quick,
> but possibly performance-impairing, approach I've seen (Matz's suggestion)
> is:
>
> n = 0
> ary.sort_by {|x| [x, n += 1]}
> Apparently it's also possible in 1.9.x (and thus MacRuby) to do:
>
> ary.sort_by.with_index {|x, i| [x, i]}
>
> It's not much faster, though. In the end, I'd probably suggest writing
> your own, if the performance of this is too poor. (One person claimed this
> was on the order of 50 times slower; I haven't benchmarked it myself.)
> Mergesort is stable, for example.
>
> This is a common problem; most systems don't need a stable sort, so they
> use Quicksort as a 'best general purpose' algorithm.
>
> -- Morgan
>
> On Sun, Jan 30, 2011 at 12:03 PM, Robert Rice <rice.au...@pobox.com>wrote:
>
>> Hi:
>>
>> Does the Ruby Array sort algorithm maintain the relative position for
>> children returning the same value for the comparison? I had an instance
>> where two children having the compare value were interchanged.
>>
>> Thanks,
>> Bob Rice
>>
>> _______________________________________________
>> MacRuby-devel mailing list
>> MacRuby-devel@lists.macosforge.org
>> http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel
>>
>
> _______________________________________________
> MacRuby-devel mailing list
> MacRuby-devel@lists.macosforge.org
> http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel
>
>
>
> _______________________________________________
> MacRuby-devel mailing list
> MacRuby-devel@lists.macosforge.org
> http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel
>
>
_______________________________________________
MacRuby-devel mailing list
MacRuby-devel@lists.macosforge.org
http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel
