3

I'm trying to sort a list by frequency.

List myList = ["a", "b", "c", "d", "e", "f", "d", "d", "e"];

My expected output would be that the list is sorted on frequency & has no duplicated elements.

(myList has 3x "d" and 2x "e").

List output = ["d", "e", "a", "b", "c", "f"];

What's the most efficient way to do it?

Thanks in advance!

Is it also possible to do the same system with a List of Maps/Objects?

List myList2 = [{"letter": a, "info": myInfo}, {"letter": b, "info": myInfo}, ...]
Karel Debedts
  • 5,226
  • 9
  • 30
  • 70
  • 1
    first use `groupBy()`, then use `List.sort()` – pskink Mar 23 '20 at 12:12
  • To compare two objects: https://stackoverflow.com/questions/18428735/how-do-i-compare-two-objects-to-see-if-they-are-the-same-instance-in-dart – Blasanka Mar 23 '20 at 13:31
  • 1
    `List myList = ["a", "b", "c", "d", "e", "f", "d", "d", "e"]; var out = groupBy(myList, (e) => e).values.toList()..sort((a, b) => b.length - a.length); print(out); print(out.map((e) => e[0]));` – pskink Mar 23 '20 at 20:45
  • Thanks @pskink, this is exactly what I was looking for! – Shawn Lauzon Dec 20 '21 at 03:01

1 Answers1

2

It is not difficult to do that even without using package:collection.

List myList = ['a', 'b', 'c', 'd', 'e', 'f', 'd', 'd', 'e'];

// Put the number of letters in a map where the letters are the keys.
final map = <String, int>{};
for (final letter in myList) {
  map[letter] = map.containsKey(letter) ? map[letter] + 1 : 1;
}

// Sort the list of the map keys by the map values.
final output = map.keys.toList(growable: false);
output.sort((k1, k2) => map[k2].compareTo(map[k1]));

print(output);  // [d, e, a, b, c, f]

As for the second one, your desired output is unclear, but assuming that the values corresponding to the key letter are String and that you need exactly the same output as that of the first one, you can achieve it in a very similar way.

List myList2 = [
  {'letter': 'a', 'info': 'myInfo'},
  {'letter': 'b', 'info': 'myInfo'},
  {'letter': 'c', 'info': 'myInfo'},
  {'letter': 'd', 'info': 'myInfo'},
  {'letter': 'e', 'info': 'myInfo'},
  {'letter': 'f', 'info': 'myInfo'},
  {'letter': 'd', 'info': 'myInfo'},
  {'letter': 'd', 'info': 'myInfo'},
  {'letter': 'e', 'info': 'myInfo'},
];

final map2 = <String, int>{};
for (final m in myList2) {
  final letter = m['letter'];
  map2[letter] = map2.containsKey(letter) ? map2[letter] + 1 : 1;
}

final output2 = map2.keys.toList(growable: false);
output2.sort((k1, k2) => map2[k2].compareTo(map2[k1]));

print(output2);  // [d, e, a, b, c, f]
kaboc
  • 814
  • 1
  • 6
  • 23
  • I actually overlooked the very important part mentioned by OP: `the most efficient way`, sorry. I'm curious which is more efficient with or without a package like `collection`, but either way, I believe the important thing is to measure the performance in your actual usage. – kaboc Mar 23 '20 at 14:13
  • Using containsKey is unnecessary loop. As we have the target key we can check the nullability of it directly and enhance the performance. ```map[letter] = map[letter] != null ? map[letter] + 1 : 1 ``` – Hamed Hamedi Mar 03 '21 at 03:12
  • @HamedHamedi Did you actually compare execution times? Using `containsKey()` on a map with 1,500 elements was more than 100 times faster than checking nullability on my PC. Can you show your evidence please? I wonder why `containsKey()` exists if it is really inefficient/unnecessary as you say. Is it only for better discoverability? – kaboc Mar 03 '21 at 07:01
  • Its not about inefficiency. The thing is using right tool at right place. I described my reason and the evidence is the source code of dart http://astashov.s3.amazonaws.com/dartdoc_flutter/current/dart-collection/Maps/containsKey.html – Hamed Hamedi Mar 03 '21 at 14:04
  • Based on this [simple test](https://dartpad.dev/ed2447b329493dc16237014f3f544c52) , the performance for one million items are fairly equal but in some cases the `containsKey` takes longer and in rare cases it takes twice the time of null check. So we can conclude both implementation works well in real life use-cases, but I think this test is enough to give you the main idea. Also there is a [similar discussion](https://stackoverflow.com/questions/14601016/is-using-java-map-containskey-redundant-when-using-map-get) in java which worth's checking – Hamed Hamedi Mar 04 '21 at 09:47
  • I found that the result turns around if the execution order is swapped in Hamed's code on DartPad. FYI, you can also use `Stopwatch` instead of `DateTime` for benchmarking. – kaboc Mar 04 '21 at 14:55