โครงสร้างข้อมูลและอัลกอริทึมใน Java ตอนที่ 1: ภาพรวม

โปรแกรมเมอร์ Java ใช้โครงสร้างข้อมูลเพื่อจัดเก็บและจัดระเบียบข้อมูลและเราใช้อัลกอริทึมเพื่อจัดการข้อมูลในโครงสร้างเหล่านั้น ยิ่งคุณเข้าใจโครงสร้างข้อมูลและอัลกอริทึมและวิธีการทำงานร่วมกันมากเท่าไหร่โปรแกรม Java ของคุณก็จะมีประสิทธิภาพมากขึ้นเท่านั้น

บทช่วยสอนนี้เปิดตัวชุดข้อมูลสั้น ๆ ที่แนะนำโครงสร้างข้อมูลและอัลกอริทึม ในส่วนที่ 1 คุณจะได้เรียนรู้ว่าโครงสร้างข้อมูลคืออะไรและจัดประเภทโครงสร้างข้อมูลอย่างไร นอกจากนี้คุณจะได้เรียนรู้ว่าอัลกอริทึมคืออะไรวิธีแสดงอัลกอริทึมและวิธีใช้ฟังก์ชันความซับซ้อนของเวลาและพื้นที่เพื่อเปรียบเทียบอัลกอริทึมที่คล้ายคลึงกัน เมื่อคุณมีพื้นฐานเหล่านี้แล้วคุณก็พร้อมที่จะเรียนรู้เกี่ยวกับการค้นหาและการจัดเรียงด้วยอาร์เรย์มิติเดียวในส่วนที่ 2

โครงสร้างข้อมูลคืออะไร?

โครงสร้างข้อมูลขึ้นอยู่กับชนิดข้อมูลนามธรรม (ADT) ซึ่ง Wikipedia ให้คำจำกัดความดังนี้:

[A] แบบจำลองทางคณิตศาสตร์สำหรับชนิดข้อมูลที่ชนิดข้อมูลถูกกำหนดโดยพฤติกรรม (ความหมาย) จากมุมมองของผู้ใช้ข้อมูลโดยเฉพาะในแง่ของค่าที่เป็นไปได้การดำเนินการที่เป็นไปได้กับข้อมูลประเภทนี้และพฤติกรรม ของการดำเนินการเหล่านี้

ADT ไม่สนใจเกี่ยวกับการแสดงค่าหน่วยความจำหรือวิธีการนำการดำเนินการไปใช้ เหมือนกับอินเทอร์เฟซ Java ซึ่งเป็นประเภทข้อมูลที่ไม่ได้เชื่อมต่อกับการนำไปใช้งานใด ๆ ในทางตรงกันข้ามโครงสร้างข้อมูลคือการนำ ADT มาใช้อย่างเป็นรูปธรรมเช่นเดียวกับที่คลาส Java ใช้อินเทอร์เฟซ

ตัวอย่างของ ADT ได้แก่ พนักงานยานพาหนะอาร์เรย์และรายชื่อ พิจารณา List ADT (หรือที่เรียกว่า Sequence ADT) ซึ่งอธิบายถึงคอลเลกชันที่เรียงลำดับขององค์ประกอบที่ใช้ประเภทร่วมกัน องค์ประกอบแต่ละรายการในคอลเล็กชันนี้มีตำแหน่งของตัวเองและอนุญาตให้มีองค์ประกอบที่ซ้ำกันได้ การทำงานพื้นฐานที่รายการ ADT รองรับ ได้แก่ :

  • การสร้างรายการใหม่และว่างเปล่า
  • การต่อท้ายค่าท้ายรายการ
  • การแทรกค่าภายในรายการ
  • การลบค่าออกจากรายการ
  • ทำซ้ำในรายการ
  • กำลังทำลายรายการ

โครงสร้างข้อมูลที่สามารถใช้ List ADT ประกอบด้วยอาร์เรย์มิติเดียวขนาดคงที่และขนาดไดนามิกและรายการที่เชื่อมโยงแบบเดี่ยว (คุณจะได้รู้จักกับอาร์เรย์ในส่วนที่ 2 และรายการที่เชื่อมโยงในส่วนที่ 3)

การจำแนกโครงสร้างข้อมูล

โครงสร้างข้อมูลมีหลายประเภทตั้งแต่ตัวแปรเดียวไปจนถึงอาร์เรย์หรือรายการที่เชื่อมโยงของวัตถุที่มีหลายเขตข้อมูล โครงสร้างข้อมูลทั้งหมดสามารถจัดประเภทเป็นแบบดั้งเดิมหรือแบบรวมและบางส่วนถูกจัดประเภทเป็นคอนเทนเนอร์

