Algorytmy oparte na tożsamości fizycznej do Hashtbl.hash

Question

Próbuję wyprowadzić plik Graphviz opisujący strukturę wartości. Ma to na celu diagnostykę, dlatego chcę, aby mój wykres odzwierciedlał rzeczywistą strukturę w pamięci tak ściśle, jak to możliwe. Używam poniżej mapowanie wartości wierzchołków Graphviz tak, że mogę ponownie użyć wierzchołek gdy wartość ma dwie lub więcej odniesień przychodzących:

let same = (==) 

module StateIdentity : Hashtbl.HashedType = struct 
    type t = R.meta_t state 
    let hash = Hashtbl.hash 
    let equal = same 
end 

module StateHashtbl = Hashtbl.Make (StateIdentity) 

Dokumentacja Hashtbl.hash sugeruje, że nadaje się do zastosowania zarówno przy StateIdentity.equal = (=) i kiedy StateIdentity.equal = (==), ale chciałbym, aby dostęp do tablicy hash był możliwie jak najbliżej O (1), wolałbym nie przepuszczać wykresu obiektów (potencjalnie dużego w tym przypadku) podczas każdego wyszukiwania.

Wiem, że Ocaml przenosi referencje dookoła, ale czy istnieje O (1) proxy dla tożsamości referencyjnej dostępnej w Ocaml?

Odpowiedź na Hashtable of mutable variable in Ocaml sugeruje, że nie.

Nie lubię dołączać numerów seryjnych do stanów, ponieważ jest to kod diagnostyczny, więc wszelkie błędy, które robię, mogą maskować inne błędy.

Answer 1

Jeśli używasz słowa "obiekt" w rozumieniu typów obiektów OCaml <...>, możesz użyć Oo.id, aby uzyskać niepowtarzalną liczbę całkowitą dla każdej instancji. W przeciwnym razie odpowiedź na pytanie "czy istnieje ogólny wskaźnik tożsamości wartości" brzmi "nie". W takim przypadku moja rada brzmi: zacznij od Hashtbl.hash, oceń, czy pasuje do twoich potrzeb, i w inny sposób zaprojektuj własną funkcję mieszającą.

Można również odtwarzać za pomocą Hashtbl.hash_param (patrz documentation), aby obracać pokrętłami przesuwów wartości podczas mieszania. Zauważ, że kod Hashtbl wykorzystuje listy połączone dla wiadra z tymi samymi hasłami, więc posiadanie mnóstwa konfliktów hash wywoła liniowe zachowanie wyszukiwania. Lepszym rozwiązaniem może być przejście do innych implementacji przy użyciu binarnych drzewek wyszukiwania dla segmentów konfliktów. Ale potem jeszcze raz, powinieneś ocenić swoją sytuację, zanim przejdziesz do bardziej złożonych (i gorszych wyników w "dobrym przypadku") rozwiązań.

Answer 2

Zauważyłem, że bardzo trudne jest używanie fizycznej równości do robienia haszyszu. Z pewnością nie możesz użyć czegoś takiego jak adres wartości jako swojego klawisza skrótu, ponieważ (jak mówisz) rzeczy są przenoszone przez GC. Kiedy masz już klucz hash, wydaje się, że możesz używać fizycznej równości do porównań, o ile twoje wartości są zmienne. Jeśli twoje wartości nie są zmienne, OCaml nie gwarantuje wiele o znaczeniu (==). Praktycznie rzecz biorąc, niezmienne obiekty, które są równe (=), teoretycznie mogą zostać scalone w jeden fizyczny obiekt, jeśli chce tego kompilator lub środowisko wykonawcze OCaml (lub na odwrót).

Kiedy pracuję nad różnymi możliwościami, zwykle umieszczam numer sekwencji w moich wartościach, kiedy potrzebuję unikalnego identyfikatora. Jak mówi gasche, możesz użyć Oo.id, jeśli twoje wartości są rzeczywistymi obiektami typu OO.

Answer 3

Podobnie jak inne, myślę, że unikalne identyfikatory są drogą do zrobienia.

Unikatowe identyfikatory nie są trudne do wygenerowania w bezpieczny sposób. Jednym rozwiązaniem jest użycie tak zwanego prywatnego rekordu w następujący sposób. Uniemożliwia użytkownikom modułu z kopiowania pola ID:

 
module type Intf = 
sig 
    type t = private { 
    id : int; 
    foo : string; 
    } 

    val create_t : foo: string -> t 
end 

module Impl : Intf = 
struct 
    type t = { 
    id : int; 
    foo : string; 
    } 

    let create_id = 
    let n = ref 0 in 
    fun() -> 
     if !n = -1 then 
     failwith "Out of unique IDs" 
     else (
     incr n; 
     !n 
    ) 

    let create_t ~foo = { 
    id = create_id(); 
    foo 
    } 
end 

Answer 4

przepraszam za brzydkie siekać, ale zrobiłem coś takiego jakiś czas temu.

Sztuczka polega na tym, aby upewnić się, że wartości nie zostaną przeniesione do pamięci po wstawieniu do tabeli.Istnieją dwie sytuacje, w których można przenosić wartości w pamięci: kopiowanie od mniejszego do większego sterty i zagęszczanie sterty. Oznacza to, że po wstawieniu wartości do tabeli musi ona znajdować się w sterty głównej i pomiędzy dwiema operacjami na stole, aby upewnić się, że nie doszło do zagęszczenia.

Sprawdzanie, czy wartość jest w małej stercie, można wykonać za pomocą funkcji C is_young, jeśli tak jest, można wymusić migrację wartości do głównej sterty za pomocą Gc.minor().

W przypadku drugiego problemu można całkowicie dezaktywować kompakty lub odbudować tabelę na komponentach. Wyłączanie można to zrobić za pomocą

Gc.set { Gc.get() with Gc.max_overhead = max_int } 

Wykrywanie że zagęszczanie się można dokonać porównując na każdym Dostęp do tabeli liczbę zwracanych przez

(Gc.quick_stat()).Gc.compactions 

Zauważ, że musisz być wyłączyć zagęszczanie przed dostępem stół. Jeśli wyłączysz zagęszczanie, powinieneś także rozważyć zmianę zasad alokacji, aby uniknąć nieskończonej fragmentacji sterty.

Gc.set {(Gc.get()) with Gc.allocation_policy = 1} 

Jeśli chcesz coś naprawdę brzydkiego w starych wersjach SML (przed 4.00) zagęszczania przechowywane wartości w tej samej kolejności w pamięci, więc można wdrożyć lub zestaw map na podstawie adresu fizycznego bez obaw.