论坛首页数据库天梯榜凯恩移动App 手游预约

//没登陆

欢迎您来到凯恩之角，奈非天!

凯恩之角 › 暗黑破坏神III › 仙塞学院›致各位罗技宏作者，发一个罗技的“多线程”框架

发帖

返回列表

1 234 5 / 5 页下一页

楼主: 雪落丶丿寒

[心得分享] 致各位罗技宏作者，发一个罗技的“多线程”框架

[复制链接]

骑士

子车车车

帖子：226

符文：245

31^#

加班写的头昏脑涨，打开凯恩又看了10分钟代码

发表于 2019-9-28 15:16:30 来自凯恩之角App |只看该作者来自：北京

回复举报

骑士

雪落丶丿寒

帖子：319

符文：70

32^#

子车车车发表于 2019-9-28 15:16
加班写的头昏脑涨，打开凯恩又看了10分钟代码

哈哈，今天加班可太惨了，连上8天嗷

发表于 2019-9-28 17:10:12 来自凯恩之角App |只看该作者来自：江苏

回复举报

领主

qykjerry

帖子：1221

符文：801

33^#

太牛逼了，程序员改变世界

点评

雪落丶丿寒哈哈发表于 2019-9-29 16:52

发表于 2019-9-28 20:32:03 来自凯恩之角App |只看该作者来自：上海

回复举报

骑士

雪落丶丿寒

帖子：319

符文：70

34^#

顺便贴一个之前写的数据模型，这个数据模型底层通过红黑树进行维护，学过java的朋友应该一眼就能看出来是treeMap。此数据模型的插入和读取的时间复杂度为o(lgn),并且底层为自排序数列，通过迭代器iter输出的值是从小到大的。需要的可以直接拿去用。

