问题描述：
提供一个月的用户来电和来电时间，计算24小时之内重复拨打的来电号码数量。
备注：
输入为csv文件，两列，大概一个月100w行数据左右。附件为实例数据。
【method1直观遍历】
复杂度O(kn)，k约为3w
优化：1判断时间先后靠getTime得到毫秒数long值；2电话号码用long的equals
【method2利用HashSet】
复杂度O(n)
维护一个集合利用空间换时间，两个int型指针s和e，s控制遍历列表，e控制24小时来电范围。每次s推进1位，判断e指向的新增通话是否在集合中，是则count++，e到达范围结尾时从集合中删去s指向的号码。
【method3将HashSet改为HashMap】
由于HashSet中元素不能重复，重复号码count++但无法再次加入HashSet。但每次s推进1位都会删除一个号码，则会造成重复数较少的bug。
解决方法是改用HashMap，记录号码key及号码的出现次数value，这样重复号码可以多次加入集合（次数+1），删除时只是次数-1。由于Java的HashSet底层由HashMap实现，对性能完全没有影响。
经测试，100w级来电数据mehod1(用时5min)和method3(用时2s)重复率数字完全一致
package bjtel;
import java.io.File;
import java.nio.charset.Charset;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import com.csvreader.CsvReader;
public class DuplicateIn24 {
public static void main(String[] args) throws Exception {
for(File f:new File("D:\\工作相关\\24小时重复拨打率").listFiles()){
if(f.isFile())
run(f);
}
// CsvReader reader = new CsvReader("D:\\工作相关\\24小时重复拨打率\\test2.csv", ',', Charset.forName("GBK"));
// DateFormat format=new SimpleDateFormat("yyyy/MM/dd HH:mm");
// DateFormat format2=new SimpleDateFormat("yyyy/MM/dd");
// List<Long> dates=new ArrayList<>();
// List<Long> calls=new ArrayList<>();
// reader.readHeaders();
// while(reader.readRecord()){
// try {
// calls.add(Long.parseLong(reader.getColumnCount()==3?reader.get(2):reader.get(0)));
// } catch (Exception e) {
// continue;
// }
// try {
// dates.add(format.parse(reader.get(1)).getTime());
// } catch (Exception e) {
// dates.add(format2.parse(reader.get(1)).getTime());
// }
//
// }
// reader.close();
// if(dates.size()==calls.size())
// System.out.println("共扫描"+dates.size()+"条通话");
// int count=method3(dates, calls);
// System.out.println("方法1：24小时重复拨打"+count+"条,占"+(double)count/calls.size());
// System.out.println("方法2：");
// method1(dates, calls);
}
public static void run(File file) throws Exception{
CsvReader reader = new CsvReader(file.getCanonicalPath(), ',', Charset.forName("GBK"));
DateFormat format=new SimpleDateFormat("yyyy/MM/dd HH:mm");
DateFormat format2=new SimpleDateFormat("yyyy/MM/dd");
List<Long> dates=new ArrayList<>();
List<Long> calls=new ArrayList<>();
reader.readHeaders();
while(reader.readRecord()){
try {
calls.add(Long.parseLong(reader.getColumnCount()==3?reader.get(2):reader.get(0)));
} catch (Exception e) {
continue;
}
try {
dates.add(format.parse(reader.get(1)).getTime());
} catch (Exception e) {
dates.add(format2.parse(reader.get(1)).getTime());
}
}
reader.close();
if(dates.size()==calls.size())
System.out.println("【"+file.getName()+"】共扫描"+dates.size()+"条通话");
int count=method3(dates, calls);
System.out.println("重复拨打"+count+"条,占"+(double)count/calls.size());
}
public static int method2(List<Long> dates,List<Long> calls){
int count=0;
Set<Long> scale=new HashSet<>();
for(int s=0,e=1;s<dates.size();s++){
scale.add(calls.get(s));
while(e<dates.size()&&dates.get(e)<dates.get(s)+86400000){
if(e>=calls.size())
return count;
if(scale.contains(calls.get(e))){
count++;
}
scale.add(calls.get(e++));
}
scale.remove(calls.get(s));
}
return count;
}
public static int method3(List<Long> dates,List<Long> calls){
int count=0;
Map<Long,Integer> scale=new HashMap<>();
for(int s=0,e=1;s<dates.size();s++){
// if(s%10000==0)
// System.out.println(count);
for(;e<dates.size()&&dates.get(e)<dates.get(s)+86400000;e++){
if(e>=calls.size())
return count;
int t=scale.get(calls.get(e))==null?0:scale.get(calls.get(e));
if(t>0)
count++;
scale.put(calls.get(e), t+1);
}
int t=scale.get(calls.get(s))==null?0:scale.get(calls.get(s));
if(t<=1)
scale.remove(calls.get(s));
else
scale.put(calls.get(s), t-1);
}
return count;
}
public static int method1(List<Long> dates,List<Long> calls){
int count=0;
for(int i=0;i<dates.size();i++){
if(i%50000==0)
System.out.println("已扫描"+i+"条"+" 重复"+count+"条");
long scale=dates.get(i)+86400000;
// for(int j=i+1;dates.get(j)<scale;j++){
int j=i+1;
while(j<dates.size()&&dates.get(j)<scale){
if(calls.get(i).equals(calls.get(j))){
count++;
break;
}
j++;
}
// if(j==dates.size())
// System.out.println(i+" "+dates.get(i));
}
System.out.println("方法2：24小时重复拨打"+count+"条,占"+(double)count/calls.size());
return count;
}
}
若增加需求，统计出现重复的电话的原接待人并输出每个负责人共造成多少重复拨打。
则将method3的HashMap，改为记录key为号码，value为出现次数及负责人封装而成的对象。
代码如下：（附件2为新需求的输入）
package bjtel;
import java.io.FileWriter;
import java.nio.charset.Charset;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import com.csvreader.CsvReader;
public class DuplicateIn24WithDetail {
public static void main(String[] args) throws Exception{
String input=args.length==2?args[0]:"D:\\工作相关\\24小时重复拨打率\\contactdetail_20141231.csv";
String output=args.length==2?args[1]:"D:\\data.csv";
CsvReader reader = new CsvReader(input, ',', Charset.forName("GBK"));
DateFormat format=new SimpleDateFormat("yyyy-MM-dd HH:mm:SS");
DateFormat format2=new SimpleDateFormat("yyyy-MM-dd");
List<Call> calls=new ArrayList<>();
reader.readHeaders();
while(reader.readRecord()){
Call call=new Call();
try {
call.number=Long.parseLong(reader.get(0));
} catch (NumberFormatException e) {
call.number=System.currentTimeMillis();
}
call.receiver=reader.get(2);
try {
call.time=format.parse(reader.get(1)).getTime();
} catch (Exception e) {
call.time=format2.parse(reader.get(1)).getTime();
}
calls.add(call);
}
reader.close();
// Map<String,Integer> detail=new HashMap<>();
// System.out.println(method2(calls, detail)+" "+detail);
// Map<String,Integer> detail1=new HashMap<>();
// System.out.println(method1(calls, detail1)+" "+detail1);
Map<String,Integer> detail=new HashMap<>();
System.out.println(format2.format(new Date(calls.get(0).time))+"共出现"+method2(calls, detail)+"例重复拨打");
System.out.println("共"+detail.size()+"名员工的具体数据输出至"+args[1]);
FileWriter fileWriter=new FileWriter(output,true);
for(Entry<String, Integer> e:detail.entrySet()){
fileWriter.append(format2.format(new Date(calls.get(0).time))+","+e.getKey()+","+e.getValue()+"\r\n");
}
fileWriter.close();
}
public static int method1(List<Call> calls, Map<String,Integer> detail) {
int count=0;
for(int i=0;i<calls.size();i++){
if(i%50000==0)
System.out.println("已扫描"+i+"条"+" 重复"+count+"条");
long scale=calls.get(i).time+86400000;
int j=i+1;
while(j<calls.size()&&calls.get(j).time<scale){
if(calls.get(i).number.equals(calls.get(j).number)){
count++;
detail.put(calls.get(i).receiver, detail.get(calls.get(i).receiver)==null?1:detail.get(calls.get(i).receiver)+1);
break;
}
j++;
}
}
return count;
}
public static int method2(List<Call> calls, Map<String,Integer> detail){
int count=0;
Map<Long,Scale> scale=new HashMap<>();
for(int s=0,e=1;s<calls.size();s++){
for(;e<calls.size()&&calls.get(e).time<calls.get(s).time+86400000;e++){
if(e>=calls.size())
return count;
Scale unique=scale.get(calls.get(e).number);
int t=unique==null?0:unique.count;
if(t>0){
count++;
detail.put(unique.lastReceiver, detail.get(unique.lastReceiver)==null?1:detail.get(unique.lastReceiver)+1);
}
scale.put(calls.get(e).number, new Scale(t+1, calls.get(e).receiver));
}
int t=scale.get(calls.get(s).number)==null?0:scale.get(calls.get(s).number).count;
if(t<=1)
scale.remove(calls.get(s));
else
scale.put(calls.get(s).number, new Scale(t-1, scale.get(calls.get(s).number).lastReceiver));
}
return count;
}
}
class Call{
public long time;
public Long number;
public String receiver;
}
class Scale{
public int count;
public String lastReceiver;
public Scale(int count,String lastReceiver){
this.count=count;
this.lastReceiver=lastReceiver;
}
}
结论：method2较快，但只能统计一个集合内重复的拨打数；method1较慢，但采用顺序遍历可以统计截止到某个时间段的24小时重复拨打量
相关推荐
源程序文件重复率检测系统是一种专门用于分析和评估代码复用程度的工具，它能够帮助开发者、教育者或代码审查人员快速找出代码中的相似或重复部分。这种系统通常基于先进的文本匹配算法，如最长公共子序列（LCS）、...
标题中的“论文降低重复率辅助软件”是一种专为学术写作设计的工具，旨在帮助作者减少论文中的抄袭或重复内容，确保学术诚信。在撰写IEEE（Institute of Electrical and Electronics Engineers）论文时，遵循原创性...
在开发这个Windows应用程序时，我们需要考虑的核心问题是如何有效地实现题目的随机分配，同时确保分配给每个成员的题目重复率低于30%。这个问题涉及到算法设计、数据结构的应用以及用户界面的构建。以下是对这些关键...
实际用水量-新水取用量-工业用水新水取用量_万立方米 城市节约用水-实际用水量-重复利用量_万立方米 城市节约用水-实际用水量-重复利用量-工业用水重复利用量_万立方米 城市节约用水-重复利用率_百分比 城市节约用水...
比较代码是否相同，查代码重复率的python程序
详细介绍了如何在目前国内论文检测系统（知网、PaperRater等）的检测报告的基础上，有效的修改自己的毕业论文（文中介绍了几种不同但很有效的论文修改方法和论文写法），快速降低论文重复率，顺利通过学校检测，顺利...
在IT行业中，尤其是在电子商务、零售和SaaS领域，提高顾客重复购买率是至关重要的业务策略。这不仅能够增加公司的销售收入，还能降低获取新客户的成本，巩固品牌忠诚度。本文件"如何提高顾客重复购买率.pptx"显然是...
本文将深入探讨如何有效地修改论文以降低重复率，避免学术不端的嫌疑。 首先，了解学术不端检测系统的原理是至关重要的。这些系统通常基于大规模的文献数据库，通过比对提交的论文与已发表文献的相似度来计算重复率...
论文检测重复率工具是用于验证论文中是否存在抄袭或不恰当引用他人的研究成果的重要辅助手段。这类工具在毕业论文、学位论文以及学术期刊投稿过程中扮演着不可或缺的角色。以下将详细阐述论文检测重复率工具的功能、...
查重是指对文本、论文、作业等进行重复率检测，以防止学术不端和抄袭。查重主要是通过计算机程序对文本进行比对，发现文本中相似或完全相同的部分，生成重复率报告。 方法/步骤 文本比对法：将被检测的文本与...
本研究聚焦于大规模中文搜索日志中的查询重复性分析，通过对查询重复率和用户个体查询重复率的数据统计，得出了几个关键结论： 1. **查询串、文档点击及用户查询频率**：这三项指标均呈现出Zipf分布的特点，即少数...
在这一背景下，USF Health通过采用Onyx技术和英特尔处理器，推出了PharmacyPlus项目，旨在通过数字化改造配药流程，降低患者的重复入院率。PharmacyPlus项目是一个典型的医疗机构在物联网（IoT）技术支持下的创新...
### 如何提高重复购买率——基于芳草集吕长城2011派代年会演讲的知识点提炼 #### 一、影响重复购买率的关键因素 提高重复购买率是电子商务领域中一个重要的课题，它直接关系到企业的长期盈利能力和品牌忠诚度的...
重复利用量-工业用水重复利用量_万立方米 城市节约用水-重复利用率_百分比 城市节约用水-重复利用率-工业用水重复利用率_百分比 城市节约用水-节约用水量_万立方米 城市节约用水-节约用水量-工业用水节约用水量_万...
地县级城市建设2022-2002 实际用水量-实际用水量合计 -实际用水量合计-工业用水实际用水量 -新水取用量 -新水取用量-工业用水新水取用量 -重复利用量 -重复利用量-工业用水重复利用量 重复利用率 重复利用率 ...
论文查重原理及规避高重复率方法 在本文中，我们将详细介绍论文查重原理及其规避高重复率的方法。这些方法基于中国知网学位论文检测系统的原理和特点，并提供了实践证明的修改技巧。 一、论文查重原理 论文查重是...