月归档：2017年11月

暴雪是一个不会做游戏的公司

发表于2017年11月20日由archdevil

看到标题，我相信大部分人就会感到不适了，如果是暴白可能就要开始喷粪了。在讨论暴 … 继续阅读 →

发表在游戏 | 留下评论

C++跳表 skip_list 模板

发表于2017年11月2日由archdevil

#ifndef __SKIP_LIST_H_
#define __SKIP_LIST_H_

#include <iostream>
#include <cstdio>
#include <stdlib.h> 
#include <time.h>  

const int MAX_LEVEL = 32;

/* 从第0层开始，第0层拥有所有元素
 * 
 *
 *
 */


/* T需要提供 GetKey()与GetValue()函数 
 */
template <class T>
struct SLNode{
	T*		element;
	 /* 从第0层开始，每一层的指针。
	  * 如：高度为3，则0、1、2层都有指针，之后的为NULL
	  */
	SLNode* forward[MAX_LEVEL];
	 /* 当前节点与后继节点跨过的节点数量
	  * 用来查询某元素在列表中的排名
	  */
	int		span[MAX_LEVEL];
};

template <class T>
class SkipList{
public:
	typedef typename SLNode<T> Element;

public:
	void		Create( int level );
	void		Insert( T* );
	bool		Delete( int key );
	SLNode<T>*	Search( int key );
	int			Rank( int key ); // 获得key在跳表中的排名，查询不到返回-1
 
	// test
	void Dump();

private:
	Element* CreateNode( T* );

private:
	int			m_level;
	int			m_max_level;
	int			m_length;
public:
	SLNode<T>	m_root;	 
};

// 返回0到小于max_level之间的值
int GetRandLevel( int max_level )
{
	static bool init = false;
	if( false == init )
	{
		srand((unsigned)time(NULL));  
		init = true;
	}

	int level = 0;
	for( int i = 1; i < max_level; i++ )
	{
		/* 新节点的层数的概率，每次向上延伸一层都有p的概率。 q = 1 - p
		 * 如: 节点为0层的概率是q, 为第1层是p, 为第2层是p * p， 以此类推
		 * 这里取p = 0.5， 
		 * 据说取0.25来说对有GC(垃圾回收机制)的语言来说是最好的，我有查询过论文，但是没有细读。
		 */
		if( rand() % 2 )
			break;
		else
			level++;
	}

	return level;
}

template<class T>
void SkipList<T>::Create( int level )
{
	level = level < MAX_LEVEL ? level : MAX_LEVEL;
	m_max_level		= level;
	m_level			= 0;
	m_root.element	= NULL;
	m_length		= 0;
	/* 初始化根节点
	 */
	for( int i = 0; i < m_max_level; i++ )
	{
		m_root.forward[i]	= NULL;
		m_root.span[i]		= 0;
		m_root.element		= new T;
		m_root.element->SetKey( -1 );
	}
}

template<class T>
void SkipList<T>::Insert( T* t )
{
	 //定义 节点数组 update用户保存插入节点每一层的前驱节点
	Element *update[MAX_LEVEL];
	Element *p = NULL, *q = NULL;
	//rank 数组 用于保存 插入节点插入位置在每一层中跨国的节点数
	int rank[MAX_LEVEL] = {0};
	//设置头节点
	q = &m_root;

	int level = GetRandLevel( m_max_level );
	for( int i = m_level; i >= 0; --i )
	{	
		//如果是最高层，则标示扩过0个 节点，否则 记录跨过的节点数 与上一层相同
		if ( i != m_level ) rank[i] = rank[i + 1];
		else rank[i] = 0;

		while( ( p = q->forward[i] ) && t->GetKey() > q->element->GetKey() )
		{
			rank[i] += q->span[i];	
			q = p;					
		}
		update[i] = q;
		//if ( i > 0 )
		//	rank[0] += rank[i];
	}

	if( p != NULL && p->element->GetKey() == t->GetKey())
	{
		printf( "same key %d\n", t->GetKey() );
		return;
	}

	//如果层高 比 当前层高 要高，则将header的指针指向 超出当前层高的部分
	if( level > m_level )
	{
		for( int i = level; i > m_level; --i )
		{
			update[i] = &m_root;
			update[i]->span[i] = m_length;
			rank[i] = 0;

		}
		m_level = level;
	}

	Element *node = CreateNode( t );
	      /*
         header                update[i]     x    update[i]->forward         
          |-----------|-----------|-----------|-----------|-----------|-----------|
                                  |<---update[i].span---->|
          |<-------rank[i]------->|                      
          |<-------------------rank[0]------->|
         
          更新update数组中span值和新插入元素span值, rank[0]存储的是x元素距离头部的距离, rank[i]存储的是update[i]距离头部的距离, 上面给出了示意图
          */
	for ( int i = level; i >= 0; --i )
	{
		node->forward[i] = update[i]->forward[i];
		update[i]->forward[i] = node;

		node->span[i] = update[i]->span[i] - ( rank[0] - rank[i] );
		update[i]->span[i] = ( rank[0] - rank[i] ) + 1;
	}

	// 上层的所有前节点的span都需要加1
	for( int i = level + 1; i <= m_level; i++ )
	{
		update[i]->span[i]++;
	}		

	m_length++;
}

