點陣圖

来源:https://www.cnblogs.com/searchtosuggest/archive/2018/07/09/9278513.html
-Advertisement-
Play Games

1、引言 點陣圖是使用位（bit）數組來對數據進行統計，排序和去重，其結構圖如下： 其中點陣圖的索引映射需要存儲的值，點陣圖索引所在位置的值表示索引對應的值是否已經存儲。 2、介面 3、實現 定義靜態byte數組常量，用於快速檢驗點陣圖上索引對應的值： 聲明欄位： 其中size為點陣圖的大小；當點陣圖的size ...


1、引言

　　點陣圖是使用位（bit）數組來對數據進行統計，排序和去重，其結構圖如下：

　　　　

　　其中點陣圖的索引映射需要存儲的值，點陣圖索引所在位置的值表示索引對應的值是否已經存儲。

2、介面

 1 public interface ByteMap {
 2 
 3     /* get the value in the index of byte map
 4      * @param index the index in byte map to get 
 5      * @return 1 or 0 base the value in the index of byte map
 6      */
 7     int getByte(int index);
 8     
 9     /* set the value in the index of byte map
10      * @param index the index in byte map to set
11      * @param flag the value setted in the index of byte map
12      */
13     void setByte(int index, int flag);
14     
15     /* set the value in byte map from start to end
16      * @param start the start index in byte map
17      * @param end the end index in byte map
18      * @flag the value setted in byte map from start to end
19      */
20     void setByte(int start, int end, int flag);
21     
22     /*
23      * get the size of byte map
24      */
25     int getSize();
26     
27     /*
28      * set the size of byte map
29      * @param size to be setted
30      */
31     void setSize(int size);
32     
33     /*
34      * count how many 1 in byte map
35      */
36     int countOne();
37     
38     /*
39      * count how many i in byte map from start to end
40      */
41     int countOne(int start, int end);
42     
43     /*
44      * get the sub map of byte map from start to end
45      */
46     ByteMap subMap(int start, int end);
47     
48     /*
49      * flip the value in byte map 
50      */
51     ByteMap not();
52     
53     /*
54      * or operation with another byte map
55      */
56     ByteMap or(ByteMap byteMap);
57     
58     /*
59      * xor operation with another byte map
60      */
61     ByteMap xor(ByteMap byteMap);
62     
63     /*
64      * and operation with another byte map
65      */
66     ByteMap and(ByteMap byteMap);
67     
68     /*
69      * byte map left shift operation
70      */
71     ByteMap leftShift(int shiftStep);
72     
73     /*
74      * byte map right shift operation
75      */
76     ByteMap rightShift(int shiftStep);
77 }

 3、實現

　　定義靜態byte數組常量，用於快速檢驗點陣圖上索引對應的值：

 1 private static final byte[] BYTE_VALUE = {
 2         0x0001,
 3         0x0002,
 4         0x0004,
 5         0x0008,
 6         0x0010,
 7         0x0020,
 8         0x0040,
 9         -0x0080
10 };

聲明欄位：

1 private int size;
2 private byte b;
3 private byte[] biteMap;

其中size為點陣圖的大小；當點陣圖的size小於等於8時，使用b，否則使用biteMap

構造函數：

 1 public ByteMapImpl() {
 2     this(8);
 3 }
 4     
 5 public ByteMapImpl(int size) {
 6     if(size <= 0) {
 7         throw new IllegalArgumentException("ByteMap size value should be positive");
 8     }
 9     this.size = size;
10     if(size <= 8) {
11         this.b = 0;
12     }else {
13         int len = (size >> 3) + ((size & 7) > 0 ? 1 : 0);
14         this.biteMap = new byte[len];
15     }
16 }

 其中點陣圖的索引從0開始的

點陣圖最重要的兩個介面是：

 1 public int getByte(int index) {
 2     if(index < 0 || index >= this.size) {
 3         throw new IllegalArgumentException("index out of bit map");
 4     }
 5     byte unit = (this.size <= 8) ? this.b : this.biteMap[index >> 3];
 6     int result = 0;
 7     result = unit & BYTE_VALUE[index & 7];
 8     return result == 0 ? 0 : 1;
 9 }
