Java语言Volatile原理

Java语言提供了一种稍弱的同步机制,即volatile变量,用来确保将变量的更新操作通知到其他线程。当把变量声明为volatile类型后,编译器与运行时都会注意到这个变量是共享的,因此不会将该变量上的操作与其他内存操作一起重排序。volatile变量不会被缓存在寄存器或者对其他处理器不可见的地方,因此在读取volatile类型的变量时总会返回最新写入的值。

在访问volatile变量时不会执行加锁操作,因此也就不会使执行线程阻塞,因此volatile变量是一种比sychronized关键字更轻量级的同步机制。

1553739684-9830-20160708224602686-2141387366

当对非 volatile 变量进行读写的时候,每个线程先从内存拷贝变量到CPU缓存中。如果计算机有多个CPU,每个线程可能在不同的CPU上被处理,这意味着每个线程可以拷贝到不同的 CPU cache 中。

而声明变量是 volatile 的,JVM 保证了每次读变量都从内存中读,跳过 CPU cache 这一步。

当一个变量定义为 volatile 之后,将具备两种特性:

1.保证此变量对所有的线程的可见性,这里的“可见性”,当一个线程修改了这个变量的值,volatile 保证了新值能立即同步到主内存,以及每次使用前立即从主内存刷新。但普通变量做不到这点,普通变量的值在线程间传递均需要通过主内存来完成。

2.禁止指令重排序优化。有volatile修饰的变量,赋值后多执行了一个“load addl $0x0, (%esp)”操作,这个操作相当于一个内存屏障(指令重排序时不能把后面的指令重排序到内存屏障之前的位置),只有一个CPU访问内存时,并不需要内存屏障;

什么是指令重排序:是指CPU采用了允许将多条指令不按程序规定的顺序分开发送给各相应电路单元处理。

volatile 性能:

volatile 的读性能消耗与普通变量几乎相同,但是写操作稍慢,因为它需要在本地代码中插入许多内存屏障指令来保证处理器不发生乱序执行。

快排算法的实现与讲解(java/C++)

快排的算法其实不复杂,但是很少时候,偶尔整的自己头晕,所以写一篇博客,以免以后忘记。

假设我们的数组为:{5,2,1,8,9,3,7,0,4,6},一共10个数字,现在需要将这个数组进行排序。首先我们需要找一个基准数,其实就是参照物,得有个东西跟你对比吧?不然怎么可以呈现出你的美?

假设左边为i=0; 右边j = 9;

方法很简单,分别从数组的左右边两段进行“探测”。首先是左边移动,最左边的第一个数字是5,而最右边的数字是6。

6 >= 5 条件成立,接着左边往右边移动一位(j–)

……

4>=5条件不成立,这个时候就换一下位置,4跟5换。现在的数组应该就是这样子:{4,2,1,8,9,3,7,0,5,6}

接着轮到右边探测,左边的数字已经被替换为4,而右边的是5(因为j自减了一次);那么现在条件对比:

5>=4条件成立,右边往左边靠拢(i++)

5>=2条件成立,右边往左边靠拢(i++)

……

5>=8条件不成立,换位置:{4,2,1,5,9,3,7,0,8,6}

