我要分享技术
0%

ARTS-5

发表于 更新于 分类于

ARTS-5

Algorithm

引言

本周的题目为从之前没做的题目中顺序拿的, 没有特别选取。 感觉下一周可以做这个Hard的sudoku resolver题目了。

Description

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
sudoku
A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2:

Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
The given board contain only digits 1-9 and the character '.'.
The given board size is always 9x9.
    
    
    Success
    Details 
    Runtime: 32 ms, faster than 12.85% of C++ online submissions for Valid Sudoku.
    Memory Usage: 13.9 MB, less than 25.89% of C++ online submissions for Valid Sudoku.

Soduku 国内叫数独, 是一个填字游戏, 相信大多数人都玩过。 规则为在一个 9*9的矩阵的空白处填入取值为1-9的数字, 使的每一行, 每一列, 每个九宫格分块都是由 1-9 这九个数字组成, 都有且不重复。

思路

首先是最直观的思路, 因为表中有未填写的格子, 使用了 . 来填充, 所以这是个未完成的数独图, 那么验证是否能够完成这个数独, 仅需验证每一行/列/块中是否出现了重复的数字即可, 这依据的是完成的数独图的性质, 1-9数字出现且仅出现一次。

Result1

Status Runtime Memory Language
Accepted 32 ms 13.9 MB cpp

Code1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<set<char>> columns = vector<set<char>>();
        vector<set<char>> rows = vector<set<char>>();
        vector<set<char>> blocks = vector<set<char>>();
        
        for (int i=0; i<9; ++i) {
          columns.push_back(set<char>());
          rows.push_back(set<char>());
          blocks.push_back(set<char>());
        }
      
        int ln = 0;
        for (auto line : board) {
          int col = 0;
          for (auto c : line) {
            if (c=='.') { ++col; continue;}
            if (rows[ln].find(c) != rows[ln].end())
              return false;
            if (columns[col].find(c) != columns[col].end())
              return false;
            int blk = ln/3*3 + col/3;
            if (blocks[blk].find(c) != blocks[blk].end())
              return false;
            rows[ln].insert(c);
            columns[col].insert(c);
            blocks[blk].insert(c);
            ++col;
          }
          ++ln;
        }
        return true;
    }
};

结果分析1

原以为这个方案效率可以接受, 但是从结果上来看, 位于c++方案的后半截, 现在看来有明显浪费的地方就是行、列、块这27个set了, 感觉它们不需要每个都存在,仅当需要进行判断是存在即可, 但是感觉这样会导致对输入数据多次遍历, 权当测试了, 所以, 后面优化了一版。

方案2

方案二待改

Review

What Is a Pure Function in JavaScript?

JavaScript中纯函数是什么。

引言

本篇是ARTS-3中的Review部分 an introduction of to principles of Functional Programming 文内的引用的使用javascript做介绍的部分。 由于我之前阅读了函数式编程简介, 本周给我的周推送, 感觉推送还挺精准的。

纯函数的特征

在阅读本文之前,我觉得有必要先回顾一下纯函数的概念(或者说我自己的总结)

一个函数,具备以下两个特征, 那它是纯函数 * 多次执行，给定相同的参数必然得到相同的结果。 * 执行中，不会带来可以观察到的副作用状态改变。

关于内容

Same Input => Same Output

文章开始简介了纯函数的特征, 作者并给出了一个配图, 图片如下 pure function

原图出自 https://cdn-images-1.medium.com/max/1600/0*a_yub2gTwY-1eK8j.png

特征与我之前总结的一般无二, 作者在这里根据JavaScript语言的应用场景将之更加细化了, 直接指出了 记日志、http请求、写磁盘 等行为 是会造成可观测到的影响的。 文章原文中使用了 side-effects 来描述这一现象。

The Checklist
A function must pass two tests to be considered “pure”:

* Same inputs always return same outputs
* No side-effects

作者使用了几个简单的代码例子来举例说明了 Same Input => Same Output 感觉这几个例子有点刻意, 可以丑化了非纯函数的实现, 用来说明纯函数的优点的话感觉这里并不贴切, 毕竟,正常人也不能写出demo中的代码。

No Side-Effects

avoid side-effects
This test itself is a checklist. A few examples of side-effects are

Mutating your input
console.log
HTTP calls (AJAX/fetch)
Changing the filesystem (fs)
Querying the DOM

简译为: 1. 改变输入(这里应当为参数) 2. 打印日志 console.log 3. 发起HTTP请求(ajax/fetch) 4. 文件系统的改变 5. 查询DOM

最明显, 我感觉 console.log 是不必要的, 在平时很多场景下, 我都会在函数里打log, 它只用于输出必要信息, 如果日志系统影响到了正常的业务逻辑, 那只能是说明代码结构有问题了, 日志系统应完全独立于业务系统, 所以,这个点上我是不赞同的。即使, 后文中作者说了console.log可能不会造成恶劣的影响。

其他几点上, http请求可能也不那么赞同, 发起请求并不会对系统内产生可观测的影响吧, 感觉这里是, 在函数里使用http请求的结果更合适一些。(后来想想, 我是错了, 发起请求后可能会收到响应, 这个会改变系统的整体状态, 按照严格意义上来说的话,是产生了影响)

其余几点没什么好说的。

采用返回新对象的形式避免更改输入参数

针对避免影响外部的第一点, 避免修改输入参数, 先贴一段作者的demo代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
const pureAssoc = (key, value, object) => {
    const newObject = { ...object };
    newObject[key] = value;
    return newObject;
};
const person = {
    name: 'Bobo'
};
const result = pureAssoc('shoeSize', 400, person);
console.log({
    person,
    result
});

按照一般的OOP风格, 这段代码的关键函数 pureAsoc 很可能绝大多数人,当然也包括在下, 实现成如下的形式:

