PHP Interview Questions(11)

面试时间:2019 年 11 月 4 日,星期一,下午两点。


1. 给定一个二维数组,数组每一行从左到右都是递增的,每一列也是递增的。请完成一个函数,输入为如上二维数组和一个整数,函数功能为判断该整数是否存在于数组中。时间复杂度尽可能的低。(请说明你的算法的复杂度。)

下面是一个例子:

二维数组:

1 2 8 9

2 4 9 12

4 7 10 13

6 8 11 15

数字:9

<?php

$array = [
    [1, 2, 8, 9],
    [2, 4, 9, 12],
    [4, 7, 10, 13],
    [6, 8, 11, 15],
];

$number = 9;

/**
 * 最简单的方法就是遍历整个数组
 * 时间复杂度 O(Row*Column-1)
 */
function findNumberInArray($array, $number) {
    foreach ($array as $rowArray) {
        foreach ($rowArray as $value) {
            echo $value, " ";
            if ($number == $value) {
                return true;
            }
        }
    }

    return false;
}

/**
 * 从二维数组的左下角开始逐行查找
 * 时间复杂度 O(Row+Column-1)
 */
function findNumberInArray2($array, $number) {
    $minRow = 0;
    $minColumn = 0;
    $maxRow = count($array) - 1;
    $maxColumn = count($array[0]) - 1;

    if ($number < $array[0][0] || $number > $array[$maxRow][$maxColumn]) {
        return false;
    }

    for ($row = $maxRow; $row >= $minRow; $row--) {
        for ($column = $minColumn; $column <= $maxColumn; $column++) {
            echo $array[$row][$column], " ";
            if ($array[$row][$column] == $number) {
                return true;
            }
            if ($array[$row][$column] > $number) {
                break;
            }
            if ($array[$row][$column] < $number) {
                $minColumn = $column + 1;
            }
        }
    }

    return false;
}

/**
 * 从二维数组的右上角开始逐行查找
 * 时间复杂度 O(Row+Column-1)
 */
function findNumberInArray3($array, $number) {
    $minRow = 0;
    $minColumn = 0;
    $maxRow = count($array) - 1;
    $maxColumn = count($array[0]) - 1;

    if ($number < $array[0][0] || $number > $array[$maxRow][$maxColumn]) {
        return false;
    }
    
    for ($row = $minRow; $row <= $maxRow; $row++) {
        for ($column = $maxColumn; $column >= $minColumn; $column--) {
            echo $array[$row][$column], " ";
            if ($array[$row][$column] == $number) {
                return true;
            }
            if ($array[$row][$column] > $number) {
                $maxColumn = $column - 1;
            }
            if ($array[$row][$column] < $number) {
                break;
            }
        }
    }

    return false;
}

echo "/**
* 最简单的方法就是遍历整个数组
* 时间复杂度 O(Row*Column-1)
*/\n";
for ($number = 0; $number <= 15; $number++) {
    echo "find ", $number, ": ";
    findNumberInArray($array, $number);
    echo "\n";
}

echo "/**
* 从二维数组的左下角开始逐行查找
* 时间复杂度 O(Row+Column-1)
*/\n";
for ($number = 0; $number <= 15; $number++) {
    echo "find ", $number, ": ";
    findNumberInArray2($array, $number);
    echo "\n";
}

echo "/**
* 从二维数组的右上角开始逐行查找
* 时间复杂度 O(Row+Column-1)
*/\n";
for ($number = 0; $number <= 15; $number++) {
    echo "find ", $number, ": ";
    findNumberInArray3($array, $number);
    echo "\n";
}

2.把数组最开始的若干个元素搬到数组末尾,称为数组的旋转。给定一个递增数组的旋转数组,请完成一个函数,时间复杂度尽可能的低,输出该旋转数组的最小元素。并给出复杂度。

例如输入数组(4,5,6,7,8,10,1,2,3),输出 1。

<?php

$array = [4, 5, 6, 7, 8, 10, 1, 2, 3];

/**
 * 使用 min() 函数
 * 时间复杂度:O(N)
 * 源码:https://github.com/php/php-src/blob/master/ext/standard/array.c
 */
echo min($array), "\n";

/**
 * 使用二分查找法
 * 时间复杂度:O(log2N)
 */