10     
11 public void setByte(int index, int flag) {
12     if(index < 0 || index >= this.size) {
13         throw new IllegalArgumentException("index out of bit map");
14     }
15     if(flag != 0 && flag != 1) {
16         throw new IllegalArgumentException("illegal flag argument, must be 1 or 0");
17     }
18         
19     if(flag == this.getByte(index)) {
20         return;
21     }
22     int offSet = index & 7;
23     if(this.size <= 8) {
24         if(flag == 1) {
25             this.b = (byte) (this.b | BYTE_VALUE[offSet]);
26         }else {
27             this.b = (byte) (this.b & (~BYTE_VALUE[offSet]));
28         }
29             
30     }else {
31         int unitIndex = index >> 3;
32         byte unit = this.biteMap[unitIndex];
33         if(flag == 1) {
34             this.biteMap[unitIndex] = (byte) (unit | BYTE_VALUE[offSet]);
35         }else {
36             this.biteMap[unitIndex] = (byte) (unit & (~BYTE_VALUE[offSet]));
37         }
38     }
39 }

通過位操作與，或以及移位實現以上兩個介面

剩下的介面基於以上實現的：

  1 public void setByte(int start, int end, int flag) {
  2     for(int i = start ; i <= end; ++i) {
  3         this.setByte(i, flag);
  4     }
  5 }
  6     
  7 public int getSize() {
  8     return size;
  9 }
 10 
 11 public void setSize(int size) {
 12     this.size = size;
 13 }
 14     
 15 public int countOne() {
 16     return this.countOne(0, this.size - 1);
 17 }
 18     
 19 public int countOne(int start, int end) {
 20     int count = 0;
 21     for(int i = start; i <= end; i++) {
 22         count += this.getByte(i);
 23     }
 24     return count;
 25 }
 26     
 27 public ByteMap subMap(int start, int end) {
 28     ByteMap byteMap = new ByteMapImpl(end - start + 1);
 29     for(int i = start; i <= end; ++i) {
 30         if(this.getByte(i) != 0) {
 31             byteMap.setByte(i - start, 1);
 32         }
 33     }
 34     return byteMap;
 35 }
 36     
 37 public  ByteMap not() {
 38     ByteMap byteMap = new ByteMapImpl(this.size);
 39     for(int i = 0; i < this.size; ++i) {
 40         int flag = (this.getByte(i) == 0) ? 1 : 0;
 41         byteMap.setByte(i, flag);
 42     }
 43     return byteMap;
 44 }
 45     
 46 public ByteMap or(ByteMap byteMap) {
 47     int s1 = this.size;
 48     int s2 = byteMap.getSize();
 49     int orSize = s1 > s2 ? s1 : s2;
 50     ByteMap orMap = new ByteMapImpl(orSize);
 51     int i = 0;
 52     while(i < s1 && i < s2) {
 53         if(this.getByte(i) != 0 || byteMap.getByte(i) != 0) {
 54             orMap.setByte(i, 1);
 55         }
 56         ++i;
 57     }
 58     while(i < s1) {
 59         if(this.getByte(i) != 0) {
 60             orMap.setByte(i, 1);
 61         }
 62         ++i;
 63     }
 64     while(i < s2) {
 65         if(byteMap.getByte(i) != 0) {
 66             orMap.setByte(i, 1);
 67         }
 68         ++i;
 69     }
 70     return orMap;
 71 }
 72     
 73 public ByteMap xor(ByteMap byteMap) {
 74     int s1 = this.size;
 75     int s2 = byteMap.getSize();
 76     int xorSize = s1 > s2 ? s1 : s2;
 77     ByteMap xorMap = new ByteMapImpl(xorSize);
 78     int i = 0;
 79     while(i < s1 && i < s2) {
 80         if(this.getByte(i) !=  byteMap.getByte(i)) {
 81             xorMap.setByte(i, 1);
 82         }
 83         ++i;
 84     }
 85     while(i < s1) {
 86         if(this.getByte(i) != 0) {
 87             xorMap.setByte(i, 1);
 88         }
 89         ++i;
 90     }
 91     while(i < s2) {
 92         if(byteMap.getByte(i) != 0) {
 93             xorMap.setByte(i, 1);
 94         }
 95         ++i;
 96     }
 97     return xorMap;
 98 }
 99     
