Wednesday, April 15, 2015

Data Structures in Python compared with Java: Sets

A set is an unordered collection with no duplicate elements. Set models the mathematical set abstraction. Both Python and Java use hashtable as the underlying data structure of set.

Creating a set
Also allows different types of element
#empty set
basket = set()
basket = {'shirley',2014}

Python also allows for creating a character set using the following method:

basket = set('abaabab')

Duplicate elements will be removed.

In Java:

Set basket = new HashSet ()

Of course only one type is allowed.
Java also provide constructor to create a hash set from another collection, if created from a collection that contains duplicate elements, duplicate ones will be removed.

List listA = new ArrayList ();
  listA.add(1);
  listA.add(2);
  listA.add(1);
  Set t = new HashSet (listA);


Union
In Python, it is the same way as you do binary operation:

>>> a = {'shirley',2015}
>>> b = {'dora', 2014}
>>> a | b
{'shirley', 'dora', 2014, 2015}

In Java, we use addAll(Collection<? extends E> c) method:

a.addAll(b);

Complements
Python:

>>> a = set('aabbccabc')
>>> b = set('abdd')
>>> a - b
{'c'}

It will return the elements in a that is not in b.

In Java, we use removeAll(Collection<? extends E> c) method:

a.remveAll(b);

Intersection
Python:

>>> a
{'a', 'b', 'c'}
>>> b
{'a', 'b', 'd'}
>>> a&b
{'a', 'b'}
>>> 

Java: retainAll(Collection<? extends E> c) method:

a.retainAll(b);

XOR (?)
Actually, it is elements in a or b but not both

>>> a
{'a', 'b', 'c'}
>>> b
{'a', 'b', 'd'}
>>> a^b
{'d', 'c'}

I couldn't find any built in methods to do this in Java, however, we can always do a little bit coding to acquire the desired result:


Set a = new HashSet ();
  a.add(1);
  a.add(2);
  Set b = new HashSet ();
  b.add(2);
  b.add(6);
  Set c = new HashSet(a);
  c.removeAll(b);
  Set d = new HashSet(b);
  d.removeAll(a);
  c.addAll(d);


Sorted sets:
Java provides TreeSet data structure. It is based on red - black tree implementation (See here for implementations). In Python, I think this needs to be acquired by using lambda function(?). I am not quite familiar with the lambda function, but I will take a look later.



References:
[1]. Not-very-familiar Python doc
[2]. www.grepcode.com
[3]. Beloved Java doc
[4]. www.codatlas.com

No comments:

Post a Comment