Monday, April 23, 2018

Overload Operators in C++ & Scala

Target audience: Beginner
Estimated reading time: 4'

Operator overloading allows for a reinterpretation of existing operators by imparting a distinct significance to them, all while preserving their original function. This is an example of compile-time polymorphism
While C++ offers the capability to assign unique meanings to operators for specific data types, how does its approach align with that of Scala's operator overloading?


Table of contents
Follow me on LinkedIn
 

Overview

In object-oriented programming, operator overloading is a specific case of polymorphism, where different operators may have different implementations depending on their arguments. The main benefit of operator overloading is to allow the developer to program using notation relevant to the domain (i.e. summation of vectors) and allows user-defined types a similar level.

C++ and Scala supports overloaded or redefinition of operators.
There is however a distinction between C++ and Scala in terms of operator overloading: In Scala the operators are over-loadable by the programmer who create methods with operator name while in C++ the operators are over-loadable by the language as a predefined set.

Notes
  • For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omitted.
  • Scala version used in 2.11.8

C++ operator overloading

In C++, operator overloading instructs the compiler to perform a certain operation when its corresponding operator is used on one or more variables. However, the && , || and comma operators cannot be overloaded.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Point {
private:
   int x;
   int y;
public:
      // Constructor
   Point(int x = 0, int y = 0) : x(x), y(y) { }

      // overloading += operator
   Point& operator+=(const Point& p) { 
       this.x += x;
       this.y += y;
       return (*this);
    }
  
   Point operator+(const Point& p) {
       Point result;
       result.x = x + p.getX();
       result.y  = y + p.getY();
       return result, 
   }

   friend std::ostream& operator<<(std::ostream& out, Point p) {
        out << "(" << p.getX() << "," << p.getY() << ")";
        return out;
   }
};


int main() {
    Point p1(4, 5), p2(5, 11)
    cout << "p1=" << p1 << "p1 + p2=" << p1+p2;
    return 0;
}

Scala overloading by proxy

Scala does not technically have operator overloading because it does not have operators in the common sense.  The operators are indeed function name defined by the programmer. Scala treats all operators as methods and thus allows operator overloading by proxy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
final class Point(val x: Int, val y: Int) {
 
   // Binary operator
   def +(p : Point) : Point = {
       require(p != null, "cannot add a null point")
       new Point(x + p.x, y + p.y)
    }
    
    override def toString : String = s"(${x.toString},${y.toString)"           
}
 
object Overload extends App {
    val p1 = new Point(2, 0)
    val p2 = new Point(4, -2)
       
    Console.println(s"p1=$p1 and p1+p2=${(p1 + p2)}")
}

The class Point is immutable as the coordinate, x and y are declared private value. It is highly recommended to create immutable objects and containers because it reduced the object state lifecycle. Immutability avoids the need of complex and error-prone concurrent update of the state of an object (race condition).

Thank you for reading this article. For more information ...

References

  • Scala for the Impatient - C. Horstman - Addison-Wesley 2012
  • The Annotated C++ Reference Manual - M. Ellis,  B. Stroustrup - Addison-Wesley 1991
  • github.com/patnicolas

---------------------------
Patrick Nicolas has over 25 years of experience in software and data engineering, architecture design and end-to-end deployment and support with extensive knowledge in machine learning. 
He has been director of data engineering at Aideo Technologies since 2017 and he is the author of "Scala for Machine Learning" Packt Publishing ISBN 978-1-78712-238-3

Friday, March 16, 2018

Fisher-Yates Shuffle in Scala

Target audience: Intermediate
Estimated reading time: 4'


This post describes the Fisher-Yates algorithm to shuffle randomly a sequence of objects.
Follow me on LinkedIn

Note: The code associated with this article is written using Scala 2.12.4

Overview

The generation of a sequence of randomly ordered elements from an existing sequence is a common problem. How can you be sure if the new sequence of items is actually randomly generated?
The Fisher-Yates shuffle algorithm (a.k.a. Donald Knuth shuffle) produces unbiased permutations with a similar likelihood.
One important benefit of Fisher-Yates is the ability to shuffle the elements of the sequence, in place.


Note:
There are several interpretations of the shuffling algorithm. This post describes the implementation of the most common Fisher-Yates algorithm


Fisher-Yates

Here is the Fisher-Yates in a nutshell. Let's consider an array arr of n elements
For each array index k from n-1 to 1
    Select a random value m  between k and 0
    Swap arr[r] and arr[k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def fisherYates[T](t: Seq[T]): Seq[T] = {

   setSeed(System.currentTimeMillis)
  
   (0 until t.size).foreach (n => {
       val randomIdx = n + nextInt(t.size-n)
       val tmp = t(randomIdx)
       t.update(randomIdx, t(n))
       t(n) = tmp
   })
   t
} 

The Fisher-Yates algorithm executes as an iteration with the following two steps:
  • Select a random item in the remaining sequence (line 6)
  • Swap the randomly selected item with the current item (lines 8,9)

Fast Fisher-Yates implementation

The performance of the Fisher-Yates algorithm can be improved by implementing the swapping of the randomly selected item with the current time in-place using bit manipulation operators.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def fisherYates2(seq: mutable.Seq[Int]): IndexedSeq[Int] = {
  require(seq.size > 0, "Undefined argument")

  setSeed(System.currentTimeMillis)
  (0 until seq.size).map(i => {
     var randomIdx: Int = i + nextInt(seq.size-i)
     seq(randomIdx) ^= seq(i)
     seq(i) = seq(randomIdx) ^ seq(i) 
     seq(randomIdx) ^= (seq(i))
     seq(i)
  })
}

The following code snippet tests the two implementations of the Fisher-Yates shuffling algorithm.
  val input = Array[Char](
    'a', 't', '4', '&', '9', '2', 'z', 'y', 'r', '8', '*', '?'
  )
  println(fisherYates[Char](input).mkString(","))
  // t,&,*,2,a,r,4,z,?,y,8,9

  println(fisherYates2(Array.tabulate(34)(n => n)).mkString(","))
  // 9,24,11,29,1,31,28,20,6,18,23,0,13,17,22,0,27,
  // 4,16,7,25,14,30,32,5,12,8,19,21,0,0,33,26,0
Note: Scala standard library provides developers with a shuffling method: Random.shuffle.

Thank you for reading this article. For more information ...

References


---------------------------
Patrick Nicolas has over 25 years of experience in software and data engineering, architecture design and end-to-end deployment and support with extensive knowledge in machine learning. 
He has been director of data engineering at Aideo Technologies since 2017 and he is the author of "Scala for Machine Learning" Packt Publishing ISBN 978-1-78712-238-3