coding_basics.tex

\newpage
\section{Coding Basics}
\subsection{C++}

\subsubsection{Useful Function}

Some useful C++ function

\begin{lstlisting}
string::append("abc")
string::append(5, 'c')

//#include<algorithm>
vector<int> a(20, 0);
nth_element(a.begin(), a.begin()+6, a.end()); // partition algo
*min_element(a.begin(), a.end());
*max_element(a.begin(), a.end());

//#include<cmath>
double i=0;
abs(i);
ceil(i);
floor(i);
\end{lstlisting}


\subsubsection{Break String}
A very basic thing about c++ is how to break the string using some token. Since C++11 add regex, so there are two common way of breaking strings.

\begin{lstlisting}
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<regex>

using namespace std;

vector<string> break_string1(string& str){
  vector<string> res;
  stringstream ss(str);
  string buff;
  while(getline(ss, buff, ',')){
    res.push_back(buff);
  }
  return res;
}

vector<string> break_string2(string& str){
  regex r(",");
  vector<string> res;
  for(
    auto x = sregex_token_iterator(str.begin(), str.end(), r, -1);
    x!=sregex_token_iterator();
    x++){
    res.push_back((x->str()));
  }
  return res;
}

int main(int argc, char *argv[])
{
  string a("123,234,345");
  for(auto x: break_string1(a))cout << x << " ";
  cout <<endl;
  for(auto x: break_string2(a))cout << x << " ";
  cout <<endl;
  return 0;
}
\end{lstlisting}

remember when you use \textit{sregex\_token\_iterator}, the {\color{blue}regex must not be a right value}.


\subsubsection{Template}

Key things to know for template:
\begin{enumerate}
\item as long as the type is specified clearly, template class will be initiated at compile type
\item you can write a factorial calculation at using template at complied time. also {\color{blue}constexpr} will achieve this function as well
\item we can achieve virtual function by using template
\item the template function can do the type deduction, while template class must specify the typename or leave it blank
\item think of var-dict as Type ...
\item template deduction can be used for compiled time calculation
\item template can also be used to achieve static poly-morphism
\item Java constructor does not have return type and invoke implicitly
\item we cannot overwrite static method in class
\item just like c++ you cannot change return type during overloading
\item It's possible to override the function by return different type (must be sub-type) and it's called {\color{red}covariant}.
\end{enumerate}

\subsubsection{Compiled Time Calculation}
This is called template-metaprogramming. You actually store function template dur- ing compliation. Trade-o↵ between compile time and run-time. Also, use \textit{ftemplate- depth=200000} to enforce how many recursion you need in compile

\begin{lstlisting}
#include <iostream >
using namespace std;
template<int N> int gauss_sum(){
  return N + gauss_sum <N-1>();
}
template <> int gauss_sum <0>(){
  return 0;
}
int main(int argc, char *argv[]) {
  cout<<gauss_sum <20>() << endl;
  return 0; }
}
\end{lstlisting}

\subsubsection{Variadic Template}

Use variable dict template to write print function

\begin{lstlisting}
#include<iostream>
#include<string>
using namespace std;

template<typename T> void print(const T&t){
  cout << t << endl;
}

template<typename T, typename... Y> void print(const T& first, Y... y){
  cout << first << " ";
  print(y...);
}

int main(){
  print(1, 2, 3, "abc");
}
\end{lstlisting}

\subsubsection{Static Polymorphism (CRTP)}
Polymorphism can be achived using inheritance. You first write a base class as template algorithmm and customize small function using inheritance to overwrite.

Also you can do it using following template pattern
\begin{lstlisting}
#include < iostream >
#include < string >
using namespace std;
template <typename derived > class base{
  public:
  void talk (){
    cout << "my name is " << get_name() << endl;
  }
  string get_name (){
    return static_cast <derived*>(this) -> get_name();
  }
};
// must be public inheritance here otherwise error
class cat: public base <cat >{
  // must add friend here since base class need to // access this method
  private:
  friend string base <cat >:: get_name (); string get_name (){
    return "cat"; }
  };

int main(int argc, char *argv[]) {
    // direct initialize
    cat d; d.talk();
    // use heap to initialize
    base<cat>* c = new cat(); c->talk();
    return 0;
}


\end{lstlisting}

\subsubsection{Perfect Forwarding}

