Published on

ARTS 第28周

Authors

Algorithm

package org.nocoder.leetcode.solution;

import java.util.Arrays;

/**
 * 976. Largest Perimeter Triangle
 * <p>
 * Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.
 * <p>
 * If it is impossible to form any triangle of non-zero area, return 0.
 * <p>
 * Example 1:
 * <p>
 * Input: [2,1,2]
 * Output: 5
 * Example 2:
 * <p>
 * Input: [1,2,1]
 * Output: 0
 * Example 3:
 * <p>
 * Input: [3,2,3,4]
 * Output: 10
 * Example 4:
 * <p>
 * Input: [3,6,2,3]
 * Output: 8
 * <p>
 * <p>
 * Note:
 * <p>
 * 3 <= A.length <= 10000
 * 1 <= A[i] <= 10^6
 *
 * @author jason
 * @date 2019/1/19.
 */
public class LargestPerimeterTriangle {

    public int largestPerimeter(int[] arr) {
        Arrays.sort(arr);
        for (int i = arr.length - 3; i >= 0; --i) {
            if (arr[i] + arr[i + 1] > arr[i + 2]) {
                return arr[i] + arr[i + 1] + arr[i + 2];
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        LargestPerimeterTriangle lpt = new LargestPerimeterTriangle();
        System.out.println(lpt.largestPerimeter(new int[]{3, 6, 2, 3}));
    }
}

Review

A Beautiful Race Condition

Tip

mysqlslap is a diagnostic program designed to emulate client load for a MySQL server and to report the timing of each stage. It works as if multiple clients are accessing the server.

mysqlslap是mysql自带的性能测试工具,可以模拟多个mysql客户端连接进行并发测试,输出测试结果。

测试100个并发线程,测试次数1次,自动生成SQL测试脚本,读、写、更新混合测试,自增长字段,测试引擎为innodb,共运行5000次查询
#mysqlslap -h127.0.0.1 -uroot -p --concurrency=100 --iterations=1 --auto-generate-sql --auto-generate-sql-load-type=mixed --auto-generate-sql-add-autoincrement --engine=innodb --number-of-queries=5000
Benchmark
Running for engine innodb
Average number of seconds to run all queries: 0.351 seconds
Minimum number of seconds to run all queries: 0.351 seconds
Maximum number of seconds to run all queries: 0.351 seconds
Number of clients running queries: 100
Average number of queries per client:50

Share

理解Map

Map的基本思想是它维护的是键值对,可以使用键来查找值。Java标准库中包含了Map和几种实现,包括HashMap,TreeMap, LinkedHashMap, WeakHashMap, ConcurrentHashMap, IdentityHashMap。它们都实现了Map接口,但是行为特性各不相同,表现在效率,键值对的保存及呈现次序、对象的保存周期、如何在多线程程序中工作和判定key等价的策略等方面。

以下是一个极简的map实现:

package org.nocoder.map;

/**
 * Simple map, associates keys with values
 * low efficiency, fixed size
 * @author yangjinlong
 */
public class AssociativeArray<K, V> {
    private Object[][] pairs;
    private int index;

    public AssociativeArray(int length) {
        pairs = new Object[length][2];
    }

    public void put(K key, V value) {
        if (index >= pairs.length) {
            throw new ArrayIndexOutOfBoundsException("Too many values");
        }
        pairs[index++] = new Object[]{key, value};
    }

    public V get(K key) {
        for (int i = 0; i < index; i++) {
            if (key.equals(pairs[i][0])) {
                return (V) pairs[i][1];
            }
        }
        return null;
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < index; i++) {
            if (i == 0) {
                result.append("{");
            }
            result.append(pairs[i][0].toString());
            result.append("=");
            result.append(pairs[i][1].toString());
            if (i < index - 1) {
                result.append(", ");
            } else {
                result.append("}");
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        AssociativeArray<String, Integer> map = new AssociativeArray<>(2);
        try {
            map.put("Jason", 29);
            map.put("Freda", 26);
        } catch (ArrayIndexOutOfBoundsException e) {
            e.printStackTrace();
        }
        System.out.println(map);
        System.out.println(map.get("Jason"));
    }
}

最常用的Map的实现应该就是 HashMap 了,HashMap的数据结构是由数组和链表构成,Java8以后还加入了红黑树。HashMap中的几个术语需要了解:

  • 容量:表中的桶位数
  • 初始容量:在创建时所拥有的桶位数
  • 尺寸:表中当前存储的项数
  • 负载因子:尺寸/容量。空表的负载因子是0,半满表的负载因子是0.5,以此类推,HashMap 使用的默认负载因子是0.75,当表达到3/4满时,再进行rehash。

HashMap通常会用一个指针数组(假设为table[])来做分散所有的key,当一个key被加入时,会通过Hash算法通过key算出这个数组的下标i,然后就把这个<key, value>插到table[i]中,如果有两个不同的key被算在了同一个i,那么就叫冲突,又叫碰撞,这样会在table[i]上形成一个链表。

HashMap是非线程安全的,所以在并发情况下,HashMap可能会出现死循环导致CPU占用100%,查看耗叔的疫苗:JAVA HASHMAP的死循环 - CoolShell文章可以了解导致死循环的细节。