CODEWITHSUNDEEP
dart
davecom
davecom

Reputation: 1498

Fastest way to check Map for duplicate values?

Given a Map, assignment, what is the fastest way to check if it contains any duplicate values in Dart? I am currently using a Set formed from the Map's values and checking its length against the original Map, which works of course, but I'm wondering if there's an especially performant alternative.

Set d = new Set.from(assignment.values);
if (d.length < assignment.length) {
  return false;  // indicates has duplicates in this context
}

EDIT: Tried @mezoni's solution modified for my program, but it actually ran a bit slower than my original version. It probably has more to do with constant times than anything else. 

List values = new List.from(assignment.values);
Set set = new Set();
for (var i = 0; i < assignment.length; i++) {
  if (!set.add(values[i])) {
    return false;
  }
}

Upvotes: 2

Views: 2608

Answers (3)

mezoni
mezoni

Reputation: 11210

Fastets way (if you realy need better performance):

void main() {
  // Values from map
  var values = [1,2,3,2,1,3,2,1];
  var length = values.length;
  var set = new Set();
  var duplicate = false;
  // Only for statistics purpose
  var statistics = 0;
  for(var i = 0; i < length; i++) {
    statistics++;
    if(!set.add(values[i])) {
      duplicate = true;
      break;
    }
  }

  print("Duplicate: $duplicate");
  print("Performed in ${statistics} iteration(s) from $length possible");
}

Output:

Duplicate: true
Performed in 4 iteration(s) from 8 possible

P.S.

The first example can be recommended to use with List values.

But because Map.values not a List but Iterable then it would be more efficient do not convert them to List but use as is.

Here is modified sample for use with Iterable objects.

It will be work faster because in this algorithm not required convert all values to the List object because it not want using of all elements without exception.

Instead it wants use as less as possible access operation on original source. If the source supports lazy operation of the access to values (as Iterable) this will be even better.

void main() {
  // Values from map
  var values = [1,2,3,2,1,3,2,1];
  var assignment = {};
  var length = values.length;
  var key = 0;
  for(var value in values) {
    assignment[key++] = value;
  }

  var set = new Set();
  var duplicate = false;
  // Only for statistics purpose
  var statistics = 0;
  for(var value in assignment.values) {
    statistics++;
    if(!set.add(value)) {
      duplicate = true;
      break;
    }
  }

  print("Duplicate: $duplicate");
  print("Performed in ${statistics} iteration(s) from $length possible");
}

Upvotes: 1

tusj
tusj

Reputation: 297

This is more of a algorithms question than a Dart question. In any case, you have to check every value against the others, giving n-1 + n-2 + ... + n-(n-1) checks, or n^2/2. Programmatically, it's easy to create a set, but you could also generate an array, sort the array, and then iterate once to check for duplicates. That finishes in O(n log n).

Upvotes: 2

Florian Loitsch
Florian Loitsch

Reputation: 8128

Complexity wise you won't be able to get anything faster. Creating the Set and filling it with the values of the Map is linear in the number of elements. Clearly you have to run through all the values, so you can't do any better than that.

Maybe you could find a solution with a smaller constant factor, but that's not clear. In particular for larger sets I think the Set solution is pretty efficient.

Upvotes: 3

Related Questions