ट्री टू ऐरे एल्गोरिथम (रूबी)

Question

मेरे पास एक शाखा मॉडल है जिसमें parent_id और child_id शामिल हैं। मैं अपने बच्चों के लिए प्रत्येक माता-पिता से पूछताछ किए बिना माता-पिता/बच्चों के संबंधों की एक सरणी प्राप्त करना चाहता हूं।

इस तालिका के लिए:

Parent_id | Child_id
1         | 2
1         | 6
1         | 9
2         | 3
3         | 10
4         | 7

मैं 1 के बच्चे और उसके बच्चों के बच्चे इस तरह प्राप्त करना चाहता हूं:

{2 => {3 => {10}}, 6, 9}

अपने बच्चों के लिए प्रत्येक माता-पिता से पूछे बिना।

क्या इसे कुशलता से हासिल करने के लिए कोई एल्गोरिदम है या क्या मुझे प्रत्येक माता-पिता के माध्यम से जाने की ज़रूरत है? धन्यवाद।

ruby algorithm tree

4

Gal 6 नवम्बर 2011, 19:51

[2 => [3 => [10]], 6, 9] रूबी मान्य नहीं है। ऐरे या हैश?

–

tokland

6 नवम्बर 2011, 20:00

कोई फर्क नहीं पड़ता, मैं या तो हैश/सरणी प्रतिनिधित्व की तलाश में हूं।

–

Gal

6 नवम्बर 2011, 20:02

1

अच्छा सवाल और अच्छे जवाब!

–

Zabba

6 नवम्बर 2011, 20:41

Answer 1

एक सांस-पहली खोज काम करेगी।

def build_tree(i, edges)
    list = {}
    out_nodes = edges.select {|e| e[0] == i}.map {|e| e[1]}.uniq
    out_nodes.each {|n| list[n] = build_tree(n, edges)}
    list
end

edges = [[1,2],[1,6],[1,9],[2,3],[3,10],[4,7]]
puts build_tree(1, edges)
# {2=>{3=>{10=>{}}}, 6=>{}, 9=>{}}

5

ZelluX 6 नवम्बर 2011, 20:36

ज़माने को समझ लिया। यह 3.6 सेकंड में, 100,000 बार तेजी से चलता है। बेंचमार्क पेस्टी।

–

Zabba

6 नवम्बर 2011, 21:02

Answer 2

एक कार्यात्मक और पुनरावर्ती दृष्टिकोण:

require 'facets'

def create_tree(pairs, root)
  relationships = pairs.map_by { |parent, child| [parent, child] }  
  get_children = proc do |parent|
    (relationships[parent] || []).mash do |child| 
      [child, get_children.call(child)]
    end
  end  
  get_children.call(root)
end

pairs = [[1, 2], [1, 6], [1, 9], [2, 3], [3, 10], [4, 7]]
p create_tree(pairs, 1)
#=> {6=>{}, 2=>{3=>{10=>{}}}, 9=>{}}

[संपादित करें] बिना पहलुओं के (और अब आप देखेंगे कि मैं इसका उपयोग क्यों करता हूं!):

def create_tree(pairs, root)
  relationships = Hash[pairs.group_by { |p, c| p }.map { |p, ary| [p, ary.map { |p, c| c }] }]
  get_children = proc do |parent|
    Hash[(relationships[parent] || []).map do |child| 
      [child, get_children.call(child)]
    end]
  end  
  get_children.call(root)
end

2

tokland 6 नवम्बर 2011, 20:43

पहलू मेरे लिए काम नहीं कर रहा है (मुझे 500 त्रुटि मिलती है)। तुम जानते हो क्यों?

–

Gal

6 नवम्बर 2011, 20:32

क्या आपने gem install facets की कोशिश की?

–

Zabba

6 नवम्बर 2011, 20:33

मेरे पास यह मेरे जेमफाइल में है (मैं रेल का उपयोग कर रहा हूं), बंडल चला गया।

–

Gal

6 नवम्बर 2011, 20:34

ज़माने को समझ लिया। पहला कोड 5 सेकंड का है, 100,000 बार चलाएँ।

–

Zabba

6 नवम्बर 2011, 20:45

@ ज़ब्बा, बेंचमार्किंग के लिए धन्यवाद। तो क्या यह कोड अनिवार्य से तेज है? यह थोड़ा आश्चर्य की बात है, शायद ज़ेलुएक्स का कोड सबसे तेज़ कार्यान्वयन नहीं है।

–

tokland

6 नवम्बर 2011, 20:47

ट्री टू ऐरे एल्गोरिथम (रूबी)

2 जवाब

संबंधित सवाल

नए सवाल