ATRS Week 5

2023-09-18
日本
本文字数：2547 字
阅读完需：约 8 分钟

Algorithm 一道算法题

一开始最直接的想法就是用递归的方式。

class Solution {    public int integerReplacement(int n) {        if (n == 1) return 0;                if (n % 2 == 0) {          return integerReplacement(n / 2) + 1;        }
        return Math.min(integerReplacement(n + 1), integerReplacement(n - 1)) + 1;    }}

复制代码

然后发现有个 case 过不了，就是n = Integer.MAX_VALUE的时候，因为n + 1会溢出。

然后加了个判断

class Solution {    public int integerReplacement(int n) {        if (n == 1) return 0;
        if (n == Integer.MAX_VALUE) return 32;                if (n % 2 == 0) {          return integerReplacement(n / 2) + 1;        }
        return Math.min(integerReplacement(n + 1), integerReplacement(n - 1)) + 1;    }}

复制代码

然后就过了，但是这个解法的时间复杂度是O(2^n)，所以肯定不是最优解。想着能不能用一个数组来存储已经计算过的值，这样就不用重复计算了。

class Solution {    List<Integer> twoPower = Arrays.asList(            1, 2, 4, 8, 16, 32, 64, 128, 256, 512,            1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288,            1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912,            1073741824    );
    public int integerReplacement(int n) {        if (n == 1) return 0;
        if (twoPower.contains(n)) return twoPower.indexOf(n);
        if (n == Integer.MAX_VALUE) return 32;                if (n % 2 == 0) {          return integerReplacement(n / 2) + 1;        }
        return Math.min(integerReplacement(n + 1), integerReplacement(n - 1)) + 1;    }}

复制代码

发现还更慢了，因为List.contains()的时间复杂度是O(n)。然后看了别人的解法，有个思路就是，如果 n 是奇数，那么 n+1 和 n-1 都是偶数，而且(n+1)/2 和(n-1)/2 是相邻的数，有一个是偶数，所以我们只需要判断 n+1 和 n-1 哪个能被 4 整除，然后就可以得到最优解了。

class Solution {    public int integerReplacement(int n) {        if (n == Integer.MAX_VALUE) return 32;                int count = 0;        while (n > 1) {            if (n % 2 == 0) {                n /= 2;            } else {                if ((n + 1) % 4 == 0 && (n != 3)) n++;                else n--;            }            count++;        }                return count;    }}

复制代码

Review 一篇英文文章

这周看的文章是Should I use Parquet Files or Delta Format Files – A comparative analysis.。因为最近做的一个事情需要做一个选择，看看是用 Parquet 还是 Delta，所以就找了这篇文章来看看。看完之后觉得还是 Parquet 比较好，因为我们对这些数据只需要读取就行，并不需要 ACID 这些复杂的特性。

Technique/Tips 一个技术点

这周主要是尝试了如何用 Java 来读取 Parquet 文件。主要是用到了这两个 package。

implementation 'org.apache.parquet:parquet-avro:1.13.1'implementation 'org.apache.hadoop:hadoop-common:3.3.6'

复制代码

package org.example;
import org.apache.hadoop.conf.Configuration;import org.apache.hadoop.fs.Path;import org.apache.parquet.column.page.PageReadStore;import org.apache.parquet.example.data.simple.SimpleGroup;import org.apache.parquet.example.data.simple.convert.GroupRecordConverter;import org.apache.parquet.hadoop.ParquetFileReader;import org.apache.parquet.hadoop.util.HadoopInputFile;import org.apache.parquet.io.ColumnIOFactory;import org.apache.parquet.io.MessageColumnIO;import org.apache.parquet.io.RecordReader;import org.apache.parquet.schema.MessageType;import org.apache.parquet.schema.Type;
import java.io.IOException;import java.util.ArrayList;import java.util.List;
public class ParquetReaderUtils {    public static List<SimpleGroup> getParquetData(String filePath) throws IOException {        List<SimpleGroup> simpleGroups = new ArrayList<>();        ParquetFileReader reader = ParquetFileReader.open(HadoopInputFile.fromPath(new Path(filePath), new Configuration()));        MessageType schema = reader.getFooter().getFileMetaData().getSchema();        List<Type> fields = schema.getFields();        PageReadStore pages;        while ((pages = reader.readNextRowGroup()) != null) {            long rows = pages.getRowCount();            MessageColumnIO columnIO = new ColumnIOFactory().getColumnIO(schema);            RecordReader recordReader = columnIO.getRecordReader(pages, new GroupRecordConverter(schema));
            for (int i = 0; i < rows; i++) {                SimpleGroup simpleGroup = (SimpleGroup) recordReader.read();                simpleGroups.add(simpleGroup);            }        }        reader.close();        return simpleGroups;    }}

复制代码

Share 一个观点

这周做了一个 design review，里面又一些需要总结的地方。

在做正式的 design review 之前，最好和对这一块比较熟悉的人先 review 一下，这样可以避免一些低级的错误。
对于你决定的最后的 design，可以提前和老板过一下，看看有没有什么大的 concern，尤其是技术敏感型的老板。
在做 design review 的时候，可以先把整个流程走一遍，然后再把每个步骤的细节展开来讲。然后对于各个方案，列出来优缺点，然后再说为什么选择这个方案。
Review 过程中肯定会有很多问题以及建议，最后要总结一下，哪些问题是需要解决的，哪些是不需要解决的，哪些是可以先不解决的。然后最好发一个邮件给所有参加 review 的人，把这些问题和建议都列出来，然后再写一下自己的总结，这样可以避免一些误解。

发布于: 刚刚阅读数: 5

Geek_c25301

关注

还未添加个人签名 2022-03-19 加入

还未添加个人简介

发布

暂无评论

创作场景

ATRS Week 5

Algorithm 一道算法题

Review 一篇英文文章

Technique/Tips 一个技术点

Share 一个观点

Geek_c25301

评论