【Spring】@Transactional 閑聊

菜瓜:上次的AOP理論知識看完收穫挺多的,雖然有一個自定義註解的demo,但還是覺得差點東西

水稻:我也覺得沒有跟一遍源碼還是差點意思,這次結合@Transactional註解深入源碼看一下

菜瓜:事務註解,這個平時用的挺多的

水稻:是嗎?來看看你的基礎咋樣

  1. 要保證一個方法中多個數據庫操作的原子性,要共用一個數據庫連接,但是coding時我們不用显示傳遞連接對象,這是咋弄的?
  2. 如果一個方法裏面只有查詢操作,是否不用開啟事務?
  3. 如何解決非事務方法調用本地事務方法失效的?
  4. 註解常用的傳播屬性,你知道他們的區別嗎

菜瓜:雖然沒看過源碼,我大膽猜測一下

  1. 隱式傳遞連接對象可以將其封裝到線程中,一般一次請求操作都是在一個線程中完成。使用ThreadLocal將連接和線程綁定
  2. 查詢操作也得看業務場景,如果多次查詢相同的數據要避免不可重複讀問題,可開啟只讀事務 (readOnly = true)
  3. 結合AOP的知識,這裏其實要解決調用事務方法的對象不是代理對象的問題。用代理對象調本地事務方法即可(注入自己)
    • /**
       * @author QuCheng on 2020/6/24.
       */
      @Service
      public class ItemServiceImpl implements ItemService {
      
          @Resource
          private IcbcItemMapper itemMapper;
      
          @Resource
          private ItemService itemService;
      
          @Override
          public void changeNameById(Long itemId) {
              // changeItemById(itemId);
              itemService.changeItemById(itemId);
          }
      
          @Transactional(rollbackFor = RuntimeException.class)
          @Override
          public void changeItemById(Long itemId) {
              itemMapper.updateNameById(itemId, "name4");
              int a = 10 / 0;
              itemMapper.updatePriceById(itemId, 100L);
          }
      }
  4. 傳播屬性這個沒了解過啊,數據庫事務裏面么得這個概念

水稻:可以啊,平時的代碼沒白寫

菜瓜:coding這種事情,easy啦!

水稻:這就飄了?來看這個問題

  • 如果我想在A事務方法中調用B事務方法,B方法如果回滾了,不能影響A事務繼續執行,但是A事務如果執行出問題了,B也要回滾,怎麼弄?

菜瓜:。。。這不就是大事務嵌套小事務嘛。。。我不會

水稻:不扯了,來看源碼吧,這個問題等解釋了傳播屬性你就知道了

  • 上回我們說到,@Transactional是AOP的典型應用,bean被實例化之後要創建代理(參考自定義註解),就少不了切面類Advisor對象。那麼它是誰,它在哪,它在干什麼?
  • 回到夢開始的地方,事務功能開啟的註解@EnableTransactionManagement
    • 沒錯,它肯定會有一個Import註解引入TransactionManagementConfigurationSelector類,它又引入了切面類
    • public class TransactionManagementConfigurationSelector extends AdviceModeImportSelector<EnableTransactionManagement> {
       
         @Override
         protected String[] selectImports(AdviceMode adviceMode) {
            switch (adviceMode) {
               case PROXY:
                  return new String[] {AutoProxyRegistrar.class.getName(),
                        // 看這裏
                        ProxyTransactionManagementConfiguration.class.getName()};
               case ASPECTJ:
                  return new String[] {determineTransactionAspectClass()};
               default:
                  return null;
            }
         }
      。。。
      
      }
      
      
      @Configuration
      public class ProxyTransactionManagementConfiguration extends AbstractTransactionManagementConfiguration {
      
         @Bean(name = TransactionManagementConfigUtils.TRANSACTION_ADVISOR_BEAN_NAME)
         @Role(BeanDefinition.ROLE_INFRASTRUCTURE)
         public BeanFactoryTransactionAttributeSourceAdvisor transactionAdvisor() {
            BeanFactoryTransactionAttributeSourceAdvisor advisor = new BeanFactoryTransactionAttributeSourceAdvisor();
            advisor.setTransactionAttributeSource(transactionAttributeSource());
            advisor.setAdvice(transactionInterceptor());
            if (this.enableTx != null) {
               advisor.setOrder(this.enableTx.<Integer>getNumber("order"));
            }
            return advisor;
         }
      
         @Bean
         @Role(BeanDefinition.ROLE_INFRASTRUCTURE)
         public TransactionAttributeSource transactionAttributeSource() {
            return new AnnotationTransactionAttributeSource();
         }
      
         @Bean
         @Role(BeanDefinition.ROLE_INFRASTRUCTURE)
         public TransactionInterceptor transactionInterceptor() {
      // 增強 TransactionInterceptor interceptor
      = new TransactionInterceptor(); interceptor.setTransactionAttributeSource(transactionAttributeSource()); if (this.txManager != null) { interceptor.setTransactionManager(this.txManager); } return interceptor; } } 
    • 切面類對象設置了事務的掃描器,也set了增強類TransactionInterceptor
    • public class TransactionInterceptor extends TransactionAspectSupport implements MethodInterceptor, Serializable {
      。。。
      @Override
          @Nullable
          public Object invoke(MethodInvocation invocation) throws Throwable {
              // Work out the target class: may be {@code null}.
              // The TransactionAttributeSource should be passed the target class
              // as well as the method, which may be from an interface.
              Class<?> targetClass = (invocation.getThis() != null ? AopUtils.getTargetClass(invocation.getThis()) : null);
      
              // Adapt to TransactionAspectSupport's invokeWithinTransaction...
              return invokeWithinTransaction(invocation.getMethod(), targetClass, invocation::proceed);
          }
      }
      
      public abstract class TransactionAspectSupport implements BeanFactoryAware, InitializingBean {
        
      。。。  
      @Nullable
      protected Object invokeWithinTransaction(Method method, @Nullable Class<?> targetClass,
            final InvocationCallback invocation) throws Throwable {
         。。。
      // ①創建事務,數據庫連接處理也在這 TransactionInfo txInfo
      = createTransactionIfNecessary(tm, txAttr, joinpointIdentification); Object retVal = null; try {
      // 調用目標方法 retVal
      = invocation.proceedWithInvocation(); } catch (Throwable ex) {
      // 異常後事務處理 completeTransactionAfterThrowing(txInfo, ex);
      throw ex; } finally { cleanupTransactionInfo(txInfo); } commitTransactionAfterReturning(txInfo); return retVal; } 。。。 } 

