Java'da veri yapıları ve algoritmalar, Bölüm 1: Genel Bakış

Java programcıları, verileri depolamak ve düzenlemek için veri yapılarını kullanır ve bu yapılardaki verileri işlemek için algoritmalar kullanırız. Veri yapıları ve algoritmaları ve birlikte nasıl çalıştıkları hakkında ne kadar çok şey anlarsanız, Java programlarınız o kadar verimli olacaktır.

Bu eğitim, veri yapılarını ve algoritmaları tanıtan kısa bir seriyi başlatır. 1. Bölümde, bir veri yapısının ne olduğunu ve veri yapılarının nasıl sınıflandırıldığını öğreneceksiniz. Ayrıca bir algoritmanın ne olduğunu, algoritmaların nasıl temsil edildiğini ve benzer algoritmaları karşılaştırmak için zaman ve uzay karmaşıklığı işlevlerinin nasıl kullanılacağını da öğreneceksiniz. Bu temel bilgileri edindikten sonra, Bölüm 2'de tek boyutlu dizilerle arama ve sıralama hakkında bilgi edinmeye hazır olacaksınız.

Veri yapısı nedir?

Veri yapıları, Wikipedia'nın aşağıdaki gibi tanımladığı soyut veri türlerine (ADT) dayanmaktadır:

Bir veri türünün, özellikle olası değerler, bu tür veriler üzerindeki olası işlemler ve davranış açısından, bir veri kullanıcısının bakış açısından davranışı (anlambilim) tarafından tanımlandığı veri türleri için matematiksel model bu işlemlerin.

Bir ADT, değerlerinin bellek temsilini veya işlemlerinin nasıl uygulandığını umursamaz. Herhangi bir uygulamayla bağlantısı kesilen bir veri türü olan Java arayüzü gibidir. Buna karşılık, bir veri yapısı , Java sınıflarının arabirimleri nasıl uyguladığına benzer şekilde, bir veya daha fazla ADT'nin somut bir uygulamasıdır.

ADT örnekleri arasında Çalışan, Araç, Dizi ve Liste bulunur. Ortak bir türü paylaşan sıralı öğe koleksiyonunu tanımlayan Liste ADT'yi (Sıralı ADT olarak da bilinir) düşünün. Bu koleksiyondaki her öğenin kendi konumu vardır ve yinelenen öğelere izin verilir. ADT Listesi tarafından desteklenen temel işlemler şunları içerir:

  • Yeni ve boş bir liste oluşturma
  • Listenin sonuna bir değer eklemek
  • Listeye bir değer eklemek
  • Listeden bir değer silme
  • Liste üzerinde yinelemek
  • Listeyi yok etmek

Liste ADT'yi uygulayabilen veri yapıları arasında sabit boyutlu ve dinamik olarak boyutlandırılmış tek boyutlu diziler ve tekil bağlantılı listeler bulunur. (Bölüm 2'de dizilerle ve Bölüm 3'te bağlantılı listelerle tanışacaksınız.)

Veri yapılarının sınıflandırılması

Tek değişkenlerden dizilere veya birden çok alan içeren bağlantılı nesne listelerine kadar değişen birçok veri yapısı türü vardır. Tüm veri yapıları ilkel veya kümeler olarak sınıflandırılabilir ve bazıları kaplar olarak sınıflandırılır.

İlkeller ve toplamlar

En basit veri yapısı türü, tek veri öğelerini depolar; örneğin, bir Boolean değerini depolayan bir değişken veya bir tamsayı depolayan bir değişken. Bu tür veri yapılarına ilkeller olarak atıfta bulunuyorum .

Birçok veri yapısı, birden çok veri öğesini depolayabilir. Örneğin, bir dizi, çeşitli yuvalarında birden çok veri öğesini depolayabilir ve bir nesne, alanları aracılığıyla birden çok veri öğesini depolayabilir. Bu veri yapılarını kümeler olarak adlandırıyorum .

Bu seride inceleyeceğimiz tüm veri yapıları kümelerdir.

Konteynerler

Veri öğelerinin depolandığı ve alındığı her şey bir veri yapısı olarak kabul edilebilir. Örnekler, daha önce bahsedilen Çalışan, Araç, Dizi ve Liste ADT'lerinden türetilen veri yapılarını içerir.

Birçok veri yapısı, çeşitli varlıkları açıklamak için tasarlanmıştır. Bir Employeesınıfın örnekleri, örneğin çeşitli çalışanları tanımlamak için var olan veri yapılarıdır. Buna karşılık, bazı veri yapıları, diğer veri yapıları için genel depolama araçları olarak mevcuttur. Örneğin, bir dizi ilkel değerleri veya nesne referanslarını saklayabilir. Bu son veri yapıları kategorisine kapsayıcılar olarak atıfta bulunuyorum .

