我要分享技术
0%

ARTS-7

发表于 更新于 分类于

ARTS-7

Algorithm

Sudoku Solver

引言

上回, ARTS-5 做了一个验证sudoku是否有效的题目, 本题是它的后续。

Description

  1. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character '.'.

A sudoku puzzle...

数独谜题

...and its solution numbers marked in red.

数独完成

Note:

The given board contain only digits 1-9 and the character '.'. You may assume that the given Sudoku puzzle will have a single unique solution. The given board size is always 9x9

大意

前面的分享已经介绍过数独游戏, 本次题目提供一个未完成的数组, 其中未填充的数字使用字符.来填充。

我们的解决方案需要替换原数组中的., 使数独结构成立, 假设题目给出的数组都只有唯一解。

思路

首先最容易想到的就是最简单直接的解法, 本科阶段学习数据接口课程, 对于栈和递归这两个章节都拿数独举过例子。数独的解法和迷宫一样, 都是一个简单直接的栈结构, 一个个放入尝试, 如果成立则递归解下一个单元格, 否则则退回上一步重新放置一个上一步的数字再试。

解法 1

这里先使用了最直接的解法, 我实现了cpp和java两个版本的方案, 这里贴出一个java版本的方案, 因为后面还继续讨论一下jvm对于这个情况的优化。

第一段代码 

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
36
public class Solution {
    public void solveSudoku(char[][] board) {
        solveNext(board);
    }
    
