Forum: Ruby How can I do the below operation less then O(n2) time ?

249c7fd851c5c5ac5a1abdb756472ae1?d=identicon&s=25 Arup Rakshit (my-ruby)
on 2014-03-14 15:35
arr = [
         {:id=>12, :name=>"foo1"}, {:id=>15, :name=>"foo3"},
         {:id=>26, :name=>"foo2"}, {:id=>18, :name=>"foo4"}
      ]

sort_order = [15,12,18,26]

# below is working, but O(n2)
sort_order.map { |id| arr.find { |h| h[:id] ==  id }
E088bb5c80fd3c4fd02c2020cdacbaf0?d=identicon&s=25 Jesús Gabriel y Galán (Guest)
on 2014-03-14 16:34
(Received via mailing list)
On Fri, Mar 14, 2014 at 3:35 PM, Arup Rakshit <lists@ruby-forum.com>
wrote:
> arr = [
>          {:id=>12, :name=>"foo1"}, {:id=>15, :name=>"foo3"},
>          {:id=>26, :name=>"foo2"}, {:id=>18, :name=>"foo4"}
>       ]
>
> sort_order = [15,12,18,26]
>
> # below is working, but O(n2)
> sort_order.map { |id| arr.find { |h| h[:id] ==  id }

My solution builds an index first in a hash, O(n), followed by a
sort_by the indexed value. Checking the index is O(1), and sort_by I
suppose it's O(n*log n) (can someone confirm which is the time
complexity of sort_by?)

2.0.0p195 :011 > index = {}
 => {}
2.0.0p195 :012 > sort_order.each_with_index {|e,i| index[e] = i}
 => [15, 12, 18, 26]
2.0.0p195 :013 > arr.sort_by {|h| index[h[:id]]}
 => [{:id=>15, :name=>"foo3"}, {:id=>12, :name=>"foo1"}, {:id=>18,
:name=>"foo4"}, {:id=>26, :name=>"foo2"}]

So, that should make it O(n*log n), or whatever the complexity of
sort_by is.

Hope this helps,

Jesus.
Dd70f9d8cc5f9ee488d68e7a787ba526?d=identicon&s=25 Sergey Avseyev (avsej)
on 2014-03-14 17:55
(Received via mailing list)
Attachment: signature.asc (230 Bytes)
On Fri, 14 Mar 2014 15:35:49 +0100
Arup Rakshit <lists@ruby-forum.com> wrote:

> arr = [
>          {:id=>12, :name=>"foo1"}, {:id=>15, :name=>"foo3"},
>          {:id=>26, :name=>"foo2"}, {:id=>18, :name=>"foo4"}
>       ]
>
> sort_order = [15,12,18,26]
>
> # below is working, but O(n2)
> sort_order.map { |id| arr.find { |h| h[:id] ==  id }
>

You can also use sort_order directly

    arr.sort_by{|i| sort_order.index(i[:id]) }

Note that `sort_order.index` will be called only once for each `arr`
entry
E088bb5c80fd3c4fd02c2020cdacbaf0?d=identicon&s=25 Jesús Gabriel y Galán (Guest)
on 2014-03-14 18:13
(Received via mailing list)
On Fri, Mar 14, 2014 at 5:54 PM, Sergey Avseyev
<sergey.avseyev@gmail.com> wrote:
>> # below is working, but O(n2)
>> sort_order.map { |id| arr.find { |h| h[:id] ==  id }
>>
>
> You can also use sort_order directly
>
>     arr.sort_by{|i| sort_order.index(i[:id]) }
>
> Note that `sort_order.index` will be called only once for each `arr`
> entry

Please note that this is O(n2) still. Calling index once for each
element in arr, makes it O(n) calls, and the index method itself is
also linear, so O(n) * O(n).

Jesus.
Please log in before posting. Registration is free and takes only a minute.
Existing account

NEW: Do you have a Google/GoogleMail, Yahoo or Facebook account? No registration required!
Log in with Google account | Log in with Yahoo account | Log in with Facebook account
No account? Register here.