Parallele Berechnung von Primzahlen

1. Aufgabe

Unter „Multithreading => Multithreading mit der Klasse Thread“ finden Sie eine WPF-Anwendung vor, die sich auf die Suche nach Primzahlen begibt. Und dies mit der Hilfe von mehreren Threads, die auf einem modernen PC echt-parallel agieren.

Die Multithreading-Fähigkeiten von Smartphones hingegen gelangen erst recht langsam ans Tageslicht. Gerade deshalb fand ich es reizvoll, das Beispielprogramm auf ein Java/Android-Smartphone zu portieren. Für die Aufgabenstellung selbst sehen Sie am besten direkt in der oben erwähnten Rubrik nach. Das Beispiel ist dort unter der Überschrift „Parallele Berechnung von Primzahlen“ hinterlegt. Für die Gestaltung der Oberfläche finden Sie in Abbildung 1 eine Anregung vor:

Oberfläche der Android-Primzahlen-Anwendung.

Abbildung 1. Oberfläche der Android-Primzahlen-Anwendung.

2. Lösung

Da der WPF/Windows-Lösungsvorschlag recht ausführlich gehalten ist, beschränke ich mich in diesem Abschnitt darauf, nur die notwendigen Dateien der Android-Anwendung vorzustellen. Sie sind das Ergebnis einer, soweit machbar, möglichst getreuen Portierung der entsprechenden C#-Lösung:

