算法图解第三章笔记：递归(java版)

Posted on

3.1 递归

案例：寻找祖母的钥匙。

钥匙在祖母的盒子里，一个大盒子中有很多小盒子，小盒子中也可能还有盒子。钥匙就在某个盒子中。如何找到钥匙？

方法一：

  1. 创建一个要查找的盒子堆
  2. 从盒子中取出一个盒子，在里面找
  3. 如果找到的是盒子，就将其加入到盒子堆中，以便以后再查找。
  4. 如果找到钥匙，则大功告成
  5. 回到第二步

方法二

  1. 检查盒子中的每样东西
  2. 如果是盒子，就回到第一步
  3. 如果是钥匙，则大功告成

第一种方法使用while循环：只要盒子堆不空，就从中取一个盒子，并在其中仔细查找。

第二种方法使用递归—函数调用自己。

两种方法作用相同。递归只是让解决方案更加清晰，并没有性能上的优势。有一句是这样说的：“如果使用循环，程序的性能可能更高；如果使用递归。程序可能更容易理解。如何选择要看什么对你来说更重要”。

3.2 基线条件和递归条件

由于递归函数自己调用自己，因此编写这样的函数时很容易出错，进而导致无限循环。

例如：假设你要编写一个像下面这样的倒计时函数：

>3…..2…..1

可以编写的递归函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
public class Code_02_BaseCase {
	public static void main(String[] args) {
		countDown(3);
	}
	/*
	 * 未添加基线条件，所以程序会一直运行下去
	 */
	public static void coutDown(int i){
		System.out.println(i);
		coutDown(i-1);
	}
 }

当你运行时，这个函数会一直运行下去。。。。

所以编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）

给函数countDown添加基线条件：

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
/*
 * 	设计一个倒计时3、2、1的计时器
 * 
 * 	基线条件：
 * 
 */
public class Code_02_BaselineCondition {
	public static void main(String[] args) {
		countDown(3);
	}
	
	/*
	 * 添加基线条件
	 */
	public static void countDown(int i){
		System.out.println(i);
            //基线条件  
		if(i <= 1 ){
			return;
		}else{
              //递归条件
              countDown_1(i-1);
		}
	}	
	
}

打印输出为：

3.3 栈

​ 调用栈 call stack

​ 有两种操作：压入（插入）和 弹出（删除并读取）

1.调用栈：

​ 一个简单的函数，来看看计算机是如何调用栈的。

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
/*
 * 	演示计算机是如何调用栈的
 * 
 */
public class Code_03_CallStack {
	public static void main(String[] args) {
		greet("John");
	}
	
	public static void greet(String name){
		System.out.println("hello,"+ name + "!");
		greet2(name);
		System.out.println("getting ready to say bye....");
		bye();
	}
	
	public static void greet2(String name){
		System.out.println("how are you, "+ name + "?");
	}
	
	public static void bye(){
		System.out.println("ok bye");
	}
}

打印输出为：

一个重要的概念：调用另一个函数时，当前函数暂停并处于未完成的状态。

2.递归调用栈：

递归函数也使用调用栈。下面是一个例子：

factorial(5)写作5！其定义如下：5！= 5 * 4 * 3 * 2 * 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * 	递归调用栈：
 * 		递归函数求解
 * 			5！= 5*4*3*2*1
 * 
 */
public class Code_04_RecursionCallStack {
	
	public static void main(String[] args) {
		System.out.println(factorical(5));
	}
	/*
	 * 递归函数
	 */
	public static int factorical(int x){
		//基线条件
		if(x == 1){
			return 1;
		}else{
			//递归条件
			return x*factorical(x - 1);
		}
	} 
}

打印输出为：

算法图解第二章笔记：选择排序（java版）

Posted on

数组：

使用数组意味着所有待办事项都在内存中都是相连的（紧靠在一起的）

优势：需要随机读取元素时，数组的效率很高。

链表：

链表中的元素可以存储在内存的任何地方，链表的每个元素都存储了下一个元素的地址，从而使一些系列的随机的内存地址串在一起。

优势：在插入元素方面。需要同时读取所有元素时，链表的效率很高。

局限：需要跳跃，链表的效率很低。

