一個操作讓數組處理速度快了5倍,到底是為什麼

来源:https://www.cnblogs.com/hanbing81868164/p/18092404
-Advertisement-
Play Games

概述:通過對數組進行排序,代碼更好地利用了緩存,從而提高了程式的性能。這種現象通常被稱為"緩存友好"(cache-friendly)或"空間局部性"(spatial locality) 今天做一個數組數據計算時,發現一個效率問題,給大家分享一下 一個數組排序和不排序時同樣的邏輯處理速度是不一樣的。排 ...


 

概述:通過對數組進行排序,代碼更好地利用了緩存,從而提高了程式的性能。這種現象通常被稱為"緩存友好"(cache-friendly)或"空間局部性"(spatial locality)

今天做一個數組數據計算時,發現一個效率問題,給大家分享一下 一個數組排序和不排序時同樣的邏輯處理速度是不一樣的。排序後速度快了近5倍,上圖:

 

  1. 再來說明原因:

這段代碼之所以在排序後運行更快,是因為它利用了現代電腦體繫結構中的一個優化:CPU緩存。

在主迴圈中,對data數組的訪問是順序的,即按照數組元素的順序依次訪問。在沒有排序的情況下,由於數組的記憶體佈局是隨機的,這可能導致對記憶體的隨機訪問,而這種隨機訪問可能導致較多的緩存缺失(cache misses)。

而在經過排序之後,數組的元素被重新排列,使得相鄰元素的值更加接近。這就意味著在主迴圈中,對數組的訪問會更加連續,這有助於提高緩存的命中率(cache hit rate)。高緩存命中率意味著CPU可以更快地獲取數據,而不必等待緩慢的主記憶體。這對於迴圈中的迭代非常重要,因為它會不斷地訪問數組的不同部分。

通過對數組進行排序,代碼更好地利用了緩存,從而提高了程式的性能。這種現象通常被稱為"緩存友好"(cache-friendly)或"空間局部性"(spatial locality)。

  1. 然後來看看實際測試代碼,不排序測試:
        static void Main()
        {
            double elapsedTime = Test1();
            double elapsedTime2 = Test2();

            Console.WriteLine($"排序前後:Test1/Test2={(double)(elapsedTime / elapsedTime2)}");
            Console.ReadKey();
        }

        /// <summary>
        /// 不排序測試
        /// </summary>
        static double Test1()
        {
            // 生成數據
            const int arraySize = 32768;
            int[] data = new int[arraySize];
            Random rand = new Random();

            for (int c = 0; c < arraySize; ++c)
                data[c] = rand.Next(256);  // 生成0-255的隨機數

            // 測試
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();

            long sum = 0;
            for (int i = 0; i < 100000; ++i)
            {
                for (int c = 0; c < arraySize; ++c)
                {   // 主迴圈
                    if (data[c] >= 128)
                        sum += data[c];  // 如果數據大於等於128,則加到總和中
                }
            }

            stopwatch.Stop();
            double elapsedTime = stopwatch.ElapsedMilliseconds;  // 計算所花費的時間

            Console.WriteLine($"不排序效果:用時{elapsedTime}毫秒");  // 輸出所花費的時間
            Console.WriteLine("sum = " + sum);  // 輸出總和
            Console.WriteLine();
            return elapsedTime;
        }
  1. 排序後的測試代碼:
        /// <summary>
        /// 排序測試
        /// </summary>
        /// <returns></returns>
        static double Test2()
        {
            // 生成數據
            const int arraySize = 32768;
            int[] data = new int[arraySize];
            Random rand = new Random();

            for (int c = 0; c < arraySize; ++c)
                data[c] = rand.Next(256);  // 生成0-255的隨機數


            double elapsedTime = 0;
            // 測試
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();

            // 對數據進行排序,這樣下一個迴圈會運行得更快
            Array.Sort(data);
            stopwatch.Stop();
            elapsedTime = stopwatch.ElapsedMilliseconds;  // 計算所花費的時間
            stopwatch.Restart();

            long sum = 0;
            for (int i = 0; i < 100000; ++i)
            {
                for (int c = 0; c < arraySize; ++c)
                {   // 主迴圈
                    if (data[c] >= 128)
                        sum += data[c];  // 如果數據大於等於128,則加到總和中
                }
            }

            stopwatch.Stop();
            double elapsedTime2 = stopwatch.ElapsedMilliseconds;  // 計算所花費的時間

            double elapsedTime3 = (elapsedTime + elapsedTime2);

            Console.WriteLine($"排序後效果:排序用時{elapsedTime}毫秒,計算用時:{elapsedTime2}毫秒,合計用時:{(elapsedTime3)}毫秒");  // 輸出所花費的時間
            Console.WriteLine("sum = " + sum);  // 輸出總和
            Console.WriteLine();

            return elapsedTime3;
        }

