美國電動車商特斯拉（Tesla）於10月26日發表今年第三季財報，以淨營收2,190萬美元的成果翻紅，EPS相當於每股0.14美元。全球電動車市場蓬勃，且Model 3車款的訂單爆量，市況前景佳，也帶動了上游的供應鏈興盛。為特斯拉車用電池供應原料的日本住友金屬礦山（Sumitomo Metal Mining）也宣布將擴大產能。

特斯拉轉盈

特斯拉今年第三季的淨營收為2,190萬美元，EPS每股0.14美元，較去年每股虧損1.78美元有大幅成長。經會計調整後，第三季EPS為0.71美元，遠高於原先路透社調查預估的虧損0.54美元。會計調整後營收23億美元，也優於原先法人預期的19.8億美元。

特斯拉執行長Elon Musk在財報說明會上表示，今年下半年仍力求出貨5萬輛電動車的目標，並將致力於提升毛利率；在此基礎下，Musk看好第四季營收仍將持續獲利。

特斯拉亦指出，Model 3的交車時間表仍在軌道上，相當於駁斥Model 3將會面臨交車延遲的市場傳聞。特斯拉第三季財報的表現，也將影響股東於11月17日的股東會上針對是否併購SolarCity之投票案的意願。

特斯拉訂單多，上游樂

特斯拉的車用電池由Panasonic提供，而Panasonic的鋰離子電池其中一項原料──鎳酸鋰，則幾乎都由日本住友金屬礦山供應。因應特斯拉訂單強勁，以及全球電動車需求成長，住友金屬礦山宣布砸下180億日圓資金，擴大鎳酸鋰產能。

住友金屬礦山目前的鎳酸鋰每月產能約為1,850噸，預計在2018年1月擴產至3,550噸，以供應未來電動車用鋰電池所需。同時，住友金屬礦山也與Panasonic合作研發高性能鎳酸鋰的產能。

住友金屬礦山的擴產計畫，與特斯拉預計在2017年開始出貨Model 3有直接關聯。加上特斯拉預計2018年要出貨50萬輛Model 3，住友金屬礦山也因此將原先擴產到2,550噸的計畫提高到3,550噸。

其他鋰電池材料，如正負極、分隔膜、電解液等，日系、韓系廠商如住友化學、Toray、旭化成、昭和電工等的市占率相當高。這些廠商也都看好電動車市場的需求繼續成長，持續有擴產計畫，並與鋰電池大廠Panasonic、LG Chem等公司密切合作。

（照片來源： shared by CC 2.0）

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司“嚨底家”!

※推薦評價好的iphone維修中心

※聚甘新

目錄

• 簡介
• LogCompilation簡介
• LogCompilation的使用
• 解析LogCompilation文件
• 總結

簡介

我們知道在JVM中為了加快編譯速度，引入了JIT即時編譯的功能。那麼JIT什麼時候開始編譯的，又是怎麼編譯的，作為一個高傲的程序員，有沒有辦法去探究JIT編譯的秘密呢？答案是有的，今天和小師妹一起帶大家來看一看這個編譯背後的秘密。

更多精彩內容且看：

• 區塊鏈從入門到放棄系列教程-涵蓋密碼學,超級賬本,以太坊,Libra,比特幣等持續更新
• Spring Boot 2.X系列教程:七天從無到有掌握Spring Boot-持續更新
• Spring 5.X系列教程:滿足你對Spring5的一切想象-持續更新
• java程序員從小工到專家成神之路（2020版）-持續更新中,附詳細文章教程

LogCompilation簡介

小師妹：F師兄，JIT這麼神器，但是好像就是一個黑盒子，有沒有辦法可以探尋到其內部的本質呢？

追求真理和探索精神是我們作為程序員的最大優點，想想如果沒有玻爾關於原子結構的新理論，怎麼會有原子體系的突破，如果沒有海森堡的矩陣力學，怎麼會有量子力學的建立？

JIT的編譯日誌輸出很簡單，使用 -XX:+LogCompilation就夠了。

如果要把日誌重定向到一個日誌文件中，則可以使用-XX:LogFile= 。

但是要開啟這些分析的功能，又需要使用-XX:+UnlockDiagnosticVMOptions。 所以總結一下，我們需要這樣使用：

-XX:+UnlockDiagnosticVMOptions -XX:+LogCompilation -XX:LogFile=www.flydean.com.log

LogCompilation的使用

根據上面的介紹，我們現場來生成一個JIT的編譯日誌，為了體現出專業性，這裏我們需要使用到JMH來做性能測試。

JMH的全稱是Java Microbenchmark Harness，是一個open JDK中用來做性能測試的套件。該套件已經被包含在了JDK 12中。

如果你使用的不是JDK 12，那麼需要添加如下依賴：

<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-core</artifactId>
    <version>1.19</version>
</dependency>
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-generator-annprocess</artifactId>
    <version>1.19</version>
</dependency>

更多詳情可以參考我之前寫的： 在java中使用JMH（Java Microbenchmark Harness）做性能測試一文。

之前有的朋友說，代碼也用圖片，看起來好看，從本文之後，我們會盡量把代碼也轉成圖片來展示：

看完我的JMH的介紹，上面的例子應該很清楚了，主要就是做一個累加操作，然後warmup 5輪，測試5輪。

在@Fork註解裏面，我們可以配置jvm的參數，為什麼我註釋掉了呢？因為我發現在jvmArgsPrepend中的-XX:LogFile是不生效的。

沒辦法，我只好在運行配置中添加：

運行之後，你就可以得到輸出的編譯日誌文件。

解析LogCompilation文件

小師妹：F師兄，我看了一下生成的文件好複雜啊，用肉眼能看得明白嗎？

別怕，只是內容的多一點，如果我們細細再細細的分析一下，你會發現其實它真的非常非常……複雜!

其實寫點簡單的小白文不好嗎？為什麼要來分析這麼複雜，又沒人看，看了也沒人懂的JVM底層…..

大概，這就是專業吧！

LogCompilation文件其實是xml格式的，我們現在來大概分析一下，它的結構，讓大家下次看到這個文件也能夠大概了解它的重點。

首先最基本的信息就是JVM的信息，包括JVM的版本，JVM運行的參數，還有一些properties屬性。

我們收集到的日誌其實是分兩類的，第一類是應用程序本身的的編譯日誌，第二類就是編譯線程自己內部產生的日誌。

第二類的日誌會以hs_c*.log的格式存儲，然後在JVM退出的時候，再將這些文件跟最終的日誌輸出文件合併，生成一個整體的日誌文件。

比如下面的兩個就是編譯線程內部的日誌：