选择排序code：

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
public class SelectionSort_1 {
    public static void main(String[] args) {
         //测试数组
		int[] testArr = {5,3,6,2,10};
		selectionSort(testArr);
	}
 
	public static void selectionSort(int[] arr){
		 for (int i = 0; i < arr.length; i++) {  
			   int lowerIndex = i;  
			   // 找出最小的一个索引  
			   for (int j = i + 1; j < arr.length; j++) {  
			    if (arr[j] < arr[lowerIndex]) {  
			     lowerIndex = j;  
			    }  
			   }  
			   //交换元素的位置  
			   int temp = arr[i];  
			   arr[i] = arr[lowerIndex];  
			   arr[lowerIndex] = temp;  
			  }  
			  for (int i : arr) {  
			   System.out.print(i + " ");  
			  }  
	}
	
}

输出为：

win10完整Tensorflow-GPU环境搭建教程(附CUDA+cuDNN安装过程)

Posted on

最近一直想要用GPU训练一个五子棋AI，无奈自己的笔记本是A卡，速度太慢，计算一局需要7、8分钟。所以在之前安了Ubuntu虚拟机，使用了ROCm框架，训练速度提升为一局1、2分钟，但其实速度还是很慢。这两天实验室老师拿来了一台主机，配置：Nvidia 显卡，GeForce GTX1660。所以就想安一下GPU，安了一下午，终于可以调用GPU训练了，速度为1分钟12局。。。真是舒服了。

1.查看你的显卡是否支持GPU

点击查看显卡是否支持GPU

满足之后就可以进行下面的步骤了。

2.安装python环境

其实大家知道，安装python环境可以直接安装，也可以通过Anaconda安装，Anaconda安装时候需要注意你想要安装python版本，如果不想要默认自带的python版本，就不要勾选

建议不要勾选把path直接加入到环境变量中：

安装好之后，打开Anaconda命令行，输入conda -V，如果输出是你所安的版本，即为成功。

3.安装Tensorflow-GPU

可以打开tensorflow官网：https://www.tensorflow.org/install/install_windows#installing_with_anaconda ，可以了解下官网上有详细的教程。

我是新建了一个名为“tensorflow”的conda环境：版本可以自选，要注意tensorflow-GPU与python版本对应

1
conda create -n tensorflow pip python=3.6

推荐更换国内的源，速度会快很多的。

然后要激活环境，才能继续在这个环境下安装tensorflow-GPU。当然你也可以不新建一个环境，直接就在anaconda环境下安装也是可以的。

1
activate tensorflow

下面进行安装tensorflow-GPU，虽然换源了，但你会发现下载还是会很慢。

1
pip install --ignore-installed --upgrade tensorflow-gpu

推荐使用这行代码下载：

1
2
3
4
5
6
pip install --ignore-installed --upgrade tensorflow-gpu -i https://pypi.tuna.tsinghua.edu.cn/simple

这样安装的版本可能不是你所需要的，可以指定tensorflow的版本安装，只需在tensorflow-gpu后面指定版本即可，即改为：我安装的tensorflow-gpu 1.14.0版本

pip install --ignore-installed --upgrade tensorflow-gpu==1.14.0 -i https://pypi.tuna.tsinghua.edu.cn/simple

4.安装CUDA ToolKit +cuDNN

第一步要查看要安装的CUDA + cuDNN版本，因为大家要安的tensoflow版本不一样，所以对应的CUDA 和cuDNN版本也就不一样，所以一定要对应上，否则就会报错。

可以点击查看你所要安装的tensorflow所对应的版本cuDNN和CUDA版本

记得点击右上角的 语言选项，把中文改成英语，否则最新的版本显示不出来。然后点击左侧栏的windows

Image

然后向下翻，翻到这里，查看对应关系，我要安的是1.14.0，所以按第一行的对应版本安装

Image

然后下载CUDA + cuDNN

在这个网址查找CUDA已发布版本：https://developer.nvidia.com/cuda-toolkit-archive

按照刚才官网提示进行下载，我下载的是10.0本地安装版本。

下载好CUDA Toolkit 10.0 后，我们开始下载cuDnn 7.4，需要注意的是，下载cuDNN需要在nvidia上注册账号，使用邮箱注册，完全免费的。登陆账号之后才可以继续下载。

