W jaki sposób zestawy tablic i zestawy sortowania zaimplementowane pod maską w Ruby

Question

Zazwyczaj tablice są implementowane jako porcje pamięci, zestawy jako mapy skrótów i sortowane zestawy jako listy pominięć. Czy tak też jest w przypadku Rubiego?

Próbuję ocenić zastosowanie różnych pojemników w Ruby pod względem wydajności i pamięci ślad

Answer 1

Tablice są częścią podstawowego biblioteki Ruby. Każda implementacja Ruby ma własną implementację tablic. Specyfikacja języka Ruby określa jedynie zachowanie tablic Ruby, nie określa żadnej konkretnej strategii implementacji. Nie określa nawet żadnych ograniczeń wydajności, które wymuszałyby lub przynajmniej sugerowałyby konkretną strategię wdrażania.

Jednak większość Rubiego pewne oczekiwania dotyczące spełniania charakterystyk tablic, które zmuszają implementację, która nie spełnia je w zapomnienie, bo nikt nie będzie faktycznie używać go:

• wstawianie, poprzedzenie lub dołączanie jako podobnie jak usunięcie elementu ma najgorszy przypadek - stopień złożoności O (n) i amortyzowany najgorszy przypadek - stopień złożoności O (1)
• uzyskiwania dostępu do elementu ma najgorszy możliwy stopień złożoności O (1)
• iteracja wszystkich elementów ma najgorszy możliwy stopień złożoności O (n)

Oznacza to, że tablice muszą być implementowane jako dynamiczne tablice z wykładniczą zmianą rozmiaru, w przeciwnym razie nie można spełnić tych gwarancji wydajności. You może uciec z bardzo szerokim i płytkim drzewem, ale AFAIK nie ma implementacji Ruby.

Oto Rubinius's array implementation, które osobiście uważam za najłatwiejszy ze wszystkich implementacji Rubiego. (Uwaga: tylko podstawowe funkcje są implementowane w C++, większość metod tablicowych jest zaimplementowanych w Ruby, np. W kernel/common/array.rb).

Set i SortedSet są częścią biblioteki set w pliku stdlib. Stdlib jest dzielony w większości niezmieniony pomiędzy implementacjami Ruby (przynajmniej części, które są faktycznie napisane w Ruby, oczywiście części napisane w innych językach nie mogą być udostępniane), a ponieważ Set jest napisane w Ruby, możesz oczekiwać tego samego we wszystkich implementacjach Ruby.

Set jest zaimplementowany jako Hash, gdzie stosowane są tylko klucze, wartości są po prostu zawsze true: patrz Set#add in lib/set.rb.

SortedSet jest wspierane przez czerwono-czarne drzewo, które nie jest zaimplementowane w Ruby.

Answer 2

Poprzednia odpowiedź w rzeczywistości nie obejmowała wydajności SortedSet.

• Array - O (1) dla dodawania, usuwania i elementem dostępu wskaźnika
• hash (używa tabeli mieszania) - O (1) (powiększenie 1 oczywiście niż macierze) dla dodawania, usuwania i Dostęp przez kluczowego
• Set - realizowany przez Hash więc sam
• SortedSet:

więc po odczytaniu kodu i testowania ręcznie za pomocą klasy, która licząc każdy porównać metody połączenia, oto wynik. Próbuje załadować moduł "rbtree" i używa zwykłego ustawienia jako zastępczego.

więc 2 opcje:

1. RBTree dostępne, wszystko jest szybko i zgodnie z oczekiwaniami, O (logN) na każdym Dodatkowo, O (1) na uzyskanie pierwszego, O (n) na soeted_set.to_a.
2. Usługa RBTree jest niedostępna. Używa Set (Hash underneath) i zmienia kolejność, jeśli jest brudny podczas czytania.

z Ruby 2.0.0 set.rb:

def to_a 
    (@keys = @hash.keys).sort! unless @keys 
    @keys 
end 

znaczy, że po kodzie:

X.times{ sorted_set << num; sorted_set.first } 

będzie O (XNlog (N)), ponieważ jest uporządkowana w przybliżeniu nlog (N).

W zasadzie używanie SortedSet bez upewnienia się, że RBTree jest dostępny, jest mylące i nieefektywne, ponieważ nie wykorzystuje faktu, że jest sortowane (wyszukiwanie binarne) podczas wstawiania. Używanie normalnych metod Set i array może być w tym przypadku szybsze.

sam przykład za pomocą zwykłego zestawu:

X.times{ set << num; set.min } 

będzie O (XN)

Konkluzja, jeśli trzeba SortedSet pracować wydajny, również dodać 'rbtree' do Gemfile.