<thread_logfile thread='22275' filename='/var/folders/n5/217y_bgn49z18zvjch907xb00000gp/T//hs_c22275_pid83940.log'/>
<thread_logfile thread='41731' filename='/var/folders/n5/217y_bgn49z18zvjch907xb00000gp/T//hs_c41731_pid83940.log'/>

上面列出了編譯線程的id=22275，如果我們順着22275找下去，則可以找到具體編譯線程的日誌：

<compilation_log thread='22275'>
...
</compilation_log>

上面由compilation_log圍起來的部分就是編譯日誌了。

接下來的部分表示，編譯線程開始執行了，其中stamp表示的是啟動時間，下圖列出了一個完整的編譯線程的日誌：

<start_compile_thread name='C2 CompilerThread0' thread='22275' process='83940' stamp='0.058'/>

接下來描述的是要編譯的方法信息：

<task compile_id='10' method='java.lang.Object <init> ()V' bytes='1' count='1409' iicount='1409' stamp='0.153'>

上面列出了要編譯的方法名，compile_id表示的是系統內部分配的編譯id，bytes是方法中的字節數，count表示的是該方法的調用次數，注意，這裏的次數並不是方法的真實調用次數，只能做一個估計。

iicount是解釋器被調用的次數。

task執行了，自然就會執行完成，執行完成的內容是以task_done標籤來表示的：

<task_done success='1' nmsize='120' count='1468' stamp='0.155'/>

其中success表示是否成功執行，nmsize表示編譯器編譯出來的指令大小，以byte為單位。如果有內聯的話，還有個inlined_bytes屬性，表示inlined的字節個數。

<type id='1025' name='void'/>

type表示的是方法的返回類型。

<klass id='1030' name='java.lang.Object' flags='1'/>

klass表示的是實例和數組類型。

<method id='1148' holder='1030' name='<init>' return='1025' flags='1' bytes='1' compile_id='1' compiler='c1' level='3' iicount='1419'/>

method表示執行的方法，holder是前面的klass的id，表示的是定義該方法的實例或者數組對象。method有名字，有
return，return對應的是上面的type。

flags表示的是方法的訪問權限。

接下來是parse，是分析階段的日誌：

<parse method='1148' uses='1419.000000' stamp='0.153'>

上面有parse的方法id。uses是使用次數。

<bc code='177' bci='0'/>

bc是byte Count的縮寫，code是byte的個數，bci是byte code的索引。

<dependency type='no_finalizable_subclasses' ctxk='1030'/>

dependency分析的是類的依賴關係，type表示的是什麼類型的依賴，ctkx是依賴的context class。

我們注意有的parse中，可能會有uncommon_trap：

<uncommon_trap bci='10' reason='unstable_if' action='reinterpret' debug_id='0' comment='taken never'/>

怎麼理解uncommon_trap呢？字面上意思就是捕獲非常用的代碼，就是說在解析代碼的過程中發現發現這些代碼是uncommon的，然後解析產生一個uncommon_trap，不再繼續進行了。

它裏面有兩個比較重要的字段，reason表示的是被標記為uncommon_trap的原因。action表示的出發uncommon_trap的事件。

有些地方還會有call：

<call method='1150' count='5154' prof_factor='1.000000' inline='1'/>

call的意思是，在該代碼中將會調用其他的方法。count是執行次數。

總結

複雜的編譯日誌終於講完了，可能講的並不是很全，還有一些其他情況這裏並沒有列出來，後面如果遇到了，我再添加進去。

本文的例子https://github.com/ddean2009/learn-java-base-9-to-20

本文作者：flydean程序那些事

本文鏈接：http://www.flydean.com/jvm-jit-logcompilation/

本文來源：flydean的博客

歡迎關注我的公眾號:程序那些事，更多精彩等着您！

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司“嚨底家”!

※推薦評價好的iphone維修中心

※聚甘新

目錄

一.ConcurrentHashMap的模型圖

二.源碼分析-類定義

　　2.1 極簡ConcurrentHashMap定義

　　2.2 Segment內部類

　　2.3 HashEntry內部類

　　2.4 ConcurrentHashMap的重要常量

三.常用接口源碼分析

　　3.1 ConcurrentHashMap構造方法

　　3.2 map.put操作

　　3.3 創建新segment

　　3.4 segment.put操作

　　3.5 segment.rehash擴容

　　3.6 map.get操作

　　3.7 map.remove操作

　　3.8 map.size操作

 

　　原文地址：https://www.cnblogs.com/-beyond/p/13157083.html

一.ConcurrentHashMap的模型圖

　　之前看了Java8中的HashMap，然後想接着看Java8的ConcurrentHashMap，但是打開Java8的ConcurrentHashMap，瞬間就慫了，將近7k行代碼，而反觀一下Java7的Concurrent，也就在1500多行，那就先選擇少的看吧。畢竟Java7的ConcurrentHashMap更加簡單。下面所有的介紹都是針對Java7而言！！！！！

　　下面是ConcurrentHashMap的結構圖，ConcurrentHashMap有一個segments數組，每個segment中又有一個table數組，該數組的每個元素時HashEntry類型。

　　 

　　可以簡單的理解為ConcurrentHashMap是多個HashMap組成，每一個HashMap是一個segment，就如傳說中一樣，ConcurrentHashMap使用分段鎖的方式，這個“段”就是segment。

　　ConcurrentHashMap之所以能夠保證併發安全，是因為支持對不同segment的併發修改操作，比如兩個線程同時修改ConcurrentHashMap，一個線程修改第一個segment的數據，另一個線程修改第二個segment的數據，兩個線程可以併發修改，不會出現併發問題；但是多個線程同一個segment進行併發修改，則需要先獲取該segment的鎖后再修改，修改完后釋放鎖，然後其他要修改的線程再進行修改。

　　那麼，ConcurrentHashMap可以支持多少併發量呢？這個也就是問，ConcurrentHashMap最多能支持多少線程併發修改，其實也就是segment的數量，只要修改segment的這些線程不是修改同一個segment，那麼這些線程就可以并行執行，這也就是ConcurrentHashMap的併發量（segment的數量）。

　　注意，ConcurrentHashMap創建完成后，也就是segment的數量、併發級別已經確定，則segment的數量和併發級別都不能再改變了，即使發生擴容，也是segment中的table進行擴容，segment的數量保持不變。

 

二.源碼分析-類定義

2.1 極簡ConcurrentHashMap定義

　　下面是省略了大部分代碼的ConcurrentHashMap定義：

package java.util.concurrent;

import java.util.AbstractMap;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable {

    final Segment<K, V>[] segments;

    /**
     * segment分段的定義
     */
    static final class Segment<K, V> extends ReentrantLock implements Serializable {

        transient volatile HashEntry<K, V>[] table;
    }

    /**
     * 存放的元素節點
     */
    static final class HashEntry<K, V> {

    }
}

 