一定要按照tensorflow官网的提示，选择安装CUDA和cuDNN的版本，一定要对应好。

cuDNN历史版本在该网址下载网址：https://developer.nvidia.com/rdp/cudnn-archive

下载之后，下面进行安装。

注意：最重要的一步，先卸载原有的显卡的驱动。

CUDA Toolkit需要在指定版本显卡驱动环境下才能使用，如果已经安装了nvidia显卡驱动，再安装CUDA Toolkit时，会因二者版本不兼容而导致CUDA无法使用。而CUDA Toolkit安装包中自带与之匹配的显卡驱动，所以一定要删除电脑先前的显卡驱动。

大家可以在左下角的 小娜 中搜索，NVIDIA GeFore Experience(我安装的驱动是这个，具体还要看你自己的驱动名称，一定要找好了，别删错了)，找到之后，卸载掉就可以安装CUDA Toolkit了。建议先把自己原来的驱动型号先记下来，万一出什么问题，还可以补救。

先安装CUDA Toolkit,安装路径默认就可以了，但是要记住这个路径，一会还有用。接下来就是安装了，在安装选项时，选择自定义，然后在自定义安装选项中，勾选所有的安装项，然后就可以了。

接下来将cudnn的那个压缩包解压，里面有三个文件夹，直接复制到CUDA的根目录下就可以，例如这个路径下：C:\Program Files\NVIDIA GPU Computing Toolkit\CUDA\v10.0，然后进行环境变量配置。记住：要改成你自己的路径，否则系统是找不到。

1
2
3
4
5
6
7
C:\Program Files\NVIDIA GPU Computing Toolkit\CUDA\v10.0

C:\Program Files\NVIDIA GPU Computing Toolkit\CUDA\v10.0\bin

C:\Program Files\NVIDIA GPU Computing Toolkit\CUDA\v10.0\lib\x64

C:\Program Files\NVIDIA GPU Computing Toolkit\CUDA\v10.0\libnvvp

到这里安装步骤已经全部完成，下面就可以开始愉快的测试了。

5 测试

在你的环境下依次运行代码：

1
2
3
4
5
python

import tensorflow as tf 

tf.test.gpu_device_name()

我的命令行输出的是：

上面是自己机器还有GPU的信息，出现的最后一句：‘/device：GPU：0’ 则说明安装成功了。

查看在使用那个GPU，依次输入代码：

1
2
3
from tensorflow.python.client import device_lib

device_lib.list_local_devices()

我这个主机只有一块GPU，所以输出的信息也是只有一块。

至此，终于安装完成了。。。

真心希望这个教程可以帮助到大家，少走一些弯路，早点开始调用GPU训练，说句题外话：训练的速度是真的快啊，如有任何疑问，欢迎交流。

算法图解笔记：第一章（java版）

Posted on

二分查找：

优点：时间复杂度低，仅为logN

注意：前提是有序数组

Code：

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
public class Code_01_binarySearch {
	public static void main(String[] args) {
		//测试数组
		int[] myList = {1,3,5,7,9};
		System.out.println(binarySearch(myList, 7));
		System.out.println(binarySearch(myList, 10));
	}
	
	public static int binarySearch(int[] list,int item){
		int low = 0;
		int high = list.length - 1;
		while(low <= high){
			//定义中间位置
			int mid = low +(high - low)/2;
			int guess = list[mid];
			if(guess == item){
				return mid;
			}
			if(guess < item){
				low = mid + 1;
			}
			else{
				high = mid - 1;
			}
		}
		return -1;
	}
	
}

tensorflow在AMD上用ROCm框架实现GPU训练

Posted on

众所周知，a卡对于tensorflow gpu的支持很小，要想使用的话一般都得配n卡的电脑。而我只是感兴趣一个项目，想要跑出来一个模型，如果不用gpu加速，可能得跑一个月，所以不得不寻找在a卡上的解决方案。好在，终于找到了一个解决方案，虽然只是取巧，速度也不如正常n卡跑的快，但已经很不错了。

1
2
3
4
我的配置：
显卡：RX 550
所用系统：虚拟机ubuntu 18
注：如果是虚拟机的话，最好分配3GB内存或以上，否则可能无法import tensorflow