大家在Java、C++、Python是不是也遇到過類似的問題。

源代碼獲取:https://pan.baidu.com/s/1vm6faDdFFGFEmvpLMPATcQ?pwd=6666 

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 一、前言 隨著網路的發展,企業對於信息系統數據的保密工作愈發重視,不同身份、角色對於數據的訪問許可權都應該大相徑庭。 列如 1、不同登錄人員對一個數據列表的可見度是不一樣的,如數據列、數據行、數據按鈕等都可能不太一樣。 2、表單的靈活設計及呈現。 3、流程的靈活設計及呈現。 4、介面的調用信息者及性能 ...
  • 概述:WPF支持綁定到對象的屬性而不是欄位,主要因為屬性提供了更多控制和擴展性。屬性包含get和set方法,支持數據驗證和通知屬性更改,而欄位通常被認為是內部實現。使用屬性使WPF能夠更靈活、可控地與數據交互,提高代碼的可讀性和可維護性。 WPF(Windows Presentation Found ...
  • 概述:上述C#示例演示瞭如何在同步方法中調用非同步方法。通過使用`async`和`await`關鍵字,實現了同步方法對非同步方法的調用。建議使用`await`而不是`Result`來避免潛在的死鎖問題。這種模式在處理非同步任務時能夠提高代碼的可讀性和性能。 在C#中,從同步方法調用非同步方法的過程涉及到使用 ...
  • 一:背景 1. 講故事 前些天有一位朋友在公眾號上找到我,說他們的WinForm程式部署在20多台機器上,只有兩台機器上的程式會出現崩潰的情況,自己找了好久也沒分析出來,讓我幫忙看下怎麼回事,就喜歡這些有點調試基礎的,dump也不需要我指導怎麼去抓,接下來我們就上windbg開始分析吧。 二:Win ...
  • 構建類型是動態代碼生成過程中的關鍵一環,通過靈活運用 TypeBuilder 和相關工具,我們可以實現各種複雜類型的動態生成,為程式的靈活性和可擴展性提供有力支持。總的來說,本章節通過演示如何使用 Emit 來動態創建類型,包括定義欄位、方法、屬性和事件等, 幫助讀者理解如何在運行時生成和操作類型信... ...
  • 前言 本文的主題是 Visual Studio 調試 NuGet 包,以及符號包的概念,如何去發佈一個 NuGet 包,讓我們的 NuGet 包支持 SouceLink,這些都是我們開發中比較容易忽視的內容,但是熟悉了以後可以讓我們在調試中得心應手,也是開源項目開發的基礎篇。 demo 源代碼在文末 ...
  • 在Orleans 7中,Grain放置是指確定將Grain對象放置在Orleans集群中的哪些物理節點上的過程。 Grain是Orleans中的基本單位,代表應用程式中的邏輯單元或實體。Grain放置策略是一種機制,用於根據不同的因素,將Grain對象放置在合適的節點上,以實現負載均衡、最小化網路延 ...
  • 在之前的WPF示例中,都會用到一個MVVM框,也是一個比較常的MVVM框架,就是MVVM工具包【CommunityToolkit.Mvvm】,今天專門以一個簡單的小例子,簡述一下MVVM工具包的常見用法,僅供學習分享使用,如有不足之處,還請指正。 ...
一周排行
    -Advertisement-
    Play Games
  • PasteSpider是什麼? 一款使用.net編寫的開源的Linux容器部署助手,支持一鍵發佈,平滑升級,自動伸縮, Key-Value配置,項目網關,環境隔離,運行報表,差量升級,私有倉庫,集群部署,版本管理等! 30分鐘上手,讓開發也可以很容易的學會在linux上部署你得項目! [從需求角度介 ...
  • SQLSugar是什麼 **1. 輕量級ORM框架,專為.NET CORE開發人員設計,它提供了簡單、高效的方式來處理資料庫操作,使開發人員能夠更輕鬆地與資料庫進行交互 2. 簡化資料庫操作和數據訪問,允許開發人員在C#代碼中直接操作資料庫,而不需要編寫複雜的SQL語句 3. 支持多種資料庫,包括但 ...
  • 在C#中,經常會有一些耗時較長的CPU密集型運算,因為如果直接在UI線程執行這樣的運算就會出現UI不響應的問題。解決這類問題的主要途徑是使用多線程,啟動一個後臺線程,把運算操作放在這個後臺線程中完成。但是原生介面的線程操作有一些難度,如果要更進一步的去完成線程間的通訊就會難上加難。 因此,.NET類 ...
  • 一:背景 1. 講故事 前些天有位朋友在微信上丟了一個崩潰的dump給我,讓我幫忙看下為什麼出現了崩潰,在 Windows 的事件查看器上顯示的是經典的 訪問違例 ,即 c0000005 錯誤碼,不管怎麼說有dump就可以上windbg開幹了。 二:WinDbg 分析 1. 程式為誰崩潰了 在 Wi ...
  • CSharpe中的IO+NPOI+序列化 文件文件夾操作 學習一下常見的文件、文件夾的操作。 什麼是IO流? I:就是input O:就是output,故稱:輸入輸出流 將數據讀入記憶體或者記憶體輸出的過程。 常見的IO流操作,一般說的是[記憶體]與[磁碟]之間的輸入輸出。 作用 持久化數據,保證數據不再 ...
  • C#.NET與JAVA互通之MD5哈希V2024 配套視頻: 要點: 1.計算MD5時,SDK自帶的計算哈希(ComputeHash)方法,輸入輸出參數都是byte數組。就涉及到字元串轉byte數組轉換時,編碼選擇的問題。 2.輸入參數,字元串轉byte數組時,編碼雙方要統一,一般為:UTF-8。 ...
  • CodeWF.EventBus,一款靈活的事件匯流排庫,實現模塊間解耦通信。支持多種.NET項目類型,如WPF、WinForms、ASP.NET Core等。採用簡潔設計,輕鬆實現事件的發佈與訂閱。通過有序的消息處理,確保事件得到妥善處理。簡化您的代碼,提升系統可維護性。 ...
  • 一、基本的.NET框架概念 .NET框架是一個由微軟開發的軟體開發平臺,它提供了一個運行時環境(CLR - Common Language Runtime)和一套豐富的類庫(FCL - Framework Class Library)。CLR負責管理代碼的執行,而FCL則提供了大量預先編寫好的代碼, ...
  • 本章將和大家分享在ASP.NET Core中如何使用高級客戶端NEST來操作我們的Elasticsearch。 NEST是一個高級別的Elasticsearch .NET客戶端,它仍然非常接近原始Elasticsearch API的映射。所有的請求和響應都是通過類型來暴露的,這使得它非常適合快速上手 ...
  • 參考delphi的代碼更改為C# Delphi 檢測密碼強度 規則(仿 google) 仿 google 評分規則 一、密碼長度: 5 分: 小於等於 4 個字元 10 分: 5 到 7 字元 25 分: 大於等於 8 個字元 二、字母: 0 分: 沒有字母 10 分: 全都是小(大)寫字母 20 ...