Consider example below, if there is no perfect forwarding, the passed in right value $t$ will become left value if passed to the next function on the stack.
\begin{lstlisting}
#include<utility>
template<typename T, typename U>
std:: pair<T, U>make_pair_wrapper(T&&t, U&&u){
	return std::make_pair(std::forward<T>(t), std::forward<U>(u));
}
\end{lstlisting}
\subsubsection{Smart Pointer}
Key things to remember:
\begin{enumerate}
\item smart pointer will have a internal reference will add 1 when copy, create, go into field and minus 1 when destruct out of field.
\item smart pointer must be copy when returned
\item comment area wont work, no implicit conversion
\item no cycle allowed, use weak pointer.
\end{enumerate}

\begin{lstlisting}
#include<memory>
using namespace std;
/*
int* test(){
  return make_shared<int>(1);
}
*/

shared_ptr<int> test(){
  return make_shared<int>(1);
}
\end{lstlisting}

\subsection{Java}
A bit overview here:
\begin{enumerate}
\item All the value are reference but all the value are passed by value in argument
\item No operator overloading like C++, but {\color{red} except for String that is pre-given}
\item Array does not support allocating generic type \textit{eg. ArrayList}
\item Boolean, String is inmmutable in Java, as well as {\color{blue} Integer, Boolean, etc} wrapper types
\item Java manage memory like convey belt, keep move heap head pointer foward while using GC move what are behind closer to head.
\item {\color{blue} adaptive garbage collection scheme} has two types {\color{blue} Stop And Copy} and {\color{blue} Mark and Sweep}.
\item ArrayList vs Vector/Stack in Java is that the later two are thread safe but slower
\item {\color{blue}default} keyword is for restricting use of class inside package
\
\end{enumerate}

\subsubsection{Pass by Value}

Java's references in fact act as a handle (with value in memory) that point to a position of an Object (More like a pointer instead of another name). Therefore, \textit{swap} function like in C++ can not really achieve jobs.

\begin{lstlisting}
class MyObject{
    public MyObject(int x){
        data = x;
    }

    public MyObject(MyObject other){
        data = other.data;
    }
    public int data;
}

class pass_by_reference{
    public static void swap(MyObject a, MyObject b){
        MyObject c = new MyObject(a);
        a = b;
        b = c;
    }

    public static void main(String args[]){
        MyObject a = new MyObject(1);
        MyObject b = new MyObject(2);
        swap(a, b);
        System.out.printf("a: %d, b: %d\n", a.data, b.data);
        // results are: a: 1, b: 2
    }
}
\end{lstlisting}

\subsubsection{Producer And Consumer}
Java has good ability of multi-processing. Here is a example using ArraList implementing a locked bounded queue.

In Java, {\color{blue} using \textit{new Thread lambda} can bypass the constrain of using \textit{Runnable} where you need to make sure your queue is \textit{static final}}

Here are summary of Semaphore/Conditional variable
\begin{enumerate}
\item Semaphore must acquire before locked
\item Conditional variable must acquire after locked, and use while to keep release; While in C++ you don't need to
\end{enumerate}

\begin{lstlisting}
package com.company;
import java.util.ArrayList;
import java.util.Random;
import java.util.concurrent.Semaphore;

public class Main {

    static class Buffer {
        private int size;
        private ArrayList<Integer> data;
        private Semaphore full;
        private Semaphore empty;
        public Buffer(int size){
            this.size=size;
            this.data = new ArrayList<Integer>();
            this.full = new Semaphore(this.size);
            this.empty = new Semaphore(0);
        }
        public void add(int value){
            try {
                full.acquire();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            synchronized (this) {
                data.add(value);
                empty.release();
            }
        }
        public Integer get(){
            try {
                empty.acquire();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            synchronized(this){
                Integer value = data.get(data.size()-1);
                data.remove(data.size()-1);
                full.release();
                return value;
            }

        }
    } ;

    public static void main(String[] args) throws InterruptedException {
        Buffer b = new Buffer(10);
        int producer_num = 2;
        int consumer_num = 2;
        ArrayList<Thread> a = new ArrayList<Thread>();
        for(int i = 0; i< producer_num; i++){
            a.add(new Thread(() ->{
                    for(int j = 0; j<20; j++) {
                        int value = new Random().nextInt(100);
                        b.add(value);
                        System.out.printf("producer %d add %d\n",
                        Thread.currentThread().getId(), value);
                    }
            }));
        }
        for(int i = 0; i< consumer_num; i++) {
            a.add(new Thread(()-> {
                for (int j = 0; j < 20; j++) {
                    Integer value = new Integer(b.get());
                    System.out.printf("consumer %d get %d\n",
                    Thread.currentThread().getId(), value);
                }
            }));
        }
        for(Thread i: a) i.start();
        for(Thread i: a) i.join();
    }
}
\end{lstlisting}





\subsection{Python}

\subsubsection{Meta Class}
A metaclass is a class whose instances are classes. Like an "ordinary" class defines the behavior of the instances of the class, a metaclass defines the behavior of classes and their instances.

You can think of metaclass as a dispatcher when creating a new class in Python. New class will have customize
attributes after metaclass's operation.

type will provide a mapping from text code to real class type that we defined,

In python, default meta class is type.
\begin{lstlisting}
class LittleMeta(type):
    def __new__(cls, clsname, superclasses, attributedict):
        print "LittleMeta.__new__ called"
        # return a instance of LittleMeta, which is A
        return type.__new__(cls, clsname, superclasses, attributedict)

