TEG后端开发一面总结

塞尔达这个系列，我在之前只是略有耳闻。我第一次接触《旷野之息》是当switch和这一作首发的时候，那个时候我的资讯流突然就被塞尔达刷屏了。
仿佛周围的人都在玩塞尔达（并没有），各种游戏玩家都在说塞尔达是怎样的神作。如今如果你在网络上搜索关键词“塞尔达”，你会看到各种塞尔达的安利文。
我当时虽然有玩这作的冲动，但是苦于没有switch，只能“望游兴叹”。

体验和亮点

直到去年双11,我才在狗东入手了一台swtich，当然，第一件事就是买《旷野之息》来玩。
说实话，我很久没有这样有动力玩一款RPG了，两年前在PC上买的《巫师3》，玩到20多级以后就再也没碰过，原因是我在游玩过程中，经常会遇到，为了钱或者是装备，必须要去做我不想去做的事。
当我想一心一意推主线的时候，我会发现，我的等级不够/我的钱不够/装备不好，甚至最绝望的是，装备坏了都没钱修……
这些事情，都极大的阻碍了我的游戏体验，虽然《巫师3》同样也是开放世界，并且似乎看起来，这个世界比塞尔达的还要大和真实。但是由于这些方面的缺失，所以很难让人有肝下去的欲望。（至少我是这样的）

《旷野之息》在这些方面处理的非常好，首先他不是采用传统的等级机制来限制玩家，装备也没有“修理”这个选项。所有武器都有耐久。这样就既保证了玩家不再受到经验值的束缚，能做什么事完全取决于自身水平，林克的成长也是玩家自己的成长。
让玩家随着游戏人物一起成长，玩家就更乐意去做一些能够提升他自己的事情。其次，里面采用到的引力法则和“三角形法则”可以看到，任天堂真的在游戏性上，下足了功夫，游戏里的每一座山，每一颗树，都不是随随便便就加上的，除了考虑观感的同时，还要对玩家的行为作出预测，利用不同的对象去引导玩家。

《旷野之息》还有一个非常巧妙的地方，还在于物理和化学引擎的使用。什么是化学引擎，这个是任天堂这次提出的一个新概念，对应物理引擎。
所谓物理引擎就是“计算物体的行为的引擎”。而化学引擎，则是“计算物体的状态的引擎”。

这跟我们认识的物理和化学上面当然就有一些出入。
比如游戏中的电流和扇出来的风，这些本来应该是物理引擎处理的东西，但是实际处理的却是化学引擎。
当然，游戏本身就是应该对真实世界的抽象简化再处理后得到的产物，所以根据上面的对引擎的定义就不难理解，为什么本来应该是物理引擎处理的事，却变成了化学引擎来做。
有了物理和化学引擎的加持还不够，目前大量游戏都在使用Havok这个物理引擎，但是只有《旷野之息》将物理引擎融入了游戏的玩法本身。

不足与缺憾

说了这么多《旷野之息》做的好的地方，我也要说说他给我的体验带来的缺憾之处。

首先就是对于NPC行为的处理，NPC的行为过于单一，甚至不如里面的怪物的行为丰富，所以有时候觉得很出戏。
还记得有一对在寻找静谧公主的情侣，当我把静谧公主放到他们面前的时候，和他们对话的内容仍然是感叹静谧公主难寻。
同样的事情发生在一队找生命松露的姐妹身上。这在游玩过程中，造成了不少的阻碍。
不少人在玩《旷野之息》的时候，会感受到一种孤独感，我想这可能就是因为NPC的对话并不会随着玩家的行为改变的原因。
任天堂不知道有没有试过将物理和化学引擎同样运用到NPC上，我想，这可能会带来一番新的体验。

其次还有一些各种各样的小问题，比如没有充分利用到Switch的机能啦，剧情有些不够自然导致救公主的欲望较低啦之类的。
当然这些小问题都是有其存在的原因，比如要考虑到这之前是一款wiiu上的游戏，然后也是要以游戏性为最高优先级。
在这里指出批评一番的话，颇有些鸡蛋里挑骨头的意味。所以在此就不多做评论。

在最后，不管这款游戏有怎样的小毛病，也不得不承认其对于开放世界的贡献和其神作的地位。
希望以后，能有更多像《旷野之息》这样的大作诞生！�样的大作诞生！

存储器的层次结构

发表于 2019-01-30 更新于 2020-03-04

编写程序的时候，性能优化的瓶颈不是往往不是在与计算量，而是I/O时间的开销。要能够更好的优化程序，就必须得了解一些存储器层次知识。

