Odnajdywaniie najdłuższych stringów z strumienia Stringów

Odnajdywaniie najdłuższych stringów z strumienia Stringów
S9
  • Rejestracja:ponad 10 lat
  • Ostatnio:7 miesięcy
  • Lokalizacja:Warszawa
  • Postów:3573
0

Witam mam takie zadanko:

Mając skończony strumień ciągów znaków, odnajdź wszystkie ciągi znaków o największej długości

Zaimplementowałem to tak:

Kopiuj
   Map<Integer, Set<String>> lengthStringsMap = strings.collect(groupingBy(String::length, mapping(Function.identity(), toSet())));
    return lengthStringsMap.entrySet().stream().
        max(Comparator.comparingInt(Map.Entry::getKey)).
        orElseGet(() -> new SimpleEntry<>(0,Collections.singleton(""))).
        getValue();
  }

Chciałbym się spytać czy istnieje jakiś sposób lepszy?

Wzywam na pomoc @Koziołek @Shalom @jarekr000000 :)

PS. Tak wiem jak mapa jest pusta powinienem zwrócić pustego Seta, ale skupiłem się na czymś innym


"w haśle <młody dynamiczny zespół> nie chodzi o to ile masz lat tylko jak często zmienia się skład"
edytowany 1x, ostatnio: scibi92
Shalom
  • Rejestracja:ponad 21 lat
  • Ostatnio:około 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
0

A masz tu jakieś dodatkowe ograniczenia? Bo teraz zrobiłeś to w złożoności pamięciowej O(n) podczas gdy można by pesymistycznie w O(n/k) gdzie k to liczba unikalnych długości ciągów na wejściu. No i zrobiłeś na końcu z tego set, a treść mówi że masz znaleźć wszystkie podciągi a nie wszystkie unikalne podciągi.


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
edytowany 1x, ostatnio: Shalom
Koziołek
Moderator
  • Rejestracja:około 18 lat
  • Ostatnio:7 dni
  • Lokalizacja:Stacktrace
  • Postów:6822
0

Trochę przekombinowane, bo niepotrzebnie podzieliłeś to na kilka kawałków:

Kopiuj
public class LongestStrings {

	public static void main(String[] args) {
		Set<String> strings = Arrays.stream("Ala ma kota a kot ma hive".split(" "))
				.collect(Collectors.groupingBy(
						String::length, HashMap::new, toSet()
				)).entrySet().stream().max(Comparator.comparingInt(Map.Entry::getKey))
				.map(Map.Entry::getValue)
				.orElse(Collections.singleton(""));
		System.out.println(strings);

	}
}

Sięgam tam, gdzie wzrok nie sięga… a tam NullPointerException
Shalom
  • Rejestracja:ponad 21 lat
  • Ostatnio:około 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
5

@Koziołek: taka sama uwaga jak wyżej -> kod niby zwięzły, ale wywali się dla długiego strumienia, nawet jeśli realistycznie nie ma w nim żadnego bardzo długiego podciągu stringów tej samej długości, bo najpierw zbierasz wszystko w pamięci a dopiero potem coś z tym robisz. Dodatkowo przelatujesz drugi strumień kolejny raz, więc pesymistycznie nie tylko O(n) pamięci ale jeszcze 2*O(n) czasowo (edit: w średnim przypadku mamy O(n)+O(k) bo maxa szukamy w zgrupowanych)
Nie aż takie krótkie, ale w sumie równie trywialne rozwiązanie, z lepszą złożonoscią:

Kopiuj
import java.util.*;
import java.util.function.BiConsumer;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collector;
import java.util.stream.Stream;

class StoreOnlyLongestStringList {
    private final List<String> longestStrings = new ArrayList<>();
    private int currentLen = 0;

    public void addNewEntry(String newEntry) {
        int len = newEntry.length();
        if (len == currentLen) {
            longestStrings.add(newEntry);
        } else if (len > currentLen) {
            currentLen = len;
            longestStrings.clear();
            longestStrings.add(newEntry);
        }
    }

