算法1-比赛出线问题


足球比赛,一个小组有8支球队进行单循环赛,胜者积3分,平则算法同积1分,负则不积分,规定积分最高的4支球队出线,则出线至少需要多少分?未出线最多可能有多少分?

循环赛的概念是每一支球队会与其他所有球队各进行一场比赛。8支球队共进行8*7/2=28场比赛。


1、出线至少需要多少分?

  • 我的解释:分数最少还要出线,所以优先输掉比赛,其次是打平。所以输掉3场,也就是输给了3个队(输给4个队,就不能保证分数最少出线了)。然后和剩下的4个队打平,这样也就是有5支队伍都只有4个积分,剩下3支都赢了剩下的5支。这样,5个4分的队伍争第四名,则出线至少要4个积分

  • 别人的解释:赢得比赛积分最快,打平积分增长慢,输掉比赛积分不变。如果想以最少的积分赢,着眼点应该在第四名上。对于第四名,如果想要满足以最少的积分赢,那么他应该输给比他强的人(与第一名、第二名、第三名比赛不积分),与所有不如自己的人打平(与第五名、第六名、第七名、第八名比赛,每场积一分),这样,第四名得分最少为4分


2、未出线最多可能有多少分?

  • 我的解释: 不出线分数还要最多,所以优先赢得比赛,其次打平。所以赢3场(赢4场就不能保证分数最多还不出线了),也就是赢了3个弱队,与剩下的4个队都打平。这样一共5个强队,每个强队都赢了3个弱队,强队之间都赢2场输2场(强队之间打平的话4分,2输2赢要6分,所以优先赢),这样也就是3x3+2x3=15分,所以有5支15分的队来争取不要不出线。这样,不出线最多能拿15分。**

  • 别人的解释: 考虑第四名与第五名并列,积分相同(通过其他方式角逐第四名)。
    这样有五个强队(前五名),三个弱队(后三名),假设后三名的球队与前五名的球队比赛时,都输给前五名,这样,前五名的每一支球队通过与后三名的球队比赛都获得3x3=9分,前五名球队的比赛,每个球队会参加4场比赛,假设,每个球队都赢两场,负两场,那么前五只球队在这个过程中每人获得2x3=6分,加上与后三名比赛积分6+9=15分,前五名并列(通过其他方式角逐名次),未出线最多获得15分


0 Comments

《Deep Neural Networks for YouTube Recommendations》 -2016 RecSys-论文阅读

这是Google16年在RecSys大会上发表的一篇深度学习在youTube视频推荐上应用的论文,原文地址 点这里

本文主要专注在候选集生产网络的网络架构,如何负采样,如何训练视频的embedding,网络中的u的含义,最终网络学习到的是什么


论文里提到的洞察、还有youtube视频推荐算法考虑了哪些方面的问题等可自行阅读论文或下面的链接 用深度学习(DNN)构建推荐系统 - Deep Neural Networks for YouTube Recommendations论文精读


系统介绍

整个推荐系统包括了两个神经网络:候选集生成网络、排序网络。

对于每个用户,该算法先通过候选集生成网络从海量的视频库里选出几百个视频,然后通过排序网络从这几百个视频里,选择出最终推荐给用户的视频。

两阶段方法的好处:使得该算法可以适应大规模的数据,第一层候选网络的压力也没那么大,这样只需要不多的特征就可以完成候选任务,降低算法计算。在第二层,还可以利用以前的算法积累的经验和特征,用来精准的排序。


候选集生成网络

此处通过浅层网络来模拟矩阵分解算法,从这个角度,可以将候选集生成网络看成是一个泛化的非线性矩阵分解模型。

这里将候选集生成问题看成了一个极限的多分类的预测问题,视频库里的每个视频都是一个类别。

网络架构

这个网络采用塔型结构,特征先输入宽的第一层,后面全连接了多层的ReLU层,每层的ReLU单元数量减半。最后一层是256个ReLU,来连接256维的softmax。

训练时最后一层ReLU的结果是一个256维的用户向量u,训练时连接softmax分类器。上亿个视频向量V与u进行softmax计算,输出每个视频的可能性。按照可能性排序,选择前topN作为候选集。