template<class T>
SLNode<T>* SkipList<T>::CreateNode( T* t ) 
{
	Element *node = new Element;
	node->element = t;
	for( int i = 0; i < m_max_level; i++ )
	{
		node->forward[i]	= NULL;			
		node->span[i]		= 0;
	}
	return node;
}

template<class T>
bool SkipList<T>::Delete( int key )
{
	Element *update[MAX_LEVEL];
	Element *p = NULL, *q = NULL;
	q = &m_root;

	for( int i = m_level; i >= 0; --i )
	{
		while( ( p = q->forward[i] ) && ( p->element->GetKey() < key )  )
		{
			q = p;
		}
		update[i] = q;
	}

	if( NULL == p || p->element->GetKey() != key )
	{
		// 找不到
		return false;
	}

	for ( int i = 0; i < m_level; ++i )
	{
		if( update[i]->forward[i] == p )
		{
			// 存在删除节点的层数， 间隔 =  原间隔 + 删除节点的间隔 - 1
			update[i]->span[i] += p->span[i] - 1;
			update[i]->forward[i] = p->forward[i];
		}
		else
		{
			// 不存在删除节点的层数， 只需要减少1
			update[i]->span[i] -= 1;
		}
	} 

	for( int i = m_level; i >= 0; --i )
	{
		// 某层不存在节点，高度需要减1
		if ( NULL == m_root.forward[i] )
			m_level = i - 1;
		else		
			break;		
	}
	
	delete p;
	m_length--;
	return true;
}

template<class T>
SLNode<T>* SkipList<T>::Search( int key )
{
	Element *q = NULL, *p = NULL;
	q = &m_root;

	for( int i = m_level; i >= 0; --i )
	{
		while( ( p = q->forward[i] ) && p->element->GetKey() < key )
		{
			q = p;
		}
	}
	if( p != NULL && p->element->GetKey() == key )
		return p;
	return NULL;
}

template<class T>
int SkipList<T>::Rank( int key )
{
	Element *q = NULL, *p = NULL;
	q = &m_root;
	int rank = 0;

	for( int i = m_level; i >= 0; --i )
	{
		while( ( p = q->forward[i] ) && p->element->GetKey() < key )
		{			
			rank += q->span[i];
			q = p;			
		}
		//rank += q->span[i];
	}
	if( p != NULL && p->element->GetKey() == key )
	{		
		return rank;
	}
	return -1;
}

template<class T>
void SkipList<T>::Dump()
{
	printf( "\n" );
	for( int i = 0; i <= m_level; ++i )
	{
		Element *p = &m_root;
		while( ( p = p->forward[i] ) && p != NULL )
		{
			if ( p->element != NULL )
				printf( "%d ", p->element->GetKey() );
		}
		printf( "\n" );
	}
	printf( "\n" );
}

#endif

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

#ifndef __SKIP_LIST_H_

#define __SKIP_LIST_H_

#include <iostream>

#include <cstdio>

#include <stdlib.h>

#include <time.h>

const int MAX_LEVEL = 32;

