We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
IntStream.range(0, in.nextInt()) - constructs a stream of ints [0..N). Think of it like (for i = 0; i < N; i++)
.mapToObj(i -> in.next()) - for each i from stream we read a word
.collect(Collectors.toList()); - gather to list
So at this points we just read out N words to List<String> strings
IntStream.range(0, in.nextInt()).mapToObj(i -> in.next()) -- same as previous: read count, and read M words
.mapToLong(q -> strings.stream().filter(q::equals).count()) - for each of M word: iterate over N words, filter those who are equal to current word, and count elements.
.forEach(System.out::println) - output that count.
That is called 'functional style'. If you really want to learn this approach - i'd suggest learning haskell. It's the most pure functional language.
Funny, because it's copypasted from AC solution without imports and class boilerplate.
If you need - I can provide you with full copypaste so you can "just copypaste" and execute.
Thank you for your helpful comment.
I can't find the imports.
Actually the problem is with the parsing of the input as mentioned previously. Even a simple loop had trouble.
It seems "hit and miss" with this website.
Speaking of learning concepts, if I wanted to use Maps without Stream, what are the steps I would use for that? Specifically, from the half-dozen websites I researched, but it seems like I will have to manually place strings into the maps; is this correct?
Will operation time be O(n + q + hash_constant), then?
This is one of my first posts; sorry if this is a stupid question/formatted badly.
Besides a shorter solution, what are the advantages of a functional approach compared to say a HashMap? Does the functional approach take more memory and/or run time?
What are you looking for, is classical "Functional-vs-Imperative" holywar :). There are tons on that in the internet.
It's "managing calculations"-vs-"managing state". In functional style you feel yourself like a mathematician constructing complete function. In imperative you feel yourself like a programmer thinking "how state will change" if I write this.
Classical "what it is"-vs-"how to do it".
HashMap solution could be written in functional style too.
My personal thoughts on that - functional features are good, give better readability. I'd suggest using them in things like list comprehensions, e.g. you want to filter, count, aggregate something for elements. But personally I prefer mostly imperative code, because it's self-contained and self-explaning. E.g. you know what's going on for sure, though you have to write more code.
Also, functional-styled code is more bugless in terms of multithreading and multicore/multinode processing - e.g. filters, aggregators/reducers is good paralellable architecture. That's why it's often used in things like map-reduce, data processing and so on.
In terms of memory/runtime - depends on environment and implementation of functional language. In most cases they are constantly equal. But there are some cases when functional code under-the-hood generates a lots of object which "annoy" garbage collection. And also, there are some problems which require managing state directly. E.g. immutability would be an overdose.
Let's say you can always do better in imperative. But in most cases you gain more because of shortness and cleaniness of functional. However, you still need to be sure what it's doing under-the-hood and use it carefully.
what exactly do you mean by functional approach? I mean if you mean just breaking code into different methods such that one method does one job then we can use Hashmap in that way also. But other than that are there any serious issues in using a Hashmap instead of char array as discussed in the editorial?
"Functional programming" doesn't mean breaking code into smaller methods. Functional programming is a pretty different way to think about software (compared to writing a list of instructions to be followed).
I don't have much experience with functional programming myself, but I did enjoy reading a cute little book called The Little Schemer: https://mitpress.mit.edu/books/little-schemer . I haven't had a chance to read the rest of the series.
I think he was just trying to get a 2 line solution. The code is terribly inefficient when compared with a HashMap solution, much harder to understand, and (if implemented in any real system) nearly impossible to maintain.
As the original poster indicated he was going for "shortest/cleanest" code. He might have succeeded with "shortest", but "cleanest" is a stretch.
Despite of java verbosity, if you get used to functional style, what you see there is just "col1.each | e1 -> col2.filter(==e1).count | sout". Isn't that clean, easy to read, and maintainable?
Terribly inefficient comparing to HashMap? Disagree. If author wanted, he'd made a test case where all strings have same hashCodes, and HashMap solution would've been even 2xtimes worse than straight O(N*N).
But in general, for randomly generated (which was not stated in task) "terribly inefficient" is true, because HashMap solution gives you O(N) instead O(N*N)
raggzy, no intent to inflame here, I can tell you're a true believer; I work with another. I've heard the "once you learn how to read it, it's much simpler" argument before. I do know how to read it, and sometimes use Java streaming and functional programming.
That said, here are a couple of anecdotal observations.
1) A few months back, I informally polled a dozen colleagues (all experienced developers) with small samples of code using Java streaming vs. more traditional style. About 80% found the streaming code more difficult to read.
2) In some recent performance analysis work, I found issues with streaming code. IMO, it becomes so easy to just stream one structure into another, filter/collect, etc., that developers (even ones very experienced with functional programming) begin to forget about the cost of the operations. Data structures are easily created and discarded, without thought.
Regarding efficiency of the example (where N is the number of strings, and Q is the number of queries): Typical hashmap O(N + Q). You're correct that it might be possible (though extremely difficult) to create strings with the same hash which could cause HashMap performance to degenerate into a TreeMap - which would give a worst case performance of O((N log UniqueN) + (Q log UniqueN)). It is likely that this is still better performance than O(N + N * Q) - unless, of course, the number of queries is very small and most values of N are unique.
More plausible than strings with the same hash, would be repeated queries of the same string. With the hashmap solution we get: typical O(Q), worst case O(Q log UniqueN). For the streaming solution O(Q * N).
I recommend using streaming/functional programming, where the TYPICAL reader will find it easily understandable. I recommend being careful to watch for tencencies to create and trash structures without thinking about the algorithm.
And nice work on doing this with only 2 LOC. I wouldn't have thought to use IntStream.range() as a technique for reading the input like that. Pretty cool.
Ah, I thought we'd have some small imperative-functional holywar :)
Someone asked me above in this thread about the same, and I find your reply here pretty similar to what I replied. Which means we're actually on the same, imperative side :)
Just sometimes using Collectors.join() and IntStram.range() .max() .min() .anyMatch() and so on because it's not bad.
Well you can also use trie Data Structure Just in case if the input is very big.
But in this question the input set is very small so you can just use simple code.
Sparse Arrays
You are viewing a single comment's thread. Return to all comments →
Ok)
IntStream.range(0, in.nextInt()) - constructs a stream of ints [0..N). Think of it like (for i = 0; i < N; i++)
.mapToObj(i -> in.next()) - for each i from stream we read a word
.collect(Collectors.toList()); - gather to list
So at this points we just read out N words to List<String> strings
IntStream.range(0, in.nextInt()).mapToObj(i -> in.next()) -- same as previous: read count, and read M words
.mapToLong(q -> strings.stream().filter(q::equals).count()) - for each of M word: iterate over N words, filter those who are equal to current word, and count elements.
.forEach(System.out::println) - output that count.
That is called 'functional style'. If you really want to learn this approach - i'd suggest learning haskell. It's the most pure functional language.
Thank You ! This is really helpful!
that was some amazing code...
amazing nobody noticed it didn't work.
Funny, because it's copypasted from AC solution without imports and class boilerplate. If you need - I can provide you with full copypaste so you can "just copypaste" and execute.
Thank you for your helpful comment. I can't find the imports. Actually the problem is with the parsing of the input as mentioned previously. Even a simple loop had trouble. It seems "hit and miss" with this website.
Just in case, here is version with boilerplate. Java8, copypaste, ..., profit!
import java.io.*; import java.util.*; import java.util.stream.*; public class Solution { // the code from above public static void main(String[] args) { Scanner in = new Scanner(System.in); List<String> strings = IntStream.range(0, in.nextInt()).mapToObj(i -> in.next()).collect(Collectors.toList()); IntStream.range(0, in.nextInt()).mapToObj(i -> in.next()).mapToLong(q -> strings.stream().filter(q::equals).count()).forEach(System.out::println); } // }why so negative? this isn't a website that offers solutions to problems, but a place for people to learn.
Using stream is inefficient
Hi!
Speaking of learning concepts, if I wanted to use Maps without Stream, what are the steps I would use for that? Specifically, from the half-dozen websites I researched, but it seems like I will have to manually place strings into the maps; is this correct?
Will operation time be O(n + q + hash_constant), then?
This is one of my first posts; sorry if this is a stupid question/formatted badly.
Thanks in advance.
That's not amazing it's a clusterfuck just to make it work in 2 lines.
http://www.vitavonni.de/blog/201603/2016030101-stop-abusing-lambda-expressions---this-is-not-functional-programming.html
totally agree. Besides a simpler approach would probably run quicker :)
Agree with you. Lamda is great but not in cases with complex biz logic inside.... Thank for the link you shared.
Besides a shorter solution, what are the advantages of a functional approach compared to say a HashMap? Does the functional approach take more memory and/or run time?
What are you looking for, is classical "Functional-vs-Imperative" holywar :). There are tons on that in the internet. It's "managing calculations"-vs-"managing state". In functional style you feel yourself like a mathematician constructing complete function. In imperative you feel yourself like a programmer thinking "how state will change" if I write this. Classical "what it is"-vs-"how to do it".
HashMap solution could be written in functional style too.
My personal thoughts on that - functional features are good, give better readability. I'd suggest using them in things like list comprehensions, e.g. you want to filter, count, aggregate something for elements. But personally I prefer mostly imperative code, because it's self-contained and self-explaning. E.g. you know what's going on for sure, though you have to write more code.
Also, functional-styled code is more bugless in terms of multithreading and multicore/multinode processing - e.g. filters, aggregators/reducers is good paralellable architecture. That's why it's often used in things like map-reduce, data processing and so on.
In terms of memory/runtime - depends on environment and implementation of functional language. In most cases they are constantly equal. But there are some cases when functional code under-the-hood generates a lots of object which "annoy" garbage collection. And also, there are some problems which require managing state directly. E.g. immutability would be an overdose.
Let's say you can always do better in imperative. But in most cases you gain more because of shortness and cleaniness of functional. However, you still need to be sure what it's doing under-the-hood and use it carefully.
what exactly do you mean by functional approach? I mean if you mean just breaking code into different methods such that one method does one job then we can use Hashmap in that way also. But other than that are there any serious issues in using a Hashmap instead of char array as discussed in the editorial?
"Functional programming" doesn't mean breaking code into smaller methods. Functional programming is a pretty different way to think about software (compared to writing a list of instructions to be followed).
I did a little googling and came up with this: https://wiki.haskell.org/Functional_programming . Maybe that helps?
I don't have much experience with functional programming myself, but I did enjoy reading a cute little book called The Little Schemer: https://mitpress.mit.edu/books/little-schemer . I haven't had a chance to read the rest of the series.
I think he was just trying to get a 2 line solution. The code is terribly inefficient when compared with a HashMap solution, much harder to understand, and (if implemented in any real system) nearly impossible to maintain.
As the original poster indicated he was going for "shortest/cleanest" code. He might have succeeded with "shortest", but "cleanest" is a stretch.
Despite of java verbosity, if you get used to functional style, what you see there is just "col1.each | e1 -> col2.filter(==e1).count | sout". Isn't that clean, easy to read, and maintainable?
Terribly inefficient comparing to HashMap? Disagree. If author wanted, he'd made a test case where all strings have same hashCodes, and HashMap solution would've been even 2xtimes worse than straight O(N*N).
But in general, for randomly generated (which was not stated in task) "terribly inefficient" is true, because HashMap solution gives you O(N) instead O(N*N)
raggzy, no intent to inflame here, I can tell you're a true believer; I work with another. I've heard the "once you learn how to read it, it's much simpler" argument before. I do know how to read it, and sometimes use Java streaming and functional programming.
That said, here are a couple of anecdotal observations. 1) A few months back, I informally polled a dozen colleagues (all experienced developers) with small samples of code using Java streaming vs. more traditional style. About 80% found the streaming code more difficult to read. 2) In some recent performance analysis work, I found issues with streaming code. IMO, it becomes so easy to just stream one structure into another, filter/collect, etc., that developers (even ones very experienced with functional programming) begin to forget about the cost of the operations. Data structures are easily created and discarded, without thought.
Regarding efficiency of the example (where N is the number of strings, and Q is the number of queries): Typical hashmap O(N + Q). You're correct that it might be possible (though extremely difficult) to create strings with the same hash which could cause HashMap performance to degenerate into a TreeMap - which would give a worst case performance of O((N log UniqueN) + (Q log UniqueN)). It is likely that this is still better performance than O(N + N * Q) - unless, of course, the number of queries is very small and most values of N are unique.
More plausible than strings with the same hash, would be repeated queries of the same string. With the hashmap solution we get: typical O(Q), worst case O(Q log UniqueN). For the streaming solution O(Q * N).
I recommend using streaming/functional programming, where the TYPICAL reader will find it easily understandable. I recommend being careful to watch for tencencies to create and trash structures without thinking about the algorithm.
And nice work on doing this with only 2 LOC. I wouldn't have thought to use IntStream.range() as a technique for reading the input like that. Pretty cool.
Ah, I thought we'd have some small imperative-functional holywar :)
Someone asked me above in this thread about the same, and I find your reply here pretty similar to what I replied. Which means we're actually on the same, imperative side :)
Just sometimes using Collectors.join() and IntStram.range() .max() .min() .anyMatch() and so on because it's not bad.
Very nice approach! Thanks for explaning it.
Excellent explanation , I wish i can code like that :D
super bro how can i learn functional style programming language
Well you can also use trie Data Structure Just in case if the input is very big. But in this question the input set is very small so you can just use simple code.
Can't we use parallelStream in place to stream for better performance.
WOW +1000
Why use an O(N*M) algorithm when it can be done O(N+M)?