function findMinimumNumberInArray($array, $start = 0, $end = null) {
    if ($end == null) {
        $end = count($array) - 1;
    }

    if ($start == $end) {
        return $array[$start];
    }

    $middle = floor(($start + $end) / 2);

    if ($array[$start] < $array[$end]) {
        return findMinimumNumberInArray($array, $start, $middle);
    } else {
        return findMinimumNumberInArray($array, $middle, $end);
    }
}

echo findMinimumNumberInArray($array), "\n";

3.输入一个字符串,输出该字符串中字符的所有组合。(不限编程语言,请注明你选择的语言)

下面是一个例子:

输入参数:字符串:“abc”

输出:“a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”

<?php

$string = "abc";
$length = strlen($string);

/**
 * 使用二进制表示不同的排列组合
 * 
 * 0 0 1 a
 * 0 1 0 b
 * 0 1 1 ab
 * 1 0 0 c
 * 1 0 1 ac
 * 1 1 0 bc
 * 1 1 1 abc
 */
 for ($i = 1; $i < 1 << $length; $i++) {
     for ($j = 0; $j < $length; $j++) {
         if ($i & (1 << $j)) {
             echo $string[$j];
         }
     }
     echo "\n";
 }

参考:

剑指Offer面试题:2.二维数组中的查找

剑指Offer面试题:7.旋转数组的最小数字

剑指Offer面试题:26.字符串的排列

113 total views, 4 views today

Java 8 函数式编程(3)

本篇对应《Java 8 函数式编程》的第四章。


要点回顾

  1. 使用为基本类型定制的Lambda表达式和Stream,如IntStream可以显著提升系统性能。
  2. 默认方法是指接口中定义的包含方法体的方法,方法名有default关键字做前缀。
  3. 在一个值可能为空的建模情况下,使用Optional对象能替代使用null值。

练习

Question 1:

/** 该接口表示艺术家的演出——专辑或演唱会 */
public interface Performance {

    public String getName();

    public Stream<Artist> getMusicians();

    public default Stream<Artist> getAllMusicians() {
        return getMusicians()
              .flatMap(artist -> concat(Stream.of(artist), artist.getMembers()));
    }

}

Question2:

不能。

public interface Parent {
    default public boolean equals(Object object) {
        return true;
    }

