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

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:

   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

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.

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

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);

	}
}

@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ą:

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).

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:

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;
        }
    }
}

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

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);
	}

}

A w Vavr/javaslang - klasyczny fold

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.

@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 ;]

@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.

A co jest nie tak z takim rozwiązaniem?

val list = List("ala", "ma", "kot", "ala")
val max = list.map(_.length).max
list.filter(_.length == max)

@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ę.

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.

@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.

@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.

ja ze stringami to sie bawilem tak

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

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 :)

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)

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

Najlepszy sposób:

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)
        }
    }
}

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ść.