目录
- 介绍
- 分析
- 完整代码:
免责声明:
本文章是实习期间的C++练习题目,可能会存在大量错误,文章仅作为个人笔记供作者自己方便观看.
介绍
在一个游戏里,可能会出现大量的NPC, 这些NPC有很多都是相同的名字.
存放NPC名字的文件可能是一个Excel文件, 现在的需求是在游戏运行时并且是在节省内存的基础上,快速找到某个NPC名字(某个字符串)的位置
分析
为了节省内存,我们不能使用string类型来存储字符串,因为string类型占用内存消耗太大了
在32位下,string占28个字节,在64位下,string占用40个字节(VS)
(不同的编译环境是不一样的)
我们先用set容器进行字符串的去重和排序,因为string内存太大,为了节省内存,所以我们选择不使用string类型,而是使用char数组,将排序去重后字符串存在char数组中,并且每一个NPC的名字都用 ‘ \0 ’隔开,然后为每一个NPC的名字编码,每个NPC名字的int编码是 字符串的首字符在 char数组中的位置. 因为字符串已经排序了,并且编码也是递增的,所以此时我们可以通过int编码对字符串使用二分操作.
完整代码:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<fstream>
#include<algorithm>
#include<set>
using namespace std;
string RandString()
{
char ch[500] = { 0 };
int len = rand() % 13 + 4;
for (int i = 0; i <= len; i++)
{
ch[i] = rand() % 26 + 'A';
}
return ch;
}
void Init()
{
std::string Result;
std::vector<std::string> Seed;
for (int i = 1; i <= 5000; ++i)
{
Seed.emplace_back(RandString());
}
for (int i = 1; i <= 10000; ++i)
{
Result.append(Seed[rand() % 5000]);
Result.append("\r\n");
}
FILE* fl = fopen("data.txt", "wb");
fwrite(Result.c_str(), sizeof(Result), 100, fl);
fclose(fl);
}
/上面都是准备阶段,创建一个有字符串的TXT文件.
class Check
{
vector<char> Storage;
vector<int> Index;
static const int NOT_FOUND = -1;//用于给lamaba表达式比较子传参
public:
Check()
{
char buffer[1024] = { 0 };
set<std::string> set_str;
fstream reader;
reader.open("data.txt");
while (reader >> buffer)
{
set_str.insert(buffer);
}
for (auto it : set_str)
{
for (int i = 0; i < it.size(); ++i)
{
Storage.emplace_back(it[i]);
}
Storage.emplace_back('\0');
}
int id = 0;
for (auto i : set_str)
{
Index.push_back(id);
id += i.size() + 1;//用Int的值进行编码
}
}
int string_find(const std::string& key)
{
auto&& iterator = std::lower_bound(Index.begin(), Index.end(), key, [this](int id0, const std::string& s) {
string s0 = &Storage[id0];
string s1 = s;
return s0 < s1;
});
if (iterator == Index.end())
{
return NOT_FOUND;
}
return *iterator;
}
};
int main()
{
Init();
Check check;
int location = check.string_find("ANDTBBZEGQTZED");
cout << "字符串的位置:" << location << endl;
}