ARTS 第33周：翻转图像算法、倒排索引、聚合模式与数据库设计范式化

Algorithm:832. Flipping an Image
Review: Inverted Index
Tip: Aggregation pattern
Share: 数据库设计的范式化和反范式化

Algorithm

package org.nocoder.leetcode.solution;

/**
 * 832. Flipping an Image
 * Given a binary matrix A, we want to flip the image horizontally,
 * then invert it, and return the resulting image.
 *
 * To flip an image horizontally means that each row of the image is reversed.
 * For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].
 *
 * To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0.
 * For example, inverting [0, 1, 1] results in [1, 0, 0].
 *
 * Example 1:
 *
 * Input: [[1,1,0],[1,0,1],[0,0,0]]
 * Output: [[1,0,0],[0,1,0],[1,1,1]]
 * Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
 * Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]
 * Example 2:
 *
 * Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
 * Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
 * Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
 * Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
 * Notes:
 *
 * 1 <= A.length = A[0].length <= 20
 * 0 <= A[i][j] <= 1
 * @author yangjinlong
 */
public class FlippingAnImage {
    public static void main(String[] args) {
        int[][] arr = new int[][]{{1,1,0},{1,0,1},{0,0,0}};
        int[][] result = flipAndInvertImage(arr);
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length ; j++) {
                System.out.print(result[i][j]);
            }
            System.out.print(", ");
        };
    }
    public static int[][] flipAndInvertImage(int[][] arr) {
        if(arr == null || arr.length < 1 || arr[0].length > 20){
            throw new IllegalArgumentException();
        }

        for (int i = 0; i < arr.length; i++) {
            int[] reverseArray = reverseArray(arr[i]);
            for (int j = 0; j < reverseArray.length; j++) {
                if(reverseArray[j] == 0){
                    reverseArray[j] = 1;
                }else{
                    reverseArray[j] = 0;
                }
                arr[i] = reverseArray;
            }
        }
        return arr;
    }
    public static int[] reverseArray(int[] arr){
        if(arr == null || arr.length < 1){
            return arr;
        }
        int[] result = new int[arr.length];
        int j = 0;
        for (int i = arr.length-1; i >= 0; i--) {
            result[j++] = arr[i];
        }
        return result;
    }
}

Review

Inverted Index

倒排索引是索引数据结构，其存储从诸如单词或数字的内容到其在文档或一组文档中的位置的映射。简单来说，它是一个类似于数据结构的散列图，可以将您从单词引导到文档或网页。

假设我们要搜索文本“hello everyone, ” “this article is based on inverted index, ” “which is hashmap like data structure”。按照（文本，文本中的单词的位置）来构建索引，带有文本位置的索引如下：

 hello                (1, 1)
 everyone             (1, 2)
 this                 (2, 1)
 article              (2, 2)
 is                   (2, 3); (3, 2)
 based                (2, 4)
 on                   (2, 5)
 inverted             (2, 6)
 index                (2, 7)
 which                (3, 1)
 hashmap              (3, 3)
 like                 (3, 4)
 data                 (3, 5)
 structure            (3, 6)

构建倒排索引的步骤：

获取文档 删除文档中无用的词，如“我”，“该”，“我们”，“是”，“一个”。
根词的词干 每当我想搜索“cat”时，我想看到一个包含它的信息的文档。但文档中出现的单词称为“cat”或“catty”而不是“cat”。为了把这两个词联系起来，我会把我读过的每一个单词的一部分都删掉，这样我就能得到“根词”。有一些标准的工具可以执行此操作，如“Porter’s Stemmer”。
记录文档ID 如果单词已存在，则将文档引用添加到索引，否则创建新条目。添加其他信息，如单词的频率，单词的位置等。
对所有文档重复并对单词进行排序。

倒排索引的优点：

倒排索引允许快速全文搜索，但是在将文档添加到数据库时会增加处理成本。
容易开发。
它是文档检索系统中最常用的数据结构，例如在搜索引擎中大规模使用。

倒排索引的缺点：

更新，删除和插入时存储开销大，维护成本高。

Tip

Aggregator Pattern

Problem

We have talked about resolving the aggregating data problem in the API Gateway Pattern. However, we will talk about it here holistically. When breaking the business functionality into several smaller logical pieces of code, it becomes necessary to think about how to collaborate the data returned by each service. This responsibility cannot be left with the consumer, as then it might need to understand the internal implementation of the producer application.

Solution

The Aggregator pattern helps to address this. It talks about how we can aggregate the data from different services and then send the final response to the consumer. This can be done in two ways:

A composite microservice will make calls to all the required microservices, consolidate the data, and transform the data before sending back.
An API Gateway can also partition the request to multiple microservices and aggregate the data before sending it to the consumer.

It is recommended if any business logic is to be applied, then choose a composite microservice. Otherwise, the API Gateway is the established solution.

数据库设计的范式化和反范式化

范式设计需要考虑应用类型以及数据分布情况,灵活选择范式化或者反范式化

1、范式化的优点是:更新速度快,没有或者很少冗余数据,通常表也比较小;缺点是 :通常的查询读需要进行一次甚至是多次关联,代价十分昂贵。

2、反范式化的优点是:数据都在一张表里,可以避免关联查询,最差的情况下数据比内存大的多的情况下也会比关联查询效率更高,因为全表扫描基本上是顺序 IO。

3、因此单纯的范式化或者反范式化都是不现实的,灵活选择结合使用才是王道。