    public StoreOnlyLongestStringList combine(StoreOnlyLongestStringList otherList) {
        otherList.retrieveResult().forEach(this::addNewEntry);
        return this;
    }

    public List<String> retrieveResult() {
        return longestStrings;
    }
}

class RetainLongestStringListCollector implements Collector<String, StoreOnlyLongestStringList, List<String>> {

    @Override
    public Supplier<StoreOnlyLongestStringList> supplier() {
        return StoreOnlyLongestStringList::new;
    }

    @Override
    public BiConsumer<StoreOnlyLongestStringList, String> accumulator() {
        return StoreOnlyLongestStringList::addNewEntry;
    }

    @Override
    public BinaryOperator<StoreOnlyLongestStringList> combiner() {
        return StoreOnlyLongestStringList::combine;
    }

    @Override
    public Function<StoreOnlyLongestStringList, List<String>> finisher() {
        return StoreOnlyLongestStringList::retrieveResult;
    }

    @Override
    public Set<Characteristics> characteristics() {
        return Collections.emptySet();
    }
}

public class LongestStringsFinder {

    private List<String> findLongest(Stream<String> input) {
        return input.collect(new RetainLongestStringListCollector());
    }

    public static void main(String[] args) {
        LongestStringsFinder longestStringsFinder = new LongestStringsFinder();
        List<String> input = Arrays.asList("ala", "ma", "kot", "ala");
        System.out.println(longestStringsFinder.findLongest(input.stream()));
    }
}

Troche rozwlekłe, ale mamy wynik za 1 przejsciem strumienia O(n), dodatkowo pamięciowo mamy O(n/k).


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
edytowany 2x, ostatnio: Shalom
jarekr000000
  • Rejestracja:ponad 8 lat
  • Ostatnio:19 minut
  • Lokalizacja:U krasnoludów - pod górą
  • Postów:4709
1

Dla mnie naturalne jest reduce (w sumie jeden pies z collectorem). Prawda jest taka, że wszędzie foldl dobrze wygląda tylko nie w Javie (w VAVR/JavaSlang jest już lepiej).
Więc mutacja tego co wyżej na reduce:

Kopiuj
public class LongestStringFinder {

    private List<String> findLongest(Stream<String> input) {
        return input.reduce(Longest.empty(), Longest::bigger, Longest::bigger).strings;
    }

    public static void main(String[] args) {
        LongestStringFinder longestStringsFinder = new LongestStringFinder();
        List<String> input = Arrays.asList("ala", "ma", "kot", "ala");
           System.out.println(longestStringsFinder.findLongest(input.stream()));
    }

    static class Longest {
        public final List<String> strings;
        public final int length;

        static Longest empty() {
            return new Longest(Collections.emptyList(), 0);
        }

        public Longest bigger(final String otherString) {
            if ( length < otherString.length()) {
                return new Longest(Arrays.asList(otherString), otherString.length());
            } else if ( length == otherString.length()) {
                final List<String> newList = new ArrayList<>(this.strings);
                newList.add(otherString);
                return new Longest(newList, this.length);
            } else {
                return this;
            }
        }

        public Longest bigger(final Longest other) {
            if ( length< other.length) {
                return other;
            }  else  if ( length > other.length) {
                return this;
            } else {
                final List<String> newList = new ArrayList<>(this.strings);
                newList.addAll(other.strings);
                return new Longest(newList, this.length);
            }
        }

        private Longest(List<String> strings, int length) {
            this.strings = strings;
            this.length = length;
        }
    }
}