我们编写程序，直接打交道的存储器就是寄存器和内存，有时还会加上硬盘。但其实，在计算机内部，缓存的作用也是不容小视的。内部计算机中的存储器容量越大，单位成本越便宜，但是相应的速度也就越慢，一台现代计算机拥有的存储器从CPU访问的速度由快到慢排序大致有以下几个部分：寄存器、CPU中的L1L2L3缓存（SRAM）、内存（DRAM）、固态硬盘、机械硬盘。在硬盘内部为了提升速度，也带有一定大小的缓存。可见，缓存无处不在，我们只有利用好缓存，才能够有效缩短I/O时间。

考虑这两个不同计算二维数组元素和的函数：

long long sum1(int m, int n, int array[m][n])
{
  long long ret = 0;
  for (int i = 0;i < m;i++)
  {
    for (int j = 0;j < n;j++)
    {
      ret += array[i][j];
    }
  }
  return ret;
}
long long sum2(int m, int n, int array[m][n])
{
  long long ret = 0;
  for (int j = 0;j < n;j++)
  {
    for (int i = 0;i < m;i++)
    {
      ret += array[i][j];
    }
  }
  return ret;
}

乍一看，这两个函数似乎没有什么区别，但其实，在m和n足够大的情况下，sum1的运行速度要比sum2要快很多。这就是缓存的作用，在sum1中，我们对array的访问基本上顺序的，由于array在内存中是顺序存储的，所以我们访问内存的时候，也是顺序访问。而内存访问一次需要花费不少时钟周期，所以缓存会一次读取内存中接下来的部分，在下面的访问中，省去了每次都要访问内存的时间。然而，由于我们的缓存不是无限大的，后面加载的值会覆盖掉前面的值，在sum2里，因为我们不是顺序的访问内存，所以在m和n够大的情况下，我们基本上无法从缓存里拿到我们想要的值。这就导致了sum1和sum2的运行效率有着决定性的差距。在编写程序时，我们也要利用这一点，写出带有所谓“空间局部性”的程序，尽量顺序访问内存，可以使运行速度提升不少。

除了“空间局部性”以外，还有一个对于程序运行速度关系很大的性质——“时间局部性”，所谓时间局部性，就是把对于同一块内存的访问，尽量集中到一个时间内，这样可以有效的利用这块内存被预读到缓存的性质，提高I/O效率。具体的举例由于需要针对不同类型的缓存才能看出效果，在这里就不做展开了。

十分钟用Python创建一个Echo Server

发表于 2018-12-04 更新于 2020-03-04

近日想玩一下网络编程方面，但是实在不想用C去写笨重的代码，于是就使用python写了一个简单的TCP Echo Server。代码很少，标题虽然写了十分钟，但是我自己磕磕碰碰还是折腾了一天（标题党了）

什么是Echo Server

Echo Server一般是运行在7端口的一项服务，其一大特点就是会返回从客户端接收到的消息。（通俗来说就是复读机）

Echo Server能用来做什么

Echo Server是最容易实现的网络服务之一，可以用来学习Socket编程的一些基本知识，还可以用来检测客户端与服务器之间的连通性，丢包率，连接速度和传输速度。

实现思路

一开始我觉得应该挺容易的，快速的从网上找到了一些相关的代码，采用Ctrl C V大法，但是却发现有很多问题，最终还是自己动手才写出一个像样的东西。

首先第一步，我们得监听一个端口，调用python的socket模块，让其绑定在一个端口，监听TCP连接。

1
2
3

#使用IPV4和TCP连接，监听端口程序
tcpSocket = socket.Socket(socket.AF_INET, socket.SOCK_STREAM)
tcpSocket.bind((HOST, PORT))

第二步，我们检测是否有客户端连接上，如果连接上了，就将对这个客户的处理逻辑单独放到一个线程里跑(这是坑最多的一部，看了网上很多代码，要么就是直接一个线程，无法处理多客户，要么就是所有客户端共用一个处理线程，当数据量较大时就会出现问题)

while True:
  clientSocket, clientAddr = tcpSocket.accept()
  t = threading.Thread(target = handle, args = (clientSocket, clientAddr), daemon = True)
  t.start()

最后我们只要在线程处理逻辑中，编写相关的回显逻辑，就可以了。

while True:
  data = clientSocket.recv(BUFSIZE)
  if not data:
    break
  clientSocket.send(data)
clientSocket.close()

当然上面为了演示，对实际代码做了很多精简，完整的代码在下面（需要科学上网）:

服务端
 客户端
(客户端为一个类似nc的小程序)

哈希表的优势和实现

发表于 2018-08-24 更新于 2020-03-04

在对二叉树进行学习之后，相信每个人都会对于其精妙和最坏情况下仍然能保证线性对数级别时间复杂度的增删改查赞叹不已。其用来实现符号表（存储键值对）是一种较为高效的实现。