softmax预测可能性的公式:

其中u代表了一个高维的用户、上下文信息的embedding向量,vj代表视频库里的每个视频id的embedding向量。公式计算结果表示基于上下文C,用户U最终在t时间看的一个视频wt是视频库里的视频i的可能性。

这个候选集网络是参考了Word2vec里的CBOW模型。CBOW模型结构如下:

负采样下的CBOW模型的理解可以参考 word2vec 中的数学原理详解(五)基于 Negative Sampling 的模型 - CSDN博客

这里参考一下 tesorflow wor2vec的skip-gram model的实现里的loss计算 word2vec_basic.py

这里的nce loss的计算参考 Tensorflow 的NCE-Loss的实现和word2vec - 简书

这两个看完,对cbow理解基本解决了。

cbow中间只有一层,中间层的输出是Xw,youtube在此基础上多加了几层。且输入不仅仅只有context的视频的embedding的均值,还包含了用户的context信息的embedding(这里的embedding可以提前训练好),视频年龄等特征

下面从cbow过渡到youtube,理解里面的细节

广义上,这里的u可以理解成cbow中的Xw,cbow中的theta参数就是视频的embedding。word2vec_basic.py里是单独申请的权重变量,这里视频的embedding和最后一层的参数是同一个。

注意:代码里为了实现视频的embedding和最后一层的nce权重参数是同一个,同时更新,采取了2个操作:
1,将输入的embedding在申请变量的时候,设置成不可训练,即不会加到optimizer的参数列表里,因此后向传播时不会被求梯度然后被更新,但是最后一层的NCE-权重参数会被更新
2,将更新的NCE-权重(其实是真正的视频embedding)重新赋值给输入的embedding变量。


以上就是对候选集生成网络的架构的理解。

正负样本的选取

  • 完成了某个视频,则该视频就是正样本。这里没有选择用户对推荐结果的显式反馈(比如用户对已推荐的视频的点赞行为)作为正样本,之所以没有这样,是因为隐式反馈(比如看完了某个视频)在量级上更高,显式反馈数据稀疏并且长尾效果不好。通俗地讲,就是一个用户历史记录里看完了某个视频这样的行为可能要比点赞的行为更多。

  • 正样本以外的就是负样本,但是为了加速计算,这里负样本使用了基于背景权重分布的采样方式获得

输入特征

1用户的观看历史、2用户的搜索历史、3用户的地理特征、4设备类型、5用户性别、6年龄、7登录状态、8样本年龄

12采用平均的embedding,34采用简单的embedding,567归一化到[0,1]就行。

12各自最多选择50个,然后作embedding,然后平均,集成为一个观看向量/搜索向量作为输入特征。

  • 8样本年龄的设计

    第一,YouTube每秒都会上传巨大量的视频,所以新的视频也能被推荐至关重要。第二,发现用户喜欢点击新上传的视频,即使这些视频在内容上跟用户偏好关系不大。此外,简单地将用户喜欢的新的视频放在推荐位置的前面,这对于内容的病毒性传播现象是关键的。

    机器学习系统通常是利用用户历史记录预测未来的行为,也就是在训练时样本的年龄是被看成平均分布的,为了纠正这个问题,训练时将样本年龄作为一个训练特征加入。在上线时,把训练阶段上传的视频的所有样本年龄设置成0或者很小的非负值。

图中显示,加入了样本年龄,样本年龄在0+附近预测出的可能性最高,10天以后的基本保持稳定。这样的效果符合原本设计。

  • 1用户观看历史的设计

    a. 训练样本是YouTube所有的视频(包括嵌在YouTube里其他网站的视频),而不只是推荐槽位上出现的视频。

    这样选择的原因是只选择推荐结果里的视频泛化性不好、对于视频的爆炸性传播现象(如果大量用户火热的观看了一个视频,我们希望这个视频能够通过协同过滤快速的传播出去)适应性不好(通过非推荐槽位的其他方法看到的视频不能很好的爆炸性传播)。

    b. 更一个关键的洞察:每个用户选择统一大小的训练集,平衡冷热用户对loss函数的影响。

    c. 用户消费的非对称问题:用户对于同系列的视频消费多,或者比起冷门音乐人的视频,用户通常会先看流行的音乐人的视频。所以预测用户可能观看的下一个视频要比随机的预测可能会看的视频会取得更好的效果。通常的协同过滤算法是随机选取一个样本和这个样本的上下文,然后利用其他所有的历史记录来预测。这显然忽略了非对称问题。所以这里,先随机选择一个视频,然后只选择它之前的历史记录作为输入。

  • 2用户搜索历史的设计

    a. 为了防止过拟合,比如一个用户刚搜索了一个词,推荐结果就变成了这个词相关的视频。这里先打乱用户历史搜索词,然后做embedding。

    b. 采用同样的方式处理用户非对称消费问题。