jeden i pół terabajta powinno wystarczyć każdemu
Zobacz pozostałe 4 komentarze
jarekr000000
No to zobacz niżej na wersje javaslang/vavr
jarekczek
Dalej kwadrat. Wg tej tabelki List.append ma complexity linear.
jarekr000000
Jak pisałem koment to zmieniłem na prepend.
jarekczek
Dobre. I dobry argument za vavrem. Dzięki.
jarekr000000
Generalnie z java.util. też się pewnie da coś zrobić... ale życie est za krótkie żeby sobie je marnować na mutowalne kolekcje z java.util. Czasem trzeba - bo jednak są skubańce wydajne ( w połączeniu z imperatywnym kodem :-) ), ale jak nie trzeba to się nie warto w to pchać.
danek
  • Rejestracja:ponad 10 lat
  • Ostatnio:8 miesięcy
  • Lokalizacja:Poznań
  • Postów:797
2

A takie coś, tylko bez javy 8? Idea ta sama chyba

Kopiuj
public class Main {

	public static void main(String[] args) {
		List<String> result = new ArrayList<String>();
		int max = 0;
		String[] split = "Ala ma kota a kot ma hive".split(" ");
		for (String string : split) {
			int length = string.length();
			if(length>max) {
				result = new ArrayList<String>();
				result.add(string);
				max = length;
			}else if(length == max) {
				result.add(string);
			}
		}
        System.out.println(result);
	}

}

Spring? Ja tam wole mieć kontrole nad kodem ᕙ(ꔢ)ᕗ
Haste - mała biblioteka do testów z czasem.
jarekr000000
Imperatywne... ale czytelne i krótkie. (To straszne).
Julian_
tak samo bym zrobił.
jarekr000000
  • Rejestracja:ponad 8 lat
  • Ostatnio:19 minut
  • Lokalizacja:U krasnoludów - pod górą
  • Postów:4709
0

A w Vavr/javaslang - klasyczny fold

Kopiuj
import javaslang.collection.List;

import java.util.Arrays;

public class LongestStringFinderVavr {

    private List<String> findLongest(java.util.stream.Stream<String> input) {
        return javaslang.collection.Stream.ofAll(input)
                .foldLeft(Longest.empty(), Longest::bigger).strings;
    }

    public static void main(String[] args) {
        LongestStringFinderVavr longestStringsFinder = new LongestStringFinderVavr();
        java.util.stream.Stream<String> input = Arrays.asList("ala", "ma", "kot", "ali", "ma").stream();
        System.out.println(longestStringsFinder.findLongest(input));
    }

    static class Longest {
        public final List<String> strings;
        public final int length;

        static Longest empty() {
            return new Longest(List.empty(), 0);
        }

        Longest bigger(final String otherString) {
            if (length < otherString.length()) {
                return new Longest(List.of(otherString), otherString.length());
            } else if (length == otherString.length()) {
                return new Longest(strings.prepend(otherString), this.length);
            } else {
                return this;
            }
        }

        private Longest(List<String> strings, int length) {
            this.strings = strings;
            this.length = length;
        }
    }
}

Trochę mniej rypania.


jeden i pół terabajta powinno wystarczyć każdemu
edytowany 1x, ostatnio: jarekr000000
katelx
teraz na haskella albo clojure i ze 2 linijki beda ;)
S9
  • Rejestracja:ponad 10 lat
  • Ostatnio:7 miesięcy
  • Lokalizacja:Warszawa
  • Postów:3573
0

@Shalom: wiem że algorytmicznie to nie jest najbardziej optymalne, ale założyłem że to jest ćwiczenie ze streamów i chciałem je wykonać po prostu dobrze z ich użyciem, w miarę poprawny sposób nie męcząc się z własnymi collectorami itp
Chociaż Twoje rozwiązanie na pewno jest ciekawe ;]


"w haśle <młody dynamiczny zespół> nie chodzi o to ile masz lat tylko jak często zmienia się skład"
Shalom
  • Rejestracja:ponad 21 lat
  • Ostatnio:około 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
0

@danek zadziała ale ktoś chciał uzyc strumieni ;) Poza tym rozwiazanie ze streamami, szczególnie to od @jarekr000000 bo wygląda na thread-safe (to moje miało mutowalny stan akumulatora!), można machnąć sobie na paralellStream i nagle liczy się współbieżnie, a przerobienie twojej naiwnej pętli na wersje wielowątkową to byłby trochę ból.


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
danek
racja, mój błąd ;)
0

