Linux Find 指令操作指南 (find command cheatsheet)

发表于 2019-07-08 更新于 2025-05-03 分类于 Linux Waline：阅读次数：本文字数： 1.2k 阅读时长 ≈ 1 分钟

By Long Luo

find 指令是 Unix/Linux 系统中很常用的指令之一，在日常开发维护中常常使用到这个工具。find 是一个很有用的指令，它支援非常多的查找选项，可以依照权限、拥有者、群组、文件类型、日期与大小等条件来查找，这里整理了一些常用的 find 指令的使用技巧。

Find files by name

$ find /home/user/documents -name “example.txt”

Find files by extension

$ find /var/log -name “*.log”

$ find /etc -mtime -7

$ find /usr/local -mtime +30

$ find /tmp -name “oldfile.txt” -delete

$ find /var/www -empty

$ find /home/user/downloads -size +100M

$ find /home -user username

$ find /etc -perm 0644

$ find /var/log -name “*.log” -exec {} ;

$ find /home/user/documents -type f -empty -exec {} ;

$ find /home/user/documents -type f -exec {} ;

$ find / -path “/proc” -prune -o -name “*.conf -print

$ find /var/www -mmin -60

$ find /home/user/pictures -name “*.jpg” | xargs tar -czvf archive.tar.gz

$ find /usr/bin -type I

Find Files by Inode Number

$ find / -inum 456332

$ find /home/user -not -name “*.txt”

$ find /var/log -group syslog

$ find /home/user/downloads -size +50M -size -100M

$ find /var/log -type f -exec s {} +

$ find /var/log -mmin -120

$ find /home -user username -group groupname

$ find /var/log -perm 600

$ find /var/log -size +1G -exec {} ;

$ find /home/user -maxdepth -name “*txt”

$ find /var/log -atime +90

$ find /home/user -name “.*”

$ find /home/user -ctime +1

$ find /dev -type b

$ find / -perm /a=r -not -perm /a=w

$ find /home/user -name “config”

参考文献

5分钟掌握矩阵乘法的Strassen算法

发表于 2019-06-21 更新于 2025-05-03 分类于 Data Structures and Algorithms Waline：阅读次数：本文字数： 6.4k 阅读时长 ≈ 6 分钟

By Long Luo

机器学习中需要训练大量数据，涉及大量复杂运算，例如卷积、矩阵等。这些复杂运算不仅多，而且每次计算的数据量很大，如果能针对这些运算进行优化，可以大幅提高性能。

一、矩阵乘法

假设 $A$ 为 $m \times p$ 的矩阵，$B$ 为 $p \times n$ 的矩阵，那么称 $m \times n$ 的矩阵 $C$ 为矩阵 $A$ 与 $B$ 的乘积，记作 $C = AB$，称为矩阵积（$\textit{Matrix Product}$）。

其中矩阵 $C$ 中的第 $i$ 行第 $j$ 列元素可以表示为：

\[ (AB)_{ij} = \sum_{k=1}^{p}{a_{ik}b_{kj}} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{ip}b_{pj} \]

如下图所示：

假如在矩阵 $A$ 和矩阵 $B$ 中，$m=p=n=N$，那么完成 $C=AB$ 需要多少次乘法呢？

对于每一个行向量 $r$ ，总共有 $N$ 行；
对于每一个列向量 $c$ ，总共有 $N$ 列；
计算它们的内积，总共有 $N$ 次乘法计算。

综合可以看出，矩阵乘法的算法复杂度是：$O(N^3)$。

二、Strassen算法

那么有没有比 $O(N^{3})$ 更快的算法呢？

1969年，Volker Strassen 提出了第一个算法时间复杂度低于 $O(N^{3})$ 矩阵乘法算法，算法复杂度为 $O(n^{log_{2}^{7}})=O(n^{2.807})$ 。从下图可知，$\textit{Strassen}$ 算法只有在对于维数比较大的矩阵( $N > 300$ ) ，性能上才有很大的优势，可以减少很多乘法计算。

图2. x^3 vs. x^{2.807} — 图2. $x^3$ vs. $x^{2.807}$