1
2
3
4
const pureAssoc = (key, value, object) => {
    object[key] = value
    return object;
};

这个实现方式就是典型的违背了避免修改入参这一点。

看起来这个代码是完美了, 但是, {...object} 语法实现的是浅拷贝(shallow copy), 一旦有嵌层的对象,还是没办法从根本上解决问题。于是, 作者又贴了一段代码:

1
2
3
4
5
6
7
const person = {
  name: 'Bobo',
  address: { street: 'Main Street', number: 123 }
}
const deepPersonClone = JSON.parse(JSON.stringify(person));
deepPersonClone.address.number = 456;
console.log({ person, deepPersonClone });

这段代码确实实现了深拷贝, 但是作为一个不太写JavaScript的强迫症患者, 感觉先将对象 stringify 成一个字符串,再重新解析一遍成js对象的做法深感受不了。

总结

A Function’s pure if it’s free from side-effects and returns the same output, given the same input.

Side-effects include: mutating input, HTTP calls, writing to disk, printing to the screen.

You can safely clone, then mutate, your input. Just leave the original one untouched.

Spread syntax (… syntax) is the easiest way to shallowly clone objects.

JSON.parse(JSON.stringify(object)) is the easiest way to deeply clone objects. Thanks again Rodrigo Fernández Díaz!

Tips

打破直观的编程方式实现对数据配置代码的压缩

引言

上周连续的加班,周日的时候老大过去视察, 我跟他说了我在上一篇ARTS中分享的Tips点, 使用代理的模式来避免代码修改。老大很惊奇的跟我说, 我们的配置数据一直是这么做的啊, 你没有看过么。

好吧,我确实看过, 但是, 动态语言有一些写法我真的没看懂, 技术领导力极强的老大不辞劳苦给我讲了一遍, 于是, 就有了这周的Tips。

背景

我现在做的项目是一个手游MMORPG游戏, 其中客户端使用lua实现逻辑, 我们需要将策划同学配表(csv表格)转换成lua代码, 以便我们在实现业务代码的时候直接调用。

一般的配置文件就是一个二维表格, 有时候这个表格会非常大举个例子

场景Id 地图Id 场景名 容纳上限 进入等级Min 进入等级Max 是否允许Pk param1 param2 param3 param4
1 1 主城 200 1 999 TRUE 0 0 0 0
.. .. .. .. .. .. .. .. .. .. ..

简单直观做法

按照最简单直观的做法生成的配置, 大概是这样的

1
2
3
config = {}
config[1] = { 场景Id = 1, 地图Id = 1, 场景名 = '主城', 容纳上限 = 200, 进入等级Min = 1, 进入等级Max = 999, 是否允许Pk = TRUE, param1 = 0 , param2 = 0 , param3 = 0 , param4 = 0}
return config

使用时代码

1
2
3
4
local cfg = config[1]
if cfg.param1 > 122 then
    -- do game logic
end

该做法有个一眼能看出来的严重的弊端, config是一个数组, 它里面的每个元素都是一个table,而且是map形式的table, 此时, 每行数据都多余的存了一个key的信息, 实际上, 我们严谨的二维表格是不需要这个信息的。于是, 就给了我们一个优化空间。

简单优化做法

方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
config = {}
data = {}
index = { 场景Id = 1, 地图Id = 2, 场景名 = 3, 容纳上限 = 4, 进入等级Min = 5, 进入等级Max = 6, 是否允许Pk = 7, param1 = 8 , param2 = 9 , param3 = 10 , param4 = 11}
data[1] = { 1, 1, '主城', 200, 1, 999, TRUE, 0, 0, 0, 0}
data[2] = { --[[ ... ]]}

local newget = function(i)
    local instance = {_i = i}
    setmetatable ({}, 
    {
        __index = function(table, key)
            local idx = index[key]
            return data[table._i][idx]
        end
    }
    return instance
)
end

table.insert(config, newget(1)) 
table.insert(config, newget(2))

config.get = function(idx) return config[idx] end
config.all = config
return config

使用方法 

1
2
3
4
5
6
7
8
9
10
11
local cfg = config.get(1)
if cfg.param1 > 122 then
    -- do game logic
end

-- 遍历方案
for _, cfg in pairs(config.all) do 
    if cfg.param1 > 122 then
        -- do something
    end
end
经过上述优化, 使用方式基本不变, 其内存占用量可以节省百分之五十以上。

优化原理

直观方案的浪费源头主要在对于每一行数据, 都需存它的key, 那么有N行的话, 就有(N-1)份的key是浪费的, 明显的, 一个配置列数据基本是一个简单类型, 那么, 直观方案我们冗余的key的存储空间比实际上数据占用的空间更多!!!

优化时, 我们只保存一份key, 然后建立一个索引表存储对应关系, 这样, 我们在使用key访存时, 可以做一个映射, 然后去数组结构中获取相应的数据, 但是, 我们需要多开辟一份空间来存这个索引表。 一个表的行数越多, 节省就越明显。

更激进的优化

这个方案这里我不贴代码了, 因为实在太复杂, 老大只是口头传授了我, 也没有给我一个代码demo看一下。

其原理类似于稀疏矩阵的存储, 对于绝大多数的表, 尤其是大表来说, 其中很多列的内容都是相同的, 或者为空, 或者是同一个值, 或者是 0-5之间取值, 甚至列类型是布尔值。 对于这种列, 我们就不再存储到 data 行中, 而是在行中插入一个函数, 它实际上可以被大多数列共享, 用于返回公共数据。

请参考: 稀疏矩阵存储

Share

这是一篇翻译国外大神前辈关于插值实践的文章, 读完收获很大, 本周又多看了一遍。

插值那些事儿

End