Optimization (in terms of speed )

Question

is there any other way to optimize this code. Anyone can come up with better way because this is taking lot of time in main code. Thanks alot;)

    HashMap<String, Integer> hmap = new HashMap<String, Integer>();
    List<String> dup = new ArrayList<String>();
    List<String> nondup = new ArrayList<String>();
    for (String num : nums) {
        String x= num;
        String result = x.toLowerCase();
        if (hmap.containsKey(result)) {
            hmap.put(result, hmap.get(result) + 1);
        }
        else {
            hmap.put(result,1);
        }
    }
    for(String num:nums){
        int count= hmap.get(num.toLowerCase());
        if (count == 1){
            nondup.add(num);
        }
        else{
            dup.add(num);
        }
    }

output: [A/tea, C/SEA.java, C/clock, aep, aeP, C/SEA.java]

Dups: [C/SEA.java, aep, aeP, C/SEA.java]

nondups: [A/tea, C/clock]

[This](https://stackoverflow.com/questions/3590677/how-to-do-union-intersect-difference-and-reverse-data-in-java) might help. — Andrew S, Mar 29 '22 at 21:55
Instead of `if (hmap.containsKey(result)) { hmap.put(result, hmap.get(result) + 1); } else { hmap.put(result,1); }` you can use `hmap.merge(result, 1, Integer::sum);` But since you don’t care about the actual number, but only whether it’s more than one, you can use a `Boolean` instead of `Integer` in the first place: `HashMap hmap = new HashMap<>(); List dup = new ArrayList<>(), nondup = new ArrayList<>(); for(String num: nums) { hmap.merge(num.toLowerCase(), false, (a,b) -> true); } for(String num: nums) { (hmap.get(num.toLowerCase())? nondup: dup).add(num); }` — Holger, Apr 01 '22 at 08:24

Louis Wasserman · Accepted Answer · 2022-03-29T22:07:03.940

How much time is "a lot of time"? Is your input bigger than what you've actually shown us?

You could parallelize this with something like Arrays.parallelStream(nums).collect(Collectors.groupingByConcurrent(k -> k, Collectors.counting()), which would get you a Map<String, Long>, but that would only speed up your code if you have a lot of input, which it doesn't look like you have right now.

You could parallelize the next step, if you liked, like so:

Map<String, Long> counts = Arrays.parallelStream(nums)
   .collect(Collectors.groupingByConcurrent(k -> k, Collectors.counting());
Map<Boolean, List<String>> hasDup =
   counts.entrySet().parallelStream()
     .collect(Collectors.partitioningBy(
        entry -> entry.getValue() > 1,
        Collectors.mapping(Entry::getKey, Collectors.toList())));

List<String> dup = hasDup.get(true);
List<String> nodup = hasDup.get(false);

Hey @Louis - is there any way to make changes to second part: Map> hasDup such that it gives the output like Dups: [C/SEA.java, aep, aeP, C/SEA.java] nondups: [A/tea, C/clock] — checked, Apr 03 '22 at 00:08
@Emmef Here the code gives output like: Dups: [c/sea.java, aep] nondups: [a/tea,c/clock] — checked, Apr 03 '22 at 00:09

score 0 · Answer 2 · answered Mar 31 '22 at 21:32

The algorithms in the other answers can speed up execution using multiple threads.

This can theoretically reduce the processing time with a factor of M, where M is the maximum number of threads that your system can run concurrently. However, as M is a constant number, this does not change the order of complexity, which therefore remains O(N).

At a glance, I do not see a way to solve your problem in less than O(N), I am afraid.

Optimization (in terms of speed )

2 Answers2