数据结构与算法
大家都知道选择合适的数据结构将会显著地提升代码的性能。即使是像数组和集合这样相似的两种数据结构，在高负荷的运行环境下也会表现得天差地别。但是就算数据结构确定了，代码的速度也还会受另一重要因素影响，那就是算法。
那么数据结构与算法，到底难吗?说实话，难，因为很抽象，也复杂，再加上我们的思维定式，没有形成系统化的学习与练习，很多人呐，这块都是短板，尤其新手这块，知道这块重要，但是完全摸不着头脑。这些虽然是难啃的点，但是要吃透下面这份字节内部笔记这些都是小问题，这份笔记用浅显易懂的方式介绍了数据结构与算法基础知识，摒弃了传统参考书中复杂的数学公式与理论，很适合期望提高编程水平的程序员。
为了不影响大家阅读体验我把获取方式放在了文末！！！
第1章和第2章,解释数据结构和算法是什么,并探索时间复杂度这一判断算法效率的概念。
第1章 数据结构为何重要
- 基础数据结构:数组
- 集合:一条规则决定性能
第2章 算法为何重要
- 有序数组
- 查找有序数组
- 二分查找
- 二分查找与线性查找
第3~6章，以老奶奶都听得懂的方式去揭示大О记法的本质。以及进一步探索大O记法，并以实例来演示如何利用它来加快代码运行速度。还会提到各种排序算法，包括冒泡排序、选择排序和插入排序。
第3章 大O记法
- 大O:数步数
- 常数时间与线性时间
- 同—算法，不同场景
- 第三种算法
- 对数
- 解释O(log N)
- 实例
第4章 运用大O来给代码提速
- 冒泡排序
- 冒泡排序实战
- 冒泡排序的实现
- 冒泡排序的效率
- 二次问题
- 线性解决
第5章 用或不用大O来优化代码
- 选择排序
- 选择排序实战
- 选择排序的实现
- 选择排序的效率
- 忽略常数
- 大O的作用
- 一个实例
第6章 乐观地调优
- 插入排序
- 插入排序实战
- 插入排序的实现
- 插入排序的效率
- 平均情况
- 一个实例
第7、8章探讨几种数据结构，包括散列表、栈和队列，展示它们对代码速度和可读性的影响，并学会用其解决实际问题。
第7章 查找迅速的散列表
- 探索散列表
- 用散列函数来做散列
- 一个好玩又赚钱的同义词典
- 处理冲突
- 找到平衡
- 一个实例
第8章 用t栈和队列来构造灵巧的代码
- 栈
- 栈实战
- 队列
- 队列实战
- 总结
- 递归
- 用递归代替循环
- 基准情形
- 阅读递归代码
- 计算机眼中的递归
- 递归实战
第9章介绍递归，计算机科学中的核心概念。我们会对其进行分解，考察它在某些问题上的利用价值。
第9章 递归
- 分区
- 快速排序
- 快速排序的效率
- 最坏情况
- 快速选择
第10章运用递归来实现一些飞快的算法，例如快速排序和快速选择，提升大家的算法开发能力。
第10章 飞快的递归算法
- 分区
- 快速排序
- 快速排序的效率
- 最坏情况
- 快速选择
第11~13章探索基于结点的数据结构，包括链表、二叉树和图，并展示它们在各种应用中的完美表现。
第11章 基于结点的数据结构
- 链表
- 实现一个链表
- 读取
- 查找
- 插入
- 删除
- 链表实战
- 双向链表
第12章 让—切操作都更快的二叉树
- 二叉树
- 查找
- 插入
- 删除
- 二叉树实战
第13章 连接万物的图
- 图
- 广度优先搜索
- 图数据库
- 加权圈
- Dijkstra算法
第14章，介绍空间复杂度。当程序运行环境的内存空间不多，或处理的数据量很大时，理解空间复杂度便显得特别重要。
第14章 对付空间限制
- 描述空间复杂度的大O记法
- 时间和空间之间的权衡
最后
编程基础的初级开发者，计算机科学专业的学生，以及平时没怎么利用过数据结构与算法的开发人员希望复习这些概念为下次技术面试做准备。或者想学习一些计算机科学的基本概念，以优化代码，提高编程技能。这份笔记都是可以作为参考的。
需要这份数据结构与算法笔记的老哥，帮忙评论加转发然后私信【666】即可获取
问题描述
给定一个文件长度为 ，现在要求读取长度为 的内容，当 时，只读取 个字节，当 时，循环读取文件进行填充， 直到读取 填充满为止。
解决办法
可以利用
FileInputStream的read(byte[], start, length)方法来解决，因为这个函数返回读取到的数据长度。实现代码如下所示。public static byte[] readBytes(String file, int maxsize) throws Exception { byte[] bts = new byte[maxsize]; FileInputStream fs = new FileInputStream(file); int left = maxsize, p = 0; while (left > 0) { p += fs.read(bts, maxsize - left, left); left -= p; } fs.close(); return bts; }
原文链接：点击打开链接
避免原文打不开，记录如下：
背景：
本人因为某Android项目需要，需要在Android中定义一个容量为2万的float数组。这两万个float值已经存在某个文件中。
方法：1.直接在Java文件里定义？Java单个函数的长度限制为65535字节（不确定具体数值，但肯定是有限制的）。故在Java文件中直接定义如此之长的数组是行不通的。
2. BufferedReader 或是 Scanner？可以创建一个文件，每行存放一个float值。通过BufferedReader.nextLine()读取每一行的字符，用Float.parseFloat(String)来将读到的字符转换成float值，最后将float值存取至数组里。也可以通过Scanner.nextFloat()这样的方法来读取文件中存放的float值。这个时候，文件里并不需要将每个float值放在单独的一行里。但是不同的float值至少需要以某些符号隔开（例如，空格）。
经过对比，通过BufferedReader读取2W个float值比较快，使用Scanner会占用大量内存，并且不断调用GC，导致线程暂停。但是，当要读取的文件很大的时候，即使使用BufferedReader也会出现问题：在低端的机子上运行时，Logcat会出现OutOfMemory的错误提示。
3. 将2万个float值写入文件后做Java的内存映射。Java内存映射网上的文章不多，可以参考：http://www.javacodegeeks.com/2013/05/power-of-java-memorymapped-file.html和http://www.studytrails.com/java-io/Channels.jsp。这种方法，需要先将所有float值以byte的形式写入到文件中。接着，使用FileChannel将文件中的byte映射到内存中，生成FloatBuffer。最后在FloatBuffer中读取float值存至float数组中。在通过经测试，这种方法比BufferedReader快很多。但是如果算上写文件的时间的话，不如BufferedReader来得方便。
大家可以借鉴一下我测试对比所用的源码。第一个部分，我使用Scanner；第二个部分，我使用BufferedReader；第三部分，我将第二部分读取到的float值以byte形式存取至文件中；第四部分，我使用MappedByteBuffer将文件中的内容映射至内存，并生成新的float数组。
源码下载地址：https://db.tt/9jCbO653
以下是结果运行截图：
当然，以上测试程序均在PC java端运行。真正要移植到Android上进行内存映射，还需要：1. 由于从assets里读文件只能获取InputStream，而调用FileChannel.map()必须从FileInputStream中获得，故需要将assets里的内存映射文件转移至sd卡上后再从sd卡上读取它们。2.在测试文件中，我使用了DataOutputStream.writeFloat()将float数组写入内存映射文件。该方法写入遵循BIG_ENDIAN规则。故当进行内存映射的时候，很有可能是以LITTLE_ENDIAN的方法读取的（这还要看你是如何实现内存映射的）。
以下这段代码，给出了如何将一个存好的float数组（cubeTextureCoordinateData）以LITTLE_ENDIAN的方式写入内存映射文件：
/* Writing Memory Map Raw Data */
ByteBuffer littleEndian = ByteBuffer.allocateDirect(11160 * 4).order(ByteOrder.LITTLE_ENDIAN);
i = 0;
while (i < 11160) {
littleEndian.putFloat(cubeTextureCoordinateData[i++]);
}
littleEndian.flip();
try {
FileOutputStream fos = new FileOutputStream("memorymap_texture_little_endian");
FileChannel fc = fos.getChannel();
fc.write(littleEndian);
fc.close();
fos.close();
} catch (IOException e) {
e.printStackTrace();
}
Power of Java MemoryMapped File
In JDK 1.4 an interesting feature of Memory mapped file was added to Java, which allows to map any file to OS memory for efficient reading. A memory mapped file can be used to develop an IPC type of solution. This article is an experiment with memory mapped file to create IPC.
Some details about Memory Mapped File, definition from WIKI
A memory-mapped file is a segment of virtual memory which has been assigned a direct byte-for-byte correlation with some portion of a file or file-like resource. This resource is typically a file that is physically present on-disk, but can also be a device, shared memory object, or other resource that the operating system can reference through a file descriptor. Once present, this correlation between the file and the memory space permits applications to treat the mapped portion as if it were primary memory.
Sample Program
Below we have two Java programs, one is a writer and the other is a reader. The writer is the producer and tries to write to Memory Mapped file, the reader is the consumer and it reads messages from the memory mapped file. This is just a sample program to show you the idea, it does’t handle many edge cases but it is good enough to build something on top of a memory mapped file.
MemoryMapWriter
MemoryMapReader
Observation
Using a memory mapped file can be a very good option for developing Inter Process communication, throughput is also reasonably well for both produce & consumer. Performance stats by run producer and consumer together:
Each message is one long number
Produce – 10 Million message – 16(s)
Consumer – 10 Million message 0.6(s)
A very simple message is used to show you the idea, but it can be any type of complex message, but when there is complex data structure then serialization can add to overhead. There are many techniques to get over that overhead. More in next blog.
Java NIO - Channels and Memory mapping
Channel Classes
A FileChannel is used to read and write data to a file. It implements seekableByteChannel, ScatteringByteChannel and GatheringByteChannel. It is possible to map a region of file directly into memory. Data can be transferred to another channel or from another channel using the transferTo(..) and transferFrom(..) methods. These methods use the underlying optimization of the operating system. File locking can be applied to manage access between multiple processes. The methods are thread safe and a thread that wishes to modify the position may be blocked until another thread is acting upon the file.
Data from a File Channel can be read into multiple buffers. This is known as a scatter read. Here's and example demonstrating a scatter read.
|
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
35
36
37
38
|
//
create a temp filePath
tempFile =Files.createTempFile("fileChannelExample", "txt",new
FileAttribute<?>[0]);//
write some data to this filePrintWriter
writer = new
PrintWriter(tempFile.toFile());writer.println("First
Line");writer.println("Second
Line");writer.println("Third
Line");writer.close();//
get an input stream for this file.FileInputStream
in = new
FileInputStream(tempFile.toFile());//
get the fileChannel for this input streamFileChannel
fileChannel = in.getChannel();//
get the positionSystem.out.println(fileChannel.position());//print
0//
create a char bufferByteBuffer
buffer = ByteBuffer.allocate(11);//
read the fist line - 10 characters into the byte bufferfileChannel.read(buffer);//
get the position of the fileSystem.out.println(fileChannel.position());//
prints 11//
we have read the first 10 chars into the buffer now. find out the//
total size of the fileSystem.out.println(fileChannel.size()); //
prints 37//
we read the next 27 characters in two buffers using a scattering readByteBuffer
buffer1 = ByteBuffer.allocate(14);ByteBuffer
buffer2 = ByteBuffer.allocate(12);fileChannel.read(new
ByteBuffer[] { buffer1, buffer2 });//
lets see the contents of the buffersbuffer1.flip();buffer2.flip();System.out.print(Charset.defaultCharset().decode(buffer1)); //
prints "Second Line"System.out.print(Charset.defaultCharset().decode(buffer2));//
prints "Third Line"fileChannel.close(); |
we can write the bytes back to the file using a scattering write. The filechannel was created on the inputstream so the channel is only readable but not writable. we create a filechannel from an output stream
|
1
2
3
4
5
6
7
8
9
10
11
|
FileOutputStream
out = new
FileOutputStream(tempFile.toFile()); FileChannel
fileOutputChannel = out.getChannel(); ByteBuffer
buffer3 = Charset.defaultCharset().encode( CharBuffer.wrap("Line1\n".toCharArray())); ByteBuffer
buffer4 = Charset.defaultCharset().encode( CharBuffer.wrap("Line2".toCharArray())); fileOutputChannel.write(new
ByteBuffer[] { buffer3, buffer4 }); //
we force the update to the file fileOutputChannel.force(true); //
lets look at the position in the file System.out.println(fileOutputChannel.position()); |
Java NIO allows reading huge files directly from the memory. i.e. The file need not be loaded into the JVM. All reads and writes on the byte buffer happen direclty on the file.
|
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
|
import
java.io.File;import
java.io.IOException;import
java.io.RandomAccessFile;import
java.nio.MappedByteBuffer;import
java.nio.channels.FileChannel;public
class
ReadingHugeFilesUsingMemoryMappedBuffer { /** *
use a MappedByteBuffer to wrap a huge file. Using a MappedByteBuffer does *
not load the file in JVM but reads it directly off the file system *
memory. The file can be opened in read, write or private mode. */ //
to test you can use any video movie file if you dont have any other large //
file for testing. private
static
String hugeFile = "A
Huge File"; public
static
void
main(String[] args) throws
IOException { File
file = new
File(hugeFile); FileChannel
fileChannel = new
RandomAccessFile(file, "r").getChannel(); MappedByteBuffer
buffer = fileChannel.map( FileChannel.MapMode.READ_ONLY, 0,
fileChannel.size()); //
the buffer now reads the file as if it were loaded in memory. note //
that for smaller files it would be faster //
to just load the file in memory //
lets see if this buffer is loaded fully into memory System.out.println(buffer.isLoaded()); //
the mappedbytebuffer can be used as a normal buffer to do read and/or //
write operations //
read the size System.out.println(buffer.capacity()); }} |
1.数组的作用
char int float double 只能存放单个类型的数据
数组用来保存多个相同类型的数据
2.数组如何定义
在定义一个数组是必须要能确定数组的元素个数
eg.//定义一个数组，拥有5个元素 默认每个元素的值为0
int numsArray[5]; 占用5*4=20个字节
//定义一个数组，拥有4个元素，一次是1，2，3，4
int numsArray[]={1,2,3,4}; 占用4*4=16个字节
//定义一个数组，拥有五个元素，第一个值是1，第二个值是2，后面默认为0
int numsArray[5]={1,2}; 占用5*4=20个字节
3.如何访问数组中的元素
//数组的索引值从0开始
注意：当索引值超过数组的个数时，就越界了!
转载于:https://www.cnblogs.com/hmzxwky/p/5028836.html