2.2 Segment內部類

　　ConcurrentHashMap內部有一個segments屬性，是Segment類型的數組，Segment類和HashMap很相似（Java7的HashMap)，維持一個數組，每個數組是一個HashEntry，當發生hash衝突后，則使用拉鏈法（頭插法）來解決衝突。

　　而Segment數組的定義如下，省略了方法：

static final class Segment<K, V> extends ReentrantLock implements Serializable {
    static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
    private static final long serialVersionUID = 2249069246763182397L;
    
    // segment的負載因子（segments數組中的所有segment負載因子都相同）
    final float loadFactor;
    
    // segment中保存元素的數組
    transient volatile HashEntry<K, V>[] table;
   
    // 該segment中的元素個數
    transient int count;
    
    // modify count，該segment被修改的次數
    transient int modCount;
    
    // segment的擴容閾值
    transient int threshold;
}

　　注意每個Segment都有負載因子、以及擴容閾值，但是後面可以看到，其實segments數組中的每一個segment，負載因子和擴容閾值都相同，因為創建的時候，都是使用0號segment的負載因子和擴容閾值。

 

2.3 HashEntry內部類

　　Segment類中有一個table數組，table數組的每個元素都是HashEntry類型，和HashMap的Entry類似，源碼如下：（省略了方法）

/**
 * map中每個元素的類型
 */
static final class HashEntry<K, V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K, V> next;
}

 

2.4 ConcurrentHashMap的一些常量

　　ConcurrentHashMap中有很多常量，

// 默認初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;

// 默認的負載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 默認的併發級別(同時支持多少線程併發修改)
// 因為JDK7中ConcurrentHashMap中是用分段鎖實現併發，不同分段的數據可以進行併發操作，同一個段的數據不能同時修改
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 每一個分段的數組容量初始值
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;

// 最多能有多少個segment
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

// 嘗試對整個map進行操作（比如說統計map的元素數量），可能需要鎖定全部segment；
// 這個常量表示鎖定所有segment前，嘗試的次數
static final int RETRIES_BEFORE_LOCK = 2;

　　

三.常用接口源碼分析

3.1 ConcurrentHashMap構造方法

　　ConcurrentHashMap有多個構造方法，但是內部其實都是調用同一個進行創建：

public ConcurrentHashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}

public ConcurrentHashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}

public ConcurrentHashMap(int initialCapacity, float loadFactor) {
    this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
}

/**
 * 統一調用的構造方法
 *
 * @param initialCapacity  初始容量
 * @param loadFactor       負載因子
 * @param concurrencyLevel 併發級別
 */
@SuppressWarnings("unchecked")
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
    // 校驗參數合法性
    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) {
        throw new IllegalArgumentException();
    }

    // 對併發級別進行調整，不允許超過segment的數量（超過segment其實是沒有意義的）
    if (concurrencyLevel > MAX_SEGMENTS) {
        concurrencyLevel = MAX_SEGMENTS;
    }

    // 根據concurrencyLevel確定sshift和ssize的值
    int ssize = 1; // ssize是表示segment的數量，ssize是不小於concurrencyLevel的數，並且是2的n次方
    int sshift = 0;// sshift是ssize轉換為2進制后的位數，比如ssize為16（1000），則sshift為4
    while (ssize < concurrencyLevel) {
        ++sshift;
        ssize <<= 1;
    }
    // 比如concurrencyLevel默認為16，走完循環，sshift為4，ssize為16
    // 如果concurrentLevel為8，則sshift為3，ssize為8

    // segment的shift偏移量
    this.segmentShift = 32 - sshift;
    // segment掩碼
    this.segmentMask = ssize - 1;

    // 對傳入的初始容量進行調整（不允許大於最大容量）
    if (initialCapacity > MAXIMUM_CAPACITY) {
        initialCapacity = MAXIMUM_CAPACITY;
    }

    // 假設傳入的容量為128，併發級別為16，則initialCapacity為128，ssize為16
    int c = initialCapacity / ssize;
    // c可以理解為根據傳入的初始容量，計算出每個segment中的數組容量
    if (c * ssize < initialCapacity) {
        ++c;
    }

    // cap表示的是每個segment中的數組容量
    int cap = MIN_SEGMENT_TABLE_CAPACITY;
    // 如果默認的每個segment中的數組長度小於上面計算出來的每個segment的數組長度，則將容量翻倍
    while (cap < c) {
        cap <<= 1;
    }

    // 創建一個segment，作為segments數組的第一個segment
    Segment<K, V> s0 = new Segment<K, V>(loadFactor, (int) (cap * loadFactor), new HashEntry[cap]);

    // 創建segments數組
    Segment<K, V>[] ss = (Segment<K, V>[]) new Segment[ssize];

    // 將s0賦值給segments數組的第一個元素（偏移量為0）
    UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]

    // 複製segment數組
    this.segments = ss;
}

/**
 * 傳入map，將map中的元素加入到ConcurrentHashMap中
 * 注意使用默認的負載因子（0.75）和默認的併發級別（16）
 * 初始容量取map容量和默認容量的較大值
 */
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY),
            DEFAULT_LOAD_FACTOR,
            DEFAULT_CONCURRENCY_LEVEL);
    putAll(m);
}

　　

3.2 map.put操作

　　map.put，map就是指ConcurrentHashMap，其實就是確定HashEntry應該放入哪個segment中的哪個位置，所以可分為3步：

　　1.首先需要確定放入哪個segment；

　　2.確定segment后，再確定HashEntry應該放入segment的哪個位置；

　　3.進行覆蓋覆蓋或者插入。

/**
 * put操作，注意key或者value為null時，會拋出NPE
 */