001: <LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
002:     xmlns:tools="http://schemas.android.com/tools"
003:     android:layout_width="fill_parent"
004:     android:layout_height="fill_parent"
005:     android:paddingBottom="@dimen/activity_vertical_margin"
006:     android:orientation="vertical"
007:     android:paddingLeft="@dimen/activity_horizontal_margin"
008:     android:paddingRight="@dimen/activity_horizontal_margin"
009:     android:paddingTop="@dimen/activity_vertical_margin"
010:     tools:context=".Main" >
011:     
012:     <LinearLayout 
013:         android:orientation="horizontal" 
014:         android:layout_width="match_parent"
015:         android:layout_height="wrap_content">
016:         
017:         <Button
018:             android:id="@+id/buttonCalc"
019:             android:layout_width="wrap_content"
020:             android:layout_height="wrap_content"    
021:             android:textSize="20sp"
022:             android:layout_margin="4dp"
023:             android:text="@string/button_calc" />
024:         
025:         <EditText
026:             android:inputType="textNoSuggestions"
027:             android:singleLine="true"
028:             android:id="@+id/textViewTotal"
029:             android:layout_width="match_parent"
030:             android:layout_height="wrap_content"
031:             android:layout_gravity="center"
032:             android:textSize="20sp"
033:             android:layout_margin="4dp" />     
034:           
035:     </LinearLayout>
036:     
037:     <TextView
038:         android:id="@+id/textViewFrom"
039:         android:layout_width="wrap_content"
040:         android:layout_height="wrap_content"
041:         android:layout_margin="4dp"
042:         android:text="@string/labelFrom" />
043: 
044:     <EditText
045:         android:id="@+id/editTextFrom"
046:         android:layout_width="match_parent"
047:         android:layout_height="wrap_content"
048:         android:text="@string/editTextInitialFrom" 
049:         android:inputType="numberDecimal" />
050:     
051:     <TextView
052:         android:id="@+id/textViewTo"
053:         android:layout_width="wrap_content"
054:         android:layout_height="wrap_content"
055:         android:layout_margin="4dp"
056:         android:text="@string/labelTo" />
057: 
058:     <EditText
059:         android:id="@+id/editTextTo"
060:         android:layout_width="match_parent"
061:         android:layout_height="wrap_content"
062:         android:text="@string/editTextInitialTo"         
063:         android:inputType="numberDecimal" />
064:     
065:      <!--  empty line -->
066:      <TextView
067:         android:layout_width="match_parent"
068:         android:layout_height="0dip"
069:         android:layout_weight="1.0" />
070:         
071:     <TableLayout
072:         android:layout_width="match_parent"
073:         android:layout_height="wrap_content" >
074: 
075:         <TableRow android:layout_marginBottom="8dp">
076:             
077:             <TextView
078:                 android:id="@+id/textViewThread01"
079:                 android:layout_width="wrap_content"
080:                 android:layout_height="wrap_content"
081:                 android:textSize="15sp"
082:                 android:layout_margin="4dp"
083:                 android:text="@string/editTextThread01"
084:                 />
085: 
086:             <EditText
087:                 android:id="@+id/editTextThread01"
088:                 android:layout_width="match_parent"
089:                 android:layout_height="wrap_content"
090:                 android:layout_weight="1.0"
091:                 android:layout_margin="4dp"
092:                 android:inputType="none"
093:                 android:textSize="15sp"
094:                 android:background="#CACACA" />
095:             
096:         </TableRow>
097:         
098:         <TableRow  android:layout_marginBottom="8dp">
099:             
100:             <TextView
101:                 android:id="@+id/textViewThread02"
102:                 android:layout_width="wrap_content"
103:                 android:layout_height="wrap_content"
104:                 android:textSize="15sp"
105:                 android:layout_margin="4dp"
106:                 android:text="@string/editTextThread02"
107:                 />
108: 
109:             <EditText
110:                 android:id="@+id/editTextThread02"
111:                 android:layout_width="match_parent"
112:                 android:layout_height="wrap_content"
113:                 android:layout_weight="1.0"
114:                 android:layout_margin="4dp"
115:                 android:inputType="none"
116:                 android:textSize="15sp"
117:                 android:background="#CACACA" />
118:             
119:         </TableRow>
120:         
121:         <TableRow  android:layout_marginBottom="8dp">
122:             
123:             <TextView
124:                 android:id="@+id/textViewThread03"
125:                 android:layout_width="wrap_content"
126:                 android:layout_height="wrap_content"
127:                 android:textSize="15sp"
128:                 android:layout_margin="4dp"
129:                 android:text="@string/editTextThread03"
130:                 />
131: 
132:             <EditText
133:                 android:id="@+id/editTextThread03"
134:                 android:layout_width="match_parent"
135:                 android:layout_height="wrap_content"
136:                 android:layout_weight="1.0"
137:                 android:layout_margin="4dp"
138:                 android:inputType="none"
139:                 android:textSize="15sp"
140:                 android:background="#CACACA" />
141:             
142:         </TableRow>
143:         
144:         <TableRow  android:layout_marginBottom="8dp">
145:             
146:             <TextView
147:                 android:id="@+id/textViewThread04"
148:                 android:layout_width="wrap_content"
149:                 android:layout_height="wrap_content"
150:                 android:textSize="15sp"
151:                 android:layout_margin="4dp"
152:                 android:text="@string/editTextThread04"
153:                 />
154: 
155:             <EditText
156:                 android:id="@+id/editTextThread04"
157:                 android:layout_width="match_parent"
158:                 android:layout_height="wrap_content"
159:                 android:layout_weight="1.0"
160:                 android:layout_margin="4dp"
161:                 android:inputType="none"
162:                 android:textSize="15sp"
163:                 android:background="#CACACA" />    
164:             
165:         </TableRow>
166:     </TableLayout>
167:     
168: </LinearLayout>

Beispiel 1. Datei activity_main.xml: Gestaltung der Oberfläche.


Die diversen Zeichenketten, die in dieser App zum Einsatz gelangen, sind Android-konform in die Ressourcen-XML-Datei strings.xml ausgelagert worden:

01: <?xml version="1.0" encoding="utf-8"?>
02: <resources>
03:     <string name="app_name">MultiThreading Primes</string>
04:     <string name="action_settings">Settings</string>
05:     <string name="hello_world">Hello world!</string>
06:     <string name="button_calc">Calculate</string>
07:     <string name="labelFrom">From:</string>    
08:     <string name="labelTo">To:</string>
09:     <string name="editTextInitialFrom">1</string>
10:     <string name="editTextInitialTo">1000</string>
11:     <string name="editTextThread01">Thread 1:</string>
12:     <string name="editTextThread02">Thread 2:</string>
13:     <string name="editTextThread03">Thread 3:</string>
14:     <string name="editTextThread04">Thread 4:</string>
15: </resources>

Damit fehlen noch die beiden Klassen MainActivity und PrimeNumberCalculator bzgl. ihrer Implementierung in Java:

