Compare 2 StringList

mxloizix

I have to compare two StringList. And it have to return true even if one value is repeated in one StringList. for example this two StringList :
one : coffee, flour, tea
two : coffee, flour, tea, tea

have to be declared equals.
I have made this
what do you think ?

StringList inventory, copy;

void setup() {
  size(200, 200);
  inventory = new StringList();
  copy = new StringList();
  inventory.append("coffee");
  inventory.append("flour");
  inventory.append("tea");

  copy=inventory.copy();

  inventory.append("tea");
  inventory.append("tea");
  //copy.append("choc");

  println("iventory"+'\t'+ inventory.join(","));
  println("copy"+'\t'+copy.join(","));

  println("equal ?"+'\t'+ compareStringList( inventory, copy));

  exit();
}

boolean compareStringList(StringList a, StringList b) {
  boolean out = true;
  StringList  buffer = new StringList();
  String [] one = a.array();
  String [] two = b.array();

  for (int i=0; i<one.length; i++) {
    for (int j=0; j<two.length; j++) {
      if (one[i].equals(two[j])) buffer.append(one[i]);
    }
  }
  for (String v : buffer.values()) {
    if (a.hasValue(v)) a.removeValue(v);
    if (b.hasValue(v)) b.removeValue(v);
  }
  // reput item in StringList

  if (a.size()==0 && b.size() ==0) out = true;
  else out = false;

  a.clear();
  b.clear();
  a.append(one);
  b.append(two);

  return out;
}

GoToLoop

// forum.Processing.org/two/discussion/18893/compare-2-stringlist
// GoToLoop (2016-Nov-05)

final StringList inv1 = new StringList(), inv2 = new StringList();

void setup() {
  inv1.append(new String[] { "coffee", "flour", "tea" });
  println(inv1);

  inv2.append(inv1);
  inv2.append(new String[] { "tea", "tea" });
  inv2.shuffle(this);
  println(inv2);
  println(compareStringLists(inv1, inv2));

  inv2.append("juice");
  println(inv2);
  println(compareStringLists(inv1, inv2));

  exit();
}

static boolean compareStringLists(StringList a, StringList b) {
  for (String s : a)  if (!b.hasValue(s))  return false;
  for (String s : b)  if (!a.hasValue(s))  return false;
  return true;
}

jeremydouglass

Interesting approach, @mxloizix -- thank you for sharing it! The buffer code creates a list of shared terms -- which is useful in many cases, but not required specifically for finding differences.

Note that an interesting difference in @GoToLoop's test is that, rather than saving the result in out and returning it at the end, it returns the first time it finds a difference.

Imagine you had two lists of 10 million words and wanted to know if they were different. The only difference is that the first word of one is apple and the first word of the other is banana. Do you check all 10 million words, or stop at the first word?

mxloizix

yes of course.
thx for answering

jeremydouglass

@mxloizix -- thanks again for sharing.

As a followup, you could also try doing something with that if (one[i].equals(two[j])) buffer.append(one[i]); idea -- which is one way of giving you the overlap between two lists.

There are sometimes very fast ways of doing these things with particular methods and data structures that already exist, but it is a useful exercise to think through how you would ask various questions about two lists of strings, and answer them with functions.

For example, you could try:

• boolean compareStringLists(a,b) - are they the same?
• StringList sharedStrings(a,b) - which strings are in both?
• StringList unsharedStrings(a,b) - which strings are in only one?
• StringList uniqueStrings(a,b) - which strings occur only once, in either list?
• StringList listedStrings(a,b) - a list of each unique string, no matter how often it occurs
• StringList rankedStrings(a,b) - strings ordered most-to-least repeating
• etc. etc.

jeremydouglass

Another thing you could consider: is it possible for @GoToLoop 's suggested approach to be made more efficient?

static boolean compareStringLists(StringList a, StringList b) {
  for (String s : a)  if (!b.hasValue(s))  return false;
  for (String s : b)  if (!a.hasValue(s))  return false;
  return true;
}

For example, it compares these values 10 times before deciding they are the same:

a b c d e
e d c b a

Could it check fewer times and know they were they same? Could it check fewer times without then getting a wrong answer when comparing lists like this?

e e e e e
a b c d e

quark

Imagine you had two lists of 10 million words

With that many words then the algorithm used by GoToLoop would be inefficient as it would involve up to 200 million comparisons. (To be fair the OP's algorithm would also be inefficient)

Even so it is slightly inefficient because the lists can contain duplicates. For instance the element "tea" appears 10 times in list a and at least once in list b then it will be searched for 10 times even though it was found on the first search.

A much more efficient algorithm for large lists would involve sorting the lists first.

Here is my version

final StringList list1 = new StringList(), list2 = new StringList();

void setup() {
  list1.append(new String[] { "coffee", "flour", "tea", "coffee", "flour" });
  list2.append(new String[] { "coffee", "flour", "tea", "flour", "tea", "tea" });
  println(compareStringLists(list1, list2));

  list2.append("juice");
  println(compareStringLists(list1, list2));

  exit();
}

boolean compareStringLists(StringList a, StringList b) {
  println("Comparing ");
  println(a);
  println(b);
  // Sort the arrays before comparing them.
  a.sort();
  b.sort();
  // Find last element index values
  int lastA = a.size() - 1, lastB = b.size()-1;
  // List indicees
  int idxA = 0, idxB = 0;
  // Assume the lists are equal until we find otherwise
  boolean same = true;
  while (same && (idxA < lastA || idxB < lastB)) {
    String as = a.get(idxA);
    String bs = b.get(idxB);
    if (as.equals(bs)) {
      // In each list :- advance the index until we get the next
      // different element value
      while (idxA < lastA && as.equals(a.get(++idxA)));
      while (idxB < lastB && bs.equals(b.get(++idxB)));
    } else {
      // We found a mismatch
      same = false;
    }
  }
  return same;
}

mxloizix

thx @quark ! its interesting.