Toplu olmanın yanı sıra, bu seride inceleyeceğimiz tüm veri yapıları konteynerlerdir.

Java Koleksiyonlarında veri yapıları ve algoritmalar

Java Collections Framework, birçok türden kapsayıcıya yönelik veri yapısını ve ilişkili algoritmaları destekler. Bu dizi, bu çerçeveyi daha iyi anlamanıza yardımcı olacaktır.

Tasarım modelleri ve veri yapıları

Üniversite öğrencilerini veri yapılarıyla tanıştırmak için tasarım modellerini kullanmak oldukça yaygın hale geldi. Brown Üniversitesi makalesi, yüksek kaliteli veri yapıları tasarlamak için yararlı olan çeşitli tasarım modellerini araştırıyor. Kağıt, diğer şeylerin yanı sıra, Bağdaştırıcı modelinin yığınları ve kuyrukları tasarlamak için yararlı olduğunu göstermektedir. Gösterim kodu Liste 1'de gösterilmektedir.

Listeleme 1. Yığınlar ve kuyruklar için Bağdaştırıcı modelini kullanma (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(); } } }

Liste 1 DequeStack, Bağdaştırıcı modelini gösteren Brown Üniversitesi makalesinin sınıfından alıntılar . Not olduğunu Stackve DequeStack ve deque soyut veri tiplerini tarif arayüzleri bulunmaktadır. MyDequeuygulayan bir sınıftır Deque.

Arayüz yöntemlerini geçersiz kılma

Liste 1 dayandığını orijinal kod için kaynak kodunu mevcut değildi Stack, Dequeve MyDeque. Netlik sağlamak için, yapıcı olmayan @Overridetüm DequeStackyöntemlerin yöntemleri geçersiz kıldığını göstermek için ek açıklamalar ekledim Stack.

DequeStackMyDequeuygulayabilmesi için uyarlar Stack. Her DequeStackbireyin yönteme tek hatlı aramalar Dequearabirimin yöntem. Bununla birlikte, Dequeistisnaların istisnalara dönüştürüldüğü küçük bir kırışıklık vardır Stack.

Algoritma nedir?

Tarihsel olarak matematiksel hesaplama için bir araç olarak kullanılan algoritmalar, bilgisayar bilimi ve özellikle veri yapıları ile derinden bağlantılıdır. Bir algoritma sonlu bir zaman döneminde bir görevi gerçekleştirir talimatlar dizisidir. Bir algoritmanın nitelikleri aşağıdaki gibidir:

  • Sıfır veya daha fazla girdi alır
  • En az bir çıktı üretir
  • Açık ve net talimatlardan oluşur
  • Sonlu sayıda adımdan sonra sona erer
  • Bir kişinin bunu bir kalem ve kağıt kullanarak yapabileceği kadar basittir

Programlar doğası gereği algoritmik olabilirken, birçok programın dış müdahale olmadan sona ermediğini unutmayın.

Many code sequences qualify as algorithms. One example is a code sequence that prints a report. More famously, Euclid's algorithm is used to calculate the mathematical greatest common divisor. A case could even be made that a data structure's basic operations (such as store value in array slot) are algorithms. In this series, for the most part, I'll focus on higher-level algorithms used to process data structures, such as the Binary Search and Matrix Multiplication algorithms.

Flowcharts and pseudocode

How do you represent an algorithm? Writing code before fully understanding its underlying algorithm can lead to bugs, so what's a better alternative? Two options are flowcharts and pseudocode.

Using flowcharts to represent algorithms

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.
  • Bir uzay karmaşıklığı işlevi , bir algoritmanın uzay karmaşıklığını ölçer - bu , algoritmanın görevini gerçekleştirmek için ihtiyaç duyduğu bellek ek yükü miktarını ifade eder.

Her iki karmaşıklık işlevi de , bir şekilde girdi verilerinin miktarını yansıtan girdinin ( n ) boyutuna dayanır . Dizi yazdırma için aşağıdaki sözde kodu göz önünde bulundurun:

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

Zaman karmaşıklığı ve zaman karmaşıklığı fonksiyonları

Bu algoritmanın zaman karmaşıklığını, zaman karmaşıklığı işlevini belirterek ifade edebilirsiniz ; burada (sabit bir çarpan), bir döngü yinelemesini tamamlamak için gereken süreyi temsil eder ve algoritmanın kurulum süresini temsil eder. Bu örnekte, zaman karmaşıklığı doğrusaldır.t(n) = an+bab