评估

增加特征个数会有更好的效果,神经网络的层数增加到4层效果提升已经不明显了。


排序网络

排序的目标,是为了预测用户对每个视频的观看时间。

之所以不预测点击率然后排序取topN,是因为存在clickbiat(点击行为提高了那些只点了而未观看的伪视频的可能性)。

正负样本选择

在推荐槽位上用户点击了的作为正样本,推荐槽位上未点击的作为负样本。

特征处理

排序的时候通常使用几百个特征。

  • 输入特征

    后续附上

  • 离散特征的embedding

    后续附上

  • 连续特征的归一化

    采用累计分位点的方法进行归一化。

  • 衍生特征

    加入某些特征的次线性和超线性项作为输入特征: x^0.5、x^2

网络架构

神经网络的架构与候选集生成网络相似。

训练时最后一层ReLU的结果是一个256维的向量W,连接带权重的logistic层。正样本的权重设置为观看时间,负样本的权重设置为单位值。logistic层使用W和视频向量Vj,赋上权重,logistic层输出层是一个时间的预测值的Sigmoid值。

在线上时,采用e^(Wx+b)。至于原因,是因为正样本量很小时,有以下成立:

损失函数及参数更新

后续附上

评估

对于第二天的推荐结果里,先用模型计算出一个观看时间,如果负样本(用户没点击)收到了比正样本(用户点击了的)一个更高的分数,则正样本的预测时间计为预测错误时间。

loss = 预测错误的时间/总的预测时间

次线性和超线性加入后提升不高。

有权重的LR是有必要的。

0 Comments

Array Advanced

Java有大量的方式可以持有对象,其中数组是一种效率最高的存储和随机访问对象引用序列的方式

以下有些用了Java8的特性,刷题时看到有些人用,试了试

数组是对象


无论是基本类型数组还是对象类型数组,数组标识符只是一个引用,指向在堆里创建的一个真实对象。

1
2
3
4
5
6
7
int[] arr1 = new int[5];
Integer[] arr2 = new Integer[5];
System.out.println(arr1);
System.out.println(arr2);
Field[] fields = arr2.getClass().getDeclaredFields();
System.out.println(Arrays.toString(fields));

System.out.println()调用了String.valueOf()方法,后者最终调用了Object.toString(),返回对象的类名和16进制的对象地址值。