a卡上支持的ROCm框架，暂时只支持ubuntu系统。如果你是windows系统，可以安一个虚拟机，道理是一样的，我也是在虚拟机上跑的。要注意，你的AMD显卡是否支持ROCm框架，请参考以下链接确定你的显卡是否支持。https://rocm.github.io/hardware.html 。还有你的工程如果不是python3.5\3.6,你也用不了。

如果条件都符合，就可以开始愉快的安装了。（变通的法子就是费劲儿。。。）

更新系统

建议：把源换为国内的，比如阿里的，会快很多的。

1
2
sudo apt update
sudo apt upgrade

安装ROCm

添加ROCm库（没有这一步，会提示找不到 软件包）

1
2
wget -qO - http://repo.radeon.com/rocm/apt/debian/rocm.gpg.key | sudo apt-key add -
sudo sh -c 'echo deb [arch=amd64] http://repo.radeon.com/rocm/apt/debian/ xenial main > /etc/apt/sources.list.d/rocm.list'

安装必要的软件包

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
sudo apt update && sudo apt install -y \
  build-essential \
  clang \
  clang-format \
  clang-tidy \
  cmake \
  cmake-qt-gui \
  ssh \
  curl \
  apt-utils \
  pkg-config \
  g++-multilib \
  git \
  libunwind-dev \
  libfftw3-dev \
  libelf-dev \
  libncurses5-dev \
  libpthread-stubs0-dev \
  vim \
  gfortran \
  libboost-program-options-dev \
  libssl-dev \
  libboost-dev \
  libboost-system-dev \
  libboost-filesystem-dev \
  rpm \
  wget

安装ROCm驱动

1
2
3
4
5
6
7
8
9
sudo apt update && \
    sudo apt install -y --allow-unauthenticated \
    rocm-dkms rocm-dev rocm-libs \
    rocm-device-libs \
    hsa-ext-rocr-dev hsakmt-roct-dev hsa-rocr-dev \
    rocm-opencl rocm-opencl-dev \
    rocm-utils \
    rocm-profiler cxlactivitylogger \
    miopen-hip miopengemm

提示：rocm-dkms这一步下载的非常的慢，也和你的网络状况相关，我下的时候慢的时候10几k，快的时候有200。一共大概要下载500m,耐心等待一下吧。

添加用户

1
2
sudo adduser $LOGNAME video
sudo reboot

安装miniconda（体积小、方便）

在使用python时我们很多时候会用到conda，但是conda会改变python的一些配置。所以我们先安装conda，这样就不会出现在使用tensorflow时需要使用/usr/bin/python3这样的命令。

下载地址（64位）：https://mirrors.tuna.tsinghua.edu.cn/anaconda/miniconda/Miniconda3-latest-Linux-x86_64.sh

1
2
3
cd 下载目录
chmod +x ./Miniconda3-latest-Linux-x86_64.sh
bash Miniconda3-latest-Linux-x86_64.sh

这一步安装的时候，会让你先阅读一个license，按enter到一个栏让你选择输入yes/no，当然选yes，然后进入下一步是选择安装路径，如果选择默认路径，就按enter，然后就会出现安装的信息，安装好之后会退出来。可以新建一个终端，验证一下是否安装成功：

1
2
3
4
5
6
7
8
9
10
11
12

conda -h

#输出以下信息就是成功了

usage: conda [-h] [-V] command ...

conda is a tool for managing and deploying applications, environments and packages.

Options:

.....

ROCm版的tensorflow仅支持3.5和3.6，我的项目也是3.6的，所以需要新建一个环境。

1
conda install python=3.6

安装python相关的软件包

1
2
3
4
5
6
7
8
9
sudo apt update && sudo apt install -y \
    python3-numpy \
    python3-dev \
    python3-wheel \
    python3-mock \
    python3-future \
    python3-pip \
    python3-yaml \
    python3-setuptools

安装TensorFlow

1
pip3 install --user tensorflow-rocm -i https://pypi.tuna.tsinghua.edu.cn/simple

下载的速度很快。之后就可以验证是否成功了。

1
2
3
4
5
python

import tensorflow as tf

tf.__version__

如果import没报错，然后最后输出了tensorflow的版本，我的是1.14.1。说明一切顺利，可以愉快的开始玩耍了。

import tensorflow这一句我碰到了两个bug，给大家贴出来，避一避。

