Forum: Italian Ruby user group Implementazione Merge Sort in Ruby

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Matteo T. (Guest)
on 2009-03-20 22:38
Ciao a tutti,
studiando algoritmi e strutture dati dal famoso libro "introduction to
algorithms" ho pensato di implementare qualche algoritmo semplice in
Ruby per prova, ho provato con il merge sort.
Però il mio codice si comporta in modo strano... e visto che l'algoritmo
è praticamente copiato dal testo magari c'è qualche meccanismo ruby che
non mi è chiaro in generale qualcosa che mi è sfuggito.
Nota: visto che il testo assume che gli array vanno da 1 a N ho riaperto
la classe Array per dargli questo compotamento (forse è qui che sbaglio
qualcosa).

Codice:

---
class Array
  alias :old_slice :slice

 def slice(a, b)
    puts "Errore" if a == 0 || b == 0
    old_slice(a - 1, b)
  end

 def [](i)
    puts "Errore" if i == 0
    at(i - 1)
  end

 def []=(i, v)
    puts "Errore" if i == 0
    insert(i - 1, v)
  end

end

def mergeSort(l, p, r)
  if(p < r)
    q = (p + r) / 2
    mergeSort(l, p, q)
    mergeSort(l, q + 1, r)
    merge(l, p, q, r)
  end
end

def merge(l, p, q, r)
  sx = l.slice(p, q - p + 1)
  dx = l.slice(q + 1, r - q)
  sx << 9 # il testo qui mette infinito, io faccio prove con numeri < di
9 quindi dovrebbe andare no?
  dx << 9
  i = 1
  j = 1
  for k in (p..r)
    puts k
    if(sx[i] <= dx[j])
      l[k] = sx[i]
      puts "#{sx[i]}->#{k}"
      i = i + 1
    else
      l[k] = dx[j]
      j = j + 1
      puts "#{dx[i]}->#{k}"
    end
  end
end

l = [3, 1, 2, 0]
mergeSort(l, 1, l.length)
puts "\n", l
---

Ora la cosa strana è che come output la lista l è questa qui:

113313133120

Non solo non è ordinata ma ha pure qualche elemento di troppo, eppure
stampando i valori di k non superano mai il valore limite.

Che può essere?
Grazie
Paolo M. (Guest)
on 2009-03-21 12:18
Ciao Matteo,

se sostituisci il metodo mergeSort con il codice qui sotto vedrai che la
chiamata a merge aggiunge degli elementi all'array. L'errore è lì.

$indent = 0
def mergeSort(l, p, r)
  $indent += 1
  if p < r
    q = (p + r) / 2
    puts "#{"1".rjust($indent)} #{l.inspect}"
    mergeSort(l, p, q)
    puts "#{"2".rjust($indent)} #{l.inspect}"
    mergeSort(l, q + 1, r)
    puts "#{"3".rjust($indent)} #{l.inspect}"
    merge(l, p, q, r)
    puts "#{"4".rjust($indent)} #{l.inspect}"
  end
  $indent -= 1
end

Il debugging a puts non è grazioso, ma ha la sua efficacia :-)
Nota la inspect per stampare l'array in modo leggibile e la rjust per
mostrare il livello di ricorsione. Altra cosa: in Ruby le parentesi
nelle if non servono per cui if(sx[i] <= dx[j]) si può scrivere più
semplicemente come if sx[i] <= dx[j]

Paolo

Matteo T. wrote:
> Ciao a tutti,
> studiando algoritmi e strutture dati dal famoso libro "introduction to
> algorithms" ho pensato di implementare qualche algoritmo semplice in
> Ruby per prova, ho provato con il merge sort.
> Però il mio codice si comporta in modo strano... e visto che l'algoritmo
> è praticamente copiato dal testo magari c'è qualche meccanismo ruby che
> non mi è chiaro in generale qualcosa che mi è sfuggito.
> Nota: visto che il testo assume che gli array vanno da 1 a N ho riaperto
> la classe Array per dargli questo compotamento (forse è qui che sbaglio
> qualcosa).
>
> Codice:
>
> ---
> class Array
>   alias :old_slice :slice
>
>  def slice(a, b)
>     puts "Errore" if a == 0 || b == 0
>     old_slice(a - 1, b)
>   end
>
>  def [](i)
>     puts "Errore" if i == 0
>     at(i - 1)
>   end
>
>  def []=(i, v)
>     puts "Errore" if i == 0
>     insert(i - 1, v)
>   end
>
> end
>
> def mergeSort(l, p, r)
>   if(p < r)
>     q = (p + r) / 2
>     mergeSort(l, p, q)
>     mergeSort(l, q + 1, r)
>     merge(l, p, q, r)
>   end
> end
>
> def merge(l, p, q, r)
>   sx = l.slice(p, q - p + 1)
>   dx = l.slice(q + 1, r - q)
>   sx << 9 # il testo qui mette infinito, io faccio prove con numeri < di
> 9 quindi dovrebbe andare no?
>   dx << 9
>   i = 1
>   j = 1
>   for k in (p..r)
>     puts k
>     if(sx[i] <= dx[j])
>       l[k] = sx[i]
>       puts "#{sx[i]}->#{k}"
>       i = i + 1
>     else
>       l[k] = dx[j]
>       j = j + 1
>       puts "#{dx[i]}->#{k}"
>     end
>   end
> end
>
> l = [3, 1, 2, 0]
> mergeSort(l, 1, l.length)
> puts "\n", l
> ---
>
> Ora la cosa strana è che come output la lista l è questa qui:
>
> 113313133120
>
> Non solo non è ordinata ma ha pure qualche elemento di troppo, eppure
> stampando i valori di k non superano mai il valore limite.
>
> Che può essere?
> Grazie
Matteo T. (Guest)
on 2009-03-21 15:01
Paolo M. wrote:
> Ciao Matteo,
>
> se sostituisci il metodo mergeSort con il codice qui sotto vedrai che la
> chiamata a merge aggiunge degli elementi all'array. L'errore è lì.
>

