مقایسه ی Type wrapper ها و primitive type ها از نظر Performance

public static void main(String[] args) {
int repeats = 40000000;
long time;

time = System.currentTimeMillis();
long counterA = 0L;
for (int i = 0; i < repeats; i++) {
counterA = counterA + 4L;
}
System.out.println(counterA + " A: " + (System.currentTimeMillis() - time) + " ms");

time = System.currentTimeMillis();
Long counterB = 0L;
for (int i = 0; i < repeats; i++) {
counterB = counterB + 4L;
}
System.out.println(counterB + " B: " + (System.currentTimeMillis() - time) + " ms");
}
خروجی :


160000000 A: 0 ms
160000000 B: 284 ms


نتایج ممکن است با توجه به پردازنده, نسخه ی جاوا و... شما متفاوت باشد

دلیل نتایج فوق واضح است :
Type wrapper ها باید در heap
ذخیره شوند

و ساخت اشیا در heap هزینه ی بیشتری نسبت به stack دارد

بیاید کد بالا را بار دیگر , و اینبار به جای استفاده از autoboxing , از valueOf استفاده کنیم:
public static void main(String[] args) {
int repeats = 40000000;
long time;

time = System.currentTimeMillis();
long counterA = 0L;
for (int i = 0; i < repeats; i++) {
counterA = counterA + 4L;
}
System.out.println(counterA + " A: " + (System.currentTimeMillis() - time) + " ms");

time = System.currentTimeMillis();
Long counterB = Long.valueOf(0L);
for (int i = 0; i < repeats; i++) {
counterB = counterB + 4L;
}
System.out.println(counterB + " B: " + (System.currentTimeMillis() - time) + " ms");
}

خروجی :

160000000 A: 0 ms
160000000 B: 237 ms



دلیل این امر چیست؟

تعریف type wrapper به صورت بالا از نظر بایت کد تفاوت چندانی با تعریف به صورت زیر ندارد:
Long l = new Long(0L);


این کد همیشه یک شی جدید از Long با مقدار 0 ایجاد میکند . اما جاوا بصورت پیشفرض تعدادی از مقادیر پر استفاده را از اول اجرای برنامه ذخیره میکند تا تفاوت سرعت فاحشی میان primitive type و type wrapper بوجود نیاید :

@IntrinsicCandidate
public static Long valueOf(long l) {
final int offset = 128;
if (l >= -128 && l <= 127) { // will cache
return LongCache.cache[(int)l + offset];
}
return new Long(l);
}

با مشاهده ی متد valueOf (این متد را تحت عنوان static factory method میشناسیم)میتوان دید مقادیر -128 تا 127 کش شده اند .
و خارج از این محدوده , تفاوتی میان
Long l = 128L;
و
Long l = Long.valueOf(128L);
وجود ندارد.(البته لازم به ذکر است احتمالا اگر در برنامه ی شما یک عدد زیاد استفاده شود ان عدد نیز کش میشود)


البته استفاده از سازنده ی Long از نسخه ی 9 به بعد منسوخ شده و توسط جاوا پیشنهاد شده صرفا متد valueOf برای استفاده از Type wrapper ها به کار برده شود.

Java Roadmap

کد سوال بالا

public static int fastExp(int base,int exponential){
if(exponential==0){
return 1;
} else if(exponential==1){
return base;
}
int R = fastExp(base,exponential/2);
if(exponential%2==0){
return R*R;
}
return R*base*R;

}

الگوریتم fast exponential

پیچیدگی زمانی:
O(lgn)

پیچیدگی زمانی الگوریتم معمولی :
O(n)

دسته بندی : Divide and conquer

@this_java

یک api برای اجاره منزل نوشته شده با فریمورک Spring:
استفاده از Jsr 303
Jsr 338(Jpa)
Jwt

@this_java

Websocket با vertx
مثال استفاده از eventbus

مثال استفاده از Spring data jpa

Permutations of given array:

public class Runner {
    public static void main(String[] args) {
        int a[]={1,2,3};
        permutation(a,0);


    }

    private static void permutation(int[] a,int k) {
        if(k==a.length-1){
            System.out.println(Arrays.toString(a));
            return;
        }

        for (int i = k; i <a.length; i++) {
            int temp=a[k];
            a[k]=a[i];
            a[i]=temp;
            permutation(a,k+1);
             temp=a[k];
            a[k]=a[i];
            a[i]=temp;


        }

    }

}