1.ImportError: librccl.so: cannot open shared object file: No such file or directory During handling of the above exception, another exception occurred:

解决：Google到的。输入以下命令，安装这些包。

1
sudo apt-get update &&  sudo apt-get install -y --allow-unauthenticated  rocm-dkms rocm-dev rocm-libs rccl  rocm-device-libs  hsa-ext-rocr-dev hsakmt-roct-dev hsa-rocr-dev  rocm-opencl rocm-opencl-dev  rocm-utils  rocm-profiler cxlactivitylogger  miopen-hip miopengemm

2.terminate called after throwing an instance of ‘std::bad_alloc’ what(): std::bad_alloc 已放弃 (核心已转储)

解决：Google一下，你就知道。这句话的意思是虚拟机内存分配的不够，我原来只分配了2G的内存，加到3G以后，再import tensorflow就好用啦。

希望这个教程能帮助到大家，也希望大家都可以用a卡跑gpu。更简单的方法还是换电脑啊。。。。

Veirlog学习记录(1)--十进制计数器

Posted on

 最近在学校上FPGA这门课，课上做了一些小实验，现在记录一下。
我所使用的软件是vivado2015.4

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
module M10_counter(
    input EN,   //使能端
    input CP, //时钟
    input Rd, //清零
    output reg Cout, //进位
    output reg [3:0] Q //输出
    );
    
always @ (posedge CP,negedge Rd)
if(~Rd) Q<=4'b0000;  //异步清零
else if(EN) begin
    if(Q<4'b1001) Q<=Q+1'b1; //加计数
    else Q<=4'b0000;
end
else Q<=Q;
   always @ (Q)
    if(Q==4'b1001) Cout =1; //进位
    else Cout=0;
    
endmodule

测试文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
module M10_counter_tb();
    reg EN,CP,Rd;
    wire Cout;
    wire [3:0] Q;
    M10_counter test(.EN(EN),
                     .CP(CP),
                     .Rd(Rd),
                     .Cout(Cout),
                     .Q(Q)  );
        initial fork
            CP=0;
            EN=1; #20 EN=0; #50 EN=1;
            Rd=0; #30 Rd=1;
           join
           always #8 CP=~CP;
endmodule

仿真图：

同理可以改成任意进制，或者是可以改成减计数。

希望会对你有所启发。

更多内容可访问：

Verilog学习

解决java.lang.UnsatisfiedLinkError：java.library.path中没有rxtxSerial加载时抛出gnu.io.RXTXCommDriver错误

Posted on

 在使用Java接收串口数据的时候，需要导入有关的jar包和配置文件。
如果报这个错误，是因为jar包和配置文件没有放好的原因。
解决：要把.rxtxParallel.dll、rxtxSerial.dll拷贝到

1
D:\develop\Java\jdk1.7.0_72\bin

​ 注意：是jdk下面的bin文件夹，不是jre
需要什么版本的配置文件，看你的JDK，如果是32位的就下载32位的，如果是64位的就下载64位的，一定要对应好，否则也会报错。下载地址如下：
官网下载地址

解决在cmd编译java文件后，提示找不到或无法加载主类

Posted on

​ 最近在命令行中编译java文件，编译没有问题，却在运行的时候出现了却提示找不到或无法加载主类的报错，如下图所示。

​ 一开始我觉得是版本的问题。因为我一开始装的jdk版本是1.8，现在要用1.7的。上网搜索后，有很多办法，有的说是没加package名，还有说classPath的问题，不过都解决不了问题。后来发现如下方式可以解决：

在cmd中输入命令：

1
SET CLASSPATH=.

​ （等号后为英文点符号），即可设置解释的路径为当前路径。

​ 再次运行java xxx即可。

效果如下：

解决IntellijIDEA输入法不跟随的问题

Posted on

我在这里介绍一个非常简单的办法，非常好用。我的是2018.1.6，亲测有效，大家也可以试试，用不了一分钟就可以解决问题。

找到你idea的安装目录，然后

就是把jre那个目录重命名一下，像我一样在后面加一串数字即可。

我的弄完以后，效果如下。


希望对大家有所帮助，谢谢大家。

© 2025 XuXing's blog All Rights Reserved. 本站访客数人次 本站总访问量次
Theme by hiero