$\textit{Strassen}$ 算法证明了矩阵乘法存在时间复杂度低于 $O(N^{3})$ 的算法的存在，后续学者不断研究发现新的更快的算法，截止目前时间复杂度最低的矩阵乘法算法是 Coppersmith-Winograd 方法的一种扩展方法，其算法复杂度为 $O(n^{2.375})$ 。

三、Strassen原理详解

假设矩阵 $A$ 和矩阵 $B$ 都是 $N \times N (N = 2^{n})$ 的方矩阵，求 $C = AB$ ，如下所示：

\[ \begin{aligned} A = \left [\begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right] \\ B = \left [\begin{matrix} B_{11} & B_{12} \\ B_{21} & B_{22} \\ \end{matrix} \right] \\ C = \left [\begin{matrix} C_{11} & C_{12} \\ C_{21} & C_{22} \\ \end{matrix} \right] \end{aligned} \]

其中

\[ \begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{bmatrix} = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \cdot \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix} \]

矩阵 $C$ 可以通过下列公式求出：

\[ \begin{aligned} C_{11} = A_{11} \cdot B_{11} + A_{12} \cdot B_{21} \\ C_{12} = A_{11} \cdot B_{12} + A_{22} \cdot B_{21} \\ C_{21} = A_{21} \cdot B_{11} + A_{22} \cdot B_{21} \\ C_{22} = A_{21} \cdot B_{12} + A_{22} \cdot B_{22} \\ \end{aligned} \]

从上述公式我们可以得出，计算 $2$ 个 $n \times n$ 的矩阵相乘需要 $2$ 个 $\frac{n}{2} \times \frac{n}{2}$ 的矩阵 $8$ 次乘法和 $4$ 次加法。

我们使用 $T(n)$ 表示 $n \times n$ 矩阵乘法的时间复杂度，那么我们可以根据上面的分解得到下面的递推公式：

\[ T(n) = 8 \times T(\frac{n}{2}) + O(n^{2}) \]

其中：

$8T(\frac{n}{2})$ 表示 $8$ 次矩阵乘法，而且相乘的矩阵规模降到了 $\frac{n}{2}$。
$O(n^{2})$ 表示 $4$ 次矩阵加法的时间复杂度以及合并矩阵 $C$ 的时间复杂度。

最终可计算得到 $T(n)=O(n^{log_{2}^{8}})=O(n^{3})$ 。

可以看出每次递归操作都需要 $8$ 次矩阵相乘，而这正是瓶颈的来源。相比加法，矩阵乘法是非常慢的，于是我们想到能不能减少矩阵相乘的次数呢？

答案是当然可以！！！

$\textit{Strassen}$ 算法正是从这个角度出发，实现了降低算法复杂度！

阅读全文 »

[Leetcode][172. 阶乘后的零] 3种方法：暴力大数，计算5的个数，对数时间复杂度

发表于 2019-05-27 更新于 2025-05-02 分类于 Leetcode Waline：阅读次数：本文字数： 1.9k 阅读时长 ≈ 2 分钟

By Long Luo

Leetcode 172. 阶乘后的零题解：

方法一：用大数暴力求解并计算末尾0的数量

因为 $n!$ 得到的数字会非常大，所以需要使用BigInteger，得到结果之后，再计算末尾 $0$ 的数量。

import java.math.BigInteger;

class Solution {
    public int trailingZeroes(int n) {
        BigInteger nFactorResult = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            nFactorResult = nFactorResult.multiply(BigInteger.valueOf(i));
        }

        int ans = 0;
        while (nFactorResult.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
            ans++;
            nFactorResult = nFactorResult.divide(BigInteger.TEN);
        }

        return ans;        
    }
}

复杂度分析

时间复杂度：$O(n)$, 实际上应该是 $O(n + \log n)$，但 $\log n$ 很快，只有 $O(1)$，所以 $O(n)$ 。
空间复杂度：$O(1)$。

方法二：计算1到n中全部5因子数量

思路与算法：

考虑到计算阶乘末尾的每个 $0$ 表示乘以 $10$，那么在我们在计算 $n!$ 时乘以 $10$ 的次数是多少？考虑到两个数字 $a$ 和 $b$ 相乘，例如，要执行 $15 \times 24 = 360$，我们可以将其分解为：

