算法
5 分钟 读完 (大约 728 个字)

位图法排序(编程珠玑)

问题

输入

一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。

输出

按升序排列的输入正数的列表。

约束

最多有1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化。

解决思路

应用位图或位向量表示集合。可用一个32位长的字符串来表示一个简单的非负整数，例如，可以用如下字符串表示集合{1,2,4,5,8}。

1
01101100100

32位字符串位表示：0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
32位字符串位下标：0 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
数值的位都置为1，其他所有的位置为0。编程珠玑当中建议一个具有1000万个位的字符串来表示这个文件，那么这个文件的所占容量为10000000 bit= $10^7$bit，不到1MB的大小。
分三个阶段来编写程序。

  • 第一阶段：将所有的位都置为0，从而将集合初始化为空。
  • 第二阶段：将每个对应的位置都置为1。
  • 第三阶段：检验每一位，如果该为为1，就输出对应的整数，有此产生有序的输出文件。（通过&运算来比较是否为1）

int数组的存储位置：位置=数据/32(采用位运算即右移5位)
int数组元素的位位置：位位置=数据%32(采用位运算即跟0X1F进行与操作)
int数组如下所示，int大小：32位，从0开始。数组中每一个元素就是一个int，所以有长度是32位。

阅读更多
算法
4 分钟 读完 (大约 551 个字)

旋转交换(编程珠玑)

问题

请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8,i=3，那么向量abcdefgh旋转之后得到向量defghabc。简单编码使用一个具有n个元素的中间向量分n步即可完成此作业。你可以仅使用几十字节的微小内存，花费与n成比例的时间来旋转该向量吗？

解决思路

方法1

将向量x中的前i个元素复制到一个临时数组中，接着将余下的n-i个元素左移i个位置，然后再将前i个元素从临时数组中复制回x中的后面位置。
该方案使用i个额外的位置，如i足够大，过于浪费空间。

方法2

将这个问题看作是把数组ab转换成数组ba吧，但同时也假定我们具有在数组中转置指定部分元素的函数。我们先从ab开始，转置a得到$a^rb$，再转置b得到$a^rb^r$，然后再转置整个$a^rb^r$得到$(a^rb^r)^r$，实际上就是ba。

  • reverse(0, i-1)
  • reverse(i, n-1)
  • reverse(0, n-1)

该转置代码在时间和空间上都很有效，并且是这么简短和简单，想出错都很难。

阅读更多
书
17 分钟 读完 (大约 2621 个字)

第14章-类型的信息RTTI

以JDK6为例

介绍

RTTI运行时类型信息使得可以在程序运行时发现和使用类型信息。

Run-Time Type Information

使用方式

Java是如何在运行时识别对象和类的信息的，主要有两种方式（还有辅助的第三种方式，见下描述）

  1. “传统的”RTTI，它假定在编译时已经知道所有的类型，比如Shape s = (Shape)s1；
  2. “反射”机制，它运行在运行时发现和使用类的信息，即使用Class.forName()。
  3. 关键字instanceof，它返回一个bool值，它保持类型的概念，它指的是”你是这个类吗？或者你是这个类的派生类吗？”。而如果用==或equals比较实际的Class对象，就没有考虑继承它或者是这个确切的类型，或者不是。

    工作原理

    RTTI主要用来运行时获取对象到底是什么具体的类型。
    RTTI运行的时候，识别一个对象的类型。（运行的时候获取对象确切的类型）
    要理解RTTI在Java中的工作原理，首先必须知道类型信息在运行时是如何表示的，这项工作是由称为Class对象的特殊对象完成的，它包含与类有关的信息。Java Class对象来执行其RTTI，使用类加载器的子系统实现。
    类是程序的重要组成部分，每个类都有一个Class对象，每当编写并编译一个新类就会产生一个Class对象，它被保存在一个同名的.class文件中。在运行时，生成这个类的对象时，运行这个程序的Java虚拟机（JVM）会确认这个类的Class对象是否已经加载，如果尚未加载，JVM就会根据类名查找.class文件，并将其载入，一旦这个类的Class对象被载入内存，它就被用来创建这个类的所有对象。
    在运行时使用类型信息，就必须首先获得对恰当的Class对象的引用，获取方式有三种。

    第1种

    如果没有持有该类型的对象，则Class.forName()就是实现此功能的便捷途，因为它不需要对象信息。

    第2种

    如果已经拥有类型的对象，那就可以通过调用getClass()方法来获取Class引用，它将返回表示该对象的实际类型的Class引用。
