5
\$\begingroup\$

The three characters that occurs most in a given string should be printed by using streams/lambdas (functional programming). The order of characters that occur equally often should be preserved.

My thoughts were to use a LinkedHashMap for counting (accumulation), and then to use a ArrayList for sorting the results.

I would like to know, how can my code be improved - or if everything is OK. Thanks

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.Map;

public class CountChars {
    public static void printMostOccurring(final String s) {
        s.chars()
                .boxed()
                .reduce(new LinkedHashMap<Integer, Long>(), (a, b) -> {
                    a.put(b, a.getOrDefault(b, 0L) + 1L);
                    return a;
                }, (a, b) -> {
                    a.putAll(b);
                    return a;
                })
                .entrySet()
                .stream()
                .reduce(new ArrayList<Map.Entry<Integer, Long>>(), (a, b) -> {
                    a.add(b);
                    return a;
                }, (a, b) -> {
                    a.addAll(b);
                    return a;
                })
                .stream()
                .sorted((a, b) -> Long.compare(b.getValue(), a.getValue()))
                .limit(3)
                .forEach(me -> System.out.println((char) (int) me.getKey() + " " + me.getValue()));
        System.out.println();
    }

    public static void main(final String[] args) {
        // Examples:
        printMostOccurring("the quick brown fox jumped over the lazy dog");
        printMostOccurring("abracadabra");
        printMostOccurring("arbacadabra");
    }
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ IIRC, LinkedHashMap has an ordered stream (thus sorted() does a stable sort) and you can probably drop all the ArrayList stuff. \$\endgroup\$
    – Shawn
    Nov 5, 2023 at 10:29
  • 1
    \$\begingroup\$ Also might want to work with code points instead chars so it won't break on characters outside the BMP that don't fit in a single char. \$\endgroup\$
    – Shawn
    Nov 5, 2023 at 10:30
  • \$\begingroup\$ @Shawn Of course, .sorted((a, b) -> Long.compare(b.getValue(), a.getValue())) can be used with the result of .entrySet().stream() (type: Stream<Entry<Integer, Long>>), so ArrayList can be saved. I didn't have seen that. Thanks. \$\endgroup\$ Nov 5, 2023 at 11:10
  • 1
    \$\begingroup\$ Just for the sake of it needing to be said: the runtime performance, development cost and maintainability of the code could all be improved vastly by not using Streams. I hope that the purpose of this school assignment was to show how Streams are not always the best tool for the job. \$\endgroup\$ Nov 6, 2023 at 5:44
  • 1
    \$\begingroup\$ @TorbenPutkonen Yes, in terms of runtime, the costs are "horrible". But the "exercise" was to use strictly functional programming. Btw, this is not an "official" task, it's a task of mine. Might not be a real world scenario. \$\endgroup\$ Nov 6, 2023 at 7:46

2 Answers 2

2
\$\begingroup\$

Just a two small things:

(a, b) -> {
    a.put(b, a.getOrDefault(b, 0L) + 1L);
    return a;
}

This lambda should use better parameter names, for example map and char.

The put could be replaced by merge:

map.merge(char, 1L, Long::sum);
\$\endgroup\$
2
\$\begingroup\$

You should split this up into multiple functions for reuse and testability; especially, do not force a print - near the top level should be a format.

Do not use manual string concatenation + and don't manually cast to a char. Instead, use String.formatted and format the character code point using %c.

I find the double-reduce operation difficult to understand, and I also find difficult to understand the magic around your sorted only needing to care about the count and relying on an implicit ordering for the original characters. When you say

The order of characters that occur equally often should be preserved.

this is troubled, and I think you actually mean "after sorting in decreasing order of frequency, characters should be output in order of their first appearance in the original string".

I find it easier to understand when the actual groupingBy(classifier, downstream) is used, and I find it easier to understand when the comparator explicitly references the index.

Suggested

package com.stackexchange;

import java.util.Comparator;
import java.util.Optional;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main {
    public static class CountChars {
        private record IndexChar(int index, Integer character, long count) {
            IndexChar reduce(IndexChar other) {
                return new IndexChar(
                    Integer.min(index, other.index),
                    character,
                    count + other.count
                );
            }
        }
        
        public static Stream<IndexChar> streamMostOccurring(String s) {
            return IntStream
                .range(0, s.length())
                .mapToObj(i -> new IndexChar(i, (int)s.charAt(i), 1))
                .collect(
                    Collectors.groupingBy(
                        IndexChar::character,
                        Collectors.reducing(IndexChar::reduce)
                    )
                )
                .values()
                .stream()
                .filter(Optional::isPresent)
                .map(Optional::get)
                .sorted(
                    Comparator.comparing(IndexChar::count)
                        .reversed()
                        .thenComparing(IndexChar::index)
                );
        }

        public static String formatMostOccurring(String s, int limit) {
            return streamMostOccurring(s)
                .limit(limit)
                .map(
                    ix -> "%c %d%n".formatted(ix.character(), ix.count())
                )
                .collect(Collectors.joining());
        }

        public static void printMostOccurring(String s, int limit) {
            System.out.println(formatMostOccurring(s, limit));
        }

        public static void printMostOccurring(String s) {
            printMostOccurring(s, 3);
        }
    }

    public static void main(final String[] args) {
        // Examples:
        CountChars.printMostOccurring("the quick brown fox jumped over the lazy dog");
        CountChars.printMostOccurring("abracadabra");
        CountChars.printMostOccurring("arbacadabra");
        /*
          8
        e 4
        o 4

        a 5
        b 2
        r 2

        a 5
        r 2
        b 2 */
    }
}

Or, with pre-computed stream helper objects,

package com.stackexchange;

import java.util.Comparator;
import java.util.Map;
import java.util.Optional;
import java.util.stream.Collector;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main {
    public static class CountChars {
        private record IndexChar(int index, Integer character, long count) {
            IndexChar reduce(IndexChar other) {
                return new IndexChar(
                    Integer.min(index, other.index),
                    character,
                    count + other.count
                );
            }
        }

        private static final Collector<
            IndexChar, ?, Map<Integer, Optional<IndexChar>>
        > grouper = Collectors.groupingBy(
            IndexChar::character,
            Collectors.reducing(IndexChar::reduce)
        );

        private static final Comparator<IndexChar> comparator =
            Comparator.comparing(IndexChar::count)
            .reversed()
            .thenComparing(IndexChar::index);

        private static final Collector<CharSequence, ?, String>
            joiner = Collectors.joining();

        public static Stream<IndexChar> streamMostOccurring(String s) {
            return IntStream
                .range(0, s.length())
                .mapToObj(i -> new IndexChar(i, (int)s.charAt(i), 1))
                .collect(grouper)
                .values()
                .stream()
                .filter(Optional::isPresent)
                .map(Optional::get)
                .sorted(comparator);
        }

        public static String formatMostOccurring(String s, int limit) {
            return streamMostOccurring(s)
                .limit(limit)
                .map(
                    ix -> "%c %d%n".formatted(ix.character(), ix.count())
                )
                .collect(joiner);
        }

        public static void printMostOccurring(String s, int limit) {
            System.out.println(formatMostOccurring(s, limit));
        }

        public static void printMostOccurring(String s) {
            printMostOccurring(s, 3);
        }
    }

    public static void main(final String[] args) {
        // Examples:
        CountChars.printMostOccurring("the quick brown fox jumped over the lazy dog");
        CountChars.printMostOccurring("abracadabra");
        CountChars.printMostOccurring("arbacadabra");
        /*
          8
        e 4
        o 4

        a 5
        b 2
        r 2

        a 5
        r 2
        b 2 */
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ That's the case, yes. In the second case, the b must be output before the r, and vice versa in the third. \$\endgroup\$ Nov 6, 2023 at 0:30
  • \$\begingroup\$ First, thank you. Now you have introduced an additional (not internal) data structure (record), and I find the .collect(Collectors.groupingBy(IndexChar::character, Collectors.reducing(IndexChar::reduce))) part difficult to read and understand. Also, I'm not quite sure if the runtime costs have changed, e.g. if they are now lower or higher. \$\endgroup\$ Nov 6, 2023 at 18:41
  • 1
    \$\begingroup\$ The record is a feature, not a bug - explicitly named members are a good thing. As for performance, if you actually cared about performance you shouldn't be using streams at all. \$\endgroup\$
    – Reinderien
    Nov 6, 2023 at 19:59
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ Nov 6, 2023 at 21:21
  • 3
    \$\begingroup\$ .filter(Optional::isPresent).map(Optional::get) can be shortened to .flatMap(Optional::stream) since Java 9. \$\endgroup\$
    – sp00m
    Nov 7, 2023 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.