@SuppressWarnings("unchecked")
public V put(K key, V value) {
    Segment<K, V> s;
    if (value == null) {
        throw new NullPointerException();
    }

    // 計算key的hash
    int hash = hash(key);

    // hash值右移shift位后 與 mask掩碼進行取與，確定數據應該放到哪個segments數組的哪一個segment中
    int j = (hash >>> segmentShift) & segmentMask;

    // 判斷計算出的segment數組位置上的segment是否為null，如果為null，則進行創建segment
    if ((s = (Segment<K, V>) UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) {
        s = ensureSegment(j);
    }

    // 創建segment后，將數據put到segment中，調用的segment.put()
    return s.put(key, hash, value, false);
}

　　

3.3 創建新segment

　　上面put的時候，如果發現segment為null，則會進行調用ensureSegment進行創建segment，代碼如下：

/**
 * 擴容（創建）segment
 *
 * @param k 需要擴容或者需要創建的segment位置
 * @return 返回擴容后的segment
 */
@SuppressWarnings("unchecked")
private Segment<K, V> ensureSegment(int k) {
    final Segment<K, V>[] ss = this.segments;
    long u = (k << SSHIFT) + SBASE; // 傳入的index，對應的偏移量
    Segment<K, V> seg;

    // 判斷是否需要擴容或者創建segment，如果獲取到segment不為null，則返回segment
    if ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(ss, u)) == null) {
        Segment<K, V> proto = ss[0]; // “原型設計模式”，使用segments數組的0號位置segment
        int cap = proto.table.length;// 0號segment的table長度
        float lf = proto.loadFactor; // 0號segment的負載因子
        int threshold = (int) (cap * lf); // 0號segment的擴容閾值

        // 創建一個HashEntry的數組，數組容量和0號segment相同
        HashEntry<K, V>[] tab = (HashEntry<K, V>[]) new HashEntry[cap];

        // 再次檢測，指定的segment是不是為null，如果為null才進行下一步操作
        if ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck
            // 創建segment
            Segment<K, V> s = new Segment<K, V>(lf, threshold, tab);

            // 使用CAS將新創建的segment填入指定的位置
            while ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(ss, u)) == null) {
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s)) {
                    break;
                }
            }
        }
    }

    // 返回新增的segment
    return seg;
}

　　上面需要注意的是：

　　1.創建segment中的table數組時，是使用0號segment的table屬性（長度、負載因子、閾值）；

　　2.創建segment前會進行再check，check發現segment的確為null時，再進行創建segment；

　　3.利用CAS來將創建的segment填入segments數組中；

 

3.4 segment.put操作

　　當確定HashEntry應該放到哪個segment后，就開始調用segment的put方法，如下：

/**
 * 在確定應該存放到那個segment后，就segment.put()將k-v存入segment中
 *
 * @param key          put的key
 * @param hash         hash(key)的值
 * @param value        put的value
 * @param onlyIfAbsent true:key對應的Entry不進行覆蓋，false:key對應的entry存在與否，都進行put覆蓋
 * @return
 */
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // 先獲取鎖（ReentrantLock，內部使用非公平鎖）
    HashEntry<K, V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K, V>[] tab = table;

        // 根據hash值計算出在segment的table中的位置
        int index = (tab.length - 1) & hash;

        // 定位到segment的table的index位置（第一個節點）
        HashEntry<K, V> first = entryAt(tab, index);

        // 從第一個節點開始遍歷
        for (HashEntry<K, V> e = first; ; ) {
            // 節點不為空，則判斷是否key是否相同（相同HashEntry）
            if (e != null) {
                K k;
                // 比較是否key是否相等（判斷put的key是否已經存在）
                if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                    // 如果key已經存在，則進行覆蓋，如果onlyIsAbsent為false（不關心key對應的Entry是否存在）
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        // 覆蓋舊值，修改計數加1
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            } else {
                // 頭插法，將put的k-v創建新HashEntry，放到first的前面
                if (node != null) {
                    node.setNext(first);
                } else {
                    node = new HashEntry<K, V>(hash, key, value, first);
                }

                // segment中table元素數量加1
                int c = count + 1;

                // 加1后的size大於擴容閾值，且數組的長度小於最大容量，則進行rehash
                if (c > threshold && tab.length < MAXIMUM_CAPACITY) {
                    // 擴容，並進行rehash
                    rehash(node);
                } else {
                    // 將節點放入數組中的指定位置
                    setEntryAt(tab, index, node);
                }

                // 修改次數加一，修改segment的table元素個數
                ++modCount;
                count = c;

                // 舊值為null
                oldValue = null;
                break;
            }
        }
    } finally {
        // 釋放鎖
        unlock();
    }
    return oldValue;
}

　　梳理一下，大致在做下面幾件事：

　　1.先獲取鎖（ReetrantLock，內部使用非公平鎖NonFairSync）；

　　2.獲取到鎖后根據hash計算出在table的位置；

　　3.遍歷table的HashEntry的鏈表，如果有相同key的，則進行覆蓋，如果沒有，在進行頭插法；

　　4.插入鏈表后，確定是否需要擴容，需要則執行rehash；

　　5.修改計數（count、modCount），並且釋放鎖。

 

3.5 segment.rehash擴容

　　segment擴容時，會將該segment的容量擴容為之前的2倍，並且將各位置的鏈表節點元素進行rehash。

/**
 * 將segment的table容量擴容一倍（newCap=oldCap*2），注意只會擴容該node所在的segment
 *
 * @param node segment[i]->鏈表的頭結點
 */
@SuppressWarnings("unchecked")
private void rehash(HashEntry<K, V> node) {
    HashEntry<K, V>[] oldTable = table;
    int oldCapacity = oldTable.length;

    // 新容量為舊容量的2倍
    int newCapacity = oldCapacity << 1;

    // 設置新的擴容閾值
    threshold = (int) (newCapacity * loadFactor);

    // 申請新數組，數組長度為新容量值
    HashEntry<K, V>[] newTable = (HashEntry<K, V>[]) new HashEntry[newCapacity];

    // 循環遍歷segment的數組（舊數組）
    int sizeMask = newCapacity - 1; // 新的掩碼
    for (int i = 0; i < oldCapacity; i++) {
        // 獲取第i個位置的HashEntry節點，如果該節點為null，則該位置為空，不作處理
        HashEntry<K, V> e = oldTable[i];
        if (e != null) {
            HashEntry<K, V> next = e.next;

            // 計算新位置
            int idx = e.hash & sizeMask;

            // next為null，表示該位置只有一個節點，直接將節點複製到新位置
            if (next == null) {   //  Single node on list
                newTable[idx] = e;
            } else { // Reuse consecutive sequence at same slot
                HashEntry<K, V> lastRun = e;
                int lastIdx = idx;
                for (HashEntry<K, V> last = next; last != null; last = last.next) {
                    int k = last.hash & sizeMask;
                    if (k != lastIdx) {
                        lastIdx = k;
                        lastRun = last;
                    }
                }
                newTable[lastIdx] = lastRun;
                // 從頭結點開始，開始將節點拷貝到新數組中
                for (HashEntry<K, V> p = e; p != lastRun; p = p.next) {
                    V v = p.value;
                    int h = p.hash;
                    int k = h & sizeMask;
                    HashEntry<K, V> n = newTable[k];
                    newTable[k] = new HashEntry<K, V>(h, p.key, v, n);
                }
            }
        }
    }

    // 將頭結點添加到segment的table中
    int nodeIndex = node.hash & sizeMask; // add the new node
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;
    table = newTable;
}

　　為啥擴容的時候沒有加鎖呀？