阅读更多
Java
35 分钟 读完 (大约 5302 个字)

线程安全和锁机制

概念

临界区

临界区指的是一个访问共用资源（例如：共用设备或是共用存储器）的程序片段，而这些共用资源又无法同时被多个线程访问的特性。当有线程进入临界区段时，其他线程或是进程必须等待（例如：bounded waiting等待法），有一些同步的机制必须在临界区段的进入点与离开点实现，以确保这些共用资源是被互斥获得使用。只能被单一线程访问的设备，例如：打印机。

互斥量

互斥量是一个可以处于两态之一的变量：解锁和加锁。
这样，只需要一个二进制位表示它，不过实际上，常常使用一个整型量，0表示解锁，而其他所有的值则表示加锁。互斥量使用两个过程。当一个线程（或进程）需要访问临界区时，它调用mutex_lock。如果该互斥量当前是解锁的（即临界区可用），此调用成功，调用线程可以自由进入该临界区。
另一方面，如果该互斥量已经加锁，调用线程被阻塞，直到在临界区中的线程完成并调用mutex_unlock。如果多个线程被阻塞在该互斥量上，将随机选择一个线程并允许它获得锁。

阅读更多
并发
18 分钟 读完 (大约 2746 个字)

线程安全

核心概念

原子性

原子性是指不可再分的最小操作指令，即单条机器指令，原子性操作任意时刻只能有一个线程，因此是线程安全的。
Java内存模型中通过read、load、assign、use、store和write这6个操作保证变量的原子性操作。
这一点，跟数据库事务的原子性概念差不多，即一个操作（有可能包含有多个子操作）要么全部执行（生效），要么全部都不执行（都不生效）。 就是原子性说一个操作不可以被中途CPU暂停然后调度, 即不能被中断, 要不就执行完, 要不就不执行。
一个不正确的知识：“原子操作不需要进行同步控制”。

原子操作

是不能被线程调度机制中断的操作，一旦操作开始，那么它一定可以在可能发生中断之前执行完毕。
原子性可以应用于基本数据类型（除了long和double），对于写入和读取，可以把它们当作原子操作来操作内存。但是，long和double这两个64位长度的数据类型Java虚拟机并没有强制规定他们的read、load、store和write操作的原子性，即所谓的非原子性协定，但是目前的各种商业Java虚拟机都把long和double数据类型的4中非原子性协定操作实现为原子性。所以Java中基本数据类型的访问读写是原子性操作。
对于大范围的原子性保证需要通过lock和unlock操作以及synchronized同步块来保证。

例子

比如A和B同时向C转账10万元。如果转账操作不具有原子性，A在向C转账时，读取了C的余额为20万，然后加上转账的10万，计算出此时应该有30万，但还未来及将30万写回C的账户，此时B的转账请求过来了，B发现C的余额为20万，然后将其加10万并写回。然后A的转账操作技术——将30万写回C的余额。这种情况下C的最终余额为30万，而非预期的40万。

阅读更多
算法
1 小时 读完 (大约 8947 个字)

排序算法

排序

内部排序：待排序的元素总数相对于内存而言较小，整个排序过程可以在内存中进行。
外部排序：待排序的元素总数较多，不能全部放入内存，排序过程中需要访问外存。
内部排序算法有很多，各有其优缺点和适合的场合。
排序的稳定性：如果在排序的序列中，存在前后相同的两个元素的话，排序前和排序后他们的相对位置不发生变化。

