"brzydka" funkcja

Zakład patologii kodu
1

Nie wiem czy dział odpowiedni… bo problem raczej nie podchodzący pod Rails.

Mam w programie funkcję która zwraca indeks “równowagi”.

Już tłumaczę. Jest np taka tablica
tab = [-7, 1, 5, 2, -4, 3, 0]

Indeks równowagi wynosi 3 bo
tab[0] + tab[1] + tab[2] = tab[4] + tab[5] + tab[6]

-7 + 1 + 5 = -4 + 3

czyli po prostu

-1 = -1

Ta samo też będzie dla 6
tab[0] + tab[1] + tab[2] + tab[3] + tab[4] + tab[5] = 0
Inne wartości nie mają już tej właściwości w tym przypadku.
Indeks równowagi może mieć wartość od 0 do wielkości tablicy - 1.

Funkcja eql zwraca pierwszy znaleziony indeks równowagi a jak go nie ma to -1

[code=ruby]def is_equal?(a, b)
sum_a = sum_b = 0
a.each { |i| sum_a += i }
b.each { |i| sum_b += i }
return true if sum_a == sum_b
false
end

def eql(arr)
len = arr.size
return -1 if len < 1
return 0 if len == 1 and arr.first == 0
idx = 0
arr.each { |i|
if idx == len-1
return idx if is_equal?(arr[0…idx-1], [0])
elsif arr.index(i) != 0
return idx if is_equal?(arr[0…idx-1], arr[idx+1…len])
else
return idx if is_equal?([0], arr[idx+1…len])
end
idx += 1
}
-1
end[/code]
Generalnie działa, tylko całą konstrukcja wydaje mi się nieco bardziej podchodząca pod C niż pod Rubiego.
Da się to jakoś poprawić?

2

Przede wszystkim można zacząć od porzucenia proceduralnego podejścia, na rzecz object-oriented :slight_smile:

3

tab = [-7, 1, 5, 2, -4, 3, 0] left_sum = 0 right_sum = tab.inject(0){|s,e| s + e} indices = [] tab.each_with_index do |element,index| right_sum -= element indices << index if left_sum == right_sum left_sum += element end puts indices.join(", ")
Kod wygląda w stylu C, m.in. dlatego, że zamiast sensownych nazw typu “index”, “length”, etc. stosujesz “idx”, “len”.
Ale podstawa to dobrze przemyślany algorytm.

@pplcanfly obiektowe zorientowanie nie ma tu nic do rzeczy.

EDIT

Moje rozwiązanie nie sprawdza tego specjalnego warunku, w którym jest tylko jeden element tablicy - można to oczywiście dodać, ale nie bardzo rozumiem, dlaczego sytuacja w której po prawej i lewej stronie tego elementu nie ma żadnych wartości (tzn. każda z sum wynosi 0), jest odmienna od pozostałych sytuacji, gdy są tak jakieś wartości.

4

Wymyśliłem coś takiego,

[code]def equal_index(array)
one_element_array_without_zero = array.size == 1 && array.first != 0
return -1 if one_element_array_without_zero

(0...array.size).each do |index|
    left_slice_sum = array.slice(0..index).reduce(:+)
    right_slice_sum = array.slice(index..-1).reduce(:+)
    return index if left_slice_sum == right_slice_sum
end
-1

end[/code]

5

Niestety nie zgodzę się z kolegą wyżej by iść w kierunku oop. To jest czysta algorytmika i osobiście uważam że kod strukturalny jest typowym i poprawnym podejściem do tego typu problemów (+ częściowo funkcyjny, ale na pewno nie obiektowy). Pytanie nie jest czy kod przypomina C, ale czy przypomina algorytm. Oczywiście zawsze będzie pole do polepszenia czytelności, ale musimy się liczyć z prawdopodobnie gorszą wydajnością.

Przykładowo, rozwiązanie może być takie: dla każdego indeksu I z przedziału [0…rozmiar_tablicy-1] sprawdź czy indeks I dzieli tablicę na dwie części, których suma elementów jest równa. Zapisać to w rubym można tak:

arr = [-7, 1, 5, 2, -4, 3, 0] puts 0.upto(arr.size - 1).find_all {|i| arr[0, i].inject(0, :+) == arr[i+1..-1].inject(0, :+) }
Ładnie, prawda? Jednakże to rozwiązanie nie jest do końca optymalne gdyż w każdym kroku liczymy sumy obu podtablic (złożoność O(N^2)). Przechodząc elementy po kolei możemy zapamiętywać aktualną sumę i odpowiednio ją aktualizować.