　　其實已經加鎖了，只不過不是在rehash中加鎖！！！因為rehash是在map.put中調用，put的時候已經加鎖了，所以rehash中不用加鎖。

　　

3.6 map.get操作

　　get操作，先定位到segment，然後定位到segment的具體位置，進行獲取

/**
 * 從ConcurrentHashMap中獲取key對應的value，不需要加鎖
 */
public V get(Object key) {
    Segment<K, V> s;
    HashEntry<K, V>[] tab;

    // 計算key的hash
    int h = hash(key);

    // 計算key處於哪一個segment中（index）
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;

    // 獲取數組中該位置的segment，如果該segment的table不為空，那麼就繼續在segment中查找，否則返回null，因為未找到
    if ((s = (Segment<K, V>) UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) {

        // tab指向segment的table數組，通過hash計算定位到table數組的位置（然後開始遍歷鏈表）
        HashEntry<K, V> e;
        for (e = (HashEntry<K, V>) UNSAFE.getObjectVolatile(tab, ((long) (((tab.length - 1) & h)) << TSHIFT) + TBASE);
             e != null; e = e.next) {
            K k;
            // 判斷key和hash是否匹配，匹配則證明找到要查找的數據，將數據返回
            if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                return e.value;
        }
    }
    
    return null;
}

　　

3.7 map.remove操作

　　 刪除節點，和get的流程差不多，先定位到segment，然後確定segment的哪個位置（哪條鏈表），遍歷鏈表，找到後進行刪除。

/**
 * 刪除map中key對應的元素
 */
public V remove(Object key) {
    // 計算key的hash
    int hash = hash(key);

    // 根據hash確定segment
    Segment<K, V> s = segmentForHash(hash);

    // 調用segment.remove進行刪除
    return s == null ? null : s.remove(key, hash, null);
}

/**
 * 刪除segment中key對應的hashEntry
 * 如果傳入的value不為空，則會在value匹配的時候進行刪除，否則不操作
 */
final V segmeng.remove(Object key, int hash, Object value) {
    // 獲取鎖失敗，則不斷自旋嘗試獲取鎖
    if (!tryLock()) {
        scanAndLock(key, hash);
    }

    V oldValue = null;
    try {
        HashEntry<K, V>[] tab = table;
        // 定位到segment中table的哪個位置
        int index = (tab.length - 1) & hash;
        HashEntry<K, V> e = entryAt(tab, index);
        HashEntry<K, V> pred = null;

        // 遍歷鏈表
        while (e != null) {
            K k;
            HashEntry<K, V> next = e.next;
            // 如果key和hash都匹配
            if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                V v = e.value;
                // 如果沒有傳入value，則直接刪除該節點
                // 如果傳入了value，比如調用的map.remove(key,value)，則要value匹配才會刪除，否則不操作
                if (value == null || value == v || value.equals(v)) {
                    if (pred == null) { // 頭結點就是要找刪除的元素，next為null，則將null賦值數組的該位置
                        setEntryAt(tab, index, next);
                    } else { // 
                        pred.setNext(next);
                    }

                    // 修改次數加一，map數量減一
                    ++modCount;
                    --count;
                    oldValue = v;
                }
                break;
            }

            // 不匹配時，pred保存當前一次檢測的節點，e指向下一個節點
            pred = e;
            e = next;
        }
    } finally {
        unlock();// 釋放鎖
    }
    return oldValue;
}

　　

3.8 map.size操作

　　ConcurrentHashMap的size()，需要統計每一個segment中的元素數量（也就是count值），因為不同的segment允許併發修改，統計過程中可能會出現修改操作，導致統計不準確，所以要想準確統計整個map的元素數量，可以這樣做：通過加鎖的方式來解決（將所有的segment都加鎖），這樣就能保證元素不會變化了，這是我們的想法。

　　而ConcurrentHashMap是這樣解決的，先嘗試不加鎖進行統計兩次，這兩次統計，不止會統計每個segment的元素數量，還會統計每個segment的modCount(修改次數），進行匯總；如果兩次統計的modCount總量相同，也就說明兩次統計期間沒有修改操作，證明統計的元素總量正確；如果兩次modCount總量不相同，表示有修改操作，則進行重試，如果重試后，發現還是不準確（modCount不匹配），那麼就嘗試為所有的segment加鎖，再進行統計。

　　源碼如下：

/**
 * 獲取ConcurrentHashMap中的元素個數，如果元素個數超過Integer.MAX_VALUE，則返回Integer.MAX_VALUE
 */
public int size() {
    final Segment<K, V>[] segments = this.segments;
    int size;           // 返回元素數量（統計結果->元素的總量）
    boolean overflow;   // 標誌是否溢出（是否超過Integer.MAX_VALUE）
    long sum;           // 所有segment的modCount總量次數（整個map的修改次數）
    long last = 0L;     // previous sum，上一輪統計的modCount總量
    int retries = -1;   // 記錄重試的次數

    try {
        // 此處for循環主要用於控制重試
        for (; ; ) {
            // 重試的次數如果達到RETRIES_BEFORE_LOCK，則強制獲取所有segment的鎖
            if (retries++ == RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j) {
                    ensureSegment(j).lock();
                    // 強制獲取segment的table第i個位置，並加鎖
                }
            }

            sum = 0L;
            size = 0;
            overflow = false;
            // 開始對segments中的每一個segment中進行統計
            for (int j = 0; j < segments.length; ++j) {
                // 獲取第j個segment
                Segment<K, V> seg = segmentAt(segments, j);
                // 如果segment不為空，則進行統計
                if (seg != null) {
                    sum += seg.modCount;
                    int c = seg.count;
                    // size累加
                    if (c < 0 || (size += c) < 0)
                        overflow = true;
                }
            }

            // 如果本次統計的modCount總量和上次一樣，則表示在這兩次統計之間沒有進行過修改，則不再重試
            if (sum == last) {
                break;
            }
            // 記錄本次統計的modCount總量
            last = sum;
        }
    } finally {
        // 判斷是否加了鎖（如果retries大於RETRIES_BEFORE_LOCK），則證明加了鎖，於是進行釋放鎖
        if (retries > RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j)
                segmentAt(segments, j).unlock();
        }
    }
    return overflow ? Integer.MAX_VALUE : size;
}

　　

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司“嚨底家”!

※推薦評價好的iphone維修中心

※聚甘新