稳定性的定义

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，$r_i$=$r_j$，且$r_i$在$r_j$之前，而在排序后的序列中，$r_i$仍在$r_j$之前，则称这种排序算法是稳定的；否则称为不稳定的。
对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

稳定性的意义

  • 如果只是简单的进行数字的排序，那么稳定性将毫无意义。
  • 如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义。
  • 如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。
  • 除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。

    稳定排序

    基数排序、冒泡排序、直接插入排序、两两插入排序、归并排序。

    不稳定排序

    堆排序、快速排序、希尔排序、简单选择排序。

    直接插入排序

    基本思想

    将数组中第1个元素作为有序序列，然后将剩下的n-1数组元素，按照顺序插入第1个元素的序列中。
    插入第1个元素后，第1个元素的序列保持有序。
    将待插入有序序列的元素存入临时变量temp中，在有序序列从后往前比较大小，查找插入的位置。
    当temp小于有序序列的元素时，该有序序列元素往后移1位，temp元素继续比较。
    直到有序序列中有元素比temp小、或者到有序序列第1个元素时结束，这时将temp插入有序序列元素的位置。
    插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下(给定的数组恰好为倒序)插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ，这种极端情况下，插入排序的效率甚至比选择排序更差。

    时间复杂度

    最好情况比较次数是O(n)(有序)，最坏情况比较次数O(n*n)无序。

    空间复杂度

    O(1)每次都交换一个元素

    稳定性

    插入排序是稳定排序，如果碰到相等的元素，就把新元素插入相等元素的后面，即他们原来的顺序没有变化。（插入排序在全部元素插入完毕之前，都不能确定最终一个元素的位置）temp < A[j - 1]，如果改成temp <= A[j - 1]，则是不稳定排序。

    Java

阅读更多
Java
9 分钟 读完 (大约 1371 个字)

Java Copy-On-Write并发优化策略

基础知识

Copy-On-Write简称COW，是一种用于程序设计中的优化策略。
开始都在共享同一个内容，当想要修改这个内容的时候，才会真正把内容Copy出去形成一个新的内容然后再改，这是一种延时懒惰策略。

CopyOnWrite容器

CopyOnWrite容器即写时复制的容器。通俗的理解：往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。（但是读取的数据会有延迟）所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。目的是为了提高并发能力。

阅读更多
并发
5 分钟 读完 (大约 761 个字)

上下文切换和线程池

上下文分类

上下文切换是指CPU的控制权由运行任务转移到另外一个就绪任务时所发生的事件。

  • 高并发，低耗时的情况，上下文切换本来就多，并且高并发就意味着CPU是处于繁忙状态的， 增加更多地线程也不会让线程得到执行时间片, 反而会增加线程切换的开销。
  • 低并发，高耗时，保证有空闲线程或者增加线程数目，接收新任务，可以减少线程切换。

    让步式上下文切换

    指执行线程主动释放CPU，与锁竞争严重程度成正比（锁竞争严重，释放多），可通过减少锁竞争来避免。

    抢占式上下文切换

    后者是指线程因分配的时间片用尽而被迫放弃CPU或者被其他优先级更高的线程所抢占，一般由于线程数大于CPU可用核心数引起，可通过调整线程数，适当减少线程数来避免。

    线程池

    关键点

  • 尽量减少线程切换和管理的开支：要求线程数尽量少，这样可以减少线程切换和管理的开支。
  • 最大化利用CPU：要求尽量多的线程，以保证CPU资源最大化的利用。
阅读更多
Java
30 分钟 读完 (大约 4500 个字)

Java Class文件的结构(实践篇)

实例

首先有一个TestClass类，代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package com.ejushang.TestClass;