    default public int hashCode() {
        return 1;
    }
}
% javac Parent.java
Parent.java:2: error: default method equals in interface Parent overrides a member of java.lang.Object
    default public boolean equals(Object object) {
                           ^
Parent.java:6: error: default method hashCode in interface Parent overrides a member of java.lang.Object
    default public int hashCode() {
                       ^
2 errors

Question 3:

public class Artists {

    private List<Artist> artists;

    public Artists(List<Artist> artists) {
        this.artists = artists;
    }

    public Optional<Artist> getArtist(int index) {
        if (index < 0 || index >= artists.size()) {
            return Optional.empty();
        }
        return Optional.of(artists.get(index));
    }

    public String getArtistName(int index) {
        Optional<Artist> artist = getArtist(index);
        return artist.map(Artist::getName)
                     .orElse("unknown");
    }

}

参考:

163 total views, no views today

Java 8 函数式编程(2)

本篇对应《Java 8 函数式编程》的第三章。

PS:如果你还没有了解过 Iterator 设计模式,请先去了解一下 Iterator 设计模式


Stream

Stream 是用函数式编程方式在集合类上进行复杂操作的工具。

int sum = widgets.stream()
                 .filter(w -> w.getColor() == RED)
                 .mapToInt(w -> w.getWeight())
                 .sum();

比如这个官方文档上的代码示例:计算所有红色 Widget 的权重的总和。

  1. 使用 Collection.stream() 方法,创建 widgets 集合的流。
  2. 使用 filter 操作,产生一个只包含红色 widgets 的流。
  3. 使用 mapToInt 操作,转换成红色 widgets 的权重的流。
  4. 使用 sum 操作,计算红色 widgets 的权重之和。

Stream operations and pipelines

流操作(Stream operations)分为中间操作(intermediate operations)和终点操作(terminal operations),合在一起就形成了流管道(stream pipelines)。

一个流管道(stream pipelines)包含一个数据源(source),零到多个中间操作(intermediate operations)和一个终点操作(terminal operations)。

数据源(source)可以是一个数组,一个集合,一个生成函数,一个 I/O 通道,~。

中间操作(intermediate operations)就是把一个流转换成另外一个流,比如 filter 和 map。

终点操作(terminal operations)会产生一个结果或者副作用,比如 count 和 forEach。

流是惰性求值的,只有终点操作(terminal operations)开始的时候,所有数据源(source)上的计算才会真正被执行,并且数据源元素只在需要时才会被使用。

常用的流操作

filterintermediate operationstateless
map
mapToInt
mapToLong
mapToDouble
flatMap
flatMapToInt
flatMapToLong
flatMapToDouble
distinctstateful
sorted
peek
limit
skip
takeWhile
dropWhile
forEachterminal operation
forEachOrdered
toArray
reduce
collect
max
count
anyMatch
allMatch
noneMatch
findFirst
findAny

练习

Question 1:

    public static int addUp(Stream<Integer> numbers) {
        return numbers.reduce(0, (acc, x) -> acc + x);
    }

    public static List<String> getNamesAndOrigins(List<Artist> artists) {
        return artists.stream()
                      .flatMap(artist -> Stream.of(artist.getName(), artist.getNationality()))
                      .collect(toList());
    }

    public static List<Album> getAlbumsWithAtMostThreeTracks(List<Album> input) {
        return input.stream()
                    .filter(album -> album.getTrackList().size() <= 3)
                    .collect(toList());
    }

Question 2:

int totalMembers = (int) artists.stream().flatMap(artist -> artist.getMembers()).count();

Question 3:

a. 及早求值(Eager)- 返回 Stream
b. 惰性求值(Lazy)

Question 4:

a. 是 - 参数是函数
b. 否

Question 5:

a. 没有副作用

Question 6:

    public static int countLowercaseLetters(String string) {
        return (int) string.chars()
                           .filter(Character::isLowerCase)
                           .count();
    }

Question 7:

    public static Optional<String> mostLowercaseString(List<String> strings) {
        return strings.stream()
                      .max(Comparator.comparing(StringExercises::countLowercaseLetters));
    }

进阶练习

Question 1:

import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Stream;

/**
 * Advanced Exercises Question 1
 */
public class MapUsingReduce {

    public static <I, O> List<O> map(Stream<I> stream, Function<I, O> mapper) {
        return stream.reduce(new ArrayList<O>(), (acc, x) -> {
        	// We are copying data from acc to new list instance. It is very inefficient,
        	// but contract of Stream.reduce method requires that accumulator function does
        	// not mutate its arguments.
        	// Stream.collect method could be used to implement more efficient mutable reduction,
        	// but this exercise asks to use reduce method.
        	List<O> newAcc = new ArrayList<>(acc);
        	newAcc.add(mapper.apply(x));
            return newAcc;
        }, (List<O> left, List<O> right) -> {
        	// We are copying left to new list to avoid mutating it. 
        	List<O> newLeft = new ArrayList<>(left);
        	newLeft.addAll(right);
            return newLeft;
        });
    }

}

Question 2:

import java.util.ArrayList;
import java.util.List;
import java.util.function.Predicate;
import java.util.stream.Stream;

/**
 * Advanced Exercises Question 2
 */
public class FilterUsingReduce {

    public static <I> List<I> filter(Stream<I> stream, Predicate<I> predicate) {
        List<I> initial = new ArrayList<>();
        return stream.reduce(initial,
                             (List<I> acc, I x) -> {
                                if (predicate.test(x)) {
                                	// We are copying data from acc to new list instance. It is very inefficient,
                                	// but contract of Stream.reduce method requires that accumulator function does
                                	// not mutate its arguments.
                                	// Stream.collect method could be used to implement more efficient mutable reduction,
                                	// but this exercise asks to use reduce method explicitly.
                                	List<I> newAcc = new ArrayList<>(acc);
                                    newAcc.add(x);
                                    return newAcc;
                                } else {
                                	return acc;
                                }
                             },
                             FilterUsingReduce::combineLists);
    }

    private static <I> List<I> combineLists(List<I> left, List<I> right) {
    	// We are copying left to new list to avoid mutating it. 
    	List<I> newLeft = new ArrayList<>(left);
    	newLeft.addAll(right);
        return newLeft;
    }

}

参考:

https://www.ibm.com/developerworks/cn/java/j-lo-java8streamapi/

https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html

154 total views, no views today

Java Null Pointer Exception

Null Pointer Exception(NPE)是 Java 语言中非常常见的一个问题。


Article.java

public class Article
{
    private Author author;

    public Author getAuthor() {
        return author;
    }

    public void setAuthor(Author author) {
        this.author = author;
    }
}

Author.java

public class Author
{
    private String name;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

Main.java

public class Main
{
    public static void main(String[] args) {
        Article article = null;

        System.out.println(article.getAuthor().getName());
    }
}

比如我们写了上面这样一段代码,运行时就会报 NullPointerException。

Exception in thread "main" java.lang.NullPointerException
        at Main.main(Main.java:6)

当然解决 NullPointerException 的方法也有很多,比如使用 if-else。

public class Main1
{
    public static void main(String[] args) {
        Article article = null;

        if (article != null && article.getAuthor() != null) {
            System.out.println(article.getAuthor().getName());
        } else {
            System.out.println("Unknown");
        }
    }
}

比如使用 Java 8 的 Optional。

import java.util.Optional;

public class Main2
{
    public static void main(String[] args) {
        Article article = null;

        System.out.println(Optional.ofNullable(article).map(Article::getAuthor).map(Author::getName).orElse("Unknown"));
    }
}

或者使用 Kotlin 的 Safe Calls。

data class Article(var author: Author?);

data class Author(var name: String);

fun findArticle() : Article? {return null}

fun main() {
    val article = findArticle();
    println(article?.author?.name)
}

参考:

https://blog.udemy.com/java-null-pointer-exception/

https://kotlinlang.org/docs/reference/null-safety.html

206 total views, no views today

Java 8 函数式编程 (1)

本篇对应《Java 8 函数式编程》的第一章和第二章。


什么是函数式编程

面向对象编程是对数据进行抽象,而函数式编程是对行为进行抽象。

每个人对函数式编程的理解不尽相同。但其核心是:在思考问题时,使用不可变值和函数,函数对一个值进行处理,映射成另一个值。


Lamda 表达式

Lambda 允许把函数作为一个方法的参数(函数作为参数传递进方法中)。

lambda 表达式的语法格式如下:

(parameters) -> expression
或
(parameters) ->{ statements; }

Lambda 表达式的简单例子:

// 1. 不需要参数,返回值为 5  
() -> 5  
  
// 2. 接收一个参数(数字类型),返回其2倍的值  
x -> 2 * x  
  
// 3. 接受2个参数(数字),并返回他们的差值  
(x, y) -> x – y  
  
// 4. 接收2个int型整数,返回他们的和  
(int x, int y) -> x + y  
  
// 5. 接受一个 string 对象,并在控制台打印,不返回任何值(看起来像是返回void)  
(String s) -> System.out.print(s)

有一点需要注意的是:

Lambda表达式中引用的局部变量必须是final或既成事实上的final变量。


函数式接口

在介绍 Functional Interface 之前,我们先来了解一下另外一个概念(first-class functions)。

In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures.

这一段话并不难理解,函数是一等公民,一等公民什么都可以做。

  1. 函数可以作为其他函数的参数。
  2. 函数可以作为其他函数的返回值。
  3. 函数可以赋值给变量,可以存储在数据结构中。

为什么要在介绍函数式接口之前先介绍这些呢,因为 函数为第一公民是函数式编程的基础。而 Java 语言的函数显然是不具备这个基础的,所以便有了函数式接口。

只包含一个抽象方法的接口,称为 函数式接口(Functional Interface)。

比如 Consumer 接口,只有一个抽象方法 void accept(T t),参数 T,没有返回值。

package java.util.function;

import java.util.Objects;

/**
 * Represents an operation that accepts a single input argument and returns no
 * result. Unlike most other functional interfaces, {@code Consumer} is expected
 * to operate via side-effects.
 *
 * <p>This is a <a href="package-summary.html">functional interface</a>
 * whose functional method is {@link #accept(Object)}.
 *
 * @param <T> the type of the input to the operation
 *
 * @since 1.8
 */
@FunctionalInterface
public interface Consumer<T> {

    /**
     * Performs this operation on the given argument.
     *
     * @param t the input argument
     */
    void accept(T t);

    /**
     * Returns a composed {@code Consumer} that performs, in sequence, this
     * operation followed by the {@code after} operation. If performing either
     * operation throws an exception, it is relayed to the caller of the
     * composed operation.  If performing this operation throws an exception,
     * the {@code after} operation will not be performed.
     *
     * @param after the operation to perform after this operation
     * @return a composed {@code Consumer} that performs in sequence this
     * operation followed by the {@code after} operation
     * @throws NullPointerException if {@code after} is null
     */
    default Consumer<T> andThen(Consumer<? super T> after) {
        Objects.requireNonNull(after);
        return (T t) -> { accept(t); after.accept(t); };
    }
}

我们可以用 Consumer 接口来写的一个 Hello,World。

import java.util.function.Consumer;

public class Main
{
    public static void echo(Consumer<String> consumer, String t) {
        consumer.accept(t);
    }

    public static void main(String[] args) {
        Consumer<String> hello = string -> System.out.println("hello, " + string);

        echo(hello, "world");
    }
}

练习

* Question 1:
* a.
* b. 一元运算符,比如负号,百分比。
* c. x -> x + 1;
*
* Question 2:
* a. N/A
* b. public final static ThreadLocal<DateFormatter> formatter = ThreadLocal.withInitial(() -> new DateFormatter(new SimpleDateFormat(“dd-MMM-yyyy”)));
*
* Question 3:
* a. Yes
* b. Yes
* c. No – the lambda expression could be inferred as IntPred or Predicate<Integer> so the overload is ambiguous.

参考:

https://www.runoob.com/java/java8-lambda-expressions.html

https://www.runoob.com/java/java8-functional-interfaces.html

https://en.wikipedia.org/wiki/First-class_function

https://kotlinlang.org/docs/reference/lambdas.html

https://www.ibm.com/developerworks/cn/java/j-understanding-functional-programming-3/

223 total views, no views today

Adapter 设计模式

本篇对应《图解设计模式》第二章。

适配器模式就是“把一个接口转换成另外一个接口”。


Samsung SD Adapter for microSD

比如我们要实现一个 TF (microSD) 卡转 SD 卡适配器。

定义 SdCard 接口。

public interface SdCard {
    /**
     * read data from SD card
     * @return
     */
    public String readSd();

    /**
     * write data to SD card
     * @param data
     * @return
     */
    public Boolean writeSd(String data);
}

定义 TfCard 接口。

public interface TfCard {
    /**
     * read data from TF card
     * @return
     */
    public String readTf();

    /**
     * write data to TF card
     * @param data
     * @return
     */
    public Boolean writeTf(String data);
}

实现 SdCardAdapter。

public class SdCardAdapter implements SdCard {
    /**
     * TF card
     */
    private TfCard tfCard;

    /**
     * read data from TF card (using SD card adpater)
     */
    @Override
    public String readSd() {
        return tfCard.readTf();
    }

    /**
     * write data to TF card (using SD card adpater)
     */
    @Override
    public Boolean writeSd(String data) {
        return tfCard.writeTf(data);
    }
}

参考:

https://book.douban.com/subject/26933281/

https://www.runoob.com/design-pattern/adapter-pattern.html

80 total views, no views today

Iterator 设计模式

本篇对应《图解设计模式》第一章。

我觉得 Iterator 设计模式是一个很成功的设计模式,对集合遍历问题进行了抽象。

具体到 Java 语言来讲,Iterator 设计模式是 Collections Framework 的一部分。


Iterator 接口

package java.util;

import java.util.function.Consumer;

/**
 * An iterator over a collection.  {@code Iterator} takes the place of
 * {@link Enumeration} in the Java Collections Framework.  Iterators
 * differ from enumerations in two ways:
 *
 * <ul>
 *      <li> Iterators allow the caller to remove elements from the
 *           underlying collection during the iteration with well-defined
 *           semantics.
 *      <li> Method names have been improved.
 * </ul>
 *
 * <p>This interface is a member of the
 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 * Java Collections Framework</a>.
 *
 * @apiNote
 * An {@link Enumeration} can be converted into an {@code Iterator} by
 * using the {@link Enumeration#asIterator} method.
 *
 * @param <E> the type of elements returned by this iterator
 *
 * @author  Josh Bloch
 * @see Collection
 * @see ListIterator
 * @see Iterable
 * @since 1.2
 */
public interface Iterator<E> {
    /**
     * Returns {@code true} if the iteration has more elements.
     * (In other words, returns {@code true} if {@link #next} would
     * return an element rather than throwing an exception.)
     *
     * @return {@code true} if the iteration has more elements
     */
    boolean hasNext();

    /**
     * Returns the next element in the iteration.
     *
     * @return the next element in the iteration
     * @throws NoSuchElementException if the iteration has no more elements
     */
    E next();

    /**
     * Removes from the underlying collection the last element returned
     * by this iterator (optional operation).  This method can be called
     * only once per call to {@link #next}.
     * <p>
     * The behavior of an iterator is unspecified if the underlying collection
     * is modified while the iteration is in progress in any way other than by
     * calling this method, unless an overriding class has specified a
     * concurrent modification policy.
     * <p>
     * The behavior of an iterator is unspecified if this method is called
     * after a call to the {@link #forEachRemaining forEachRemaining} method.
     *
     * @implSpec
     * The default implementation throws an instance of
     * {@link UnsupportedOperationException} and performs no other action.
     *
     * @throws UnsupportedOperationException if the {@code remove}
     *         operation is not supported by this iterator
     *
     * @throws IllegalStateException if the {@code next} method has not
     *         yet been called, or the {@code remove} method has already
     *         been called after the last call to the {@code next}
     *         method
     */
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    /**
     * Performs the given action for each remaining element until all elements
     * have been processed or the action throws an exception.  Actions are
     * performed in the order of iteration, if that order is specified.
     * Exceptions thrown by the action are relayed to the caller.
     * <p>
     * The behavior of an iterator is unspecified if the action modifies the
     * collection in any way (even by calling the {@link #remove remove} method
     * or other mutator methods of {@code Iterator} subtypes),
     * unless an overriding class has specified a concurrent modification policy.
     * <p>
     * Subsequent behavior of an iterator is unspecified if the action throws an
     * exception.
     *
     * @implSpec
     * <p>The default implementation behaves as if:
     * <pre>{@code
     *     while (hasNext())
     *         action.accept(next());
     * }</pre>
     *
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

Iterable 接口

package java.lang;

import java.util.Iterator;
import java.util.Objects;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;

/**
 * Implementing this interface allows an object to be the target of the enhanced
 * {@code for} statement (sometimes called the "for-each loop" statement).
 *
 * @param <T> the type of elements returned by the iterator
 *
 * @since 1.5
 * @jls 14.14.2 The enhanced {@code for} statement
 */
public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();

    /**
     * Performs the given action for each element of the {@code Iterable}
     * until all elements have been processed or the action throws an
     * exception.  Actions are performed in the order of iteration, if that
     * order is specified.  Exceptions thrown by the action are relayed to the
     * caller.
     * <p>
     * The behavior of this method is unspecified if the action performs
     * side-effects that modify the underlying source of elements, unless an
     * overriding class has specified a concurrent modification policy.
     *
     * @implSpec
     * <p>The default implementation behaves as if:
     * <pre>{@code
     *     for (T t : this)
     *         action.accept(t);
     * }</pre>
     *
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    /**
     * Creates a {@link Spliterator} over the elements described by this
     * {@code Iterable}.
     *
     * @implSpec
     * The default implementation creates an
     * <em><a href="../util/Spliterator.html#binding">early-binding</a></em>
     * spliterator from the iterable's {@code Iterator}.  The spliterator
     * inherits the <em>fail-fast</em> properties of the iterable's iterator.
     *
     * @implNote
     * The default implementation should usually be overridden.  The
     * spliterator returned by the default implementation has poor splitting
     * capabilities, is unsized, and does not report any spliterator
     * characteristics. Implementing classes can nearly always provide a
     * better implementation.
     *
     * @return a {@code Spliterator} over the elements described by this
     * {@code Iterable}.
     * @since 1.8
     */
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

分别使用几种不同的方法对集合进行遍历(都是基于 Iterator 设计模式)。

import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class Main
{
    public static void main(String[] args) {
        List<String> list = Arrays.asList("Hello", "World", "GoodBye");

        whileLoop(list);

        forLoop(list);

        forInLoop(list);

        forEachLoop(list);
    }

    // while loop, using iterator design pattern
    public static void whileLoop(Iterable iterable) {
        Iterator it = iterable.iterator();
        while(it.hasNext()) {
            System.out.println(it.next());
        }
    }

    // for loop, using iterator design pattern
    public static void forLoop(Iterable iterable) {
        for(Iterator it = iterable.iterator(); it.hasNext(); ) {
            System.out.println(it.next());
        }
    }

    // for/in, based on iterator design pattern
    public static void forInLoop(Iterable iterable) {
        for(Object object : iterable) {
            System.out.println(object);
        }
    }

    // forEach, based on for/in and functional programming
    public static void forEachLoop(Iterable iterable) {
        iterable.forEach(x -> System.out.println(x));
    }
}

参考:

https://book.douban.com/subject/26933281/

https://www.runoob.com/java/collection-iterator.html

https://www.ibm.com/developerworks/cn/java/j-forin.html

https://docs.oracle.com/javase/tutorial/collections/intro/index.html

https://github.com/tanghengzhi/java-design-pattern/tree/master/src/Iterator

363 total views, no views today

Depth-First Search vs Breadth-First Search

Graph

在计算机科学中, 图(graph) 是一种抽象数据类型, 旨在实现数学中的无向图和有向图概念,特别是图论领域。

一个图数据结构是一个(由有限个或者可变数量的)顶点/节点/点和边构成的有限集。

如果顶点对之间是无序的,称为无序图,否则称为有序图;

如果顶点对之间的边是没有方向的,称为无向图,否则称为有向图;

如果顶点对之间的边是有权重的,该图可称为加权图。

Depth-First Search (DFS)

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Breadth-First Search (BFS)

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors.

参考:


https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/graph

https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/depth-first-search

https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/breadth-first-search

172 total views, 1 views today

Active Record vs Data Mapper

最近一直在用 Spring Boot 开发,项目中用到的 ORM 框架有:Spring Data JPA,Spring Data MongoDB,Mybatis,MyBatis Plus。

对照 Martin Fowler 的 Catalog of Patterns of Enterprise Application Architecture,我们分别列出 Spring Data,Mybatis,Mybatis Plus 使用的设计模式。

ORM FrameworkDesign Pattern
Spring DataRepository
MybatisData Mapper
Mybatis PlusData Mapper & Active Record

作为对比,我们看一下常用的 PHP ORM 框架使用的设计模式。

ORM Framework Design Pattern
Yii Active RecordActive Record
Laravel EloquentActive Record
Symfony Doctrine Data Mapper

可以看出 Java ORM 框架更喜欢 Data Mapper 设计模式,而 PHP ORM 框架更喜欢 Active Record 模式。

再看一下其他语言的 ORM 框架:

ORM Framework Design Pattern
Ruby on RailsActive Record
DjangoActive Record
Mongoose Active Record

不管是 Ruby on Rails(Ruby), 还是 Django(Python),或者 Mongoose(Node.js),都偏爱 Active Record 模式。


Active Record vs Data Mapper

作为两种非常常见的设计模式,让我们稍微花点时间了解一下 Active Record 和 Data Mapper 的区别。

首先我们还是参考 Martin Fowler 的 Catalog of Patterns of Enterprise Application Architecture 对比一下两种设计模式。

Active Record

Data Mapper

从图上可以看出来,两种设计模式最直观的区别是:Active Record 模式只定义了一个 Person 类,Data Mapper 模式需要定义 Person 类和 PersonMapper 类。

然后我们来对比一下两种模式代码上的区别:

Active Record

Person person = new Person();
person.firstName = "firstName";
person.lastName = "lastName";
person.insert();

Data Mapper

Person person = new Person();
person.firstName = "firstName";
person.lastName = "lastName";
personMapper.insert(person);

我个人更喜欢 Active Record 模式,不知道你们喜欢那种设计模式呢?


参考:

https://www.martinfowler.com/eaaCatalog/index.html

https://www.martinfowler.com/eaaCatalog/dataMapper.html

https://www.martinfowler.com/eaaCatalog/activeRecord.html

https://spring.io/projects/spring-data-jpa

http://www.mybatis.org/mybatis-3/

https://mybatis.plus/

https://www.yiiframework.com/doc/guide/2.0/en/db-active-record

https://laravel.com/docs/5.8/eloquent

https://symfony.com/doc/current/doctrine.html

https://guides.rubyonrails.org/active_record_basics.html

https://docs.djangoproject.com/en/2.2/topics/db/models/

https://mongoosejs.com/

314 total views, no views today