A co jest nie tak z takim rozwiązaniem?

Kopiuj
val list = List("ala", "ma", "kot", "ala")
val max = list.map(_.length).max
list.filter(_.length == max)
Shalom
  • Rejestracja:ponad 21 lat
  • Ostatnio:około 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
0

@Wybitny Szczur cała masa rzeczy. Po pierwsze nie wiesz jak duży jest strumień, a ty sobie go tu wesoło w całości konsumujesz od razu / zamieniasz na listę, więc od razu masz O(n) pamięci, co moze być bardzo dużą liczbą. Szczęśliwie dla ciebie java/scala trzyma długość stringa zapisaną, a nie liczy jej przy wywołaniu bo byłaby masakra. Niemniej nadal przelatujesz strumień dwa razy więc znów 2*O(n).
Twoje rozwiazanie niewiele różni się od tych proponowanych na samym początku i ma dokładnie te same problemy -> Zamiast jednego przejścia przez strumień i O(n/k) pamięci masz dwa przejścia przez strumień i O(n) pamięci. W zasadzie twoje rozwiazanie jest o tyle gorsze ze OP przynajmniej od razu pakował dane do mapy, więc potem wybierał max ze zgrupowanych elementów i w średnim przypadku miałby tam O(k) na szukanie maxa, a u ciebie jest O(n) bo lecisz przez całą listę.


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
edytowany 4x, ostatnio: Shalom
jarekczek
  • Rejestracja:prawie 8 lat
  • Ostatnio:ponad 4 lata
  • Lokalizacja:Siemianowice Śląskie
  • Postów:500
0

Przelatywanie strumienia 2 razy to nie jest żaden problem. Zasada 90/10. Tylko 10% napisanego kodu zajmuje 90% czasu wykonywania. Chodzi o sekcję krytyczną. W żadnym programie to miejsce nie będzie sekcją krytyczną, a przebieg strumienia to "błysk ciupagi". Praktycznie niewykrywalne.

Tak więc jeżeli kod przebiegający 2 razy będzie krótszy i czytelniejszy, to trzeba go zastosować. Więc jestem za czymś takim jak Szczur Anonim napisał.

Złożoność obliczeniowa to O(n), niezależnie od tego czy przebiegasz strumień 1 czy 3 razy. Stałą się z reguły pomija. I to się pokrywa z powyższym wywodem.

Z uwagami co do wrzucania strumienia do pamięci się zgadzam - nie ma takiej potrzeby, więc nie należy tego robić. To by już było mierzalne czasowo, a nawet mogłoby dać OOM.

Przyszedł mi do głowy jeszcze 1 argument za dwuprzebiegowością. Dane wejściowe:

aa aa aa aa .... aa aaa

Lista powinna mieć tylko 1 element, a robiąc 1-przebiegowo utworzymy listę o długości n-1, którą pod koniec wrzucimy do śmieciarki pamięciowej.


Przeważnie ignoruję niezarejestrowanych użytkowników.
edytowany 1x, ostatnio: Shalom
Shalom
  • Rejestracja:ponad 21 lat
  • Ostatnio:około 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
2