-- 红黑树--------------------------
BLACK = false;
Red = true;
Map = {root = nil,size = 0};
-----
function Map:new(o,root)--新建对象
o = o or {}
setmetatable(o,self)
self.__index=self
o.root = root
return o;
end
function Map:put(key,value)--存入键值对
local node = Node:new(key,value,BLACK)
self:insert(node);
end
function Map:get(key)--通过键获取值
local node = self:getNode(key);
return (node~=nil and {node.value} or {nil})[1];
end
function Map:remove(key)--删除
local node = self:getNode(key);
if node~=nil then self:delete(node) end;
end
function Map:length() return self.size end--获得集合长度
-------------------
Node = {key = nil,value=nil,left=nil,right=nil,parent=nil,color =nil};
function Node:new (key,value,color,left,right,parent,o)
o = o or {}
setmetatable(o,self)
self.__index=self
o.key = key
o.value = value
o.left = left
o.right = right
o.parent = parent
o.color = color
return o;
end
function Map:turn_left(x)--左旋
local y = x.right;
x.right = y.left;
if y.left ~= nil then y.left.parent = x end;
y.parent = x.parent;
if x.parent==nil then self.root=y elseif x.parent.left==x then x.parent.left=y else x.parent.right=y end
y.left = x;
x.parent = y;
end
function Map:turn_right(x)--右旋
local y = x.left;
x.left = y.right;
if y.right~=nil then y.right.parent=x end
y.parent = x.parent;
if x.parent==nil then self.root=y elseif x==x.parent.left then x.parent.left=y else x.parent.right=y end
y.right = x;
x.parent = y;
end
function Map:getNode(key)
local x = self.root;
while x~=nil do
if key==x.key then return x end
x=(x.key>key and {x.left} or {x.right})[1];
end
return nil;
end
function Map:insert(node)--插入
local y = nil;
local x = self.root;
while x~=nil do
if x.key==node.key then x.value=node.value;return 1 end
y=x;
x=(node.key<x.key and{x.left}or{x.right})[1]
end;
node.parent = y;
if y~=nil then if node.key<y.key then y.left=node else y.right=node end else self.root=node end;
node.color = RED;
self:insertFixUp(node);
self.size=self.size+1;
end
function Map:insertFixUp(node)--插入调整
local parent = node.parent
local gparent;
while (parent~=nil and parent.color==RED)do
repeat
gparent = parent.parent;
if(parent==gparent.left)then
local uncle = gparent.right;
if(uncle~=nil)and(uncle.color==RED)then
uncle.color = BLACK;
parent.color = BLACK;
gparent.color = RED;
node = gparent;
break;
end
if(parent.right==node)then
self:turn_left(parent);
local tmp = parent;
parent = node;
node = temp;
end
parent.color = BLACK;
gparent.color = RED;
self:turn_right(gparent);
else
local uncle = gparent.left;
if(uncle~=nil)and(uncle.color==RED)then
uncle.color = BLACK;
parent.color = BLACK;
gparent.color = RED;
node = gparent;
break;
end
if(parent.left==node)then
self:turn_right(parent);
local tmp = parent;
parent = node;
node = temp;
end
parent.color = BLACK;
gparent.color = RED;
self:turn_left(gparent);
end
until true;
parent = node.parent;
end
self.root.color = BLACK;
end
function Map:delete(node)
local replace = nil;
local parent = nil;
if node.left~=nil and node.right~=nil then
local x = node.right;
while x.left~=nil do x = x.left end
node.key=x.key;node.value=x.value;
return self:delete(x);
end
if node.parent==nil then
self.root=(node.left~=nil and {node.left} or {node.right})[1];
replace=self.root;
if self.root~=nil then self.root.parent=nil end;
else
local child = (node.left~=nil and {node.left}or{node.right})[1];
if node.parent.left==node then node.parent.left=child;
else node.parent.right=child end;
if child~=nil then child.parent=node.parent end
replace = child;
parent = node.parent;
end
if node.color==BLACK then self:deleteFixUp(replace,parent) end;
self.size = self.size-1;
end
function Map:deleteFixUp(replace,parent)
local brother = nil;
while replace==nil or replace.color==BLACK and replace~=self.root do
if parent.left==replace then
brother=parent.right;
if brother.color==RED then
brother.color = BLACK;
parent.color = RED;
self:turn_left(parent);
brother=parent.right;
end
if(brother.left==nil or brother.left.color==BLACK)and(brother.right==nil or brother.right.color==BLACK)then
if parent.color==RED then
parent.color=BLACK;
brother.color=RED;
break;
else
brother.color=RED;
replace=parent;
parent=replace.parent;
end
else
if brother.left~=nil and brother.left.color==RED then
brother.left.color=parent.color;
parent.color=BLACK;
self:turn_right(brother);
self:turn_left(parent);
elseif brother.right~=nil and brother.right.color==RED then
brother.color = parent.color;
parent.color = BLACK;
brother.right.color = BLACK;
self:turn_left(parent);
end
break;
end
else
brother=parent.left;
if brother.color==RED then
brother.color = BLACK;
parent.color = RED;
self:turn_right(parent);
brother=parent.left;
end
if(brother.left==nil or brother.left.color==BLACK)and(brother.right==nil or brother.right.color==BLACK)then
if parent.color==RED then
parent.color=BLACK;
brother.color=RED;
break;
else
brother.color=RED;
replace=parent;
parent=replace.parent;
end
else
if brother.right~=nil and brother.right.color==RED then
brother.right.color=parent.color;
parent.color=BLACK;
self:turn_left(brother);
self:turn_right(parent);
elseif brother.left~=nil and brother.left.color==RED then
brother.color = parent.color;
parent.color = BLACK;
brother.left.color = BLACK;
self:turn_right(parent);
end
break;
end
end
end
if replace~=nil then replace.color=BLACK;end
end
function Map:iter()--迭代器
local node = self.root;
if node==nil then return nil end;
while(node.left~=nil)do node=node.left end;
return function()
local prv = node;
if node==nil then return nil end;
if node.right~=nil then
node=node.right;
while(node.left~=nil)do
node=node.left
end
else if node.parent==nil then return nil end;
while(node.parent.left~=node)do node=node.parent if node.parent==nil then return prv end end
node=node.parent;
end
return prv;
end
end
-- 红黑树 end---------------------