Ciao ti ringrazio per la risposta, ho provato e ora vedo bene l'albero
di ricorsione, dove stampo anche mano a mano il sotto-vettore sinistro e
sotto-vettore destro.
E il vettore viene ogni volta suddiviso correttamente.
La parte di codice che è a questo punto sicuramente indagata è:

  for k in p..r
    if sx[i] <= dx[j]
      l[k] = sx[i]
      i += 1
    else
      l[k] = dx[j]
      j += 1
    end
  end

Il ciclo che di fatto fa la fusione. Infatti commentando il ciclo o
anche solo le assegnazioni a l[k] il vettore viene smontato giusto e
torna come era prima (disordinato) ma senza elementi di troppo.
Il fatto è però che se stampo il valore di k va da 1 a 4 come deve
essere, eppure vengono aggiunti elementi.

Ora di implementazioni di merge sort ne ho viste di diverse ma solo
quella di questo libro fa la fusione con questo for così organizzato.
Non vorrei che sia sbagliato il testo.. ma mi fa strano visto che è uno
dei testi più usati e rinomati sull'argomento. Un errore sarebbe reso
noto subito.
Paolo M. (Guest)
on 2009-03-22 10:33
Matteo T. wrote:
> Il ciclo che di fatto fa la fusione. Infatti commentando il ciclo o
> anche solo le assegnazioni a l[k] il vettore viene smontato giusto e
> torna come era prima (disordinato) ma senza elementi di troppo.
> Il fatto è però che se stampo il valore di k va da 1 a 4 come deve
> essere, eppure vengono aggiunti elementi.

Se ancora non l'hai fatto, ti consiglio di stampare il vettore l dopo
ogni assegnamento, così vedrai da dove saltan fuori questi elementi
extra.

Ho però un sospetto. Nel tuo codice c'è una

def []=(i, v)
  puts "Errore" if i == 0
  insert(i - 1, v)
end

La insert, dice il manuale, fa:

>  array.insert(index, obj...) → array
>
> Inserts the given values before the element with the given index (which may
> be negative).
>
>   a = %w{ a b c d }
>   a.insert(2, 99)         #=> ["a", "b", 99, "c", "d"]
>   a.insert(-2, 1, 2, 3)   #=> ["a", "b", 99, "c", 1, 2, 3, "d"]

Nota che il *before the element* non è *at the element*

Non è che al posto della insert dovevi richiamare il metodo []=
originale?

Paolo
Matteo T. (Guest)
on 2009-03-22 12:19
Paolo M. wrote:
> Matteo T. wrote:
>> Il ciclo che di fatto fa la fusione. Infatti commentando il ciclo o
>> anche solo le assegnazioni a l[k] il vettore viene smontato giusto e
>> torna come era prima (disordinato) ma senza elementi di troppo.
>> Il fatto è però che se stampo il valore di k va da 1 a 4 come deve
>> essere, eppure vengono aggiunti elementi.
>
> Se ancora non l'hai fatto, ti consiglio di stampare il vettore l dopo
> ogni assegnamento, così vedrai da dove saltan fuori questi elementi
> extra.
>
> Ho però un sospetto. Nel tuo codice c'è una
>
> def []=(i, v)
>   puts "Errore" if i == 0
>   insert(i - 1, v)
> end
>
> La insert, dice il manuale, fa:
>
>>  array.insert(index, obj...) → array
>>
>> Inserts the given values before the element with the given index (which may
>> be negative).
>>
>>   a = %w{ a b c d }
>>   a.insert(2, 99)         #=> ["a", "b", 99, "c", "d"]
>>   a.insert(-2, 1, 2, 3)   #=> ["a", "b", 99, "c", 1, 2, 3, "d"]
>
> Nota che il *before the element* non è *at the element*
>
> Non è che al posto della insert dovevi richiamare il metodo []=
> originale?
>
> Paolo


Hai proprio ragione! Facendo così:

class Array
  alias :old_slice :slice
  alias :old_op :[]=

 def slice(a, b)
    puts "Errore" if a == 0 || b == 0
    old_slice(a - 1, b)
  end

 def [](i)
    puts "Errore" if i == 0
     at(i - 1)
  end

 def []=(i, v)
    puts "Errore" if i == 0
    old_op(i - 1, v)
  end
end

Ora funziona.

Grazie di tutto.

Ciao
This topic is locked and can not be replied to.