Shulou(Shulou.com)06/02 Report--

This article mainly introduces "the concept and usage of Array array". In daily operation, I believe many people have doubts about the concept and usage of Array array. Xiaobian consulted all kinds of materials and sorted out simple and easy operation methods. I hope to help you answer the doubts about "the concept and usage of Array array"! Next, please follow the small series to learn together!

Data structure course study notes.

array concept

An array is a linear table data structure. It uses a contiguous set of memory spaces to store a set of data of the same type, and does not support dynamic expansion.

linear list

Linear tables are data structures arranged in a line. Each linear table has at most two directions. Arrays, linked lists, queues, stacks, etc. are linear table data structures.

nonlinear table

Non-linear tables are irregular data, which is opposite to linear tables, such as binary trees, heaps, etc. In nonlinear tables, the relationship between data is not simple.

array random access formula address[i] = base_address + i * data_type_size

address[i] : The address value of subscript i.

base_address: The first address of the array.

data_type_size: The size of each element in the array, that is, the data type size (bytes), for example, int is 4 bytes.

Array addition and deletion

Array (Array) In these three actions, the query is efficient, but the addition and deletion are inefficient, the query efficiency is because the array supports random access, the time complexity is O(1) , here will not be described more, but in the addition and deletion of the action, because it involves data movement, so the time complexity is O(n), the following to explain in detail.

Ineffective "insert" and "delete" int[] info = new int[6];

inserted

Array info is a one-dimensional array, its contents are 33, 44, 66, 77, 88 Now we need to insert 55 in the position of subscript 2 to make it an array of 33, 44, 55, 66, 77, 88, which involves moving the data between subscript 2 and subscript 4, and inserting 55 in the position of subscript 2 after completion. Its complexity is O(n). The complexity is O(1).

delete

For example, the array info is 33, 44, 00, 55, 66, 77 before deletion. Now delete the contents of subscript 2, which involves moving the contents of subscripts 3 to 5 forward. The time complexity of the operation is O(n). If it is to delete the last bit and there is no content behind it, the time complexity is O(1).

Insert and delete operations are inefficient because they involve data movement.

CPU cache **

The smallest unit of CPU cache is CPU cache line, a cache line size is usually 64 bytes (depending on the CPU), imagine you are traversing a long array of length 16 data[16], the original data naturally exists in main memory, the access process is described as follows:

1: Access data[0], CPU core attempts to access CPU Cache, misses.

2: Try to access the main memory. The operating system accesses the Cache line once. The size of the Cache Line is- 64 bytes. This means that the value of data[0] is obtained from the main memory. At the same time, data[0] ~ data[7] are added to the CPU Cache.

4: Access data[1]~data[7], CPU core attempts to access CPU Cache, hit directly returned.

5: Access data[8], CPU core tries to access CPU Cache, misses, tries to access main memory, repeat step 2.

Test Array and CPU Cache Lines

Since the smallest unit of CPU cache is cache line (64 bytes), let's test the specific time and performance of horizontal traversal and vertical traversal of two-dimensional arrays.

code

package com.com.array;/** * @Auther: lantao * @Date: 2019-06-24 15:52 * @Company: Pay With You Limited * @maill: lan_tao@suixingpay.com * @Description: TODO */public class ArrayTest { static long[][] arr; public static void main(String[] args) { long sum = 0L; arr = new long[1024 * 1024][10]; //horizontal traverse long l = System.currentTimeMillis(); for (int i = 0; i < 1024 * 1024; i++) { for (int j = 0; j < 10; j++) { sum += arr[i][j]; } } System.out.println("Loop Time traverse laterally: " + (System.currentTimeMillis() - l) + "ms"); long l1 = System.currentTimeMillis(); //vertical traverse for (int i = 0; i < 10; i++) { for (int j = 0; j < 1024 * 1024; j++) { sum += arr[j][i]; } } System.out.println("Loop Time Traverse: " + (System.currentTimeMillis() - l) + "ms"); }} Result: Loop Time Horizontal Traversal: 14 ms Loop Time Vertical Traversal: 83ms

Summary: Because the horizontal traversal is a row, and then in each column of the loop row, CPU cache will cache 64 bytes of cache line size, so you can reduce the interaction between CPU and main memory, directly and cache interaction, improve performance, vertical traversal because each loop is a different row, so the cache line has no effect.

At this point, the study of "the concept and usage of Array array" is over, hoping to solve everyone's doubts. Theory and practice can better match to help you learn, go and try it! If you want to continue learning more relevant knowledge, please continue to pay attention to the website, Xiaobian will continue to strive to bring more practical articles for everyone!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.