毋庸置疑，電池是新能源汽車的核心部件。當前比較主流的電池包括超級電容器、金屬氫化物鎳電池、鋰離子電池、燃料電池。超級電容器的特點是可承受瞬間大電流充放電，但儲電量低，不能驅動車輛長時間的使用；金屬氫化物電池具備大電流充放電能力，安全性好，但是比容量低，體積較大；鋰離子電池的電壓在這幾類電池中最高，比容量高，但它的是安全性、低溫性能差；燃料電池從去年開始走進更多人的視線，能量儲備充足，可快速補充燃料，但成本高，瞬間輸出能力差，致命的缺陷是不能進行能量的回饋，導致驅動的車輛不能只用燃料電池實現刹車時能量的回收。

站在“風口”的新能源汽車正在經歷“冰火兩重天”：一面是整個行業不斷高速擴張銷量加速，但另一面，作為新能源汽車“心臟”的動力電池供應卻出現不足，影響新能源整車產量從量上看，今年新能源產銷帶來的動力電池需求依然將進一步放大。但在下游原材料價格暴漲以及上游整車廠價格打壓的雙重壓力下，什麼樣的動力電池企業能夠實現突圍？業內人士預計，在短暫的火爆期之後，成本和技術導向或使得今年動力電池行業將進入洗牌期。而在霧霾圍城、PM2.5屢屢爆表的現狀下，發展並普及新能源汽車具有重要的現實意義。而因新能源汽車井噴所帶來的大量退役動力電池，引發了行業的未雨綢繆。

新能源汽車對於電池的需求量仍處於巨大的增長空間，並且總體而言，動力電池的安全性與新能源汽車的使用要求還存在一定差距，中國國際新能源汽車論壇—致力於打造全球規模最大，最國際化的新能源汽車論壇的第七屆大會攜手上海市嘉定區人民政府將會專門設立動力電池板塊，進行為期2天的技術探討及分享，屆時國內外知名的整車商，動力電池知名供應商及零部件企業高層領導等將前來分享各自對於目前動力市場的發展前景看法及介紹最前沿的技術，同時，也會側重於目前存在的難點——梯次利用及回收和技術方面進行更深層次的交流。

本屆大會將於2017年5月17-19日在上海舉辦，大會涉及七個論壇、頒獎典禮、研討會及晚宴。屆時將會有全球範圍內的整車製造商、電網電力公司、電池廠商、零部件供應商、核心技術提供商和政府官員等600多位行業人士一起，對新能源汽車產業面臨的挑戰，機遇與對策各方面進行為期三天更深層次並具有建設和戰略性的探討，期待您的參與。

會議結構

若您對峰會有更多要求，請撥打021-6045 1760與我們聯繫，謝謝理解和支持！
我們期待與貴單位一起出席於2017年5月17-19日在上海舉辦的第七屆中國國際新能源汽車論壇2017，以利決策！
想瞭解詳細內容，請登陸官方網站：
連絡人：Summer（謝清）
電話：+86 21-6045 1766
傳真：+86 21-6047 5887
郵箱: market@ourpolaris.com

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

※推薦評價好的iphone維修中心

根據路透社的報導，中國影視廠商樂視網旗下子公司，豪華電動車新創公司法拉第未來（Faraday Future），已經決定縮減在美國興建車廠的規模。組裝廠規模將由原來佔地300 萬平方英尺，大幅縮減至65 萬平方英尺，生產車款數量亦會由7 款大減至2 款。

報導指出，法拉第曾於2015 年表示，總投資金額達到13 億美元，在內華達州北拉斯維加斯的組裝廠年產可高達15 萬輛，而且2017 年底投產。不過根據目前的狀況顯示，法拉第目前該工廠得預定產能每年將少於1 萬輛，而且還必須延後到2019 年才開始正式量產。

由於受到前一段時間母公司樂視網財務困境的影響，法拉第工廠一度傳出高層離職、欠供應商貨款、甚至是停工歇業的消息。雖然，在母公司獲得人民幣168 億元的資金援助後，工廠重新啟動。不過，可能也是因為這樣的原因，使得樂事網不得不宣布縮小其工廠的規模與未來的生產能量。

在2017 年的CES 展上，法拉第推出首輛量產車款FF91 之後，由於具備高度智慧連網功能，以及搭載時下最熱門的自動駕駛技術。並且全車配備3D 雷達、10 個高感度相機、13 個長距離和短距離雷達以及12 個超聲波感測器，可以說性能超越市面上包括賓利、法拉利和特斯拉的所有電動車。但即便如此，分析師仍認為，法拉第FF91 的推出依舊是遠水救不了近火。

有統計指出，未來幾年內，樂視網在法拉第汽車上的資金缺口約在人民幣460 億元以上。而根據樂視網在2017 年1 月13 日發布的公告表示，引入包括融創中國在內的多家戰略投資，投資金額為人民幣168 億元的資金，則將汽車業務排除在外。換言之，樂事網的汽車豪賭，未來還需要再另籌資金。所以，在FF91 售價高達人民幣200 萬元，再加上樂視網資金仍有隱憂的情況下，法拉第工廠能不能順利在2019 年生產、上路，恐怕還有變數。

（合作媒體：。圖片出處：Faraday Future）

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

※推薦評價好的iphone維修中心

 

美商特斯拉（Tesla）執行長 Elon Musk 透露，Model 3 將於本月展開試產；進一步的，Tesla 更預計今夏進軍印度市場。而在以 Model 3 為主力的營運之之外，Tesla 也表示已投入開發自動駕駛卡車。

Model 3近期試產

Musk 於 2 月 5 日接受外媒訪問時透露，Tesla 目前正在投入發展自動駕駛卡車，可減少耗油、提高安全性，甚至有機會改變物流的經濟架構。若成功上路，預期會為貨物運輸帶來革新。但 Musk 估計，在監管機構對此技術認可之前，大概需要累積 60 億英里的自動駕駛資料，因此發展主力仍是 Model 3。

Tesla 已於 2 月 1 日動員供應商，預計在 2 月 20 日試產 Model 3。Model 3 是 Tesla 首輛大眾車款，去年發表至今已獲得 37 萬筆訂單，原本規劃在今年7月開始量產。在搭載的車用電池規格方面，Musk 也透過推特證實，Model 3 的電池容量不會超過 100kWh。

由於 Model 3 的車體較輕，電動機更省電，使用相同容量的車用電池時，仍可延伸續航力。Musk 曾表示，標準版 Model 3 的基礎續航里程有 350 公里左右，全配車款則可行駛 480 公里。

Tesla 汽車的 2016 年產能約為 10 萬輛，Musk 目標在 2018 年時將產能提高到 50 萬輛。

Tesla進軍印度市場，前景看好

據路透社報導，Musk 日前在推特上回文考慮今夏進軍印度市場，但尚未透露更多細節。