    public boolean solveNext(char[][] board){
        for(int row = 0; row < 9; row++){
            for(int col = 0; col < 9; col++){
                if(board[row][col] == '.'){
                    for(char c = '1'; c <= '9'; c++){
                        if(!canSet(board, row, col, c)) continue;   //check if can set c
                        board[row][col] = c; 
                        if(!solveNext(board))
                            board[row][col] = '.';  //rollback if failed
                        else
                            return true; 
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean canSet(char[][] board, int row, int col, char c){
        int brow = row /3 * 3;
        int bcol = col /3 * 3;  // recaculate the block's begin position
        for(int i = 0; i < 9; i++) {
            if(board[i][col] != '.' && board[i][col] == c) return false; 
            if(board[row][i] != '.' && board[row][i] == c) return false; 
            if(board[brow + i / 3][ bcol + i % 3] != '.' && 
                board[brow + i / 3][bcol + i % 3] == c) return false; 
        }
        return true;
    }
}

第二段代码

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
36
37
38
public class Solution {
    public void solveSudoku(char[][] board) {
        solveNext(board, 0, 0);
    }
    
    private boolean solveNext(char[][] board, int row, int col){
        for(; row < 9; row++){
            for(; col < 9; col++){
                if(board[row][col] == '.'){
                    for(char c = '1'; c <= '9'; c++){
                        if(!canSet(board, row, col, c)) continue;
                        board[row][col] = c; 
                        if(!solveNext(board, row, col))
                            board[row][col] = '.'; 
                        else
                            return true; 
                    }
                    return false;
                }
            }
            col = 0;
        }
        return true;
    }
    
    private boolean canSet(char[][] board, int row, int col, char c){
        int brow = row /3 * 3;
        int bcol = col /3 * 3;
        for(int i = 0; i < 9; i++) {
            if(board[i][col] != '.' && board[i][col] == c) return false; 
            if(board[row][i] != '.' && board[row][i] == c) return false; 
            if(board[brow + i / 3][ bcol + i % 3] != '.' && 
                board[brow + i / 3][bcol + i % 3] == c) return false; 
        }
        return true;
    }
}

贴出一个c++的代码对比

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
36
37
38
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solveNextStep(board);
    }
    
private:  
    bool solveNextStep(vector<vector<char>>& board) {
      for (int row = 0; row < 9; ++row) {
        for (int column = 0; column < 9; ++column) {
          if (board[row][column] != '.') continue;
          for (char iv = '1'; iv <= '9'; ++iv) {
            if (isValid(board, row, column, iv)) {
              board[row][column] = iv;
              if (solveNextStep(board))
                return true;
              else
                board[row][column] = '.';
            }
          }
          return false;
        }
      }
      return true;
    }
  
    static bool isValid(const vector<vector<char>>& board, int row, int col, char c) {
      int brow = row/3*3;
      int bcol = col/3*3;
      for (int i=0; i<9; ++i) {
        if (board[row][i]!='.' && board[row][i]==c) return false;
        if (board[i][col]!='.' && board[i][col]==c) return false;
        if (board[brow + i/3][bcol + i%3] !='.' && board[brow + i/3][bcol + i%3]==c) return false;
      }
      return true;
    }
};

Result 1

Time Submitted Status Runtime Memory Language
3 minutes ago Accepted 7 ms 36.6 MB java
12 minutes ago Accepted 6 ms 36.3 MB java
a few seconds ago Accepted 20 ms 8.7 MB cpp

其中, 第一行结果对应上面代码的第二段。 第二行结果对应上面结果的第一段。我本来是想稍微进行一点优化(虽然我知道这个"优化"聊胜于无), 反而结果更糟糕了, 下面我会分享一下我的猜想。

C++ 代码上在内存用量上完胜(这个应该是由于java基于jvm, 额外消耗了更多内存吧), 但是在执行时间上cpp代码完败, 猜想应该是由于cpp的标准vector类的实现问题, 和无法基于profiling 做编译时优化而造成的劣势。 针对cpp代码, 我也做了同样的传递行列参数的优化, 但是执行时间上和未优化的版本完全一致。

分析总结

我虽然提供了可以AC的答案, 但是这个答案应该是最基础的, 跟"好答案"相去甚远, 这个解法真的是对不起"Hard"这个难度。至于更优秀的解决方案, 后面我去看看讨论区大佬有什么精彩解法。

这里, 我只讨论我这两段代码, 为什么"优化"后的代码反而表现更差。 看上面的贴图相差无几, 也许可能纯粹认为是偶发的误差导致的, 但是, 我在本地机器上使用JMH反复做了测试, 结果依然如此。

猜想

这里可能涉及到一个jvm层面的优化, 可能jvm针对固定的计数循环使用了"循环展开"和"向量化"的优化技术。(这里我参考了循环优化和向量化), 由于第二种方法,我通过参数设置了循环开始条件,破坏了固定的循环计数, 导致即时编译器无法采用优化, 反而导致了运行效率更低。

对比cpp代码的两个方案, 两个代码执行时间基本一致, 所以我觉得这个java代码的差异应该就是由于编译时的优化失败导致的。

Review

JavaScript Fundamental: Prototypal Inheritance

JavaScript 基本规则 : 原型式继承

引言

本周的review内容依然来自于Medium Daily Digest, 就随缘吧, 哪天我开始写review了, 就直接使用哪天的digest了, 当然, 我绝对不是每周只读这一篇。 然后, 本篇较短。

内容

JavaScript的原型式继承

首先, 我写JavaScript并不多, 偶尔写两句。

作为JavaScript开发者, 理解JavaScript的继承的工作原理是必备知识, 面试尤其得心应手, 今天, 我来说道说道JavaScript实现的继承的优缺点。

下面的内容为原文翻译 原文链接

What is an inheritance?

什么是继承?

继承是面向对象编程的四个基本概念之一, (四个概念是: 抽象, 封装, 继承, 多态), 继承可以使一个对象获取另一个已存在的对象的属性。

Does JavaScript have inheritance?

JavaScript支持继承吗?

当然, JavaScript使用一个叫做原型式继承的类型, 它与类似Java语言的经典继承模型有很大差别。

What is prototypal inheritance?

什么是原型继承?

要搞明白原型继承, 我们先要搞明白原型链, 原型链是每个对象与其原型之间的一系列联系，它以某种方式充当“父对象”(通过原型)，直到链到达null的引用。 此外，可以使用__proto__手动设置对象的原型。举个栗子:

1
2
3
4
5
6
7
8
9
10
const vehicle = {
    numWheels: 4
}
const car = {
    numDoors: 4
}
// Setting vehicle as car object's prototype
car.__proto__ = vehicle
console.log(car.numWheels)
=> 4

card对象本身不包含numWheels属性, 但是, 当我们设置vehicle对象作为它的prototype属性, car.numWheels 取值为4, 在原型式继承中, 如果一个属性在原对象中不存在, JavaScript(执行引擎)将会通过原对象的prototype属性开始递归的搜索目标属性,直到找到目标属性,或者对象的prototype属性为null为止。

Good or bad?

优缺点

  • Good 优点
    1. 简单直接
    2. 更适合JavaScript的动态特性本质
    3. 代码冗余度低 (ps. 我表示并没有低的明显)
  • Bad 缺点
    1. 习惯于经典继承模型的人难以掌握(例如Java)
    2. JavaScript的原型继承使用构造函数模式，对象继承自另一个对象的构造函数，而不是整个对象类型，我(作者)认为它更符合原型继承试图实现的目标。
    “I was under marketing orders to make it look like Java but not make it too big for its britches. It’s just this sort of silly little brother language, right? The sidekick to Java.” -- Brandan Eich (Creator of JavaScript)

Tips

在生产环境的机器上,尤其是低配置机器,不要尝试去打开查看或者处理大文件

引言

本次Tips特别简单,真的, 它是一个警告, 只有一句话。如上

讲个故事

基于我国国情, 每一个通过域名可以访问的国内服务器(80和8080端口)都必须经过备案, 否则不可能访问通, 所以, 我购买了一个处于国外机房的vps(对, 我从不通过它访问谷歌, 那是违法的)。

本着钻研和学习的精神, 我在上面运行了一个 ss 进程, 用它来搭建代理, 提供我公司研发网络的穿透, 以便我可以在下班忘记打卡的时候可以在家里打卡下班(对, 不用来翻墙, 那样做违法)。

某天, 我又回到了家, 熟练的打开了teamviewer, 连上工位的机器, 签退页面打开, 看看还差五分钟就又满一小时了(多工作没有加班费, 我就是贱), 想着再等我分钟退吧。

正好某视频网站源码被我clone了一份在这个vps上, 而且压了一个压缩包准备下到本地, 然后手贱了一个view命令给到了压缩包上。

然后teamviewer熟练的断开了, 一查, 果然ss进程被oom关闭了, 工位上的机器teamviewer只会重试一次, 果然我没能在这个时间内重启, 于是, 考勤异常了。

相关知识

Linux的内存管理机制, 当linux内核发现可用内存不足时, 会通过3种途径来回收内存

  • 基于 LRU（Least Recently Used）算法, 回收缓存
  • 基于 Swap 机制，回收不常访问的匿名页
  • 基于 OOM（Out of Memory）机制，杀掉占用大量内存的进程。

我的故事里, ss 进程被杀死就是第三种途径在产生效果。

第三种方式，OOM 机制按照 oom_score 给进程排序。oom_score 越大，进程就越容易被系统杀死。

当然了，如果你不希望应用程序被 OOM 杀死，可以调整进程的 oom_score_adj，减小 OOM分值，进而降低被杀死的概率。

或者，你还可以开启内存的 overcommit，允许进程申请超过物理内存的虚拟内存（这儿实际上假设的是，进程不会用光申请到的虚拟内存）。

上面机制的内容引自倪朋飞发表在极客时间的课程, 版权文章, 阅读完成版可能需要付费。

Share

微软最爽命令行工具发布！引诱开发者叛逃Mac，开源六小时冲上GitHub第二

我竟然分享的是一篇软文, 没错, 它击中了部分我对ide和开发环境的幻想, 即使它是一篇软文, 我仍旧期待。在此分享, 给所有ide洁癖者。

End