001: package com.example.multithreadingprimenumbers;
002: 
003: import java.util.Locale;
004: 
005: import android.os.Bundle;
006: import android.app.Activity;
007: import android.view.Menu;
008: 
009: import android.text.Editable;
010: import android.util.Log;
011: import android.view.View;
012: import android.widget.Button;
013: import android.widget.EditText;
014: import android.view.View.OnClickListener;
015: 
016: public class MainActivity extends Activity
017:     implements OnClickListener, UpdateUIHandlerListener, Runnable {
018: 
019:     private long minimum;
020:     private long maximum;
021:     private long total;    
022: 
023:     private final int MaxThreads = 4;
024:     private Thread t;
025:     
026:     private int lastResult;
027:     
028:     private EditText editTextThreadCtrls[];
029:     private EditText editTextFrom;
030:     private EditText editTextTo;
031:     private EditText textViewTotal;
032:     
033:     @Override
034:     protected void onCreate(Bundle savedInstanceState) {
035:         super.onCreate(savedInstanceState);
036:         
037:         this.setContentView(R.layout.activity_main);
038:         
039:         // setup event handlers
040:         Button buttonCalc = (Button) this.findViewById(R.id.buttonCalc);
041:         buttonCalc.setOnClickListener(this);
042:         
043:         // retrieve UI references
044:         this.editTextThreadCtrls = new EditText[MaxThreads];    
045:         
046:         EditText editTextThread01 =
047:                 (EditText) this.findViewById(R.id.editTextThread01);
048:         EditText editTextThread02 =
049:                 (EditText) this.findViewById(R.id.editTextThread02);
050:         EditText editTextThread03 =
051:                 (EditText) this.findViewById(R.id.editTextThread03);
052:         EditText editTextThread04 =
053:                 (EditText) this.findViewById(R.id.editTextThread04);
054:         
055:         this.editTextThreadCtrls[0] = editTextThread01;
056:         this.editTextThreadCtrls[1] = editTextThread02;
057:         this.editTextThreadCtrls[2] = editTextThread03;
058:         this.editTextThreadCtrls[3] = editTextThread04;
059:         
060:         this.editTextFrom = (EditText) this.findViewById(R.id.editTextFrom);
061:         this.editTextTo = (EditText) this.findViewById(R.id.editTextTo); 
062:         this.textViewTotal = (EditText) this.findViewById(R.id.textViewTotal);
063: 
064:         // miscellaneous initializations
065:         this.t = null;
066:         this.minimum = 2;
067:         this.maximum = 1000;
068:         this.lastResult = 0; 
069:     }
070: 
071:     @Override
072:     public boolean onCreateOptionsMenu(Menu menu) {
073:         getMenuInflater().inflate(R.menu.main, menu);
074:         return true;
075:     }
076:     
077:     // @Override
078:     public void onClick(View v) {
079: 
080:         // current prime numbers search is still active
081:         if (this.t != null)
082:             return;
083: 
084:         // retrieve lower and upper limit for prime numbers calculation
085:         Editable editableFrom = this.editTextFrom.getText();
086:         Editable editableTo = this.editTextTo.getText();
087:         this.minimum = Integer.parseInt(editableFrom.toString());
088:         this.maximum = Integer.parseInt(editableTo.toString());
089:         
090:         // clear UI
091:         this.textViewTotal.setText ("");
092:         for (int i = 0; i < MaxThreads; i++)
093:             this.editTextThreadCtrls[i].setText("");
094:         
095:         // asynchronous invocation
096:         this.t = new Thread (this);
097:         this.t.start();
098:     }
099:     
100:     public void run ()
101:     {
102:         // create (single) calculator object
103:         PrimeNumberCalculator calculator = new PrimeNumberCalculator();
104:         calculator.setMinimum(this.minimum);
105:         calculator.setMaximum(this.maximum);
106:         
107:         // register (single) event listener
108:         calculator.setUpdateUIHandlerListener (this);
109:         
110:         this.total = 0;            
111:         this.lastResult = 0; 
112: 
113:         // create and launch threads
114:         Thread[] workers = new Thread [MaxThreads];
115:         for (int i = 0; i < MaxThreads; i++)
116:         {
117:             workers[i] = new Thread(calculator);
118:             workers[i].start();
119:         }
120:         
121:         for (int i = 0; i < MaxThreads; i++)
122:         {
123:             try
124:             {
125:                 workers[i].join();
126:             }
127:             catch (InterruptedException e) {}            
128:         }
129:         
130:         final String s = String.format(Locale.US, "Total: %d ", this.total);
131:         Log.i("PeLo", s.toString());            
132:         
133:         // copy message into text box
134:         this.runOnUiThread(new Runnable() {
135:             @Override
136:             public void run() {
137:                 // editTextMessages.append(response);
138:                 // editTextMessages.append("\n");
139:                 textViewTotal.setText(s);
140:             }
141:         });
142: 
143:         // enable UI
144:         this.t = null;
145:     }
146: 
147:     @Override
148:     public void UpdateUIHandler(long tid, long found) {
149:         
150:         final int currentIndex;
151:         
152:         final String s = String.format("Found %d [TID: %d] ", found, tid);
153:         Log.i("PeLo", s.toString());
154:         
155:         synchronized (this)
156:         {
157:             this.total += found;    
158:             currentIndex = this.lastResult;
159:             this.lastResult ++;
160:         }
161:         
162:         this.runOnUiThread(new Runnable() {
163:             @Override
164:             public void run() {
165:                 editTextThreadCtrls[currentIndex].setText(s);
166:             }
167:         });        
168:     }
169: }