1
2
3
[I@15db9742
[Ljava.lang.Integer;@6d06d69c
[]

数组是特殊的对象,它有一个只读成员length,但上面代码显示.getDeclaredFields()获取不到这个字段。

容器替代数组?


数组可以持有基本类型,而泛型之前的容器并不能。也就是说,在泛型之前,容器类在处理对象时都会将对象视为Object对象(没有任何具体类型),而数组可以持有某种具体类型。更深一层的意义就是在编译期可以指出类型错误。

有了泛型,容器也可以检查类型。随着自动包装机制的出现,容器已经可以和数组几乎一样方便地用于基本类型中了。数组硕果仅存的优点就是效率了。

数组初始化


基本类型数组的工作方式与对象数组一样,不过基本类型的数组直接存储基本类型数据的值。

默认初始化

1
2
3
4
5
6
7
int[] arr3;
Random rand = new Random();
arr3 = new int[rand.nextInt(5)];
//基本类型中,Arrays.stream()目前只支持int\long\double
Arrays.stream(arr3)
.forEach(s ->System.out.print(s+" "));

上面代码里我定义了一个int数组arr3,此时只是一个引用(已经为这个引用分配了足够的空间),还没有给数组对象本身分配任何空间。Random.nextInt()在运行时随机出数组的大小,这表明数组对象的创建确实是在运行时进行的。

1
0 0

初始化的默认值:对于int、long型是0,flaot、double型是0.0,char是’’即(char)0),boolean型是false,引用对象类型是null。

静态初始化

1
2
3
4
Integer[] arr5 = {
new Integer(1),
2,//自动装箱
};

在这种情况下,存储空间的分配由编译器负责。初始化列表最后一个逗号可选(这个特性使维护长列表变得更容易)。

动态初始化

1
2
3
Integer[] arr6 = new Integer[rand.nextInt(10)];
Arrays.stream(arr6).map(s -> rand.nextInt(500))
.forEach(s ->System.out.print(s+" "));

在这里,“Integer[] arr6 = new Integer[rand.nextInt(10)];”之后arr6还只是一个引用。直到map()里创建Integer对象,并把对象赋值给引用,初始化进程才算结束。

1
1 2 177 77 210 482 487 477 235 191

可变参数列表


1
2
3
4
5
6
7
8
9
10
public class VarArgs {
public static void main(String[] args){
f();
f(1,2,new Integer(3));
}
public static void f(Integer... args){
Arrays.stream(args)
.forEach(s -> System.out.print(s+" "));
}
}

可变参数与自动装箱互不影响,传递给可变参数列表0个参数也是可行的。

1
1 2 3

使用可变参数列表重载时需要多注意一点

1
2
3
4
5
6
7
8
9
10
11
12
public class OverloadingVarargs1 {
public static void main(String[] args) {
g(1,'a');
g('a','b');
}
public static void g(float i, Character... args){
System.out.println("first");
}
public static void g(Character... args){
System.out.println("second");
}
}
line 4 error: The method g(float, Character[]) is ambiguous for the type OverloadingVarargs

作为对比,又写了一个。注意这里并没有报错。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class OverloadingVarargs2 {
public static void main(String[] args) {
g(1,2);
Character c = 'c';
Double d = (double) 2;
}
public static void g(float i, double... args){
System.out.println("first");
}
public static void g(double... args){
System.out.println("second");
}
}
1
first

对于重载可能出现的匹配混淆,可以采用非可变参数来解决:

1
2
3
4
5
6
7
8
9
10
11
12
public class OverloadingVarargs3 {
public static void main(String[] args) {
g(1,'a');
g('a','b');
}
public static void g(float i, Character... args){
System.out.println("first");
}
public static void g(Character... args){
System.out.println("second");
}
}
1
2
first
second

多维数组


1
int[][] arr7;

JAVA采用上面的语法格式来定义二维数组,但它的实质还是一维数组,只是其数组元素也是引用,数组元素里保存的引用指向一维数组。并且多维数组每一维度可以具有任意的长度(被称为粗糙数组)。

对以上不太理解,可扩展阅读 Java多维数组解读

数组与泛型的斗争


泛型vs数组

你不能实例化具有参数化类型的数组。

1
ArrayList<String>[] arr9 = new ArrayList<String>[]();//illegal

擦除会移除参数化类型信息,而数组必须知道它们所持有的确切类型,以强制保证类型安全。

但是可以创建泛型数组的引用。

1
List<String>[] ls;

尽管不能创建实际的持有泛型的数组对象,但是可以创建非泛型的数组,然后对其转型。

1
2
3
4
5
6
List<String>[] arr10 = (List<String>[])new List[4];
for(int i=0;i<arr10.length;i++){
arr10[i] = new ArrayList<String>();
arr10[i].add("oath");
}
System.out.println(Arrays.toString(arr10));
1
[[oath], [oath], [oath], [oath]]

将for循环改成foreach语法打印结果均是null。

1
2
3
4
5
6
List<String>[] arr10 = (List<String>[])new List[4];
for(List<String> a: arr10){
a = new ArrayList<String>();
a.add("oath");
}
System.out.println(Arrays.toString(arr10));
1
[null, null, null, null]

foreach不能赋值,只能用来遍历。stream相关的foreach/map使用时也要注意。可扩展阅读 foreach语法详解

参数化方法vs参数化类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ParameterizedArrayType {
public static void main(String[] args) {
Integer[] ints = {1,2,3,4};
Double[] doubles = {1.1,2.2,3.3,4.4};
Integer[] ints2 = new ClassParameter<Integer>().f(ints);
Double[] doubles2 = new ClassParameter<Double>().f(doubles);
ints2 = MethodParameter.f(ints);
doubles2 = MethodParameter.f(doubles);
}
}
class ClassParameter<T>{
public T[] f(T[] arg){
return arg;
}
}
class MethodParameter{
public static <T> T[] f(T[] arg){
return arg;
}
}

参数化方法显然比参数化类方便很多,不需要为应用的每种类型都使用一个参数去实例化这个类,并且你可以把参数化方法定义成static,用类名.方法调用。

Arrays类探索


可以在java.util类库里找到Arrays类,它有一套实用的用于数组的static方法。
Arrays类对以下的方法均针对所有基本类型和Object类型做了重载。

Arrays.fill()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class FillingArrays {
public static void main(String[] args) {
String[] arr8 = new String[6];
Arrays.fill(arr8, "oath");
System.out.println(Arrays.toString(arr8));
Arrays.fill(arr8, 4, 6, "yangmen");
System.out.println(Arrays.toString(arr8));
student[] arr9 = new student[2];
Arrays.fill(arr9, new student("xiaoming"));
System.out.println(Arrays.toString(arr9));
}
}
class student{
String name;
student(String name){
this.name = name;
}
}

fill只能用同一个值填充各个位置,或者像line 6所示,只填充数组的某个区域。而针对对象而言,就是复制同一个引用进行填充。该方法内部实现也是利用for循环逐个赋值。

1
2
3
[oath, oath, oath, oath, oath, oath]
[oath, oath, oath, oath, yangmen, yangmen]
[FillingArrays.student@4c873330, FillingArrays.student@4c873330]

Array.copyOf()

1
2
3
4
5
int[] arr12 = new int[]{1,2,3,4,5};
int[] arr13 = Arrays.copyOf(arr12, 2);
System.out.println(Arrays.toString(arr13));
arr13 = Arrays.copyOfRange(arr12, 3, 5);
System.out.println(Arrays.toString(arr13));
1
2
[1, 2]
[4, 5]

copyOf()实现里调用了System.arraycopy(Object src, int srcPos,Object dest, int destPos,int length)方法。

1
2
3
4
5
6
7
8
int[] arr14 = new int[5];
int[] arr15 = new int[7];
Arrays.fill(arr14, 47);
Arrays.fill(arr15, 66);
System.out.println("arr14 "+Arrays.toString(arr14));
System.out.println("arr15 "+Arrays.toString(arr15));
System.arraycopy(arr14, 1, arr15, 1, 3);
System.out.println("arr15 "+Arrays.toString(arr15));
1
2
3
arr14 [47, 47, 47, 47, 47]
arr15 [66, 66, 66, 66, 66, 66, 66]
arr15 [66, 47, 47, 47, 66, 66, 66]

如果复制对象数组,只会复制对象的引用——而不是对象本身的拷贝(浅复制)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class FillingArrays {
public static void main(String[] args) {
student[] arr16 = new student[1];
student[] arr17 = new student[2];
Arrays.fill(arr17,new student("haha"));
student i = new student("oath");
arr16[0] = i;
System.out.println("arr16 "+Arrays.toString(arr16));
System.out.println("arr17 "+Arrays.toString(arr17));
System.arraycopy(arr16, 0, arr17, 0, 1);
System.out.println("arr17 "+Arrays.toString(arr17));
System.out.println("arr17[0]'s name: "+arr17[0].name);
i.name = "oath2";
System.out.println("arr17 "+Arrays.toString(arr17));
System.out.println("arr17[0]'s name: "+arr17[0].name);
}
}
class student{
String name;
student(String name){
this.name = name;
}
}
1
2
3
4
5
6
arr16 [CopyingArrays.student@119d7047]
arr17 [CopyingArrays.student@776ec8df, CopyingArrays.student@776ec8df]
arr17 [CopyingArrays.student@119d7047, CopyingArrays.student@776ec8df]
arr17[0]'s name: oath
arr17 [CopyingArrays.student@119d7047, CopyingArrays.student@776ec8df]
arr17[0]'s name: oath2

还要注意,System.arrayCopy()不会执行自动包装和自动拆包。不举例了。

Arrays.toString()/Arrays.deepToString()

1
2
3
4
5
int[][] arr18 = new int[2][2];
Arrays.fill(arr18[0], 11);
Arrays.fill(arr18[1], 22);
System.out.println(Arrays.toString(arr18));
System.out.println(Arrays.deepToString(arr18));

Arrays.toString()对基本类型数据进行了重载,直接打印值。

1
2
[[I@3b07d329, [I@41629346]
[[11, 11], [22, 22]]

Arrays.toString(Object[])调用String.valueOf(),后者调用了Object.toString()。

Arrays.deepToString()递归调用了自身直至最后一层,最后使用基本类型和Object的toString()方法。

此处顺便加深一下二维数组实质是一维数组。

Arrays.equals()/Arrays.deepEquals()

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 ComparingArrays {
public static void main(String[] args) {
String[] arr19 = new String[2];
Arrays.fill(arr19, "oath");
String[] arr20 = {new String("oath"),new String("oath"),};
System.out.println(Arrays.equals(arr19,arr20));
student[] arr21 = new student[2];
Arrays.fill(arr21, new student("yangmen"));
student[] arr22 = {new student("yangmen"),new studen("yangmen")};
System.out.println(Arrays.equals(arr21,arr22));
int[][] arr23 = new int[2][2];
int[][] arr24 = new int[2][2];
Arrays.fill(arr23[0], 56);
Arrays.fill(arr24[0], 56);
System.out.println(Arrays.deepEquals(arr23,arr24));
}
}
class student{
String name;
student(String name){
this.name = name;
}
}

equals()方法对所有基本类型和Object类型都做了重载。基本类型和Object类型都会先比较数组地址,再比较数组长度。最后逐个比较元素,基本类型用自身包装类的equals()方法比较每一个元素,Object类型对每一个元素使用equals()作比较判断。

1
2
3
true
false
true

String类对超类Object类的equals()方法进行了重载,比较每个元素的内容。student类并没有重写,所以结果为false。

deepEquals()会递归调用自身直至最后一层,最后使用基本类型和Object的equals()方法。

数组的比较

在排序和搜索之前,说一下数组的比较。

排序比较根据对象的实际类型执行比较操作。一种自然的解决方案是为每种不同的类型各编写一个不同的排序方法,但这样的代码难以被新的类型所复用。因此,使用策略设计模式,将“会发生变化的代码”封装在单独的类中(策略对象),然后把策略对象传递给总是相同的代码,这些代码将使用策略来完成其算法。

Java有两种方式来提供比较功能。

  • 第一种是实现java.lang.Comparable接口,使你的类具体“天生”的比较能力。这个接口很简单,只要重写compareTo()方法即可。
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
39
40
41
42
public class CompType1 {
public static void main(String[] args) {
Employee[] arr25 = new Employee[3];
for(int j=0;j<arr25.length;j++){
String name = getRandomString(4);
int age = (int)Math.round(Math.random()*50);
arr25[j] = new Employee(name,age);
}
Arrays.stream(arr25)
.forEach(s -> System.out.println(s.toString()));
Arrays.sort(arr25);
System.out.println();
Arrays.stream(arr25)
.forEach(s -> System.out.println(s.toString()));
}
public static String getRandomString(int length) {
String base = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJ"
+"KLMNOPQRSTUVWXYZ0123456789";
Random random = new Random();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < length; i++) {
int idex = random.nextInt(base.length());
sb.append(base.charAt(idex));
}
return sb.toString();
}
}
class Employee implements Comparable<Employee>{
String name;
int age;
Employee(String name,int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(Employee o) {
return age-o.age;
}
public String toString(){
return "name: "+this.name+" age: "+this.age+" ";
}
}
1
2
3
4
5
6
7
name: TKA8 age: 1
name: Yqvr age: 15
name: eN4W age: 13
name: TKA8 age: 1
name: eN4W age: 13
name: Yqvr age: 15

Arrays.sort(Object[])比较时调用Employee里的compareTo()方法。

  • 第二种是编写自己的Comparator,传递给一些排序方法如Collections.sort()或者 Arrays.sort()。

String类本身重写了comprareTo()方法,是按字典序从小到大排序的。此处想先按长度再按字典序的顺序排序。所以需要自己写一个Comparator。

此外Collections类的reverseOrder()可以产生一个Comparator,是自然排序顺序的反序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class CompType2 {
public static void main(String[] args) {
String[] arr26 = {"afsd","acsd","afsdijk"};
Arrays.sort(arr26);
Arrays.stream(arr26)
.forEach(s -> System.out.println(s.toString()));
Comparator<String> comp = new Comparator<String>(){
@Override
public int compare(String s1, String s2) {
if(s1.length()!=s2.length())
return s2.length()-s1.length();
else
return s1.compareTo(s2);
}
};
System.out.println();
Arrays.sort(arr26,comp);
Arrays.stream(arr26)
.forEach(s -> System.out.println(s.toString()));
Arrays.sort(arr26,Collections.reverseOrder());
Arrays.stream(arr26)
.forEach(s -> System.out.println(s.toString()));
}
}
1
2
3
4
5
6
7
8
9
10
11
acsd
afsd
afsdijk
afsdijk
acsd
afsd
afsdijk
afsd
acsd

Arrays.sort()

可选择全排序或者部分排序。对象实现了Comparble接口(自带compareTo())或传入自己想要的Comparator。

此处要提的是String类里也有一个自定义的Comparator,String.CASE_INSENSITIVE_ORDER

  • sort(T[] a)
  • sort(T[] a, Comparator<? super T> c)
  • sort(T[] a, int fromIndex, int toIndex,Comparator<? super T> c)

对基本类型也有相应的sort()方法重载。具体内部排序之后在排序章节补充,此处会补上跳转链接。

Arrays.binarySearch()

如果数组已经排好序了,就可以使用binaraySearch进行快速查找。这里需要知道2点:

  • 如果找到目标,Arrays.binarySearch()返回目标在数组中的index值(>=0);如果没找到则返回 -(插入点)-1 (<0)。
  • 如果使用了Comparator排序了某个对象数组(基本类型数组不能用Comparator排序),这种情况下使用binarySearch()时必须提供同样的Comparator。

    binarySearch(T[] a, T key, Comparator<? super T> c)
    binarySearch(long[] a, int fromIndex, int toIndex,long key)

    基本类型当然也重载了以上两种。

下面是float基本类型的binarySearch(),注意midBits == keyBits这部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
float midVal = a[mid];
if (midVal < key)
low = mid + 1; // Neither val is NaN, thisVal is smaller
else if (midVal > key)
high = mid - 1; // Neither val is NaN, thisVal is larger
else {
int midBits = Float.floatToIntBits(midVal);
int keyBits = Float.floatToIntBits(key);
if (midBits == keyBits) // Values are equal
return mid; // Key found
else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
low = mid + 1;
else // (0.0, -0.0) or (NaN, !NaN)
high = mid - 1;
}
}
return -(low + 1); // key not found.

浮点数判断需要注意,float 和double 的精度范围,超过范围的数字会被忽略

  • 浮点数大小判断

    如果没有等号关系在里面,也就必然一大一小,那么直接用 > 或者 <

  • 浮点数相等判断

    因为浮点数在内存中存放,可能无法精确的储存,所以不同的值,可能有相同的内存数据。所以要使用以下的方法:
    以float为例,32位APP中精度为e-7,所以取1e-7。
    两个数字A、B,如果|A-B|<1e-7,则计算机里A、B就是相等的。

举例,0.0和-0.0在内存里就是不同的存储数据,所以在查找元素的时候应当区分。其他场景下时大小应该是一样的都是0。


END

0 Comments

oath2yangmen.online start!

day1

Paloalto

0 Comments