/* 从第0层开始，第0层拥有所有元素

/* T需要提供 GetKey()与GetValue()函数

template <class T>

struct SLNode{

T* element;

/* 从第0层开始，每一层的指针。

* 如：高度为3，则0、1、2层都有指针，之后的为NULL

SLNode* forward[MAX_LEVEL];

/* 当前节点与后继节点跨过的节点数量

* 用来查询某元素在列表中的排名

int span[MAX_LEVEL];

};

template <class T>

class SkipList{

public:

typedef typename SLNode<T> Element;

public:

void Create( int level );

void Insert( T* );

bool Delete( int key );

SLNode<T>* Search( int key );

int Rank( int key ); // 获得key在跳表中的排名，查询不到返回-1

// test

void Dump();

private:

Element* CreateNode( T* );

private:

int m_level;

int m_max_level;

int m_length;

public:

SLNode<T> m_root;

};

// 返回0到小于max_level之间的值

int GetRandLevel( int max_level )

{

static bool init = false;

if( false == init )

{

srand((unsigned)time(NULL));

init = true;

}

int level = 0;

for( int i = 1; i < max_level; i++ )

{

/* 新节点的层数的概率，每次向上延伸一层都有p的概率。 q = 1 - p

* 如: 节点为0层的概率是q, 为第1层是p, 为第2层是p * p，以此类推

* 这里取p = 0.5，

* 据说取0.25来说对有GC(垃圾回收机制)的语言来说是最好的，我有查询过论文，但是没有细读。

if( rand() % 2 )

break;

else

level++;

}

return level;

}

template<class T>

void SkipList<T>::Create( int level )

{

level = level < MAX_LEVEL ? level : MAX_LEVEL;

m_max_level = level;

m_level = 0;

m_root.element = NULL;

m_length = 0;

/* 初始化根节点

for( int i = 0; i < m_max_level; i++ )

{

m_root.forward[i] = NULL;

m_root.span[i] = 0;

m_root.element = new T;

m_root.element->SetKey( -1 );

}

template<class T>

void SkipList<T>::Insert( T* t )

{

//定义节点数组 update用户保存插入节点每一层的前驱节点

Element *update[MAX_LEVEL];

Element *p = NULL, *q = NULL;

//rank 数组用于保存插入节点插入位置在每一层中跨国的节点数

int rank[MAX_LEVEL] = {0};

//设置头节点

q = &m_root;

int level = GetRandLevel( m_max_level );

for( int i = m_level; i >= 0; --i )

{

//如果是最高层，则标示扩过0个节点，否则记录跨过的节点数与上一层相同

if ( i != m_level ) rank[i] = rank[i + 1];

else rank[i] = 0;

while( ( p = q->forward[i] ) && t->GetKey() > q->element->GetKey() )

{

rank[i] += q->span[i];

q = p;

}

update[i] = q;

//if ( i > 0 )

// rank[0] += rank[i];

}

if( p != NULL && p->element->GetKey() == t->GetKey())

{

printf( "same key %d\n", t->GetKey() );

return;

}

//如果层高比当前层高要高，则将header的指针指向超出当前层高的部分

if( level > m_level )

{

for( int i = level; i > m_level; --i )

{

update[i] = &m_root;

update[i]->span[i] = m_length;

rank[i] = 0;

}

m_level = level;

}

Element *node = CreateNode( t );

header update[i] x update[i]->forward

|-----------|-----------|-----------|-----------|-----------|-----------|

|<---update[i].span---->|

|<-------rank[i]------->|

|<-------------------rank[0]------->|

更新update数组中span值和新插入元素span值, rank[0]存储的是x元素距离头部的距离, rank[i]存储的是update[i]距离头部的距离, 上面给出了示意图

for ( int i = level; i >= 0; --i )

{

node->forward[i] = update[i]->forward[i];

update[i]->forward[i] = node;

node->span[i] = update[i]->span[i] - ( rank[0] - rank[i] );

update[i]->span[i] = ( rank[0] - rank[i] ) + 1;

}

// 上层的所有前节点的span都需要加1

for( int i = level + 1; i <= m_level; i++ )

{

update[i]->span[i]++;

}

m_length++;

}

template<class T>

SLNode<T>* SkipList<T>::CreateNode( T* t )

{

Element *node = new Element;

node->element = t;

for( int i = 0; i < m_max_level; i++ )

{

node->forward[i] = NULL;

node->span[i] = 0;

}

return node;

}

template<class T>

bool SkipList<T>::Delete( int key )

{

Element *update[MAX_LEVEL];

Element *p = NULL, *q = NULL;

q = &m_root;

for( int i = m_level; i >= 0; --i )

{

while( ( p = q->forward[i] ) && ( p->element->GetKey() < key ) )

{

q = p;

}

update[i] = q;

}

if( NULL == p || p->element->GetKey() != key )

{

// 找不到

return false;

}

for ( int i = 0; i < m_level; ++i )

{

if( update[i]->forward[i] == p )

{

// 存在删除节点的层数，间隔 = 原间隔 + 删除节点的间隔 - 1

update[i]->span[i] += p->span[i] - 1;

update[i]->forward[i] = p->forward[i];

}

else

{

// 不存在删除节点的层数，只需要减少1

update[i]->span[i] -= 1;

}

for( int i = m_level; i >= 0; --i )

{

// 某层不存在节点，高度需要减1

if ( NULL == m_root.forward[i] )

m_level = i - 1;

else

break;

}

delete p;

m_length--;

return true;

}

template<class T>

SLNode<T>* SkipList<T>::Search( int key )

{

Element *q = NULL, *p = NULL;

q = &m_root;

for( int i = m_level; i >= 0; --i )

{

while( ( p = q->forward[i] ) && p->element->GetKey() < key )

{

q = p;

}

if( p != NULL && p->element->GetKey() == key )

return p;

return NULL;

}

template<class T>

int SkipList<T>::Rank( int key )

{

Element *q = NULL, *p = NULL;

q = &m_root;

int rank = 0;

for( int i = m_level; i >= 0; --i )

{

while( ( p = q->forward[i] ) && p->element->GetKey() < key )

{

rank += q->span[i];

q = p;

}

//rank += q->span[i];

}

if( p != NULL && p->element->GetKey() == key )

{

return rank;

}

return -1;

}

template<class T>

void SkipList<T>::Dump()

{

printf( "\n" );

for( int i = 0; i <= m_level; ++i )

{

Element *p = &m_root;

while( ( p = p->forward[i] ) && p != NULL )

{

if ( p->element != NULL )

printf( "%d ", p->element->GetKey() );

}

printf( "\n" );

}

printf( "\n" );

}

#endif

发表在 C++, 算法 | 留下评论

月归档：2017年11月

暴雪是一个不会做游戏的公司

C++跳表 skip_list 模板

搜索

关于本站

血型

文章归档