Primitives เทียบกับมวลรวม

โครงสร้างข้อมูลที่ง่ายที่สุดจะจัดเก็บรายการข้อมูลเดียว ตัวอย่างเช่นตัวแปรที่เก็บค่าบูลีนหรือตัวแปรที่เก็บจำนวนเต็ม ผมหมายถึงโครงสร้างข้อมูลเช่นวิทยาการ

โครงสร้างข้อมูลจำนวนมากสามารถจัดเก็บข้อมูลหลายรายการได้ ตัวอย่างเช่นอาร์เรย์สามารถจัดเก็บรายการข้อมูลหลายรายการในช่องต่างๆและออบเจ็กต์สามารถจัดเก็บรายการข้อมูลหลายรายการผ่านฟิลด์ ผมหมายถึงโครงสร้างข้อมูลเหล่านี้เป็นมวลรวม

โครงสร้างข้อมูลทั้งหมดที่เราจะดูในชุดนี้เป็นข้อมูลรวม

ตู้คอนเทนเนอร์

สิ่งใดก็ตามจากรายการข้อมูลที่ถูกจัดเก็บและเรียกใช้อาจถือได้ว่าเป็นโครงสร้างข้อมูล ตัวอย่าง ได้แก่ โครงสร้างข้อมูลที่ได้มาจาก Employee, Vehicle, Array และ List ADT ที่กล่าวถึงก่อนหน้านี้

โครงสร้างข้อมูลจำนวนมากได้รับการออกแบบมาเพื่ออธิบายเอนทิตีต่างๆ อินสแตนซ์ของEmployeeคลาสคือโครงสร้างข้อมูลที่มีอยู่เพื่ออธิบายพนักงานที่หลากหลายเช่น ในทางตรงกันข้ามโครงสร้างข้อมูลบางส่วนมีอยู่เป็นภาชนะเก็บข้อมูลทั่วไปสำหรับโครงสร้างข้อมูลอื่น ๆ ตัวอย่างเช่นอาร์เรย์สามารถเก็บค่าดั้งเดิมหรือการอ้างอิงวัตถุ ผมหมายถึงประเภทหลังนี้ของโครงสร้างข้อมูลเป็นภาชนะ

โครงสร้างข้อมูลทั้งหมดที่เราจะดูในชุดนี้คือคอนเทนเนอร์

โครงสร้างข้อมูลและอัลกอริทึมใน Java Collections

Java Collections Framework สนับสนุนโครงสร้างข้อมูลเชิงคอนเทนเนอร์และอัลกอริทึมที่เกี่ยวข้องหลายประเภท ชุดนี้จะช่วยให้คุณเข้าใจกรอบนี้ได้ดีขึ้น

ออกแบบรูปแบบและโครงสร้างข้อมูล

เป็นเรื่องปกติที่จะใช้รูปแบบการออกแบบเพื่อแนะนำนักศึกษามหาวิทยาลัยให้รู้จักโครงสร้างข้อมูล เอกสารของมหาวิทยาลัยบราวน์สำรวจรูปแบบการออกแบบต่างๆที่มีประโยชน์สำหรับการออกแบบโครงสร้างข้อมูลคุณภาพสูง เหนือสิ่งอื่นใดกระดาษแสดงให้เห็นว่ารูปแบบอะแดปเตอร์มีประโยชน์สำหรับการออกแบบกองและคิว รหัสสาธิตจะแสดงในรายการ 1

รายการ 1. การใช้รูปแบบ Adapter สำหรับสแต็กและคิว (DequeStack.java)