在没有学习哈希表之前，如果我告诉你，有一种数据结构，可以对键值对做到常数时间级别的增删改查，你一定不会相信。但是哈希表做到了，有这么高效的数据结构怎么能够不对其有了解呢？这次我们就来谈谈哈希表这种数据结构的魅力所在。

要了解哈希表，首先我们得来看一看这个哈希函数是什么东西。函数，其实就是一个映射，将所有在定义域的值映射到值域范围内。有时候我们需要对任意长度的信息，提取出信息的“指纹”，这个指纹在一定程度上反映了信息的内容，但是占用空间大大缩小。此时我们就要设计一个函数，其定义域为信息可能出现的所有空间，而值域则为需要”指纹”的大小。当这个函数可以用来完成上述用途时，这个函数就被称为哈希函数，哈希函数输出的结果被称为哈系值。一些著名的哈希函数有MD5、SHA-1、SHA-2等。

有了哈希函数，我们就可以利用哈希函数的映射，将任意长度的键映射到一个合理的区间内。试想创建一个数组，数组的下标为键的哈希值。数组的内容即为键值对的值，当我们已知键，要对值进行查找时，只需要对键取哈希，就可以在常数时间内获取到值的内容。

在哈希表的实现中，我们设计的哈希函数应该考虑的重点有如下几个

尽可能让输入中的每一位都对输出结果造成影响，减少碰撞的发生
计算尽量简单，否则哈希函数的计算也会对运行时间造成极大的影响
输出范围应当尽可能的可控

因为2的原因，我们不得不抛弃MD5和SHA这些著名的哈希函数，并且这些函数也很难自己控制输出的数据范围。哈希函数的好坏，决定了哈希表的效率。当然，实现哈希函数的方法不止一种，这里介绍比较常用的一种方法——除留余数法。

这里其实可以采用一种简单的运算来实现这个哈希函数——模运算。相信学过一点编程语言的朋友都知道，对某个数取模就是除以某个数求余数。假设我们需要0-97的哈希范围，无论多大的数，只需要对97取模，就可以获得一个在0-97之间的数，但是要注意，当我们采用的基数不是素数时，就会导致输出仅仅依赖于输入的后几位数，不满足1的情况发生。所以在使用这种方法作为哈希函数的过程中，应当选择合适的基数。

当我们有了哈系函数以后，就可以利用哈希函数类构造哈希表了。首先创建一个很大的数组array，数组的大小即为哈希函数的值域范围，然后在插入键值对时，直接使用array[hash(key)] = value的方式给数组赋值，当需要已知键，想要取出值的时候，同样采用array[hash(key)]即可。

下面我对哈希表的实现，供参考：

哈希碰撞的解决方法

读到这里，你可能已经发现了，哈希函数由于对信息进行了缩短，所以导致了有可能出现碰撞的存在，这就好像出现了两个名字一样的“张三”，当我们说，张三坐在某某位置上时，并不知道到底是哪个张三真正坐在位置上。这里有两种解决方案：拉链法和线性探测法

拉链法是将具有相同哈希值的函数放到一个链表里（整个哈希表呈现为一个链表的数组），用一个链表的数组来存放所有键值对。这种方法在最坏情况（哈希函数的返回值始终为常数）下会退化成链表。

而线性探测法则是采用两个数组，一个放键，一个放值，当即将保存的位置已经保存有数据的时候，从该位置开始往下遍历，直到遇到一个空的位置进行插入。这种方法在最坏情况下会退化成为数组。

两种方案对比，很难说哪种就一定跟高效，具体的实现中应当使用哪一种应该很据不同需求选取。

下面分别是线性探测和拉链法的哈希表实现


template <typename Key, typename Value> class LinearProbingHashST
{
private:
  size_t size_;
  size_t pair_counts_ = 0;
  Key *key_arr_ ;
  Value *value_arr_;
  size_t gethash_(Key k);
  Value get_ (Key k, size_t index);
  Value put_ (Key k, Value val, size_t index);
  void LinearProbingHashST_(size_t size);
public:
  LinearProbingHashST (size_t size);
  LinearProbingHashST ();
  virtual ~LinearProbingHashST ();
  void put(Key k, Value val);
  Value get(Key k);
  void erase(Key k);
  bool empty();
};

template <typename Key, typename Value>
size_t LinearProbingHashST<Key, Value>::
gethash_(Key k)
{
  return ( int(k) & 0x7FFFFFFF )% size_;
  //return 1;
}

template <typename Key, typename Value>
void LinearProbingHashST<Key, Value>::
LinearProbingHashST_(size_t size)
{
  size_ = size;
  key_arr_ = new Key[size_];
  value_arr_ = new Value[size_]();
}

