Usuwanie zbędnych wpisów, sposób scala

Edycja: Dodano fakt, że lista jest posortowana, a wykonanie "duplikatu" wprowadza w błąd, zastąpiło to "nadmiarowym" w tytule.Usuwanie zbędnych wpisów, sposób scala

Mam posortowaną listę wpisów określającą wartość produkcji w danym przedziale. Wpisy zawierające taką samą wartość w późniejszym czasie nie zawierają żadnych informacji i można je bezpiecznie pominąć.

case class Entry(minute:Int, production:Double) 
val entries = List(Entry(0, 100.0), Entry(5, 100.0), Entry(10, 100.0), Entry(20, 120.0), Entry(30, 100.0), Entry(180, 0.0))

Eksperymentowanie z funkcjami scala 2,8 zbiórki, do tej pory mam to realizację pracy:

entries.foldRight(List[Entry]()) { 
    (entry, list) => list match { 
    case head :: tail if (entry.production == head.production) => entry :: tail 
    case head :: tail => entry :: list 
    case List() => entry :: List() 
    } 
} 
res0: List[Entry] = List(Entry(0,100.0), Entry(20,120.0), Entry(30,100.0), Entry(180,0.0))

jakieś uwagi? Czy brakuje mi jakiejś magii scala?

Źródło

2010-04-03 andersbohn

Pamiętaj, że 'foldRight' jest nieoptymalne w przypadku' List'. Preferuj 'foldLeft' z tym.Jest to przeciwieństwo 'Haskell', gdzie' Right' jest preferowany zamiast 'Left' ze względu na nie-stricte. –

ok, ale potem muszę odwrócić wynik. Uruchomienie szybkiego testu stawia foldRight nieco przed foldLeft + reverse, więc powiedziałbym, że foldRight jest bardziej przejrzysty. – andersbohn

Porównując kolejne wpisy na liście, zacznij od zip - na liście z ogonem, aby uzyskać listę par kolejnych elementów.

Poniżej, biorę pierwszy wpis z listy i używam collect do jednoczesnego odfiltrowywania par, w których produkcja jest niezmieniona, a dla pozostałych par, mapy e2. (collect nowego w Scala 2,8 i przez czas nazwano partialMap)

scala> entries.head :: ((entries zip entries.tail).collect { 
      case (Entry(_, p1), [email protected](_, p2)) if p1 != p2 => e2 
     }) 
res13: List[Entry] = List(Entry(0,100.0), Entry(20,120.0), Entry(30,100.0), Entry(180,0.0))

UPDATE Dla uproszczenia, zakłada się, że wpisy nie jest pusty.

Źródło

2010-04-03 13:18:31 retronym

bardzo ładny ogólny pomysł, skompresowanie ogonem. Jest nieco wolniejszy niż złożony. x2 na moim setupie (2.8.0.Beta1-RC3, gdzie zbieranie jest nadal "partialMap", dunno jeśli to wpływa na wydajność) – andersbohn

@andersbohn Możesz użyć 'entries.view zip entries.tail', aby uzyskać lepszą wydajność z niego ('.toList' na końcu), ale moje testy umieściły twoją wersję na 30,' view''s na 63 i retronym na 81. –

Zamiast szukać duplikatów dla każdej pozycji, która jest O (n^2), lub skompresowanie, które jest n^2 w pamięci, użyj mapy [Double, Int]. Następnie dodaj elementy z "produkcją" jako kluczem i "minutą" jako wartością. Mapa zapewni unikalne wartości dla "produkcji". Możesz być w stanie załadować mapę naturalnie gdzie indziej w swoim kodzie, ale nawet jeśli musisz zacząć od listy jak powyżej, ładowanie mapy jest liniowe na liście i tylko O (n log (n)) na mapie.

Mapa zostanie zastąpiona po dodaniu "mymap + = produkcja -> minuta", aby zachować pierwszą wartość, odwrócić listę przed wstawieniem lub użyciem osłony "zawiera (klucz)". Sprawdzanie będzie O (log (n)), więc ogólnie algorytm będzie O (n log (n)).

BTW, możesz użyć mapy [Double, Entry], aby odwzorować wartości produkcji bezpośrednio na struktury Entry. W razie potrzeby możesz łatwo uzyskać listę, pobierając wartości mapy bezpośrednio z mapy i sortując dowolny element wpisu (w razie potrzeby).

Źródło

2010-04-03 13:56:53 DrGary

Myślę, że źle czytasz. Andersbohn musi przejść tylko raz przez listę; jest już posortowany, a jeśli produkcja pojawi się, zmieni się, a następnie się zmieni, to potrzebujesz nowej produkcji. (Chodzi o to, by wyrzucić wszystko, co już robisz, jako zbędne.) Zarówno kod retronymu, jak i andersbohn to "O (n)"; przechodzą jeden raz przez dane. –

Być może; Nie sądzę, aby oryginalne pytanie było tak konkretne. Mam nadzieję, że moja odpowiedź będzie pomocna dla osób z podobnymi pytaniami. Również przeszukiwanie całej listy za każdym razem powoduje, że algorytm O (n^2) jest liczbą pozycji. Można to poprawić za pomocą struktury hashtable lub drzewa. – DrGary

Jeśli powiedziałeś coś o aktualizacjach O (log n), może się zgodzę. W przeciwnym razie, dlaczego warto korzystać z mapy, kiedy można sortować w O (n log n), a następnie usuwać duplikaty w O (n)? –

Jest nowa metoda zipped z Tuple2, która jest bardziej wydajna (i leniwsza) niż zip na listach dla niektórych operacji. Można to wypróbować na benchmarku - Nie wiem, czy to rzeczywiście szybciej, ale na pewno mógłby być (i jest to z pewnością dużo krótsza):

entries.take(1) ::: 
(entries,entries.drop(1)).zipped.filter(_.production != _.production)._2

Zamiast skompresowanie listę parami wszystko w drodze tworzy widok listy, na której można manipulować elementami, a następnie zwraca zmanipulowane listy. Zwróć uwagę na użycie funkcji "wpadnij i upuść", aby obsłużyć pustą obudowę.

To nie jest super-wydajne, ponieważ buduje dwie listy, gdy naprawdę jest potrzebna, ale jest to klasa rozwiązań, która jeszcze się nie pojawiła.

Źródło

2010-04-05 03:17:03

Usuwanie zbędnych wpisów, sposób scala

Odpowiedz

Powiązane problemy