菜瓜:懂,接下來的代碼邏輯就是在增強類TransactionInterceptor的invoke方法里

水稻:對

  • 先看數據庫連接的處理 – 驗證ThreadLocal
  • protected void doBegin(Object transaction, TransactionDefinition definition) {
       。。。
    // 如果連接是新的,就進行綁定
    if (txObject.isNewConnectionHolder()) { TransactionSynchronizationManager.bindResource(this.obtainDataSource(), txObject.getConnectionHolder()); } 。。。 } class TransactionSynchronizationManager public static void bindResource(Object key, Object value) throws IllegalStateException { Object actualKey = TransactionSynchronizationUtils.unwrapResourceIfNecessary(key); Assert.notNull(value, "Value must not be null"); Map<Object, Object> map = resources.get(); // set ThreadLocal Map if none found if (map == null) { map = new HashMap<>(); resources.set(map); } Object oldValue = map.put(actualKey, value); // Transparently suppress a ResourceHolder that was marked as void... if (oldValue instanceof ResourceHolder && ((ResourceHolder) oldValue).isVoid()) { oldValue = null; } if (oldValue != null) { throw new IllegalStateException("Already value [" + oldValue + "] for key [" + actualKey + "] bound to thread [" + Thread.currentThread().getName() + "]"); } if (logger.isTraceEnabled()) { logger.trace("Bound value [" + value + "] for key [" + actualKey + "] to thread [" + Thread.currentThread().getName() + "]"); } }
  • 回過頭來看AB方法調用的回滾問題,直接給出答案(突然發現這個問題要講清楚篇幅會很大,就。。挺突然的。。挺突然der)
    • 在B方法上設置傳播屬性為NESTED即可,然後在A中catch住B的異常
    • 你肯定會問我不加NESTED去catch不行嗎?不行,非NESTED的方法拋出的異常是無法回滾的。
    • 不信你看
    • @Transactional(rollbackFor = RuntimeException.class)
          @Override
          public void changeNameById(Long itemId) {
              itemMapper.updateNameById(itemId, "A");
              try {
                  itemService.changeItemById(itemId);
      //            itemService.changeItemByIdNested(itemId);
              } catch (Exception e) {
                  System.out.println("我想繼續執行,不影響修改A");
              }
              itemMapper.updatePriceById(itemId, 1L);
          }
      
          @Transactional(rollbackFor = RuntimeException.class)
          @Override
          public void changeItemById(Long itemId) {
              itemMapper.updateNameById(itemId, "B+REQUIRED");
              itemMapper.updatePriceById(itemId, 10L);
              int a = 10 / 0;
          }
      
          @Transactional(rollbackFor = RuntimeException.class, propagation = Propagation.NESTED)
          @Override
          public void changeItemByIdNested(Long itemId) {
              itemMapper.updateNameById(itemId, "B+NESTED");
              itemMapper.updatePriceById(itemId, 100L);
              int a = 10 / 0;
          }
      
      
      -- 測試結果
      //①  itemService.changeItemById(itemId);  數據庫所有數據都不會改變
      我想繼續執行,不影響修改A
      org.springframework.transaction.UnexpectedRollbackException: Transaction rolled back because it has been marked as rollback-only
      
      // ② itemService.changeItemByIdNested(itemId); 第一個方法的修改會生效
      我想繼續執行,不影響修改A

菜瓜:這就是傳播屬性NESTED?默認的是REQUIRED,還有一個常用的REQUIRES_NEW呢?

水稻:搞清楚這個其實從數據庫連接入手其實就很清楚

  • REQUIRED修飾的方法和A使用同一個連接,A和B是掛一起的,誰回滾都會影響對方,且B方法的異常會被事務管理器標記為必須回滾
  • NESTED修飾的方法和A使用同一個連接,但是用到了數據庫的savePoint特性,它可以回滾到指定的點,如果是有回滾點的操作,拋出的異常可以被處理
  • REQUIRES_NEW修飾的方法和A使用的就不是一個連接了,回不回滾都不會影響對方,當然,要捕捉異常

菜瓜:傳播屬性了解。回滾的問題還得再看看,篇幅很大是很複雜嗎?

水稻:其實不複雜,就是要跟蹤源碼斷點調試。。。截圖搞來搞去,篇幅就很長,你自己去調的話其實很快

菜瓜:那我下去康康

 

總結

  • 這裏提到Transactional註解其實是為了鞏固AOP的,當然提到了一些注意點。譬如本地調用,譬如ThreadLocal的應用,還譬如傳播屬性
  • 傳播屬性其實用的少,但是聊起來就比較多了,可以聊事務的隔離級別,聊ACID的實現,聊MySQL的鎖

 

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

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

步伐密集 易事特再建江蘇充電樁專案

易事特今日發佈公告稱,與江蘇高淳經濟開發區開發總公司就新能源汽車充電樁設備研發製造、IDC整體機房研發製造、智慧微電網等項目投資達成一致意見並簽署協議書。易事特承諾新辦企業固定資產投資總額為6億元人民幣(約新臺幣30億),畝均稅收不低於20萬元(約新臺幣101萬),首期建築面積不低於30000平方米。高淳經濟開發區將供地約120畝,使用年限為50年。   易事特佈局充電樁可謂步伐密集。今年8月13日,易事特與馬鞍山經濟技術開發區管理委員會簽訂了《投資框架協議書》,擬在對方區域內投資建設資料中心、分散式發電設備與系統集成和新能源汽車充電站(樁)項目。

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

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

Jmeter系列(34)- 詳解 Counter 計數器

如果你想從頭學習Jmeter,可以看看這個系列的文章哦

https://www.cnblogs.com/poloyy/category/1746599.html

 

簡單介紹

  • 計數器的作用:循環遞增生成数字
  • 計數器使用 long 來存儲值,因此取值範圍是 -2 ^ 63 2 ^ 63-1 
  • 可以在線程組任意地方添加計數器

 

計數器

 

計數器界面介紹

 

字段介紹

字段 含義
Starting value 初始值,long 整型,默認 0
Increment 每次迭代的遞增值,默認 0,表示不增加
Maximum value 最大值,包含此值
Number format 数字可選格式
Exported Variable Name 引用名稱
Track counter independently for rach user 每個用戶都有一個獨立的計數器
Reset counter on each Thread Group Iteration 每次線程組迭代時計數器將重置為初始值

 

最基礎的栗子

只有計數器的情況下的栗子

線程組結構樹

 

線程組屬性

共有 15 個線程,模擬 15 個用戶

 

計數器

計數器最多循環計數 10 次

 

運行結果

可以看到,因為有 15 個用戶,但計數器最多循環計數 10 次,所以第一輪循環結束後會重頭開始

 

計數器 + 循環控制器的栗子

線程組結構樹

 

線程組屬性

共有 5 個線程,模擬 5 個用戶

 

循環控制器

每個線程運行 3 次

 

計數器

計數器最多循環計數 30 次

 

未勾選【與每用戶獨立的跟蹤計數器】的運行結果

可以看到

  • 因為有 5 個線程,每個線程循環 3 次,一共 15 個請求,所以計數器是循環了 15 次
  • 此時計數器是對所有線程共享的,屬於線程組全局計數器,所以計數器是累計循環了 15 次

 

勾選【與每用戶獨立的跟蹤計數器】的運行結果

可以看到

  • 每個線程運行時,計數器都是從初始值算起的
  • 此時計數器是每個線程獨享的,不再是公共計數器,所以每次有新的線程運行時,都是新的計數器開始循環計數

 

計數器的一些注意事項

使用計數器生成的變量,值的類型為 string,所以有比較之類的操作時,需要帶 “” 操作

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

原子力寄生委員會! 福島輻射污染水問題重重

文:宋瑞文(媽媽監督核電廠聯盟特約撰述)

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

電動車免牌照稅 可望延長至 2018 年

為鼓勵購買低汙染的環保車輛,電動汽車將再延長牌照稅免稅期 3 年。包括電動小客車、巴士與貨車,免徵牌照稅優惠將可持續至 2018 年 1 月 5 日為止。   為基於扶植國內電動車研發製造的需要,立法院財政委員會 12 日將審查由行政院提出的用牌照稅法修正草案,授權給地方政府對以電能為動力的電動汽車,免徵牌照稅優惠期間,可以再延長 3 年。經濟日報指出,這項減稅法案可望趕在立法院本會期結束前完成修法程序,以便接續提供減免。   財政部指出,免徵電動車使用照稅優惠措施自 2012 年 1 月 5 日施行至今,國庫釋出的免稅利益將近新台幣 1,000 萬元,平均每年約為 300 萬元。過去 3 年,申請免稅的電動車由 319 輛成長到 574 輛,減稅金額也從約 200 萬元倍增至近 400 萬元。財政部認為,電動車申請免稅案件逐年增加,代表電動車的使用與購買意願也在上升。  

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

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

4. union-find算法

  算法的主題思想:

  1.優秀的算法因為能夠解決實際問題而變得更為重要;

  2.高效算法的代碼也可以很簡單;

  3.理解某個實現的性能特點是一個挑戰;

  4.在解決同一個問題的多種算法之間進行選擇時,科學方法是一種重要的工具;

  5.迭代式改進能夠讓算法的效率越來越高效;

 

   1. 動態連通性

  動態連接:輸入是一對整數對的序列,其中每個整數代表某種類型的對象(或觸點),我們將整數對p q 解釋為意味着p連接到q。我們假設“連接到”是等價關係:

  對稱性:如果p連接到q,則q 連接到p。

  傳遞性:如果p連接到q且q 連接到r,則p連接到r。
  自反性:p與p連接。
  等價關係將對象劃分為多個等價類 或連接的組件。等價類稱為連通分量或分量。
  我們的目標是編寫一個程序,以從序列中過濾掉多餘的對:當程序從輸入中讀取整數對 p q時,只有在該對點不等價的情況下,才應將對寫入到輸出中,並且將p連接到q。如果等價,則程序應忽略整數對pq 並繼續讀取下對。

  

 

  動態連通性問題的應用:

    1.網絡

    2.變量名等價性

    3.數學集合

      在更高的抽象層次上,可以將輸入的所有整數看做屬於不同的數學集合。

   2. 定義問題

  設計算法的第一個任務就是精確地定義問題。

  算法解決的問題越大,它完成任務所需的時間和空間可能越多。我們不可能預先知道這其間的量化關係,通常只會在發現解決問題很困難,或是代價巨大,或是發現算法所提供的信息比原問題所需要的更加有用時修改問題。例如,連通性問題只要求我們的程序能夠判斷出給定的整數對是否相連,但並沒有要求給出兩者之間的通路上的所有連接。這樣的要求更難,並會得出另一組不同的算法。

  為了定義和說明問題,先設計一份API  來封裝基本操作: 初始化,連接兩個觸點,查找某個觸點的分量 ,判斷兩個觸點是否屬於同一分量,分量的數量:

    /// <summary>
    /// 動態連通API
    /// </summary>
    public interface IUnionFind
    {
        /// <summary>
        /// 連接
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        void Union(int p, int q);

        /// <summary>
        /// 查找觸點 p 的分量標識符
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        int Find(int p);

        /// <summary>
        /// 判斷兩個觸點是否處於同一分量
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        bool Connected(int p, int q);

        /// <summary>
        /// 連通分量的數量
        /// </summary>
        /// <returns></returns>
        int Count();
    }

  為解決動態連通性問題設計算法的任務轉化為實現這份API:

    1. 定義一種數據結構表示已知的連接;

    2. 基於此數據結構高效的實現API的方法;

  數據結構的性質會直接影響算法的效率。這裏,觸點為索引,觸點和連接分量都是用 int 值表示,將會使用分量中某個觸點的值作為分量的標識符。所以,一開始,每個觸點都是只含有自己的分量,分量標識符為觸點的值。由此,可以初步實現一部分方法:

 

    public class FirstUnionFind:IUnionFind
    {
        private int[] id;//* 分量id 以觸點作為索引
        private int count;//分量數量

        public FirstUnionFind(int n)
        {
            count = n;
            id = new int[n];
            for (var i = 0; i < n; i++)
            {
                id[i] = i; // 第一個 i 作為觸點,第二個 i 作為觸點的值
            }
        }

        public int Count()
        {
            return count;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        public int Find(int p)
        {
            
        }

        public void Union(int p, int q)
        {
            
        }
    }

 

  Union-find 的成本模型 是數組的訪問次數(無論讀寫)。

   3. quick-find算法實現

  quick-find 算法是保證當且僅當 id[p] 等於 id[q] 時,p 和 q 是連通的。也就是說,在同一個連通分量中的所有觸點在 id[ ] 中的值全部相等。

  所以 Find 方法只需返回 id[q],Union 方法需要先判斷 Find(p)  是否等於 Find(q) ,若相等直接返回;若不相等,需要將 q 所在的連通分量中所有觸點的 id [ ] 值全部更新為 id[p]。

    public class QuickFindUF: IUnionFind
    {
        private int[] id;//* 分量id 以觸點作為索引
        private int count;//分量數量

        public QuickFindUF(int n)
        {
            count = n;
            id = new int[n];
            for (var i = 0; i < n; i++)
            {
                id[i] = i; // 第一個 i 作為觸點,第二個 i 作為觸點的值
            }
        }

        public int Count()
        {
            return count;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        public int Find(int p)
        {
            return id[p];
        }

        public void Union(int p, int q)
        {
            var pID = Find(p);
            var qID = Find(q);

            if (pID == qID)
                return;

            for (var i = 0; i < id.Length; i++)
            {
                if (id[i] == qID)
                    id[i] = pID;
            }
            count--; //連通分量減少
        }

        public void Show()
        {
            for(var i = 0;i<id.Length;i++)
                Console.WriteLine("索引:"+i+",值:"+ id[i] );
            Console.WriteLine("連通分量數量:"+count);
        }
    }

  

  算法分析

  Find() 方法只需訪問一次數組,所以速度很快。但是對於處理大型問題,每對輸入 Union() 方法都需要掃描整個數組。

  每一次歸併兩個分量的 Union() 方法訪問數組的次數在 N+3 到 2N+1 之間。由代碼可知,兩次 Find 操作訪問兩次數組,掃描數組會訪問N次,改變其中一個分量中所有觸點的值需要訪問 1 到 N – 1 次(最好情況是該分量中只有一個觸點,最壞情況是該分量中有 N – 1個觸點),2+N+N-1。

  如果使用quick-find 算法來解決動態連通性問題並且最後只得到一個連通分量,至少需要調用 N-1 次Union() 方法,那麼至少需要 (N+3)(N-1) ~ N^2 次訪問數組,是平方級別的。

 

   4. quick-union算法實現

  quick-union 算法重點提高 union 方法的速度,它也是基於相同的數據結構 — 已觸點為索引的 id[ ] 數組,但是 id[ ] 的值是同一分量中另一觸點的索引(名稱),也可能是自己(根觸點)——這種聯繫成為鏈接。

  在實現 Find() 方法時,從給定觸點,鏈接到另一個觸點,知道到達根觸點,即鏈接指向自己。同時修改 Union() 方法,分別找到 p q 的根觸點,將其中一個根觸點鏈接到根觸點。

public class QuickUnionUF : IUnionFind
    {
        private int[] id;
        private int count;

        public QuickUnionUF(int n)
        {
            count = n;
            id = new int[n];
            for (var i = 0; i < n; i++)
            {
                id[i] = i; // 第一個 i 作為觸點,第二個 i 作為觸點的值
            }
        }

        public int Count()
        {
            return count;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        public int Find(int p)
        {
            while (p != id[p])
                p = id[p];
            return p;
        }

        public void Union(int p, int q)
        {
            var pRoot = Find(p);
            var qRoot = Find(q);

            if (pRoot == qRoot)
                return;

            id[pRoot] =qRoot;
count
--; //連通分量減少 } public void Show() { for (var i = 0; i < id.Length; i++) Console.WriteLine("索引:" + i + ",值:" + id[i]); Console.WriteLine("連通分量數量:" + count); } }

  

  森林表示

  id[ ] 數組用父鏈接的形式表示一片森林,用節點表示觸點。無論從任何觸點所對應的節點隨着鏈接查找,最後都將到達含有該節點的根節點。初始化數組之後,每個節點的鏈接都指向自己。

 

  算法分析

  定義:一棵樹的大小是它的節點的數量。樹中一個節點的深度是它到根節點的路徑上鏈接數。樹的高度是它的所有節點中的最大深度。

  quick-union 算法比 quick-find 算法更快,因為它對每對輸入不需要遍歷整個數組。

  分析quick-union 算法的成本比 quick-find 算法的成本要困難,因為quick-union 算法依賴於輸入的特點。在最好的情況下,find() 方法只需訪問一次數組就可以得到一個觸點的分量表示;在最壞情況下,需要 2i+1 次數組訪問(i 時觸點的深度)。由此得出,該算法解決動態連通性問題,在最佳情況下的運行時間是線性級別,最壞情況下的輸入是平方級別。解決了 quick-find 算法中 union() 方法總是線性級別,解決動態連通性問題總是平方級別。

  quick-union 算法中 find() 方法訪問數組的次數為 1(到達根節點只需訪問一次) 加上 給定觸點所對應節點的深度的兩倍(while 循環,一次讀,一次寫)。union() 訪問兩次 find() ,如果兩個觸點不在同一分量還需加一次寫數組。

   假設輸入的整數對是有序的 0-1, 0-2,0-3 等,N-1 對之後N個觸點將全部處於相同的集合之中,且得到的樹的高度為 N-1。由上可知,對於整數對 0-i , find() 訪問數組的次數為 2i + 1,因此,處理 N 對整數對所需的所有訪問數組的總次數為 3+5+7+ ……+(2N+1) ~ n^2

  

  

  5.加權 quick-union 算法實現

  簡單改動就可以避免 quick-union算法 出現最壞情況。quick-union算法 union 方法是隨意將一棵樹連接到另一棵樹,改為總是將小樹連接到大樹,這需要記錄每一棵樹的大小,稱為加權quick-union算法。

  代碼:

    public class WeightedQuickUnionUF: IUnionFind
    {
        int[] sz;//以觸點為索引的 各個根節點對應的分量樹大小
        private int[] id;
        private int count;

        public WeightedQuickUnionUF(int n)
        {
            count = n;
            id = new int[n];
            sz = new int[n];
            for (var i = 0; i < n; i++)
            {
                id[i] = i; // 第一個 i 作為觸點,第二個 i 作為觸點的值
                sz[i] = 1;
            }
        }

        public int Count()
        {
            return count;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        public int Find(int p)
        {
            while (p != id[p])
                p = id[p];
            return p;
        }

        public void Union(int p, int q)
        {
            var pRoot = Find(p);
            var qRoot = Find(q);

            if (pRoot == qRoot)
                return;

            if (sz[pRoot] < sz[qRoot])
            {
                id[pRoot] = qRoot;
            }
            else
            {
                id[qRoot] = pRoot;
            }
                
            count--; //連通分量減少
        }

        public void Show()
        {
            for (var i = 0; i < id.Length; i++)
                Console.WriteLine("索引:" + i + ",值:" + id[i]);
            Console.WriteLine("連通分量數量:" + count);
        }
    }

 

  算法分析

  加權 quicj-union 算法最壞的情況:

  

  這種情況,將要被歸併的樹的大小總是相等的(且總是 2 的 冥),都含有 2^n 個節點,高度都正好是 n 。當歸併兩個含有 2^n 個節點的樹時,得到的樹含有 2 ^ n+1 個節點,高度增加到 n+1 。

  節點大小: 1  2  4  8  2^k = N

  高       度: 0  1  2  3  k

  k = logN

  所以加權 quick-union 算法可以保證對數級別的性能。

  對於 N 個觸點,加權 quick-union 算法構造的森林中的任意節點的深度最多為logN。

  對於加權 quick-union 算法 和 N 個觸點,在最壞情況下 find,connected 和 union 方法的成本的增長量級為 logN。

  對於動態連通性問題,加權 quick-union 算法 是三種算法中唯一可以用於解決大型問題的算法。加權 quick-union 算法 處理 N 個觸點和 M 條連接時最多訪問數組 c M logN 次,其中 c 為常數。

  

  三個算法處理一百萬個觸點運行時間對比:

  

  

  三個算法性能特點:

 

  6.最優算法 – 路徑壓縮

  在檢查節點的同時將它們直接連接到根節點。

  實現:為 find 方法添加一個循環,將在路徑上的所有節點都直接鏈接到根節點。完全扁平化的樹。

 

  

  研究各種基礎問題的基本步驟:

  1. 完整而詳細地定義問題,找出解決問題所必須的基本抽象操作並定義一份API。

  2. 簡潔地實現一種初級算法,給出一個精心組織的開發用例並使用實際數據作為輸入。

  3. 當實現所能解決的問題的最大規模達不到期望時決定改進還是放棄。

  4. 逐步改進實現,通過經驗性分析和數學分析驗證改進后的效果。

  5. 用更高層次的抽象表示數據結構或算法來設計更高級的改進版本。

  6. 如果可能盡量為最壞情況下的性能提供保證,但在處理普通數據時也要有良好的性能。

  7.在適當的時候將更細緻的深入研究留給有經驗的研究者並解決下一個問題。

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

新能源汽車入北京 改為備案制

在中國的全球新能源汽車大會上,北京市科委新能源與新材料處處長許心超透露,北京市新能源汽車準入方式有所調整,由先前的新能源汽車目錄方式改為備案方式,車型只要備案即可在北京銷售、上牌。   先前規定,按照《北京市示範應用新能源小客車生企業及品目錄》,北京市共有 7 款新能源汽車可在備案之後直接銷售、上牌。而這次許心超表示,按照中央的要求,準入方式也在改變,主要採取備案制,只要備案了就可銷售,政府則加強事後監管。
這意味著所有中國純電動汽車都可以進京銷售、上牌,享受財政補貼,而不再像以前必須要先進入嚴格的北京市新能源汽車目錄。   另一方面,為了讓純電動汽車的使用者迅速找到充電樁,相關部門也在進行改進,一是和百度合作,標注所有充電樁的電子地圖將很快上線;二是印製北京充電樁地圖;三是辦充電體驗周活動,在 2 月 2 日至 6 日,將分 2 次聯合所有北京的汽車企業,做充電實際體驗。

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

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

「寂靜的春天」預言實現了 研究發現新菸鹼類影響水生物和魚群

環境資訊中心綜合外電;姜唯 編譯;林大利 審校

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

挖角鋰電池廠 A123 傳蘋果電動車將於 2020 年量產

過去幾個月來,蘋果打算進軍終極行動裝置──汽車的傳言甚囂塵上。最新消息更顯示,蘋果正在加緊鞭策研發團隊,希望能在 2020 年產出旗下第一輛電動車。無獨有偶,數小時前才剛洩漏的法院文件顯示,美國汽車鋰離子電池與電池系統廠商 A123 Systems Inc. 控訴蘋果挖角多名重要的工程師,或許蘋果開發電動車是真有其事。   彭博社 20 日引述未具名消息人士報導,蘋果最快 2020 年就會開始量產電動車。一般來說,有經驗的汽車業者想要研發一款全新汽車、通常得花上 5 至 7 年的時間,假如要從零開始、時間更得費上 10 年之久。蘋果設定了如此緊迫的量產時程,凸顯了該公司對汽車領域的強大企圖心。   相較之下,特斯拉(Tesla Motors Inc.)、通用汽車(General Motors Co.)這兩家汽車大廠,則都預定要在 2017 年發表一輛單次充電後可行駛超過 200 英里、售價低於 4 萬美元的電動車。   蘋果的汽車團隊過去幾個月加緊聘人、目前已有 200 人之譜,而最新延攬的員工大多是電池、機器人專才。不過,根據消息人士的說法,倘若汽車的進展不如預期,蘋果仍可能推延開發案、或甚至直接抽手退出。

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

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

C# 9.0 終於來了, Top-level programs 和 Partial Methods 兩大新特性探究

一:背景

1. 講故事

.NET 5 終於在 6月25日 發布了第六個預覽版,隨之而來的是更多的新特性加入到了 C# 9 Preview 中,這個系列也可以繼續往下寫了,廢話不多說,今天來看一下 Top-level programsExtending Partial Methods 兩大新特性。

2. 安裝必備

下載最新的 .net 5 preview 6

下載最新的 Visual Studio 2019 version 16.7 Preview 3.1

二:新特性研究

1. Top-level programs

如果大家玩過 python,應該知道在 xxx.py 中寫一句 print,這程序就能跑起來了,簡單高效又粗暴,很開心的是這特性被帶到了C# 9.0 中。

  • 修改前

using System;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
        }
    }

  • 修改后

System.Console.WriteLine("Hello World!");

這就有意思了,Main入口函數去哪了? 沒它的話,JIT還怎麼編譯代碼呢? 想知道答案的話用 ILSpy 反編譯看一下就好啦!


.class private auto ansi abstract sealed beforefieldinit $Program
	extends [System.Runtime]System.Object
{
	.custom instance void [System.Runtime]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = (
		01 00 00 00
	)
	// Methods
	.method private hidebysig static 
		void $Main (
			string[] args
		) cil managed 
	{
		// Method begins at RVA 0x2050
		// Code size 18 (0x12)
		.maxstack 8
		.entrypoint

		IL_0000: ldstr "Hello World!"
		IL_0005: call void [System.Console]System.Console::WriteLine(string)
		IL_000a: nop
		IL_000b: call string [System.Console]System.Console::ReadLine()
		IL_0010: pop
		IL_0011: ret
	} // end of method $Program::$Main

} // end of class $Program


從 IL 上看,類變成了 $Program, 入口方法變成了 $Main, 這就好玩了,在我們的印象中入口函數必須是 Main,否則編譯器會給你一個大大的錯誤,你加了一個 $ 符號,那CLR還能認識嗎? 能不能認識我們用 windbg 看一些託管和非託管堆棧,看看有什麼新發現。


0:010> ~0s
ntdll!NtReadFile+0x14:
00007ffe`f8f8aa64 c3              ret
0:000> !dumpstack
OS Thread Id: 0x7278 (0)
Current frame: ntdll!NtReadFile + 0x14
Child-SP         RetAddr          Caller, Callee
0000008551F7E810 00007ffed1e841dc (MethodDesc 00007ffe4020d500 + 0x1c System.Console.ReadLine()), calling 00007ffe400ab090
0000008551F7E840 00007ffe4014244a (MethodDesc 00007ffe401e58f0 + 0x3a $Program.$Main(System.String[])), calling 00007ffe40240f58
0000008551F7E880 00007ffe9fcc8b43 coreclr!CallDescrWorkerInternal + 0x83 [F:\workspace\_work\1\s\src\coreclr\src\vm\amd64\CallDescrWorkerAMD64.asm:101]
0000008551F7E8C0 00007ffe9fbd1e03 coreclr!MethodDescCallSite::CallTargetWorker + 0x263 [F:\workspace\_work\1\s\src\coreclr\src\vm\callhelpers.cpp:554], calling coreclr!CallDescrWorkerWithHandler [F:\workspace\_work\1\s\src\coreclr\src\vm\callhelpers.cpp:56]
0000008551F7E950 00007ffe9fb8c4e5 coreclr!MethodDesc::IsVoid + 0x21 [F:\workspace\_work\1\s\src\coreclr\src\vm\method.cpp:1098], calling coreclr!MetaSig::IsReturnTypeVoid [F:\workspace\_work\1\s\src\coreclr\src\vm\siginfo.cpp:5189]
0000008551F7EA00 00007ffe9fb8c4bf coreclr!RunMainInternal + 0x11f [F:\workspace\_work\1\s\src\coreclr\src\vm\assembly.cpp:1488], calling coreclr!MethodDescCallSite::CallTargetWorker [F:\workspace\_work\1\s\src\coreclr\src\vm\callhelpers.cpp:266]
0000008551F7EB30 00007ffe9fb8c30a coreclr!RunMain + 0xd2 [F:\workspace\_work\1\s\src\coreclr\src\vm\assembly.cpp:1559], calling coreclr!RunMainInternal [F:\workspace\_work\1\s\src\coreclr\src\vm\assembly.cpp:1459]

從上面堆棧的流程圖看: coreclr!RunMain -> coreclr!MethodDesc -> coreclr!CallDescrWorkerInternal -> $Program.$Main, 確實被調用了,不過有一個重大發現,在 $Program.$Main 調用之前底層的 CLR 讀取了 方法描述符,這就是一個重大突破點,方法描述符在哪裡呢? 可以用 ildasm 去看一下元數據列表。

可以看到,入口函數那裡打上了一個 ENTRYPOINT 標記,這就說明入口函數名其實是可以隨便更改的,只要被 ENTRYPOINT打上標記即可,CoreCLR就能認的出來~~~

2. Partial Methods

我們知道 部分方法 是一個很好的樁函數,而且在 C# 3.0 中就已經實現了,那時候給我們增加了很多限制,如下圖:

翻譯過來就是:

  • 部分方法的簽名必須一致

  • 方法必須返回void

  • 不允許使用訪問修飾符,而且還是隱式私有的。

在 C# 9.0 中放開了對 方法簽名 的所有限制,正如 issue 總結:

這是一個非常好的消息,現在你的部分方法上可以加上各種類型的返回值啦,這裏我舉一個例子:


    class Program
    {
        static void Main(string[] args)
        {
            var person = new Person();

            Console.WriteLine(person.Run("jack"));
        }
    }

    public partial class Person
    {
        public partial string Run(string name);
    }

    public partial class Person
    {
        public partial string Run(string name) => $"{name}:開溜了~";
    }

然後我們用 ILSpy 簡單看看底層怎麼玩的,如下圖可以看到其實就是一個簡單的合成,對吧。

現在我有想法了,如果我不給 Run 方法實現會怎麼樣? 把下面的 partial 類註釋掉看一下。

從報錯信息看,可訪問的修飾符必須要有方法實現,還以為直接編譯的時候抹掉呢。 這就起不到樁函數的作用:-D,不過這個特性還是給了我們更多的可能用的到的應用場景吧。

三:總結

本篇兩個特性還是非常實用的,Top-level programs 讓我們可以寫更少的代碼,甚至拿起 記事本 都可以快捷的編寫類似一次性使用的測試代碼, Partial Methods 特性留給大家補充吧,我基本上算是沒用過 (┬_┬)。

如您有更多問題與我互動,掃描下方進來吧~

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準