到此,第一轮交换结束。接下来j继续向左挪动(再友情提醒,每次必须是j先出发)。他发现了0(比基准数5要小,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下:

{4,2,1,0,9,3,7,5,8,6}

第二次交换结束,“探测”继续。接着轮到i继续向右挪动,他发现了9(比基准数5要大,满足要求)之后又停了下来。交换之后的序列如下:

{4,2,1,0,5,3,7,9,8,6}

….以此类推,哨兵i继续向右移动,悲剧!!!此时i和j撞上了,说明此时“探测”结束。我们将基准数5和3进行交换。交换之后的序列如下:

{4,2,1,0,3,5,7,9,8,6}

到此“探测”真正结束。此时以基准数5为分界点,5左边的数都小于等于5,5右边的数都大于等于5。

回顾一下刚才的过程,其实j的使命就是要找小于基准数(5)的数,而哨兵i的使命就是要找大于基准数(5)的数,直到i和j撞在一起为止为止。

那么现在数据可以区分为两组:

{4,2,1,0,3,        5       ,7,9,8,6}

左边:4  2  1  0  3

右边:7  9  8  6

数组被分为了两组,然后按照直接的方法进行对比,只是开始i=0;j=9,要变为(先从左边开始):

指针位置:i=0; j=4

数组:4  2  1  0  3

还是上一张图吧,比较好理解:

wKiom1MUSRPjUTOIAAC-kWvhNhc591

注:图片是网上找的,数组的排序跟我的不一致,但是看的明白。

最后:

  • 快排的原理很简单;
  • 就是把数组分为两节;
  • 左边的是最小的,而右边的是最大的;
  • 然后再拿左、右边的来继续递归,递归的原理也一样,也是拆分为两节,以此类推。

上代码吧,我写了java跟c的代码:

2.java代码:

public static void main(String[] args) {
    int[] arr = {5,2,1,8,9,3,7,0,4,6};
    sort(arr, 0, arr.length - 1);
    for (int i : arr) {
        System.out.print(i + " ");
    }
}

private static void sort(int[] arr, int l, int r) {
    int i = l;
    int j = r;
    if (l < r) {
        while (l < r) {
            while (l < r && arr[r] >= arr[l]) {
                r--;
            }
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

            while (l < r && arr[l] <= arr[r]) {
                l++;
            }
            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

        }
        sort(arr, i, l - 1);//递归左边,此时l=5
        sort(arr, l + 1, j);//递归右边,此时l=5
    }
}

 

2.那么c++的代码会是怎么样呢?

#include "pch.h"
#include <iostream>

using namespace std;

void sortQ(int *arr, int l, int r) {
   int i = l;
   int j = r;
   int tmp;
   if (i < j) {
      while (l < r) {
         while (l < r && arr[r] >= arr[l])
         {
            r--;
         }

         tmp = arr[l];
         arr[l] = arr[r];
         arr[r] = tmp;

         while (l < r && arr[r] >= arr[l]) {
            l++;
         }
         tmp = arr[l];
         arr[l] = arr[r];
         arr[r] = tmp;
      }

      sortQ(arr, i, l - 1);//处理左边,此时l=5
      sortQ(arr, l + 1, j);//处理右边,此时l=5
   }

}

int main()
{
    std::cout << "Hello World!\n"; 

   int arr[] = {5,2,1,8,9,3,7,0,4,6};
   int size = sizeof(arr) / sizeof(arr[0]);

   sortQ(arr, 0, size - 1);
   for (int i : arr) {
      cout << i << " ";
   }

}

 

 

 

使用C/C++新建了一个类似于Java的StringBuffer类

使用C/C++新建了一个类似于Java的StringBuffer类,主要实现了常规的几种方法:

1.StringBuffer & append(const char * _c) ;
这个方法是往字符串中插入字符到最后;

2.StringBuffer(const StringBuffer & buf);
在C语言中如果需要使用到a=b这种赋值方法,并且数据成员使用指针形式,那么则需要自定义一个复制函数;

3.char* toString();
返回数据成员中的char数据;

4.int length();
返回字符串的长度;

5.std::string substr(int start = 0,int len = 1);
截取字符串,通常需要借助indexOf的方法来查找字符串的位置;

6.void replaceAll(const char * find, const char * des);
替换字符串中的指定文字;

7.int indexOf(const char * find);
查找指定字符串的位置,如果没有则返回-1;

8.bool operator==(const StringBuffer & buf);
C/C++中特有的方法,如果需要使用运算符:a==b,增需要定义一个自定义的运算符方法,这里只定义了:==。

 

接着就是贴出头文件:StringBuffer.h

#pragma once
#include<iostream>

//exmple:
/*
// StringBuffer sb;
// or like this:
// StringBuffer sb("test");
// sb.append("append.");

// and you can like this:
// sb.append("append 1,").append("append 2,");

// equal:
// sb1==sb?1:0
// if(sb1 == sb){//do something...}

// length:
// sb.length();

// substring:
// sb.substr(int strat,int end);
// sb.substr(0,1);//it will be return "t";

// find:
// sb.indexOf(char * find_char);
// sb.indexOf("st");//it will be return 2;
// sb.indexOf("index");//it will be return -1;

// replaceAll:
// sb.replaceAll(char * find_char,char * des_char);
// like this:
// sb.replaceAll("test","1234");

// toString:
// sb.toString();
*/

#ifndef STRING_BUFFER
#define STRING_BUFFER

class StringBuffer
{
   private:
      char * value;
      char * value1;
      int len;
      int _number;
   public:
      StringBuffer();
      StringBuffer(const char * _c);
      StringBuffer & append(const char * _c) ;
      StringBuffer(const StringBuffer & buf);
      char* toString();
      int length();
      std::string substr(int start = 0,int len = 1);
      void replaceAll(const char * find, const char * des);
      int indexOf(const char * find);
      bool operator==(const StringBuffer & buf);
      ~StringBuffer();
};

#endif // !STRING_BUFFER



然后贴出代码:

#include "pch.h"
#include "StringBuffer.h"
#include<iostream>
#include<string.h>


StringBuffer::StringBuffer()
{
   len = 1;
   _number = 0;
   value = new char[2]{"\0"};
}

StringBuffer::StringBuffer(const char * _c) {
   len = std::strlen(_c) + 1;
   _number = 1;
   value = new char[len];
   strcpy_s(value, len, _c);
}

StringBuffer::StringBuffer(const StringBuffer & buf) {
   len = buf.len;
   _number = buf._number;
   value = new char[len];
   strcpy_s(value, len, buf.value);
}

StringBuffer::~StringBuffer()
{
   delete[] value;
   std::cout << "StringBuffer out." << std::endl;
}

StringBuffer & StringBuffer::append(const char * _c) {
   int _l = std::strlen(_c)+1;
   value1 = new char[len+_l];
   strcpy_s(value1, len, value);
   strcat_s(value1, len + _l, _c);

   value = value1;
   
   len += _l;
   _number++;
   return *this;
}

char* StringBuffer::toString() {
   return this->value;
}

int StringBuffer::length() {
   return strlen(value);
}

std::string StringBuffer::substr(int start, int len) {
   std::string s = value;
   return s.substr(start, len);
}

int StringBuffer::indexOf(const char * find) {
   std::string s = value;
   return s.find(find);
}

void StringBuffer::replaceAll(const char * find, const char * des) {
   int idx = 0;
   int _len = std::strlen(find);
   bool has = false;
   std::string s = value;
   while (idx > -1)
   {
      idx = s.find(find);
      if (idx > -1) {
         s = s.replace(idx, _len, des);
         has = true;
      }
   }

   if (has) {
      strcpy_s(value, strlen(s.data()) + 1, s.data());
      len = strlen(s.data()) + 1;
      value1 = value;
   }
   
}

bool StringBuffer::operator==(const StringBuffer & buf) {
   if (this == &buf) {
      return true;
   }
   return strcmp(this->value, buf.value) == 0;
}

来一张效果图呗:

QQ截图20181118163945

C/C++关键字typedef使用指南

搞懂了c++创始人写的中的下面这个例子, 有助于你理解typdef:

typedef int P();
typedef int Q();
class X {
static P(Q); // 等价于`static int Q()`, Q在此作用域中不再是一个类型
static Q(P); // 等价于`static int Q(int ())`, 定义了一个名为Q的function
};

这是一个极好的例子, 先问一下 typedef int P()到底做了什么 ? 其实是 :

declares a function type P as returning an int and taking no arguments.

1. 官方定义

初次接触此类typedef用法的程序员直观上理解这个例子比较困难, 我们来看一下typedef的官方定义 :

Typedef does not work like typedef [type] [new name].The[new name] part does not always come at the end.

You should look at it this way : if[some declaration] declares a variable, typedef [same declaration] would define a type.

总结一下就是 : 任何声明变量的语句前面加上typedef之后,原来是变量的都变成一种类型。不管这个声明中的标识符号出现在中间还是最后。

2. 隐藏技能
typedef 定义的新类型, 使用时可以省略括号。什么意思 ?

typedef int NUM;
NUM a = 10; // 也可写成`NUM(a) = 10;
NUM(b) = 12; // 也可写成`NUM b = 12;

3. 例子(先从初级的开始 :)

int整型

typedef int x; // 定义了一个名为x的int类型

自定义结构体

typedef struct { char c; } s; // 定义名为s的struct类型

指针

typedef int *p; //定义了一个名为p的指针类型, 它指向int

高级的(注意标识符不一定在最后) :

数组

typedef int A[]; // 定义一个名为A的int数组的类型

函数

typedef int f(); // 定义一个名为f, 参数为空, 返回值为int的函数类型

typedef int g(int); // 定义一个名为g, 含一个int参数, 返回值为int行的函数类型

现在回过头看:

typedef int P();
static P(Q);

应该就比较好理解了, P是一个新定义的function类型, 它返回值为int, 无参数
根据我的第2点说明, P(Q); 实际上等价于P Q, 声明Q是一个返回值为int, 无参数的函数.

这玩意有什么用呢 ?
我们都知道C++语言里, 函数都是先声明后使用的(除非在使用之前定义), 看以下例子 :

#include <iostream>
#include <stdio.h>
#include <string>

typedef int P(); // 简单的
typedef void Q(int *p, const std::string& s1, const std::string& s2, size_t size, bool is_true); // 复杂的
class X {
public:
P(eat_shit); // 等价于声明`int eat_shit();`
Q(bullshit); // 等价于声明`void bullshit(int *p, const string& s1, const string& s2, size_t size, bool is_true);`
};

int main() {
X *xx;
printf(“shit ret: %d\n”, xx->eat_shit());
int a[] = { 1, 3, 4, 5, 7 };
xx->bullshit(a, “foo”, “bar”, sizeof(a) / sizeof(int), true);
}

int X::eat_shit() {
return 888;
}

void X::bullshit(int *p, const std::string& s1, const std::string& s2, size_t size, bool is_true) {
std::cout << “s1: ” << s1 << “, s2: ” << s2 << “, size: ” << size << std::endl;
printf(“elems:\n”);
for (int i = 0; i < size; i++) {
printf(“%d %s”, *p++, (i == size – 1) ? “” : “,”);
}
printf(“\n”);
}

理解了上面的再看下面这段,理解复杂的定义和声明:

在阅读Linux的内核代码是经常会遇到一些复杂的声明和定义,例如:

  1.  void * (*(*fp1) (int))[10];
  2. float(*(*fp2) (int, int, float)) (int);
  3. typedef double(*(*(*fp3) ())[10]) ();
    1. fp3 a;
  4. int(*(*fp4())[10]) ();

 

刚看到这些声明或者定义时,初学者可能头皮发毛,基于大惑不解。如果缺乏经验和方法来对这些内容进行理解,势必会让我们浪费大量的时间。

我尝试对这些内容进行疏理和总结,为自己和有同样困惑的同学答疑解惑。要理解这些复杂的声明和定义,我觉得首先不能着急,应该由浅而深,逐步突破。下面先看一些简单的定义:

1. 定义一个整型数

int a;

2. 定义一个指向整型数的指针

int *p;

3. 定义一个指向指针的指针,它指向的指针指向一个整型数

int **pp;

我们可以用一些简单的代码把这三条给串起来:

int a;
int *p;
int **pp;

p = &a; // p指向整数a所在的地址
pp = &p; // pp指向指针p

 

4. 定义一个包含10个整型数的数组

int arr[10];

5. 定义一个指向包含10个整型数数组的指针

int(*pArr)[10];

用几行代码将4、5两个定义串起来:

int arr[10];
int(*pArr)[10];

pArr = &arr;

6. 定义一个指向函数的指针,被指向的函数有一个整型参数并返回整型值

int(*pfunc) (int);

7. 定义一个包含10个指针的数组,其中包含的指针指向函数,这些函数有一个整型参数并返回整型值

int(*arr[10]) (int);

用几行代码将6、7两个定义串起来:

int(*pfunc) (int);
int(*arr[10]) (int);

arr[0] = pfunc;

到这一步,似乎就不是那么好理解了。现在需要请出用于理解复杂定义的“右左法则”:

从变量名看起,先往右,再往左,碰到圆括号就调转阅读的方向;括号内分析完就跳出括号,还是先右后左的顺序。如此循环,直到分析完整个定义。

让我们用这个方法来分析上面的第6条定义:int(*pfunc) (int);

  • 找到变量名pfunc,先往右是圆括号,调转方向,左边是一个*号,这说明pfunc是一个指针;
  • 然后跳出这个圆括号,先看右边,又遇到圆括号,这说明(*pfunc)是一个函数,所以pfunc是一个指向这类函数的指针,即函数指针,这类函数具有一个int类型的参数,返回值类型是int。

接着分析第7条定义:int(*arr[10]) (int);

  • 找到变量名arr,先往右是[]运算符,说明arr是一个数组;
  • 再往左是一个*号,说明arr数组的元素是指针(注意:这里的*修饰的不是arr,而是arr[10]。原因是[]运算符的优先级比*要高,arr先与[]结合。);
  • 跳出圆括号,先往右又遇到圆括号,说明arr数组的元素是指向函数的指针,它指向的函数有一个int类型的参数,返回值类型是int。

分析完这两个定义,相信多数人心里面应该有点谱了。

可应该还有人会问:怎么判断定义的是函数指针(定义6),还是数组指针(定义5),或是数组(定义7)?可以抽象出几个模式:

  • type(*var)(…); // 变量名var与*结合,被圆括号括起来,右边是参数列表。表明这是函数指针
  • type(*var)[]; //变量名var与*结合,被圆括号括起来,右边是[]运算符。表示这是数组指针
  • type(*var[])…; // 变量名var先与[]结合,说明这是一个数组(至于数组包含的是什么,由旁边的修饰决定)

至此,我们应该有能力分析文章开始列出来了几条声明和定义:

(1) void * (*(*fp1) (int))[10];

  • 找到变量名fp1,往右看是圆括号,调转方向往左看到*号,说明fp1是一个指针;
  • 跳出内层圆括号,往右看是参数列表,说明fp1是一个函数指针,接着往左看是*号,说明指向的函数返回值是指针;
  • 再跳出外层圆括号,往右看是[]运算符,说明函数返回的是一个数组指针,往左看是void *,说明数组包含的类型是void *。

简言之,fp1是一个指向函数的指针,该函数接受一个整型参数并返回一个指向含有10个void指针数组的指针。

(2) float(*(*fp2) (int, int, float)) (int);

  • 找到变量名fp2,往右看是圆括号,调转方向往左看到*号,说明fp2是一个指针;
  • 跳出内层圆括号,往右看是参数列表,说明fp2是一个函数指针,接着往左看是*号,说明指向的函数返回值是指针;
  • 再跳出外层圆括号,往右看还是参数列表,说明返回的指针是一个函数指针,该函数有一个int类型的参数,返回值类型是float。

简言之,fp2是一个指向函数的指针,该函数接受三个参数(int, int和float),且返回一个指向函数的指针,该函数接受一个整型参数并返回一个float。

(3) typedef double(*(*(*fp3) ())[10]) ();

fp3 a;

  • 如果创建许多复杂的定义,可以使用typedef。这一条显示typedef是如何缩短复杂的定义的。
  • 跟前面一样,先找到变量名fp3(这里fp3其实是新类型名),往右看是圆括号,调转方向往左是*,说明fp3是一个指针;
  • 跳出圆括号,往右看是空参数列表,说明fp3是一个函数指针,接着往左是*号,说明该函数的返回值是一个指针;
  • 跳出第二层圆括号,往右是[]运算符,说明函数的返回值是一个数组指针,接着往左是*号,说明数组中包含的是指针;
  • 跳出第三层圆括号,往右是参数列表,说明数组中包含的是函数指针,这些函数没有参数,返回值类型是double。

简言之,fp3是一个指向函数的指针,该函数无参数,且返回一个含有10个指向函数指针的数组的指针,这些函数不接受参数且返回double值。

这二行接着说明:a是fp3类型中的一个。

(4) int(*(*fp4())[10]) ();

这里fp4不是变量定义,而是一个函数声明。

  • 找到变量名fp4,往右是一个无参参数列表,说明fp4是一个函数,接着往左是*号,说明函数返回值是一个指针;
  • 跳出里层圆括号,往右是[]运算符,说明fp4的函数返回值是一个指向数组的指针,往左是*号,说明数组中包含的元素是指针;
  • 跳出外层圆括号,往右是一个无参参数列表,说明数组中包含的元素是函数指针,这些函数没有参数,返回值的类型是int。

简言之,fp4是一个返回指针的函数,该指针指向含有10个函数指针的数组,这些函数不接受参数且返回整型值。

用typedef简化复杂的声明和定义,以上我们已经看到了不少复杂的声明和定义,这里再举一个例子:

int *(*a[10]) (int, char*);

  • 用前面的“右左法则”,我们可以很快弄清楚:
  • a是一个包含10个函数指针的数组,这些函数的参数列表是(int, char*),返回值类型是int*。
  • 理解已经不成问题,这里的关键是如果要定义相同类型的变量b,都得重复书写:

int *(*b[10]) (int, char*);

这里有没有方便的办法避免这样没有价值的重复?答案就是用typedef来简化复杂的声明和定义。

typedef可以给现有的类型起个别名。这里用typedef给以上a、b的类型起个别名:

typedef int *(*A[10]) (int, char*); // 在之前定义的前面加入typedef,然后将变量名a替换成类型名A

现在要再定义相同类型的变量c,只需要:
A c;

再看一例:

void(*b[10]) (void(*)());

先替换右边括号里面的参数,将void(*)()的类型起个别名pParam:

12
 
Copyright © 2008-2021 lanxinbase.com Rights Reserved. | 粤ICP备14086738号-3 |