Czy istnieje wersja NavalableMap w Scali?

W języku Java 1.6 wprowadzono interfejsy NavigableMap (i NavigableSet) i zaktualizowano TreeMap w celu implementacji nowego interfejsu. Między innymi, NavigableMap jest przydatna do zadawania pytań typu "Który element w kolekcji jest najbliższy X?" (Patrz this excellent blog post by François Sarradin na przykład i dyskusję) .Czy istnieje wersja NavalableMap w Scali?

Miałem nadzieję znaleźć coś podobnego w implementacji TreeMap Scala 2.8 , ale niestety, wydaje się, że tak nie jest (przynajmniej nie jest to oczywiste) Czy istnieje inna klasa lub cecha Scala, która jest podobna do Java NavigableMap? Jeśli nie, czy są jakieś proste idiomy Scala, które mogą być użyte aby osiągnąć coś podobnego?

Zdaję sobie sprawę, mogę używać TreeMap Javy, ale chciałbym pozostać w ramach kolekcji Scala (jeśli tylko dla uproszczenia).

Źródło

2011-08-29 Jim Hurne

W przypadku niezmiennych kolekcji posiadanie wstecznej kolekcji uniemożliwia utrwalenie kolekcji. Zamiast tego ludzie używają zippers do nawigacji po takich strukturach. ma ładny przykład użycia suwaków podczas pracy z XML.

Źródło

2011-08-29 19:37:29

Jest całkiem jasne, w jaki sposób zamek może pomóc w modyfikowaniu (kopiowaniu) drzewa, ale nie jest jasne, w jaki sposób suwak byłby używany do odpowiadania na pytania typu "Który element w kolekcji jest najbliższy X?". Wiem, że mówimy tu głównie o teorii (ponieważ zamki wydają się być w większości eksperymentalne), ale czy możesz opisać, w jaki sposób zamek błyskawiczny może odpowiedzieć na wcześniej wspomniane pytanie? –

@Jim Zippers w ogóle nie są eksperymentalne. Zamki mają dwa rodzaje operacji: inspekcja/aktualizacja i nawigacja. Tak więc, jeśli masz zamek błyskawiczny w X, jego operacje nawigacji naturalnie dadzą Ci najbliższe elementy. –

Ah Widzę teraz! Dzięki. Pytanie, które łączyłeś z zamkami błyskawicznymi, sprawiło na mnie wrażenie, że zamki błyskawiczne były eksperymentalne. Cieszę się, że są łatwo dostępne. –

Here's a thread on this topic

Wydaje SortedMapmoże móc Ci część drogi tam, ale co mam przetestowane do tej pory nie jestem pewien, czy to O (log (n)) sposób poszukiwania powinny być:

def searchMap(m: SortedMap[Int,_], k: Int) = { 
    val left = m to(k) lastKey 
    val right = m from(k) take(2) lastKey 

    if (k - left < right - k) 
     left 
    else 
     right 
}

podstawie definicji from i to pod względem rangeImpl wygląda to może być o (log (n)), ale w oparciu o faktycznie rozrządu go, wydaje się wzrastać liniowo dla wszystkich wiarygodny wartości n.

Więc nie jestem pewien.

Źródło

2011-08-29 01:37:26 Owen

Dlaczego nie, ale funkcje do i z powodu tworzenia dwóch nowych map, które mogą być niepożądane. –

Czy istnieje wersja NavalableMap w Scali?

Odpowiedz

Powiązane problemy