印度汽車市場於 2016 年已發展到 740 億美元，Musk 會對印度市場感興趣並不意外。Musk 在 2017 年的目標為擴張全球事業版圖，包括葡萄牙、台灣、南韓、紐西蘭、近期也準備發展阿拉伯聯合大公國的市場，相較於印度，上述汽車市場都較小，由此可見 Musk 想為 Model 3 拓展布局的野心。

印度城市的空氣品質近來有惡化趨勢，汽車排放廢氣是一大原因，而電動車則可能帶來幫助。Tesla 進軍印度與印度總理莫迪的「數位印度」願景相符，也可望幫助帶動印度的經濟成長。國外媒體雖估計 Model 3 一直到 2018 年才可能會在印度正式上市，但印度市場對電動車的強烈需求卻已可以預期。

（首圖來源：Tesla）

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

※推薦評價好的iphone維修中心

美國創業家Elon Musk對於新科技產業的想法與策略向來是全球關注的焦點。在成功推出電動車品牌特斯拉（Tesla）後，已帶動電動車用電池產業興起；他又在於杜拜舉辦之世界政府峰會（World Government Summit）上提到，未來可將人工智慧（AI）整合入汽車產業，推動無人駕駛功能。

Model 3試產，貿聯-KY獲利創新高

近期消息指出，Tesla平價電動車Model 3將於三月試產，下半年量產。電池模組線束之主要台系供應商貿聯-KY因而受惠，法人預期其股價大漲，營收兩位數成長。

Tesla成立之初，即配合貿聯-KY電池模組配線出貨。法人分析，身為唯一的供應商，貿聯-KY在生產成本、供貨穩定度和合作信賴度下，處於供應鏈之地位難被取代，也成為特斯拉概念股的一大受益者。

AI自駕車，以及人類與機械結合

2016年2月，谷歌（Google）母公司Alphabet Inc.旗下之波士頓動力（Boston Dynamics）發表第二代人形機器人Atlas，Musk事後提及AI發展的危險性，人類恐成為AI的居家寵物。由於在未來機器人可以完全取代人力，可預見未來將會有大量人口失業。對於AI導入目前技術，Musk認為目前首要議題是無人駕駛，AI或許能在自動駕駛方面提供幫助。

對於人類與AI共存的問題，Musk表示，由於電腦可以在每秒之間傳輸一兆位元的數據，而人類僅可以在行動裝置上每秒傳達10位元之資訊， AI大量繁衍是可以想見的趨勢。若人類想與AI共生，在腦中裝入寬頻介面成為賽博格（Cyborg）或許會有所幫助。

（圖片來源：Heisenberg Media via Flickr CC2.0）

 

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

※推薦評價好的iphone維修中心

引

Once upon a time，COVID-19席捲全球，Chinese Government要求學校複課時必須測量學生體溫
YC中學有幾萬名同學，要找到發燒的同學進行隔離 如果要讓一位老師完成所有測溫任務，那這將是一個大工程，效率會很低（左圖）
所以將學校所有同學分成班級進行，然後匯總，效率會更高（右圖）

介

剛剛引中我們說的：

將學校所有同學分成班級進行，然後匯總

這就是一種分塊
那問題來了，什麼是分塊呢？
其實通過剛剛的情景，你已經領悟到了分塊的本質：

將一個整體劃分為若干個小塊，進行處理

算法中，與之對應的就是：

整體	小塊
學校	班級
數組	若干元素

詳

總

那麼，分塊到底是怎麼一種思想呢？
整塊維護，殘塊查找

例

還是以測量體溫舉例：

現在YC中學要查找體溫在36℃~37.5℃區間內的同學
怎麼做呢？
不可能又去挨個同學去統計、去數吧
那就做一張大表吧，在之前測溫的時候就把34 ~ 35℃、35 ~36℃、36 ~ 37℃、37 ~ 38℃、38 ~ 39℃……的同學分別列出來，數量分別加出來
然後36 ~ 37℃可以就直接在表裡查出人數
那37 ~ 37.5℃怎麼辦呢？
表內並沒有37 ~ 37.5℃的這樣0.5大小的區間啊
那就在37 ~ 38℃這個區間去找唄
方法可以直接暴力遍歷，也可以二分查找等等

剛剛解決的問題就是一個典型的分塊
像34 ~ 35℃、35 ~36℃、36 ~ 37℃、37 ~ 38℃、38 ~ 39℃這種列在表上給出的就是整塊
37 ~ 37.5℃這種表上沒有，包含在一個其他整塊中的但又不足一個整塊的就叫做殘塊

優

不難發現，其實分塊這個思想是一種暴力，一種優化的暴力，但往往也很有效
Such as 線段樹過於臃腫，代碼冗長，大材小用；而直接暴力就會TLE，不能滿足數據大小
這就很適合分塊了
那麼我們具體怎麼做呢？

分

我們先要求得應該分為多少個區塊嘛，然後求得每個區塊應該包含多少個元素
然後在輸入時分塊
要使情況最優，那麼區塊既不能太少也不能太多
太少，整塊的數量會太少，花費大量的時間處理殘塊
太多，區塊的長度會太短，失去整體處理區塊的意義
所以，我們取塊數為根號n
而開平方開不盡的n，我們通常在最後接一個不足整塊元素的假整塊（可以看做整塊）
這樣在最壞情況下
我們要處理接近根號n個整塊，還要對長度為 2倍根號n 的殘塊最後單獨處理

	cin>>n;
	blo=sqrt(n);//sqrt()開平方函數
	for(int i=1;i<=n;i++){
		cin>>a[i];//儲存元素a[i]
		pos[i]=(i-1)/blo+1;//pos[i]為記錄元素a[i]屬於第幾個整塊
		m[pos[i]]=max(a[i],m[pos[i]]);//尋找第pos[i]個整塊的最大值存入m[pos[i]]
	}

統

我們先統計左右殘塊，然後再統計整塊

	cin>>q;
	int l,r;
	while(q--){
		cin>>l>>r;
		l++;
		r++;
		int ans=0;
		for(int i=l;i<=min(r, pos[l]*blo);i++){//統計左殘缺塊 
			ans=max(ans,a[i]);
		} 
		if(pos[l]!=pos[r]){//存在右殘缺塊 
			for(int i=(pos[r]-1)*blo+1;i<=r;i++){//統計右殘缺塊 
				ans=max(ans,a[i]);
			}
		} 
		for( int i=pos[l]+1;i<=pos[r]-1;i++){//統計中間整塊 
			ans=max(ans,m[i]);
		}	
		cout<<ans<<endl;
	}

分塊入門之求最大值

先看一個例題