template <typename Key, typename Value>
LinearProbingHashST<Key, Value>::
LinearProbingHashST(size_t size)
{
  LinearProbingHashST_(size);
}

template <typename Key, typename Value>
LinearProbingHashST<Key, Value>::
LinearProbingHashST()
{
  LinearProbingHashST_(997);
}

template <typename Key, typename Value>
LinearProbingHashST<Key, Value>::
~LinearProbingHashST()
{
  delete[] key_arr_;
  delete[] value_arr_;
}

template <typename Key, typename Value>
void LinearProbingHashST<Key, Value>::
put(Key k, Value val)
{
  if (pair_counts_+1 >= size_)
  {
    return;
  }
  size_t i;
  for (i = gethash_(k);key_arr_[i] != k;i = (i+1) % size_)
  {
    if (key_arr_[i] == (Key)NULL)
    {
      key_arr_[i] = k;
      pair_counts_++;
      break;
    }
  }
  value_arr_[i] = val;
}

template <typename Key, typename Value>
Value LinearProbingHashST<Key, Value>::
get(Key k)
{
  for (size_t i = gethash_(k);key_arr_[i] != (Key) NULL;i = (i+1) % size_)
  {
    if (key_arr_[i] == k)
    {
      return value_arr_[i];
    }
  }
  return (Value) NULL;
}

template <typename Key, typename Value>
void LinearProbingHashST<Key, Value>::
erase(Key k)
{
  for (size_t i = gethash_(k);key_arr_[i] != (Key) NULL;i = (i + 1) % size_)
  {
    if (key_arr_[i] == k)
    {
      key_arr_[i] = (Key) NULL;
      value_arr_[i] = (Value) NULL;
      pair_counts_--;
      for (size_t j = i+1;key_arr_[j] != (Key) NULL;j = (j+1) % size_)
      {
        Key temp_k = key_arr_[j];
        Value temp_val = value_arr_[j];
        key_arr_[j] = (Key) NULL;
        value_arr_[j] = (Key)NULL;
        pair_counts_--;
        put(temp_k, temp_val);
      }
      break;
    }
  }
}

template <typename Key, typename Value>
bool LinearProbingHashST<Key, Value>::
empty()
{
  return pair_counts_ == 0;
}


template <typename Key, typename Value>class SequentialSearchST
{
private:
  //节点
  struct Node
  {
    Key key;
    Value value;
    Node *next;
    Node (Key k,Value v,Node *n):key(k),value(v),next(n){};
  };
  Node *head_ = nullptr;
  Node *erase_(Node *node, Key k);
public:
  SequentialSearchST() = default;
  //获取对应键的键值
  Value get(Key k);
  //设置指定键的键值，如没有，创建一个新键
  void put(Key k, Value val);
  //返回符号表存的元素个数
  int size();
  bool empty();
  void erase(Key k);
  virtual ~SequentialSearchST();
};

template <typename Key, typename Value>
typename SequentialSearchST<Key, Value>::Node*
SequentialSearchST<Key,Value>::erase_(Node *node, Key k)
{
  if (node == nullptr)
  {
    return nullptr;
  }
  if (node->key == k)
  {
    Node *next_node = node->next;
    delete node;
    return next_node;
  }
  node->next = erase_(node->next, k);
  return node;
}

template <typename Key, typename Value>
Value SequentialSearchST<Key,Value>::get(Key k)
{
  for (Node *it = head_; it != nullptr; it = it->next)
  {
    if (k == it->key)
    {
      return it->value;
    }
  }
  return (Value)0;
}

template <typename Key, typename Value>
void SequentialSearchST<Key,Value>::put(Key k, Value val)
{
  for (Node *it = this->head_; it!= nullptr; it = it->next)
  {
    if (k == it->key)
    {
      it->value = val ;
      return;
    }
  }
  head_ = new Node(k, val, head_);
}

template <typename Key, typename Value>
int SequentialSearchST<Key,Value>::size()
{
  int count = 0;
  for(Node *it = head_;it != nullptr;it = it->next)
  {
    count++;
  }
  return count;
}

template <typename Key, typename Value>
SequentialSearchST<Key,Value>::~SequentialSearchST()
{
  Node *it = head_;
  while (it != nullptr)
  {
    Node *del_node = it;
    it = it->next;
    delete del_node;
  }
}

template <typename Key, typename Value>
bool SequentialSearchST<Key,Value>::empty()
{
  return head_ == nullptr;
}

template <typename Key, typename Value>
void SequentialSearchST<Key,Value>::erase(Key k)
{
  if (head_ == nullptr)
  {
    return;
  }
  head_ = erase_(head_, k);
}