    def __call__(cls, *args,**kwargs):
        # pass class A in here as a argument
        print('MetaFoo: {c},{a},{k}'.format(c=cls,a=args,k=kwargs))

        # invoke normal A initailize process
        return super(LittleMeta, cls).__call__(*args, **kwargs)


class S(object):
    pass

class A(S):
    __metaclass__ = LittleMeta

    def __new__(cls):
        print "A.__new__ called"
        return super(A, cls).__new__(cls)
    pass

a = A()
print a
\end{lstlisting}

you will get
\begin{lstlisting}
clsname:  A
superclasses:  (<class '__main__.S'>,)
attributedict:  {'__module__': '__main__', '__qualname__': 'A'}
\end{lstlisting}

The singleton in python can be done by
\begin{lstlisting}
class Singleton(type):
  _instances = {}
  def __call__(cls, *args, **kwargs):
      if cls not in cls._instances:
          cls._instances[cls] = super(Singleton, cls).__call__(*args, **kwargs)
      return cls._instances[cls]
\end{lstlisting}


\subsubsection{\_\_new\_\_ vs \_\_init\_\_}
\_\_new\_\_(cls) method in python is for creating object, which is called before the \_\_init\_\_. \_\_new\_\_ is supposed to return a obj of current class if you want to let \_\_init\_\_ get called.
\begin{lstlisting}
class A(object):

    def __new__(cls):
        print "A.__new__ called"

    def __init__(self):
        print "A.__init__ called"  # -> is actually never called

print A()
\end{lstlisting}

If we change a bit, then both method would get called
\begin{lstlisting}
class A(object):

    def __new__(cls):
        print "A.__new__ called"
        obj = super(A, cls).__new__(cls)
        return obj

    def __init__(self):
        print "A.__init__ called"  # -> is actually never called

print A()
\end{lstlisting}

\subsubsection{Abstract Class In Python}
Now we understand why when we create abstract base class in Python, we need do the following
\begin{lstlisting}

from ABC import ABCmeta

class abstract(object):
    # ABCmeta here has changed the default behavior of string->class
    # mapping So you cannot create a instance of abstract, since it
    # will raise error at the above step
    __metaclass__ = ABCmeta

    @abstractmethod
    def foo(self)

\end{lstlisting}



\subsubsection{Dataframe Data-structure}
\begin{enumerate}
\item pandas.DataFrame is a column major data structure, each colume is a pd.Series (act as a dictionary plus ndarray).
\item DataFrame frame will group all same type data into a block, int, float, datetime64 ... etc
\item string does not have representation in numpy so in pandas, it is a pointer point to other places, which is very slow
\item use {\color{red}category} dtype can solve most of string issue properly
\end{enumerate}

\subsection{MongoDB}

MongoDB has three layers:
\begin{enumerate}
\item Database (equivalent to schema)
\item Collection (equivalent to table)
\item Document (equivalent to row, in json format)
\end{enumerate}

Here are some useful command for mongodb
\begin{lstlisting}
db.createCollection("mycol", { capped : true, autoIndexId : true, size :
   6142800, max : 10000 } )

db.tutorialspoint.insert({"name" : "tutorialspoint"})

db.mycol.find({},{"title":1,_id:0})

db.COLLECTION_NAME.find().sort({KEY:1})

db.COLLECTION_NAME.ensureIndex({KEY:1})

db.mycol.aggregate([{$group : {_id : "$by_user", num_tutorial : {$sum : 1}}}])
\end{lstlisting}

MongoDB has easy to config sharding, create backup, map reduce interfaces.