分塊入門之求最大值
Input
第一行給出一個数字N，接下來N+1行，每行給出一個数字Ai，（1<=i<=N<=1E5)
接來給出一個数字Q(Q<=7000),代表有Q個詢問
每組詢問格式為a,b即詢問從輸入的第a個數到第b個數，其中的最大值是多少
Output
如題所述
Sample Input
10 0 1 2 3 2 3 4 3 2 1 0 5 0 10 2 4 3 7 7 9 8 8
Sample Output
4 3 4 3 2

坑

模板題，然後剛剛已經講過了這個代碼
唯一的坑就在於接下來N+1行都是数字Ai
也就是有n+1個数字Ai
也就是n需要n++

碼

#include <bits/stdc++.h>
using namespace std;
int n;
int a[101000];
int q;
int blo;
int pos[101000];
int m[101000];
//blo為區間大小，pos[i]表示a[i]元素位於第pos[i]塊，m[i]表示區塊最大值
int main(){
	cin>>n;
	n++;
	blo=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pos[i]=(i-1)/blo+1;
		m[pos[i]]=max(a[i],m[pos[i]]);
	}
	cin>>q;
	int l,r;
	while(q--){
		cin>>l>>r;
		l++;
		r++;
		int ans=0;
		for(int i=l;i<=min(r, pos[l]*blo);i++){//統計左殘缺塊 
			ans=max(ans,a[i]);
		} 
		if(pos[l]!=pos[r]){//存在右殘缺塊 
			for(int i=(pos[r]-1)*blo+1;i<=r;i++){//統計右殘缺塊 
				ans=max(ans,a[i]);
			}
		} 
		for( int i=pos[l]+1;i<=pos[r]-1;i++){//統計中間整塊 
			ans=max(ans,m[i]);
		}	
		cout<<ans<<endl;
	}
	return 0;
}

教主的魔法

[Noip模擬題]教主的魔法
Description
教主最近學會了一種神奇的魔法，能夠使人長高
於是他準備演示給XMYZ信息組每個英雄看
於是N個英雄們又一次聚集在了一起
這次他們排成了一列，被編號為1、2、……、N
每個人的身高一開始都是不超過1000的正整數
教主的魔法每次可以把閉區間[L, R]（1≤L≤R≤N）內的英雄的身高全部加上一個整數W
（雖然L=R時並不符合區間的書寫規範，但我們可以認為是單獨增加第L（R）個英雄的身高）
CYZ、光哥和ZJQ等人不信教主的邪
於是他們有時候會問WD閉區間 [L,R] 內有多少英雄身高大於等於C
以驗證教主的魔法是否真的有效
WD巨懶，於是他 把這個回答的任務交給了你
Input
第1行為兩個整數N、Q。Q為問題數與教主的施法數總和
第2行有N個正整數，第i個數代表第i個英雄的身高
第3到第Q+2行每行有一個操作：
（1）若第一個字母為”M”，則緊接着有三個数字L、R、W
表示對閉區間 [L, R]內所有英雄的身高加上W
（2）若第一個字母為”A”，則緊接着有三個数字L、R、C
詢問閉區間 [L, R] 內有多少英雄的身高大於等於C
N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000
Output
對每個”A”詢問輸出一行，僅含一個整數，表示閉區間 [L, R] 內身高大於等於C的英雄數。Sample Input
5 3 1 2 3 4 5 A 1 5 4 M 3 5 1 A 1 5 4
Sample Output
2 3
【輸入輸出樣例說明】
原先5個英雄身高為1、2、3、4、5，此時[1, 5]間有2個英雄的身高大於等於4
教主施法后變為1、2、4、5、6，此時[1, 5]間有3個英雄的身高大於等於4

意

很多元素，進行增加、查找最大值操作

修

多了一個修改操作，不是很難
同理像查找這樣整塊維護，殘塊增加
我們就再增加一個數組，統一記錄每個整塊變化量是多少
記錄每個整塊的變化量，然後最後找最值的時候，單個整塊的最值加上或者減去變化量比較就可以了
殘塊的單個元素就直接加上或者減去變化量，找最值

void update(int x,int y,int v){
    if(pos[x]==pos[y]){
        for(int i=x;i<=y;i++)a[i]=a[i]+v;
    }
    else{
        for(int i=x;i<=pos[x]*block;i++)a[i]=a[i]+v;
        for(int i=(pos[y]-1)*block+1;i<=y;i++)a[i]=a[i]+v;
    }
    reset(pos[x]);reset(pos[y]);
    for(int i=pos[x]+1;i<pos[y];i++)
       add[i]+=v;
}

碼

#include<bits/stdc++.h>
using namespace std;
int n;
int q,m,block;
int a[1010000],b[1010000],pos[1010000],add[1010000];
void reset(int x){
    int l=(x-1)*block+1,r=min(x*block,n);
    for(int i=l;i<=r;i++)
        b[i]=a[i];
    sort(b+l,b+r+1);
}
int find(int x,int v){
    int l=(x-1)*block+1,r=min(x*block,n);
    int last=r;
    while(l<=r){
        int mid=(l+r)>>1;
        if(b[mid]<v)l=mid+1;
        else r=mid-1;
    }
    return last-l+1;
}
void update(int x,int y,int v){
    if(pos[x]==pos[y]){
        for(int i=x;i<=y;i++)a[i]=a[i]+v;
    }
    else{
        for(int i=x;i<=pos[x]*block;i++)a[i]=a[i]+v;
        for(int i=(pos[y]-1)*block+1;i<=y;i++)a[i]=a[i]+v;
    }
    reset(pos[x]);reset(pos[y]);
    for(int i=pos[x]+1;i<pos[y];i++)
       add[i]+=v;
}
int query(int x,int y,int v){
    int sum=0;
    if(pos[x]==pos[y]){
        for(int i=x;i<=y;i++)if(a[i]+add[pos[i]]>=v)sum++;
    }
    else {
        for(int i=x;i<=pos[x]*block;i++)
            if(a[i]+add[pos[i]]>=v)sum++;
        for(int i=(pos[y]-1)*block+1;i<=y;i++)
            if(a[i]+add[pos[i]]>=v)sum++;
    }
    for(int i=pos[x]+1;i<pos[y];i++)
        sum+=find(i,v-add[i]);
    return sum;
}
int main(){
    cin>>n>>q;
    block=int(sqrt(n));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[i]=(i-1)/block+1;
        b[i]=a[i];
    }
    if(n%block)m=n/block+1;
    else m=n/block;
    for(int i=1;i<=m;i++)reset(i);
    for(int i=1;i<=q;i++){
        char ch[5];int x,y,v;
        cin>>ch>>x>>y>>v;
        if(ch[0]=='M'){
        	update(x,y,v);
		}else{
			cout<<query(x,y,v)<<endl;
		}
    }
    return 0;
}

END

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

※推薦評價好的iphone維修中心