Subsets of given array:

public static void printSubSets(int arr[],int last,int k[]){
if(last==arr.length){
System.out.println(Arrays.toString(k));
return;
}int x = arr[last];
k[last] = x;
printSubSets(arr, last + 1, k);
k[last] = -1;

printSubSets(arr, last + 1, k);


}
public static void main(String[] args) {
int arr[]={1,2,3};
int k[]={-1,-1,-1};
printSubSets(arr,0,k);

}

problem is to find a path from the upper-left corner to the lower-right corner
of an n × n grid, with the restriction that we may only move down and right. Each
square contains an integer, and the path should be constructed so that the sum of the
values along the path is as large as possible.


divide and conquer approach:

public static int maxPath(int value[][],int x,int y){

if(x==0 || y==0){
return value[x][y];
}
int max= Integer.MIN_VALUE;


max = Math.max(maxPath(value,x-1,y),maxPath(value,x,y-1))+value[x][y];


return max;

}

dynamic programming approach:

public static int maxPath(int value[][],int x,int y,int memory[][]){

if(x==0 || y==0){
return value[x][y];
}
if(memory[x][y]!=Integer.MIN_VALUE){
return memory[x][y];
}
int max= Integer.MIN_VALUE;


max = Math.max(maxPath(value,x-1,y),maxPath(value,x,y-1))+value[x][y];

memory[x][y]=max;
return max;

}

Driver code:

public static void main(String[] args) {
int value[][]= {
{3,7,9,2,7},
{9,8,3,5,5},
{1,7,9,8,5},
{3,8,6,4,10},
{6,3,9,7,8}
};
int mem[][]= new int[5][5];
for(int i=0;i<mem.length;i++) {
Arrays.fill(mem[i],Integer.MIN_VALUE);
}
System.out.println(maxPath(value,4,4,mem));
}

Largest Sum Contiguous Subarray Dynamic programming approach :

public class KadaneAlgorithm {
public static int findMaxSubArray(int[] nums) {
int maxSoFar = nums[0];
int maxEndingHere = nums[0];

for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}

return maxSoFar;
}

public static void main(String[] args) {
int[] nums = { -2, -3, 4, -1, -2, 1, 5, -3 };
int maxSum = findMaxSubArray(nums);
System.out.println("حداکثر مجموع زیرآرایه: " + maxSum);
}
}

Suppose that we are given a set of coin values coins = {c1, c2,..., ck } and a
target sum of money n, and we are asked to construct the sum n using as few coins as
possible. There are no restrictions on how many times we can use each coin value.


Divide and conquer approach:

public static int maxCoin(int n,int []price){

if(n==0){
return 0;
}
int q = Integer.MAX_VALUE;
for(int i=0;i<price.length;i++){
if(n- price[i]>=0) {
q = Math.min(maxCoin(n - price[i], price) + 1, q);
}
}
return q;
}

Dynamic programming approach:

public static int dpMaxCoin(int n,int []price,int res[]){
if(n==0){
return 0;
}
if(res[n]>-1){
return res[n];
}else {
int q = Integer.MAX_VALUE;
for (int i = 0; i < price.length; i++) {
if (n - price[i] >= 0) {

q = Math.min(dpMaxCoin(n - price[i], price,res) + 1, q);
}
}
res[n]=q;

}
return res[n];
}

Driver code:

public static void main(String[] args) {
int [] arr = {1,3,4};
int res[] = new int[15];
Arrays.fill(res,-1);
System.out.println(maxCoin(14,arr));
System.out.println(dpMaxCoin(14,arr,res));

}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class DFS {
private static boolean[] visited = new boolean[6];
private static List<List<Integer>> adj = new ArrayList<>(10);

public static void main(String[] args) {
adj.add(List.of(0));
adj.add(1, List.of(2, 4));
adj.add(2, List.of(3, 1, 5));
adj.add(3, List.of(2, 5));
adj.add(4, List.of(1));
adj.add(5, List.of(3, 2));

dfs(1);

}

//O(n+m)
public static void dfs(int s) {
List<Integer> adjOfNodeS = adj.get(s);
if (visited[s]) return;
visited[s] = true;
System.out.println("Visit :" + s);
for (int i : adjOfNodeS) {
dfs(i);
}
}
}

output :
Visit :1
Visit :2
Visit :3
Visit :5
Visit :4