1,先给出一个经常用到的代码:
#include<iostream>
using namespace std;
int binarySearch1(int t, int data[], int n)
{
int l = 0;
int u = n - 1;
int p, m;
while (true)
{
if (l > u)
{
p = -1;
break;
}
m = (l + u) / 2;
if (data[m] < t)
l = m + 1;
else if (data[m] == t)
{
p = m;
break;
}
else
u = m -1;
}
return p;
}
int main()
{
int data[]={1,4,4,5,6,8,9,9,9,9,9,10};
int n=sizeof(data)/sizeof(data[0]);
cout<<binarySearch1(9,data,n)<<endl;
return 0;
}
缺点:
(1)每次循环至少需要比较两次;
(2)如果t多次出现,那么上述代码可能返回t的任意一个位置.
2,下面改进的代码,可以保证返回t第一次出现的位置.
#include<iostream>
using namespace std;
int binarySearch2(int t, int data[], int n)
{
int l = -1;
int u = n;
int m;
while ( (l + 1) != u)
{
m = (l + u) / 2;
if (data[m] < t)
l = m;
else
u = m;
}
int p = u;
if ((u >= n) || (data[u] != t))
p = -1;
return p;
}
int main()
{
int data[]={1,4,4,5,6,8,9,9,9,9,9,10};
int n=sizeof(data)/sizeof(data[0]);
cout<<binarySearch2(9,data,n)<<endl;
return 0;
}
3,继续改进,循环展开将会有很大的提高.
#include<iostream>
#include<algorithm>
#include<iterator>
using namespace std;
const int N=1000;
int data[N];
int randInt()
{
return rand()%(5000);
}
//这里设定数组的大小为1000
int binarySearch3(int t,int data[],int n)
{
//第一步先保证搜索的范围为2的指数次.
int i=512;
int l=-1;
if(data[511]<t)
l=1000-512;
while(i!=1)
{
if(data[l+i/2]<t)
l=l+i/2;
i=i/2;
}
//assert:i==1;data[l]<t;data[l+i]>=t
int p=l+1;
if(p>=n||data[p]!=t)
p=-1;
return p;
}
int binarySearch4(int t,int data[],int n)
{
//第一步先保证搜索的范围为2的指数次.
int l=-1;
if(data[511]<t)
l=1000-512;
if(data[l+256]<t) l+=256;
if(data[l+128]<t) l+=128;
if(data[l+64]<t) l+=64;
if(data[l+32]<t) l+=32;
if(data[l+16]<t) l+=16;
if(data[l+8]<t) l+=8;
if(data[l+4]<t) l+=4;
if(data[l+2]<t) l+=2;
if(data[l+1]<t) l+=1;
//assert:i==1;data[l]<t;data[l+i]>=t
int p=l+1;
if(p>=n||data[p]!=t)
p=-1;
return p;
}
int main()
{
generate(data,data+N,randInt);
sort(data,data+N);
copy(data,data+N,ostream_iterator<int>(cout," "));
cout<<endl;
cout<<binarySearch3(447,data,N)<<endl;
cout<<binarySearch4(447,data,N)<<endl;
return 0;
}
分享到:
相关推荐
### 软件性能测试调优 #### 一、性能测试概述 性能测试是一种软件测试类型,旨在评估软件系统的性能特点。它可以帮助我们了解软件在特定条件下的行为,包括响应时间、吞吐量、资源使用情况等关键指标。性能测试的...
- 模型调优:使用网格搜索、随机搜索等方法调整超参数,以提高模型性能。 4. **模型评估**: - 二分类指标:准确率、查准率、查全率、F1分数、AUC-ROC曲线等。 - 多分类指标:混淆矩阵、Kappa系数、多类F1分数等...
3. 参数调优:LibSVM提供了一种基于网格搜索的参数调优方法,通过交叉验证在多个参数组合中寻找最佳性能的模型。主要的参数包括惩罚系数C(控制误分类的程度)和核函数的参数γ(影响模型复杂度)。 4. 训练与预测...
2. 算法:源代码中包含排序算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序)、查找算法(如顺序查找、二分查找、哈希查找)以及图算法(如深度优先搜索、广度优先搜索)。这些算法是解决问题的...
5. 优化算法:使用更高效的算法,如使用二分查找代替线性搜索。 6. 并发处理:在多线程环境下,合理使用synchronized关键字和并发工具类,保证线程安全。 7. 编译器优化:启用Java编译器的优化选项,如开启逃逸...
5. 参数调优:可能包含网格搜索或随机搜索来优化模型参数。 五、模型选择与比较 除了线性回归,还有其他回归模型可供选择,如岭回归、Lasso回归、 Elastic Net等,它们通过正则化处理过拟合问题。这些模型的代码...
2. 实践应用:通过实际运行代码,可以对数据进行预处理、模型训练、评估和调优,提升实践能力。 3. 模型比较:对比不同算法的实现,有助于选择适合特定问题的最优模型。 四、代码结构与解读 每个机器学习算法的...
3. 参数调优:网格搜索、随机搜索等方法,寻找最优超参数组合。 通过龙曲良的《TensorFlow深度学习》学习笔记和代码,读者可以系统地学习深度学习的基础知识,理解TensorFlow 2.0.0的使用,并通过实践提升自己的...
4. 模型评估与调优:交叉验证、网格搜索等方法的使用,以提高模型的泛化能力。 5. 特征工程:包括特征缩放、特征选择和特征提取等,以增强模型的性能。 6. 模型保存与加载:如何将训练好的模型保存到文件,并在需要...
例如,使用百度搜索引擎查询“性能调优”,页面完全加载完毕所需的时间就是该操作的响应时间。 **2.2 吞吐量(TPS)** 单位时间内完成的任务数量,例如每秒处理的请求数量。对于服务大量用户的系统而言,吞吐量是...
3. 参数调优:通过网格搜索或交叉验证选择最佳的C和γ参数。 4. 预测:利用训练好的模型对新数据进行分类或回归预测。 七、libsvm扩展应用 libsvm不仅适用于传统的二分类和回归任务,还可以与其他算法结合,如集成...
4. 参数调优:熟悉网格搜索、交叉验证等方法,找到最佳的模型参数。 5. 分类评估指标:如准确率、精确率、召回率、F1分数等,用于评估模型性能。 如果你计划在自己的项目中使用这个Java SVM多分类源码,首先,阅读...
6. 参数调优:通过网格搜索或随机搜索等方法调整模型参数,以优化模型性能。 7. 结果可视化:绘制混淆矩阵、ROC曲线等图表,直观展示模型效果。 总之,这个MATLAB代码示例为我们提供了一个实践SVM和神经网络分类...
- 超参数调优:网格搜索、随机搜索、贝叶斯优化等方法用于找到最佳模型参数。 - 正则化:防止过拟合,如L1和L2正则化。 - 模型验证:交叉验证、留一法等确保模型泛化能力。 4. **数据预处理** - 缺失值处理:...
9. 模型评估与调优:讲解交叉验证、网格搜索、模型选择等技巧。 10. 实战项目:结合具体案例,如手写数字识别、文本分类等,进行机器学习项目的实施。 三、PPT内容解析 PPT演示文稿通常包含每节课的关键知识点、...
代码可能包含了网格搜索或随机搜索等参数优化方法。 3. 分类评估:为了验证模型的性能,代码可能会包含交叉验证和各种评估指标,如准确率、召回率、F1分数等。 总结来说,rhythmwzj的SVM代码实现为学习者提供了一个...
- 模型选择:通过网格搜索或随机搜索找到最佳参数组合。 - 评估指标:如准确率、精确率、召回率、F1分数、AUC值等,用于衡量模型性能。 5. 特征工程: - 特征缩放:如标准化和归一化,确保不同特征在同一尺度上...
2. 超参数调优:网格搜索、随机搜索等方法来寻找最优的模型参数。 3. 模型融合:集成学习如Bagging、Boosting和Stacking,提高模型的泛化能力。 五、深度学习 1. 深度神经网络(DNN):多层神经网络,用于图像识别...
- **网格搜索**或**随机搜索**:用于调优模型参数,以提高分类效果。 通过学习和实践这些MATLAB代码,读者不仅可以深化对模式分类理论的理解,还能提升编程技能,为实际项目开发打下坚实基础。同时,这些代码也可以...
5. 超参数调优:可能使用网格搜索或随机搜索等方法,寻找最佳参数组合。 6. 验证和评估:在测试集上进行预测,计算准确率、精确率、召回率等指标,评估模型性能。 7. 应用模型:保存模型以便后续预测新数据。 在...