public class DequeStack implements Stack { Deque D; // holds the elements of the stack public DequeStack() { D = new MyDeque(); } @Override public int size() { return D.size(); } @Override public boolean isEmpty() { return D.isEmpty(); } @Override public void push(Object obj) { D.insertLast(obj); } @Override public Object top() throws StackEmptyException { try { return D.lastElement(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } @Override public Object pop() throws StackEmptyException { try { return D.removeLast(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } }

รายการ 1 ข้อความที่ตัดตอนมาจากDequeStackชั้นเรียนของ Brown University ซึ่งแสดงให้เห็นถึงรูปแบบอะแดปเตอร์ โปรดสังเกตว่าStackและDequeเป็นอินเทอร์เฟซที่อธิบาย Stack และ Deque ADTs เป็นคลาสที่ใช้MyDequeDeque

การลบล้างวิธีการอินเทอร์เฟซ

รหัสเดิมที่รายการที่ 1 จะขึ้นอยู่กับที่ไม่ได้นำเสนอรหัสที่มาStack, และDeque MyDequeเพื่อความชัดเจนฉันได้แนะนำ@Overrideคำอธิบายประกอบเพื่อแสดงว่าDequeStackเมธอดที่ไม่ใช่ตัวสร้างทั้งหมดจะแทนที่Stackเมธอด

DequeStackปรับMyDequeให้สามารถใช้งานStackได้ ทุกDequeStackวิธีการของสายหนึ่งบรรทัดกับDequeวิธีการของอินเตอร์เฟซ อย่างไรก็ตามมีริ้วรอยเล็ก ๆ ซึ่งDequeข้อยกเว้นจะถูกแปลงเป็นStackข้อยกเว้น

อัลกอริทึมคืออะไร?

ในอดีตใช้เป็นเครื่องมือสำหรับการคำนวณทางคณิตศาสตร์อัลกอริทึมมีความเชื่อมโยงอย่างลึกซึ้งกับวิทยาศาสตร์คอมพิวเตอร์และโดยเฉพาะอย่างยิ่งโครงสร้างข้อมูล ขั้นตอนวิธีการเป็นลำดับของคำสั่งที่สำเร็จการงานในช่วงเวลาที่ จำกัด ของเวลา คุณสมบัติของอัลกอริทึมมีดังนี้:

  • รับอินพุตเป็นศูนย์หรือมากกว่า
  • สร้างเอาต์พุตอย่างน้อยหนึ่งเอาต์พุต
  • ประกอบด้วยคำแนะนำที่ชัดเจนและไม่คลุมเครือ
  • สิ้นสุดหลังจากจำนวนขั้นตอนที่ จำกัด
  • เป็นพื้นฐานเพียงพอที่บุคคลสามารถพกพาได้โดยใช้ดินสอและกระดาษ

โปรดทราบว่าในขณะที่โปรแกรมอาจเป็นแบบอัลกอริทึม แต่หลาย ๆ โปรแกรมจะไม่ยุติโดยไม่มีการแทรกแซงจากภายนอก

ลำดับรหัสจำนวนมากมีคุณสมบัติเป็นอัลกอริทึม ตัวอย่างหนึ่งคือลำดับรหัสที่พิมพ์รายงาน อัลกอริทึมของ Euclid ใช้เพื่อคำนวณตัวหารร่วมที่ยิ่งใหญ่ที่สุดทางคณิตศาสตร์ อาจทำให้กรณีที่การดำเนินการพื้นฐานของโครงสร้างข้อมูล (เช่นเก็บค่าในช่องอาร์เรย์ ) เป็นอัลกอริทึม ในชุดนี้ส่วนใหญ่ฉันจะเน้นไปที่อัลกอริทึมระดับสูงที่ใช้ในการประมวลผลโครงสร้างข้อมูลเช่นการค้นหาแบบไบนารีและอัลกอริทึมการคูณเมทริกซ์

ผังงานและรหัสเทียม

คุณเป็นตัวแทนของอัลกอริทึมได้อย่างไร? การเขียนโค้ดก่อนที่จะเข้าใจอัลกอริทึมพื้นฐานอาจทำให้เกิดข้อบกพร่องได้ดังนั้นทางเลือกที่ดีกว่าคืออะไร? สองตัวเลือกคือผังงานและรหัสเทียม

การใช้ผังงานเพื่อแสดงอัลกอริทึม

A flowchart is a visual representation of an algorithm's control flow. This representation illustrates statements that need to be executed, decisions that need to be made, logic flow (for iteration and other purposes), and terminals that indicate start and end points. Figure 1 reveals the various symbols that flowcharts use to visualize algorithms.

Consider an algorithm that initializes a counter to 0, reads characters until a newline (\n) character is seen, increments the counter for each digit character that's been read, and prints the counter's value after the newline character has been read. The flowchart in Figure 2 illustrates this algorithm's control flow.

A flowchart's simplicity and its ability to present an algorithm's control flow visually (so that it's is easy to follow) are its major advantages. Flowcharts also have several disadvantages, however:

  • It's easy to introduce errors or inaccuracies into highly-detailed flowcharts because of the tedium associated with drawing them.
  • It takes time to position, label, and connect a flowchart's symbols, even using tools to speed up this process. This delay might slow your understanding of an algorithm.
  • Flowcharts belong to the structured programming era and aren't as useful in an object-oriented context. In contrast, the Unified Modeling Language (UML) is more appropriate for creating object-oriented visual representations.

Using pseudocode to represent algorithms

An alternative to flowcharts is pseudocode, which is a textual representation of an algorithm that approximates the final source code. Pseudocode is useful for quickly writing down an algorithm's representation. Because syntax is not a concern, there are no hard-and-fast rules for writing pseudocode.

You should strive for consistency when writing pseudocode. Being consistent will make it much easier to translate the pseudocode into actual source code. For example, consider the following pseudocode representation of the previous counter-oriented flowchart:

 DECLARE CHARACTER ch = '' DECLARE INTEGER count = 0 DO READ ch IF ch GE '0' AND ch LE '9' THEN count = count + 1 END IF UNTIL ch EQ '\n' PRINT count END

The pseudocode first presents a couple of DECLARE statements that introduce variables ch and count, initialized to default values. It then presents a DO loop that executes UNTILch contains \n (the newline character), at which point the loop ends and a PRINT statement outputs count's value.

For each loop iteration, READ causes a character to be read from the keyboard (or perhaps a file--in this case it doesn't matter what constitutes the underlying input source) and assigned to ch. If this character is a digit (one of 0 through 9), count is incremented by 1.

Choosing the right algorithm

The data structures and algorithms you use critically affect two factors in your applications:

  1. Memory usage (for data structures).
  2. CPU time (for algorithms that interact with those data structures).

It follows that you should be especially mindful of the algorithms and data structures you use for applications that will process lots of data. These include applications used for big data and the Internet of Things.

Balancing memory and CPU

When choosing a data structure or algorithm, you will sometimes discover an inverse relationship between memory usage and CPU time: the less memory a data structure uses, the more CPU time associated algorithms need to process the data structure's data items. Also, the more memory a data structure uses, the less CPU time associated algorithms will need to process the data items–leading to faster algorithm results.

As much as possible, you should strive to balance memory use with CPU time. You can simplify this task by analyzing algorithms to determine their efficiency. How well does one algorithm perform against another of similar nature? Answering this question will help you make good choices given a choice between multiple algorithms.

Measuring algorithm efficiency

Some algorithms perform better than others. For example, the Binary Search algorithm is almost always more efficient than the Linear Search algorithm–something you'll see for yourself in Part 2. You want to choose the most efficient algorithm for your application's needs, but that choice might not be as obvious as you would think.

For instance, what does it mean if the Selection Sort algorithm (introduced in Part 2) takes 0.4 seconds to sort 10,000 integers on a given machine? That benchmark is only valid for that particular machine, that particular implementation of the algorithm, and for the size of the input data.

As computer scientist, we use time complexity and space complexity to measure an algorithm's efficiency, distilling these into complexity functions to abstract implementation and runtime environment details. Complexity functions reveal the variance in an algorithm's time and space requirements based on the amount of input data:

  • A time-complexity function measures an algorithm's time complexity--meaning how long an algorithm takes to complete.
  • ฟังก์ชั่นพื้นที่ซับซ้อนขนาดของขั้นตอนวิธีการซับซ้อนพื้นที่ --meaning จำนวนหน่วยความจำที่จำเป็นต้องใช้ค่าใช้จ่ายโดยขั้นตอนวิธีการในการดำเนินงานของตน

ฟังก์ชันความซับซ้อนทั้งสองขึ้นอยู่กับขนาดของอินพุต ( n ) ซึ่งสะท้อนถึงปริมาณข้อมูลอินพุต พิจารณา pseudocode ต่อไปนี้สำหรับการพิมพ์อาร์เรย์:

 DECLARE INTEGER i, x[] = [ 10, 15, -1, 32 ] FOR i = 0 TO LENGTH(x) - 1 PRINT x[i] NEXT i END

ฟังก์ชันความซับซ้อนของเวลาและความซับซ้อนของเวลา

คุณสามารถแสดงความซับซ้อนของเวลาของอัลกอริทึมนี้ได้โดยการระบุฟังก์ชันความซับซ้อนของเวลาโดยที่(ตัวคูณคงที่) หมายถึงระยะเวลาในการวนซ้ำหนึ่งรอบและแสดงเวลาตั้งค่าของอัลกอริทึม ในตัวอย่างนี้ความซับซ้อนของเวลาเป็นเชิงเส้นt(n) = an+bab