100 public ByteMap and(ByteMap byteMap) {
101     int s1 = this.size;
102     int s2 = byteMap.getSize();
103     int orSize = s1 > s2 ? s1 : s2;
104     ByteMap andMap = new ByteMapImpl(orSize);
105     int i = 0;
106     while(i < s1 && i < s2) {
107         if(this.getByte(i) != 0 && byteMap.getByte(i) != 0) {
108             andMap.setByte(i, 1);
109         }
110         ++i;
111     }
112     return andMap;
113 }
114     
115 public ByteMap leftShift(int shiftStep) {
116     ByteMap shiftMap = new ByteMapImpl(this.size);
117     if(this.countOne() > 0 && shiftStep < this.size) {
118         if(shiftStep < 0) {
119             return this.rightShift((0 - shiftStep));
120         }else {
121             for(int i = shiftStep; i < this.size; ++i) {
122                 if(this.getByte(i) != 0) {
123                     shiftMap.setByte(i - shiftStep, 1);
124                 }
125             }
126         }
127     }
128     return shiftMap;
129 }
130     
131 public ByteMap rightShift(int shiftStep) {
132     ByteMap shiftMap = new ByteMapImpl(this.size);
133     if(this.countOne() > 0 && shiftStep < this.size) {
134         if(shiftStep < 0) {
135             return this.leftShift((0 - shiftStep));
136         }else {
137             for(int i = this.size - shiftStep - 1; i >= 0; --i) {
138                 if(this.getByte(i) != 0) {
139                     shiftMap.setByte(i + shiftStep, 1);
140                 }
141             }
142         }
143     }
144     return shiftMap;
145 }

4、測試

為了便於測試，重寫Object類型的toString方法：

 1 @Override
 2 public String toString() {
 3     StringBuilder sb = new StringBuilder();
 4     if(this.size <= 8) {
 5         for(int i = 0; i < 8; ++i) {
 6             if(i < 7) {
 7                 try {
 8                     sb.append(this.getByte(i) + ",");
 9                 } catch (IllegalArgumentException e) {
10                     sb.append("0,");
11                 }
12             }else {
13                 try {
14                     sb.append(this.getByte(i));
15                 } catch (IllegalArgumentException e) {
16                     sb.append("0");
17                 }
18             }
19         }
20     }else {
21         for(int i = 0; i < this.biteMap.length*8; ++i) {
22             if((i&7) == 0) {
23                 sb.append("\n" + (i>>3) + ":");
24             }else {
25                 sb.append(",");
26             }
27             try {
28                 sb.append(this.getByte(i));
29             } catch (IllegalArgumentException e) {
30                 sb.append("0");
31             }
32         }
33     }
34     return sb.toString();
35 }

測試main函數：

 1 public static void main(String[] args) {
 2     ByteMap byteMap1 = new ByteMapImpl(60);
 3     byteMap1.setByte(3, 5, 1);
 4     System.out.println("byteMap1:" + byteMap1.toString());
 5     System.out.println("byteMap1 count 1:" + byteMap1.countOne());
 6     ByteMap byteMap2 = byteMap1.subMap(1, 11);
 7     System.out.println("byteMap1 sub map:" + byteMap2);
 8     System.out.println("byteMap1 sub map count 1:" + byteMap2.countOne());
 9     System.out.println("or map:" + byteMap1.or(byteMap2));
10     System.out.println("and map:" + byteMap1.and(byteMap2));
11     System.out.println("xor map:" + byteMap1.xor(byteMap2));
12     System.out.println("byteMap1 left shift 3 bit:" + byteMap1.leftShift(3));
13     System.out.println("byteMap1 right shift 3 bite:" + byteMap1.rightShift(3));
14 }