Beispiel 2. Klasse MainActivity.


Der interface-Typ UpdateUIHandlerListener wurde so definiert:

package com.example.multithreadingprimenumbers;

public interface UpdateUIHandlerListener {
    public void UpdateUIHandler (long tid, long found);
}
001: package com.example.multithreadingprimenumbers;
002: 
003: public class PrimeNumberCalculator implements Runnable {
004:     
005:     private long minimum;
006:     private long maximum;
007:     private long next;
008:     
009:     private UpdateUIHandlerListener listener;
010: 
011:     public PrimeNumberCalculator()
012:     {
013:         this.minimum = 2;
014:         this.maximum = 1000;
015:         this.next = this.minimum;
016:         
017:         this.listener = null;
018:     }
019:     
020:     // properties
021:     public long getMinimum () {
022:         return this.minimum;
023:     }
024:     
025:     public void setMinimum (long value) {
026:         this.minimum = value;
027:         this.next = this.minimum;
028:     }
029:     
030:     public long getMaximum () {
031:         return this.maximum;
032:     }
033:     
034:     public void setMaximum (long value) {
035:         this.maximum = value;
036:     }
037:     
038:     // public interface
039:     public void run ()
040:     {
041:         long max;
042:         long next;
043: 
044:         int local = 0;
045: 
046:         synchronized (this)
047:         {
048:             // retrieve upper prime number limit
049:             max = this.maximum;
050: 
051:             // retrieve next prime number candidate
052:             next = this.next;
053: 
054:             // increment current prime number candidate
055:             // for next available client
056:             this.next++;
057:         }
058: 
059:         while (next < max)
060:         {
061:             if (PrimeNumberCalculator.IsPrime(next))
062:             {
063:                 // increment thread specific prime number counter
064:                 local++;
065:             }
066: 
067:             synchronized (this)
068:             {
069:                 // retrieve next prime number candidate
070:                 next = this.next;
071: 
072:                 // adjust current prime number candidate
073:                 // for next available client
074:                 this.next++;
075: 
076:                 // skip even numbers
077:                 if (this.next % 2 == 0)
078:                     this.next++;
079:             }
080:         }
081: 
082:         // calculation done, fire event with results
083:         if (this.listener != null)
084:         {
085:             long tid = Thread.currentThread().getId();
086:             this.listener.UpdateUIHandler(tid, local);
087:         } 
088:     }
089: 
090:     public void setUpdateUIHandlerListener(UpdateUIHandlerListener listener) {
091:         this.listener = listener;
092:     }
093:     
094:     // private helper methods
095:     private static boolean IsPrime(long number)
096:     {
097:         // the smallest prime number is 2
098:         if (number <= 2)
099:             return number == 2;
100: 
101:         // even numbers other than 2 are not prime
102:         if (number % 2 == 0)
103:             return false;
104: 
105:         // check odd divisors from 3 to the square root of the number
106:         long end = (long) Math.sqrt(number);
107:         for (long i = 3; i <= end; i += 2)
108:             if (number % i == 0)
109:                 return false;
110: 
111:         // found prime number
112:         return true;
113:     }
114: }

Beispiel 3. Klasse PrimeNumberCalculator.