\[ 15 \times 24 = 3 \times 5 \times 2 \times 2 \times 2 \times 3 = 360 \]

从上面可以得出，我们只需要考虑 $2 \times 5$ 的因子有多少对。同时，因为 $2$ 的因子数比 $5$ 的因子数要多，所以我们只需要计算 $1$ 到 $n$ 的 $5$ 的因子数有多少即可。

阅读全文 »

[LeetCode][2. 两数相加] 2种方法：模拟和递归

发表于 2019-03-26 更新于 2025-05-02 分类于 Leetcode Waline：阅读次数：本文字数： 3.1k 阅读时长 ≈ 3 分钟

By Long Luo

Leetcode 2. 两数相加题解。

方法一：模拟链表操作

思路与算法：

最开始我的思路是将 $2$ 个数字都读出来，然后相加，再逆向写入回去，但是发现链表数字太长，这个方法不可行。

由于两个链表长度不一致，还需要考虑不同位数对齐的问题，但是由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

那么只需要同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 $n_1$ ，$n_2$ ，进位值为 $\textit{carry}$ ，则它们的和为 $n_1 + n_2 + \textit{carry}$ 。

其中，答案链表处相应位置的数字为 $(n_1 + n_2 + \textit{carry}) mod 10$ ，而新的进位值为 $\textit{sum} - 10$ 。

需要注意的是：如果链表遍历结束后，有 $\textit{carry} \gt 0$ ，还需要在答案链表的后面附加一个节点，节点的值为 $\textit{carry}$ 。

于是就有了那么的第一版代码：

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode pNode1 = l1;
	ListNode pNode2 = l2;
	ListNode dummyNode = new ListNode(-1);
	ListNode pNode = dummyNode;
	int carry = 0;
	while (pNode1 != null && pNode2 != null) {
		int sum = pNode1.val + pNode2.val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}
		ListNode node = new ListNode(sum);
		pNode.next = node;
		pNode = pNode.next;

		pNode1 = pNode1.next;
		pNode2 = pNode2.next;
	}

	while (pNode1 != null) {
		int sum = pNode1.val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}
		ListNode node = new ListNode(sum);
		pNode.next = node;
		pNode = pNode.next;

		pNode1 = pNode1.next;
	}

	while (pNode2 != null) {
		int sum = pNode2.val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}
		ListNode node = new ListNode(sum);
		pNode.next = node;
		pNode = pNode.next;
		pNode2 = pNode2.next;
	}

	if (carry > 0) {
		ListNode node = new ListNode(carry);
		pNode.next = node;
	}

	return dummyNode.next;
}

实际上，上述代码可以优化，去掉多余的变量。如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 $0$ ，得到了下面的优化代码：

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode dummyNode = new ListNode(-1);
	ListNode pNode = dummyNode;
	int carry = 0;
	while (l1 != null || l2 != null) {
		int num1 = l1 != null ? l1.val : 0;
		int num2 = l2 != null ? l2.val : 0;
		int sum = num1 + num2 + carry;
		carry = sum / 10;
		pNode.next = new ListNode(sum % 10);
		pNode = pNode.next;

		if (l1 != null) {
			l1 = l1.next;
		}

		if (l2 != null) {
			l2 = l2.next;
		}
	}

	if (carry > 0) {
		pNode.next = new ListNode(carry);
	}

	return dummyNode.next;
}

复杂度分析

时间复杂度：$O(\max(m,n))$ ，其中 $m$ 和 $n$ 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 $O(1)$ 的时间。
空间复杂度：$O(1)$ 。

阅读全文 »

[LeetCode][1. 两数之和] 2种方法：暴力和 HashMap

发表于 2019-03-25 更新于 2025-02-13 分类于 Leetcode Waline：阅读次数：本文字数： 1.3k 阅读时长 ≈ 1 分钟

By Long Luo

1. 两数之和题解。

方法一：暴力枚举

思路及算法：

最容易想到的方法是使用两层循环，第一层循环枚举数组中的每一个数 $x$，下一层循环在 $x$ 之后的元素中寻找数组中是否存在 $\textit{target} - x$。

    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

复杂度分析

时间复杂度：$O(N^2)$ ，其中 $N$ 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
空间复杂度：$O(1)$ 。

阅读全文 »