結果：

byteMap1:
0:0,0,0,1,1,1,0,0
1:0,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0
byteMap1 count 1:3
byteMap1 sub map:
0:0,0,1,1,1,0,0,0
1:0,0,0,0,0,0,0,0
byteMap1 sub map count one:3
or map:
0:0,0,1,1,1,1,0,0
1:0,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0
and map:
0:0,0,0,1,1,0,0,0
1:0,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0
xor map:
0:0,0,1,0,0,1,0,0
1:0,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0
byteMap1 left shift 3 bit:
0:1,1,1,0,0,0,0,0
1:0,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0
byteMap1 right shift 3 bite:
0:0,0,0,0,0,0,1,1
1:1,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0

5、總結

　　使用點陣圖適合稠密數據，不然會造成大量空間的浪費

6、思考

　　（1）為什麼 BYTE_VALUE[7] = -0x0080；

　　（2）實現的點陣圖是非線程安全的，怎樣改進既能保證線程安全，又不會大幅度降低性能；

 

源碼參考：https://github.com/pythonerleilei/Search/tree/master/src/seach/data_structure/map

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

-Advertisement-
Play Games
更多相關文章
  • 洛谷P4316 綠豆蛙的歸宿(期望)
    題意翻譯 「Poetize3」 題目背景 隨著新版百度空間的上線，Blog寵物綠豆蛙完成了它的使命，去尋找它新的歸宿。 題目描述 給出一個有向無環圖，起點為1終點為N，每條邊都有一個長度，並且從起點出發能夠到達所有的點，所有的點也都能夠到達終點。綠豆蛙從起點出發，走向終點。 到達每一個頂點時，如果有 ...
  • 幫助小白，JDK的安裝與環境變數配置（Win 10系統）
    學習JAVA，必須首先安裝一下JDK(java development kit java開發工具包)，之後再配置環境變數就可以開始使用JAVA了。 一，安裝JDK 1，可以選擇到官網下載最新版本的JDK，地址如下： http://www.oracle.com/technetwork/java/jav ...
  • python日記-快速排序演算法
    __author__ = "yang xin"array=[]def quickSort(left,right): if left > right: return temp = array[left] i = left j = right while i < j: if array[j] >= te ...
  • HO引擎近況20180710
    首先感謝老觀眾水中盜影和其它幾位的回覆,我媽還沒見到我娶媳婦就走了,也是我的不孝啊! 這一個月前半都在跑我媽的後事,後半都是強制996的加班中 天天坐火車回去當天再回來,雖然忙但還挺充實,也沒想什麼,公證處要什麼材料我就去各單位去開各種證明... 但是公證跑完了之後,後半個月的兩周我幾乎天天失眠,甚 ...
  • 轉發： Angular裝飾器
    Angular中的裝飾器是一個函數，它將元數據添加到類、類成員（屬性、方法）和函數參數。 用法：要想應用裝飾器，把它放在被裝飾對象的上面或左邊。 Angular使用自己的一套裝飾器來實現應用程式各部件之間的相互操作。 這個地方是前面幾個模塊(Modules), 指令（Diretives）、組件(Co ...
  • Python學習：14.Python面向對象（一）
    一、面向對象簡介 Python設計之初，就是一門面向對象的語言，在Python中一切皆對象，而且在Python中創建一個對象也很簡單，今天我們就來學習一下Python的面向對象的知識。 二、兩種編程方式 在C#、Java中，只能使用面向對象編程，在Ruby、Python中可以使用函數編程以及面向對象 ...
  • DFS小題
    原創 題目為：（）（）（）+（）（）（）=（）（）（） 將1~9這9個數字填入括弧，每個數字只能用一次。 枚舉： 1 public class Test { 2 public static void main(String[] args){ 3 int a[]=new int[9]; 4 int f ...
  • Python 簡單的多線程聊天
    創建一個socketserver 至少分以下幾步 First, you must create a request handler class by subclassing the BaseRequestHandlerclass and overriding its handle() method; ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類