package cn.coderead.web;
/**
* @Copyright 源码阅读网 http://coderead.cn
*/
import com.fasterxml.jackson.core.JsonProcessingException;
import org.junit.Test;
import org.junit.platform.console.shadow.picocli.CommandLine;
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import static org.fusesource.jansi.Ansi.ansi;
/**
* @author 鲁班大叔
* @date 2023
*/
public class MathMain {
int size = 10000000;
Player redBlack = new RedBlackTree();
Player array = new Array(size, true);
Player linkTable = new LinkTable();
// Player skipList=new SkipListTable();
Player skipList=new SkipList();
List<RecordPoint> records=new ArrayList<>();
public MathMain() {
}
public void start() throws InterruptedException {
// 1千万
final List<Integer> randomNumbers = getRandomNumbers(size);
ThreadGroup group = new ThreadGroup("数据结构组");
group.setMaxPriority(Thread.MIN_PRIORITY);
List<Thread> threads = List.of(
new Thread(group, () -> run(redBlack, randomNumbers)),
new Thread(group, () -> run(skipList, randomNumbers))
// new Thread(group, () -> run(array, randomNumbers))
// new Thread(group, () -> run(linkTable, randomNumbers))
);
threads.forEach(Thread::start);// 全部启动
while (threads.stream().anyMatch(Thread::isAlive)) {
printScore();
Thread.sleep(300);
}
printScore();
}
void printScore() {
System.out.print(ansi().eraseScreen());
CommandLine.Help.TextTable textTable =
CommandLine.Help.TextTable.forColumnWidths(
CommandLine.Help.defaultColorScheme(CommandLine.Help.Ansi.OFF), 10, 20, 20, 20, 15);
textTable.addRowValues("名称", "新增", "查询", "删除", "当前速度");
// System.out.println("名称\t新增\t\t\t查询\t\t\t删除\t\t\t名次");
List<Player> players = new ArrayList<>(List.of(/*array, linkTable,*/ skipList,redBlack));
// players.sort(Comparator.comparingLong(Player::useTime));
for (Player player : players) {
String insert = player.insertCount == 0 ? "-" :
player.insertCount == player.insertTotal && player.insertTime!=0 ? timeToString(player.insertTime) :
(player.insertCount * 100 / player.insertTotal) + "% " + player.insertCount;
String search = player.searchCount == 0 ? "-" :
player.searchCount == player.searchTotal ? timeToString(player.searchTime) :
(player.searchCount * 100 / player.searchTotal) + "% " + player.searchCount;
String delete = player.deleteCount == 0 ? "-" :
player.deleteCount == player.deleteTotal ? timeToString(player.deleteTime) :
(player.deleteCount * 100 / player.deleteTotal) + "% " + player.deleteCount;
String speed = String.format("%,d/s", player.currentSpeed.get()*10/3);
// 名次
// ArrayList<Player> players1 = new ArrayList<>(players);
// players1.sort((p1,p2)-> (int) (p2.useTime()-p1.useTime()));
// int index = players1.indexOf(player) + 1;
// System.out.printf("%s\t%s\t\t%s\t\t%s\t\t%s\n", player.name, insert, search, delete, index);
textTable.addRowValues(player.name, insert, search, delete, speed);
textTable.addEmptyRow();
RecordPoint record = player.getRecord();
record.speed=player.currentSpeed.get()*10/3;
records.add(record);
try {
SseController.send(record); // 发送到远程显示
} catch (JsonProcessingException e) {
e.printStackTrace();
}
player.currentSpeed.set(0);
}
System.out.println(textTable);
}
void run(Player player, List<Integer> randomNumbers) {
int total = randomNumbers.size();// 1千万
player.insertTotal = total;
player.searchTotal = total;
player.deleteTotal = total;
long begin, end;
// 新增
begin = System.nanoTime();
for (Integer randomNumber : randomNumbers) {
player.insert(randomNumber);
player.insertCount++;
player.currentSpeed.incrementAndGet();
}
player.after("insert");
end = System.nanoTime();
player.insertTime = (end - begin) / 1000 / 1000;
// 查询
Collections.reverse(randomNumbers);
begin = System.nanoTime();
for (Integer randomNumber : randomNumbers) {
player.select(randomNumber);
player.searchCount++;
player.currentSpeed.incrementAndGet();
}
player.after("select");
end = System.nanoTime();
player.searchTime = (end - begin) / 1000 / 1000;
// 删除
begin = System.nanoTime();
for (Integer randomNumber : randomNumbers) {
player.delete(randomNumber);
player.deleteCount++;
player.currentSpeed.incrementAndGet();
}
player.after("delete");
end = System.nanoTime();
player.deleteTime = (end - begin) / 1000 / 1000;
}
private String timeToString(long milliscond) {
StringBuilder builder = new StringBuilder();
long minutes = TimeUnit.MILLISECONDS.toMinutes(milliscond);
long seconds = TimeUnit.MILLISECONDS.toSeconds(milliscond) % 60;
long m = milliscond % 1000;
if (minutes > 0) {
builder.append(minutes).append("m");
}
if (seconds > 0) {
builder.append(seconds).append("s");
}
if (m > 0) {
builder.append(".").append(m);
}
return builder.toString();
}
private static List<Integer> getRandomNumbers(int size) {
List<Integer> randomNumbers = new ArrayList(size);
for (int i = 0; i < size; i++) {
randomNumbers.add(i);
}
Collections.shuffle(randomNumbers);
return randomNumbers;
}
static class RecordPoint{
String name;
String type;
int speed;
int progress; // 进度
int count;// 已完成数
public RecordPoint(String name, String type, int speed, int progress, int count) {
this.name = name;
this.type = type;
this.speed = speed;
this.progress = progress;
this.count = count;
}
}
public static abstract class Player {
String name;
int insertTotal; //
int insertCount; // 新增进度 0~100
long insertTime;
int searchTotal; // 查询进度 0~100
long searchTime;
int searchCount; //
int deleteTotal; // 删除进度 0~100
long deleteTime;
int deleteCount; // 新增进度 0~100
AtomicInteger currentSpeed = new AtomicInteger(0);// 当前速度
public Player(String name) {
this.name = name;
}
long useTime() {
return insertTime + searchTime + deleteTime;
}
abstract void insert(Integer num);
abstract void select(Integer num);
abstract void delete(Integer num);
void after(String type) {
}
void clear() {
}
RecordPoint getRecord(){
if (insertCount>0 && insertCount< insertTotal) {
return new RecordPoint(name,"新增",currentSpeed.get()*10/3,insertCount * 100 / insertTotal,insertCount);
} else if (searchCount>0 && searchCount< searchTotal) {
return new RecordPoint(name,"查询",currentSpeed.get()*10/3,searchCount * 100 / searchTotal,sear
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
structure 跳表 vs 红黑树,对比了两种数据结构的优劣 跳表(Skip List)是一种基于并行链表的数据结构,类似于平衡树,用于在有序的序列中快速查找一个元素。它通过在链表上方增加多级索引,以实现快速查找的目的。每个索引级别都是原始链表的一部分,但它们的节点选择具有随机性,因此形成了一种分层结构。 跳表的实现是基于概率的,而不是严格的平衡性要求。这使得跳表相对于平衡树更容易实现和维护,并且在某些情况下,它的性能甚至可以超过平衡树。 红黑树(Red-Black Tree)是一种自平衡二叉查找树,它在每个节点上增加了一个额外的属性来存储节点的颜色(红色或黑色),并通过遵循一组简单的约束条件来保持树的平衡。 红黑树的特点包括: 每个节点都是红色或黑色。 根节点是黑色的。 每个叶子节点(NIL 节点,空节点)都是黑色的。 如果一个节点是红色的,则其两个子节点都是黑色的。 对于每个节点,从该节点到其所有后代叶子节点的简单路径上,黑色节点的数量必须相同。 红黑树的平衡性质保证了在最坏情况下的时间复杂度为 O(log n),其中 n 是树中节点的数量。这使得红黑树成为一种广泛应用于高性能数据结构的选择,比如在标准库中的集合类实现中,如 Java 中的 TreeSet 和 TreeMap。
资源推荐
资源详情
资源评论
收起资源包目录
structure 跳表 vs 红黑树.zip (103个子文件)
0536eb74343e6e1e0aa69e3aacbc51e015f97e 128B
10620b0bdf6ed36e7917ba7ad0200343175dcf 161B
137891791fe96927ad78e64b0aad7bded08bdc 16B
137891791fe96927ad78e64b0aad7bded08bdc 16B
20c5201e151dc33606d7dd28daeacd3935a069 182B
279583dead6e9602725a6ca4dbae54bc4b7db8 170B
28b0e37c7d206feb564310fdeec0927af4123a 55KB
3c553448c44a2f1d6ec228a8bab8d5a3c4ac09 167B
4ee831ee849796ce5317dfef038b8bfa67c270 606B
5ab4bab121c408ae246f6ef5fae23b58db2d65 556B
82ff01c6cdae4a1bb754a6e062954d77ac5c11 52KB
8ab018eaf11d9b3a4a90e7818ace373dfbb380 3KB
8fb2282df5b8f7263470a5a2dc0e196f35f35f 4KB
9e00a2a96fa9d7c5dbc9859664a78d980158c2 249B
9e00a2a96fa9d7c5dbc9859664a78d980158c2 249B
af5936a1740a768812ac6514586288b0be341c 188B
ba6f54ac526de46248af840bab26f33f946b93 3KB
bd6c8c40893a03d398ce286205b4f385e02ace 549B
MathMain.class 11KB
RedBlackTest.class 5KB
SkipList.class 4KB
MathMain$Array.class 2KB
MathMain$SkipListTable.class 1KB
MathMain$RedBlackTree.class 1KB
MathMain$LinkTable.class 1KB
MathMain$Player.class 1KB
SkipNode.class 654B
ColorTest.class 519B
mvnw.cmd 7KB
mvnw.cmd 7KB
config 137B
config 137B
description 73B
description 73B
df2854281f4cb6869e4830dd1a7abd1e946c18 4KB
.DS_Store 6KB
exclude 240B
exclude 240B
.gitignore 395B
.gitignore 395B
.gitignore 182B
HEAD 23B
HEAD 23B
index 864B
index 744B
structure-0.0.1-SNAPSHOT.jar 3.57MB
maven-wrapper.jar 61KB
maven-wrapper.jar 59KB
original-structure-0.0.1-SNAPSHOT.jar 18KB
MathMain.java 12KB
MathMain.java 11KB
RedBlackTest.java 6KB
SkipList.java 6KB
SkipList.java 6KB
SseController.java 2KB
WebApplication.java 302B
ColorTest.java 214B
WebApplicationTests.java 204B
HELP.md 861B
HELP.md 549B
mvnw 11KB
mvnw 10KB
maven-wrapper.properties 1019B
maven-wrapper.properties 233B
pom.properties 114B
application.properties 1B
application.properties 1B
application.properties 1B
application.properties 1B
pre-rebase.sample 5KB
pre-rebase.sample 5KB
update.sample 4KB
update.sample 4KB
fsmonitor-watchman.sample 3KB
fsmonitor-watchman.sample 3KB
pre-commit.sample 2KB
pre-commit.sample 2KB
prepare-commit-msg.sample 1KB
prepare-commit-msg.sample 1KB
pre-push.sample 1KB
pre-push.sample 1KB
commit-msg.sample 896B
commit-msg.sample 896B
pre-receive.sample 544B
pre-receive.sample 544B
applypatch-msg.sample 478B
applypatch-msg.sample 478B
pre-applypatch.sample 424B
pre-applypatch.sample 424B
pre-merge-commit.sample 416B
pre-merge-commit.sample 416B
post-update.sample 189B
post-update.sample 189B
workspace.xml 11KB
uiDesigner.xml 9KB
pom.xml 3KB
pom.xml 2KB
dependency-reduced-pom.xml 2KB
jarRepositories.xml 852B
compiler.xml 830B
共 103 条
- 1
- 2
资源评论
晓宜
- 粉丝: 6521
- 资源: 107
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功