public class TestClass implements Super {
	private static final int staticVar = 0;
	private int instanceVar = 0;

	public int instanceMethod(int param) {
		return param + 1;
	}

}

interface Super {
}

通过jdk1.6.0_37的javac编译后的TestClass.java对应的TestClass.class的二进制结构如下。
TestClass.class
用WinHex工具查看字节码。

阅读更多
Java
1 小时 读完 (大约 8999 个字)

Java Class文件的结构(理论篇)


学习Java的朋友应该都知道Java从刚开始的时候就打着平台无关性的旗号，说“一次编写，到处运行”，其实说到无关性，Java平台还有另外一个无关性那就是语言无关性，要实现语言无关性，那么Java体系中的class的文件结构或者说是字节码就显得相当重要了，其实Java从刚开始的时候就有两套规范，一个是Java语言规范，另外一个是Java虚拟机规范，Java语言规范只是规定了Java语言相关的约束以及规则，而虚拟机规范则才是真正从跨平台的角度去设计的。今天我们就以一个实际的例子来看看，到底Java中一个Class文件对应的字节码应该是什么样子。 这篇文章将首先总体上阐述一下Class到底由哪些内容构成，然后再用一个实际的Java类入手去分析class的文件结构。

阅读更多
关注我

链接

分类

标签云

Android Centos Effect Java JDK6 源码 JDK7 源码 JDK8 源码 JMM JVM Java Linux MongoDB Mongodb MyBatis MySQL Redis Spring Think In Java Tomcat Ubuntu 一致性哈希算法 书 倒排索引 内存泄漏 分支限界算法 分治法 分治算法 分词算法 动态规划 动态规划算法 华为 回溯算法 多线程 工具 并发 开源项目 手机游戏 排序算法 推荐 散列表 数学 数据库 数据结构 日语 最优路径算法 机器学习 源码 算法 线程安全 编程珠玑 计算机基础 设计模式 贪心算法 跳表 面试

最新文章

归档

标签

Android 1
Centos 3
Effect Java 2
JDK6 源码 18
JDK7 源码 6
JDK8 源码 1
JMM 7
JVM 10
Java 40
Linux 4
MongoDB 1
Mongodb 1
MyBatis 3
MySQL 2
Redis 1
Spring 4
Think In Java 1
Tomcat 7
Ubuntu 1
一致性哈希算法 1
书 3
倒排索引 1
内存泄漏 1
分支限界算法 2
分治法 1
分治算法 1
分词算法 2
动态规划 1
动态规划算法 2
华为 1
回溯算法 4
多线程 2
工具 1
并发 5
开源项目 17
手机游戏 1
排序算法 1
推荐 1
散列表 1
数学 1
数据库 2
数据结构 5
日语 1
最优路径算法 1
机器学习 1
源码 3
算法 26
线程安全 2
编程珠玑 3
计算机基础 1
设计模式 4
贪心算法 3
跳表 1
面试 1

最新文章

归档

标签

Android 1
Centos 3
Effect Java 2
JDK6 源码 18
JDK7 源码 6
JDK8 源码 1
JMM 7
JVM 10
Java 40
Linux 4
MongoDB 1
Mongodb 1
MyBatis 3
MySQL 2
Redis 1
Spring 4
Think In Java 1
Tomcat 7
Ubuntu 1
一致性哈希算法 1
书 3
倒排索引 1
内存泄漏 1
分支限界算法 2
分治法 1
分治算法 1
分词算法 2
动态规划 1
动态规划算法 2
华为 1
回溯算法 4
多线程 2
工具 1
并发 5
开源项目 17
手机游戏 1
排序算法 1
推荐 1
散列表 1
数学 1
数据库 2
数据结构 5
日语 1
最优路径算法 1
机器学习 1
源码 3
算法 26
线程安全 2
编程珠玑 3
计算机基础 1
设计模式 4
贪心算法 3
跳表 1
面试 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×