@jarekczek Po pierwsze wbrew pozorom takie przelecenie danych może być operacją niezwykle kosztowną, ale oczywiście to kwestia sytuacji. Jeśli chcesz przelecieć wszystkie zamówienia w historii amazona to przelecenie ich drugi raz może oznaczać wiele dodatkowych godzin ;) Stałe pomija sie przy analizie asymptotycznej a nie empirycznej, bo O(1000n) = O(n) ale jednak jak jedno wykonanie zabiera godzine to robi ci różnicę 1 a 1000 godzin.
Po drugie przecież ten kod na początku MUSI wszystko wrzucic do pamieci, bo tak działa collector który to składa do mapy. To ze dane będą wrzucone w postaci mapy to akurat bez znczenia, więc szansa na OOM wzrasta.
Po trzecie nie rozumiem argumentu z tym pesymistycznym przypadkiem, bo i tak zajmie mniej pamięci niż ten naiwny algorytm który wpakuje do pamieci wszystko.


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
jarekczek
Nie pomyślałem o tym, że odczyt streama może być taki kosztowny. To mnie przekonuje. Pesymistyczny przypadek pokazuje, że robi się wiele niepotrzebnych operacji, które mogą trochę trwać (niepotrzebna konstrukcja długiej listy).
jarekr000000
  • Rejestracja:ponad 8 lat
  • Ostatnio:19 minut
  • Lokalizacja:U krasnoludów - pod górą
  • Postów:4709
0

@jarekczek ma dużo racji. Warto sprawdzić na jakiej ilości danych pracujemy i do tego dopasowac rozwiązanie. W kodzie enterprise większość list, map ma max kilkaset elementów (a zwykle 10-20) - wtedy naprawdę nie ma co się bawić w optymalizowanie. Szkoda kodu zaśmiecać. A już widziałem potworki w stylu wymuszanie binary search (czyli wcześniejsze sortowanie) na tablicy co miała zwykle do 8 elementów.


jeden i pół terabajta powinno wystarczyć każdemu
Shalom
Jasne, trzeba metodę dostosować do problemu, ale użycie nieoptymalnej metody może mocno zamulić. Pisałem kiedyś ciekawostkę z życia wziętą -> Programistyczne WTF jakie Was spotkały ;)
jarekr000000
No tak. Nawet w nudnych systemach znajdują się takie miejsca, jedno, dwa - problem, że zwykle nie da się tego przewidzieć na etapie pisania kodu. Lepiej mieć prosty naiwny kod i znaleźć profilerem po czasie gdzie muli i naprawić, niż ślęczeć nad spaghetti operującym na tablicach, które też jest O(n^xk) tylko nie widać gdzie. Kiedyś w jednej firmie działało ładne przekleństwo - jak system mulił to trzeba było znaleźć komentarz w stylu "troche syfny kod i robi to samo co standardowa metoda w jdk, ale za to wydajniej napisane :-)". zwykle to był niezły kwiatek.
0

ja ze stringami to sie bawilem tak

Kopiuj
char kraj[20];

cin >> kraj;

for (i=0;i<20;i++) 
{
if (kraj[i]=='a') licz++
}

program sprawdza ile jest literek a w nazwie kraju

S9
  • Rejestracja:ponad 10 lat
  • Ostatnio:7 miesięcy
  • Lokalizacja:Warszawa
  • Postów:3573
0

Choć rzadko mi się to zdarza ale tutaj muszę przyznac dużo racji @jarekr000000 :) Nie zawsze warto nadmniernie optymalizowac, jednak najważniejsza jest czytelność w przypadku mniejszej ilości danych. Oczywicie kiedy jest bardziej złożony przypadek warto zmienić podejście, ale w przypadku streama z 200 słowami nie aż tak :)


"w haśle <młody dynamiczny zespół> nie chodzi o to ile masz lat tylko jak często zmienia się skład"
Shalom
Ale jak dostaniesz takie pytanie na rozmowie do amazona i im powiesz ze co za różnica czy będę przeglądał listę wszystkich zamówień raz czy dwa razy to obawiam sie że mogą nie podzielic twojego zdania :D
S9
No wiem, ale po prostu to było zadanie na ćwiczenie prostych streamów, wiadomo że w przypadku kodu produkcyjnego który przerabiałby np. 100 000 słów to nie jest najlepsze podejście. Zresztą nie od razu Rzym zbudowano ;]
vpiotr
  • Rejestracja:prawie 14 lat
  • Ostatnio:prawie 3 lata
1