lsum = 0 rsum = arr.inject(0, :+) 0.upto(arr.size - 1).find_all {|i| rsum -= arr[i]; lsum += arr[i]; (lsum - arr[i] == rsum)}
(nie gwarantuję że przypadki brzegowe są ok - musisz to sprawdzić :)).

6

Ok, zdecydowanie zagalopowałem się z OO :wink:

Mówiąc o polepszaniu czytelności, czy one-linery w tym w jakikolwiek sposób pomagają?:wink:

7

Każdy może to sam ocenić :slight_smile:
Ale moim zdaniem, istotne jest to żeby środek (zwięzły kod) do celu (zrozumiały kod) nie stał się celem samym w sobie :wink:

8

module EqualityAware def equal_index #... end end
Dla jednych:

Array.class_eval do include EqualityAware end a = Array.new a.equal_index
Dla innych:

a = Array.new a.extend(EqualityAware) a.equal_index

Ja zaś uważam, że jest mnóstwo algorytmiki w Ruby która jest przypisana jako odpowiedzialność do klas gdzie najbardziej pasuje. Gdyby ode mnie to zależało to taką funkcję chciałbym wywoływać na Array’u. W zależności od domeny z jaką miałbym doczynienia przypisałbym ten moduł na stałe do Array albo tylko do tych instancji gdzie jest mi to potrzebne. I zdecydowanie wolę takie API niż podejścia w stylu:

EqualityAware.equal_index(array) StringGsubber.gsub(string, /a/, "b") ArraySorter.sort(array)

9

paneq, to, że wywołujesz metodę na klasie Array nie znaczy, że jest to obiektowy kod. Chodziło mi o samo rozwiązanie a nie to gdzie to się umieści.

10

W ogólniejszym pojęciu co i gdzie powinno się znajdować, dalej obstawałbym za OO. Jednak kiedy na tapecie mamy tylko te dwie metodki to przychylam się do wersji, że jakiekolwiek kombinacje z modelem programowania byłyby na wyrost. Powyższy problem pachnie mi troche zadankiem z Eulera niż jakąś większą aplikacją, w której trzymanie się OO byłoby raczej wskazane:>

11

Ok. Myślałem że chodziło o obiektowe api a nie o obiektową implementację. Masz rację.

12

Stawiałem na czytelność kodu, więc bez benchmarków proszę mi tu. :wink: BTW refactoring warto zacząć od napisania paru testów.

[code=Ruby]def sum(array)
array.reduce(0, :+)
end

def balanced_index(array)
array.each_index do |i|
left = array[0, i]
right = array[i+1…-1]
return i if sum(left) == sum(right)
end

nil
end

if FILE == $0
require ‘test/unit’

class TestBalancedIndex < Test::Unit::TestCase
def test_empty
assert_nil balanced_index([])
end

def test_small
  assert_equal 0, balanced_index([2])
  assert_equal 0, balanced_index([0])
end

def test_first
  assert_equal 0, balanced_index([20, 1, -3, 2])
end

def test_last
  assert_equal 3, balanced_index([1, -3, 2, 20])
end

def test_other
  assert_equal 3, balanced_index([-7, 1, 5, 2, -4, 3, 0])
  assert_equal 2, balanced_index([-3, 3, 7])
  assert_nil balanced_index([2, 2])
  assert_nil balanced_index([-7, 1, 5, 2, -4, 4, 2])
  assert_equal 0, balanced_index([2, 1, -3, 2])
end

end
end[/code]

13

Kocham to forum – nie tylko zrefaktoryzują kod, ale i testy napiszą :slight_smile:

14

Tylko kto dostanie wypłatę/wpis w indeksie ?

15

OMG. 13 Odpowiedzi. :O.
Już czytam. :slight_smile:

16

Wynika to pewnie z faktu że mało postów jest na forum i jak coś się pojawi (sensownego) to każdy się rzuca jak na wygłodniała hiena, no ale czy to źle? Przynajmniej wiadomo że na 99% otrzyma się sensowną odpowiedź no chyba że się trafi na 1% i cię ztrollją ;]

17

I rozwiązaliście właśnie jedno z zadań z Codility :wink:

18

Moje rozwiązanie:

[code=ruby]class Array
def balance
sum = self.inject(:+)
left = 0
self.each_with_index do |v, k|
return k if 2 * left + v == sum
left += v
end
-1
end
end

puts [-7, 1, 5, 2, -4, 3, 0].balance #3[/code]