Póki jeszcze nie wszyscy pracujemy w Javie 8/9, rozwiązanie imperatywne poniżej.

  • jedno-przebiegowe
  • jedno-wątkowe
  • zapotrzebowanie na pamięć równe sumie długości najdłuższych słów
  • nie używa RegExp (String.split)
Kopiuj
import java.util.*;
import java.lang.*;
import java.io.*;

/* Find longest word in string */
class Ideone {

	private static List<String> findLongestWords(String txt) {
		int idx = 0;
		List<String> words = new ArrayList<>();
		int longest = 0;

		while (idx < txt.length()) {
			int start = idx;
			while (start < txt.length() && txt.charAt(start) == ' ') {
				start++;
			}
			
			idx = start;
			while (idx < txt.length() && txt.charAt(idx) != ' ') {
				idx++;
			}
			
			int len = idx - start;
			String word = txt.substring(start, idx);
			
			if (len > longest) {
				longest = len;
				words = new ArrayList<>();
				words.add(word);
			} else if ((len == longest) && (len > 0)) {
				words.add(word);
			}
		}
		return words;
	}

	public static void main(String[] args) throws java.lang.Exception {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextLine()) {
			String line = sc.nextLine();
			List<String> words = findLongestWords(line);
			System.out.printf("Longest: /%s/%n", words);
		}
	}
}

https://ideone.com/DZjmUk

Julian_
  • Rejestracja:około 8 lat
  • Ostatnio:ponad 4 lata
  • Postów:1703
0

Najlepszy sposób:

Kopiuj
public class Main {
    public static void main(String[] args) {
        RCaller caller=new RCaller();
        try{
        	x <- c("Trololo", "JuliaOK", "Rnajlepszy")

        	findLongestString <- function(x){
        	    counted <- sapply(x, nchar)
                x[counted == max(counted)]
        	}

        	findLongestString(x)
        }
    }
}
edytowany 2x, ostatnio: Julian_
Zobacz pozostałe 11 komentarzy
vpiotr
@Julian_: mam na myśli treść zadania.
Julian_
to nie zawracaj gitary.
PI
wyjaśniony XDDD
vpiotr
@scibi92: to chyba jakaś forma pośrednia między fanboyem a hejterem.
S9
If I only was moderator ;)
jarekczek
  • Rejestracja:prawie 8 lat
  • Ostatnio:ponad 4 lata
  • Lokalizacja:Siemianowice Śląskie
  • Postów:500
0

Puściłem komentarz do rozwiązania JarkaR. Zastanawiam się nad tym akumulatorem. Dlaczego nie może być mutowalny? Nie ma chyba takiego ograniczenia. @Shalom, dlaczego wolisz niemutowalny? To zabija efektywność.


Przeważnie ignoruję niezarejestrowanych użytkowników.
Zobacz pozostałe 2 komentarze
jarekczek
Introduction to writing custom collectors in Java 8: Generic type A simply defines the type of intermediate mutable data structure that we are going to use to accumulate items of type T in the meantime.
jarekczek
Autor tego bloga to Tomasz Nurkiewicz, Senior Software Engineer at Allegro. Budzi zaufanie :)
Koziołek
ConcurentHashMap wykorzystuje pod spodem magiczne słówko synchronize, czyli będzie powoli. Jeżeli napiszesz akumulator niemutowalny, to problem znika, a że pamięć jest tania, to nadprodukcja obiektów nie jest aż tak bolesna. A Tomka znam i nie jeden raz mieliśmy okazję sobie dyskutować o tym czy o tamtym, przy kawie, herbacie i piwerku.
Shalom
@jarekczek: nie no jasne, możesz mieć mutowalny akumulator, jak pokazałem wyżej, ale istnieje ryzyko że sie to rypnie jak puścisz paralellStream, podczas gdy niemutowalny zrobi sieczke na stercie i da więcej pracy dla GC, ale masz pewność że rozproszysz sobie na 16 czy 32 rdzenie i nadal da dobry wynik.

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.