Ist Java gut für Sortierroutinen?

[Manuel_H]

Hallo,
ich bin Java-Neuling und habe eine, eigentlich zwei Fragen.

1) Würde man in Java auch Dinge wie Sortierroutinen schreiben? Wie würde so etwas aussehen? Die Datenmenge als Array als Instanzvariable und die Routine als Algorithmus? Wäre so eine Sortierroutine so schnell wie ein Routine in einer prozeduralen Sprache?

2)Angenommen man würde einen Zoo haben. Also z.B. 20 unterschiedliche Klassen von Tieren. Diese Tiere haben so unterschiedliche Fähigkeiten, dass es keinen Sinn macht alle Tiere mit einer Klasse zu erschlagen. Aber alle Tiere können sich bewegen und diese Methode wäre für alle gleich. Müsste man diese Bewegungsmethode in alle 20 Klassen kopieren? In einer prozeduralen Sprache könnte man eine Subroutine schreiben und leicht wiederberwenden, wie ist das in JAVA? Würde man hier viel redundaten Code erzeugen oder gibt es eine elegantere Möglichkeit?

Da Java mit Objekten arbeitet, muss man Tätigkeiten/Aktionen (also Methoden) vielleicht immer mehrfach implementieren falls die in verschiedenen Objekten vorkommen?


Ich hoffe, ich habe mich verständlich ausgedrückt. Vielen Dank für jede Hilfe.

Gruß,
Manuel

 

[ARadauer]

Ist das ein Hausaufgabe?

1. JA, datenmenge als array... kommt auf die datenmenge an. was genau hast du vor?
2. Nein, vererbung benutzen

 

[Asgar13]

Ist das ein Hausaufgabe?

Hört sich für mich auch so an.(Sind Java-Basic fragen)

1.

Würde man in Java auch Dinge wie Sortierroutinen schreiben?

ja, ich meine sogar, das Java schneller wird, als C ab einer bestimmten Datenmenge.(Wobei es schon manche Sortieralgorithmen in Java schon gibt, die man aufrufen kann)

Wie würde so etwas aussehen?

Google danach (java quicksort oder java bubblesort)

Die Datenmenge als Array als Instanzvariable und die Routine als Algorithmus?

ja, siehe ARadauers post.

Wäre so eine Sortierroutine so schnell wie ein Routine in einer prozeduralen Sprache?

Siehe erste Antwort.


2.

Angenommen man würde einen Zoo haben. Also z.B. 20 unterschiedliche Klassen von Tieren. Diese Tiere haben so unterschiedliche Fähigkeiten, dass es keinen Sinn macht alle Tiere mit einer Klasse zu erschlagen. Aber alle Tiere können sich bewegen und diese Methode wäre für alle gleich. Müsste man diese Bewegungsmethode in alle 20 Klassen kopieren? In einer prozeduralen Sprache könnte man eine Subroutine schreiben und leicht wiederberwenden, wie ist das in JAVA? Würde man hier viel redundaten Code erzeugen oder gibt es eine elegantere Möglichkeit?

Vererbung
Jedes Tier erbt dann von der Klasse "Tiere" die Methoden und Eigenschaften.

 

[langhaar!]

Wäre so eine Sortierroutine so schnell wie ein Routine in einer prozeduralen Sprache?

Prozedural? Ich denke, du meinst imperativ. (Imperative Sprache sind eine Obermenge der prozeduralen Sprachen und imperativ wird gegen objektorientiert abgegrenzt)

Die Geschwindigkeit hängt von der jeweiligen Sprache ab. Eine langsame Sprache wie Basic, die interpretiert wird, wird um ein vielfaches langsamer als Java sein. Wird die Sprache komplett zu Maschinencode kompiliert, wird Java vermutlich immer das Nachsehen haben, da Java mit einer Mischform arbeitet (Es wird nicht zu Maschinencode sondern zu einem kompatiblen Bytecode kompiliert und anschließend interpretiert). Entscheidend ist also nicht das Programmierparagdigma sondern die Art der Implementierung. Einer Maschinennahen imperativen Sprache wird Java niemals das Wasser reichen können.

Jedoch gilt gerade beim Sortieren, dass der Algorithmus wesentlich wichtiger als verwendete Sprache ist.
Die Therorie dahinter ist jedoch eher für mathematisch interessierte (oder für Informatikstudenten)
Landau-Symbole ? Wikipedia

 

[langhaar!]

ja, ich meine sogar, das Java schneller wird, als C ab einer bestimmten Datenmenge,

:autsch: Bei gleichem Sortieralgorithmus nicht.

 

[faetzminator]

:autsch: Bei gleichem Sortieralgorithmus nicht.

Die Komplexität (O-Notation) ist gleich, trotzdem ist - wie du bereits geschrieben hast - ein Programm in einer Sprache schneller als in einer anderen.

 

[homer65]

Java hatt schon einen Sortieralgorythmus implemetiert.
Du brauchst das Rad nicht neu erfinden.
Es folgt ein Beispiel wie man mit Java Objekte sortieren kann.
Hier werden Objekte des Typ MP3 sortiert.

[Java]
package pack;
import java.io.*;
import java.util.*;
import java.sql.*;
public class Initialisierung implements Comparator<MP3>
{
...
public void sortMP3List()
{
Collections.sort(Global.mp3List,this);
}
public int compare(MP3 mp3a,MP3 mp3b)
{
int erg = 0;
int i1 = mp3a.getBonus();
String s1 = mp3a.getTextOhneBonus();
int i2 = mp3b.getBonus();
String s2 = mp3b.getTextOhneBonus();
if (Parameter.ansicht)
{
if (i1 > i2) erg = -1;
else if (i1 == i2)
{
if (s1.compareTo(s2) < 0) erg = -1;
else erg = 1;
}
else if (i2 > i1) erg = 1;
}
else
{
int si = s1.compareTo(s2);
if (si < 0) erg = -1;
else if (si > 0) erg = 1;
else
{
if (i1 > i2) erg = -1;
else erg = 1;
}
}
return erg;
}
...
}
[/Java]

 

[langhaar!]

Du brauchst das Rad nicht neu erfinden.

Na ja, die Frage war 'Würde man in Java auch Dinge wie Sortierroutinen schreiben?'.
Zielt meines Erachtens eher auf Machbarkeit und Geschwindigkeit als auf eine konkrete Ausführung.

Dass man ohne trifftigen Grund keine eigene Sortierroutine schreiben sollte, ist richtig. Machbar und halbwegs praktikabel ist es trotzdem (und es kann bei besonderen Rahmenbedingungen auch sinnvoll sein).

 

[homer65]

Ah ok, dann würde ich antworten:
Man schreibt in Java keine Sortieralgorythmen, da es schon einen mitgeliefert gibt.
Und wenn man nicht gerade ein Experte ist, tut man sich schwer einen besseren zu programmieren.

 

[langhaar!]

Da wird dir kaum einer widersprechen :wink:

 

[tfa]

und imperativ wird gegen objektorientiert abgegrenzt

Nein. Java ist z.B. imperativ und OO.

 

[langhaar!]

Nein. Java ist z.B. imperativ und OO.

Imperativ und Objektorientiert sind zwei verschiedenen Programmierparagdimen.
Die Existenz von Hybriden (wie auch C++) widerspricht dem nicht.

Vielmehr können - auch bei Nutzung nur einer (1) Programmiersprache - mehrere Paradigmen gleichzeitig zutreffen.

 

[The_S]

Warum sollte man keinen eigenen Sortieralgorithmus programmieren? Java bringt einen modifizierten Mergesort mit (zumindest via Collections.sort). Was wenn man weitere Kenntnisse über die zu sortierenden Daten hat und deshalb weiß, dass ein Quicksort oder ein Heapsort in der Regel schneller zum Ziel kommen wird? Oder wenn man die zu sortierenden Daten so weit kennt, dass sogar ein Bucket-, Radixsort oder gleich eine Eigenentwicklung sinnvoll erscheint? Was ist mit speziellen Strukturen, die nicht so einfach oder nur mit viel Aufwand über die Standardschnittstellen von Java sortiert werden können? Und was ist mit den ganzen Auszubildenden und Studenten, für die es kaum eine bessere und deutlichere Möglichkeit gibt, sich in Algorithmen und Datenstrukturen einzuarbeiten, als durch die Programmierung von Sortieralgorithmen?

Meiner Meinung nach macht es durchaus Sinn, Sortieralgorithmen in Java zu programmieren. Und die resultierende Geschwindigkeit liegt wohl eher an dem Algorithmus und der gewählten Implementierung und weniger an der Programmiersprache.

 

[tfa]

Imperativ und Objektorientiert sind zwei verschiedenen Programmierparagdimen.

Java ist nunmal imperativ. Was sollte es sonst sein? Deklarativ? Funktional?
Daran ändert auch eine Hybridsprache wie C++ nichts. Oder hab ich dich falsch verstanden?

Einige imperative Programmiersprachen wie z. B. C++ und Java bieten neben prozeduralen Merkmalen auch zusätzliche Sprachmittel, um explizit die objektorientierte Programmierung zu unterstützen.

Sorry für OT

 

[langhaar!]

Java ist nunmal imperativ. Was sollte es sonst sein? Deklarativ? Funktional?

Objektorientiert? Ich denke, es werden mehr Quellen Java Objektorientiertheit zusprechen als die Sprache zu den imperativen zu zählen. Streng genommen wird es ein Hybrid sein; darum auch mein Bezug zu C++. Nichtsdestotrotz wird OO in Theorie und Literatur gegen imperativ als anderes Programmierparagdigma abgegrenzt.

Warum sollte man keinen eigenen Sortieralgorithmus programmieren?

Ich hatte geschrieben, dass es unter besonderen Rahmenbedingungen sinnvoll sein kann, homer65 hatte geschrieben, dass man sich schwertun wird, wenn man kein Experte ist.
Wenn man weiß, was ein Radixsort ist und wie der zu implementieren ist und anhand der vorliegenden Daten berechnen kann, dass es erhebliche Vorteile bringen wird, liegen doch genau die Prämissen vor: man ist Experte und hat besondere Rahmenbedingungen. Da sehe ich keinen Widerspruch.

Und die resultierende Geschwindigkeit liegt wohl eher an dem Algorithmus und der gewählten Implementierung und weniger an der Programmiersprache.

Wird wohl stimmen, wenn es so oft wiederholt wird

 

[tfa]

Ich denke, es werden mehr Quellen Java Objektorientiertheit zusprechen als die Sprache zu den imperativen zu zählen.

Wenn man verstanden hat, was diese Begriffe bedeuten (und dass sie sich nicht ausschließen), wäre nichtmal das ein Problem.

 

[Manuel_H]

Hallo,
erstmal vielen Dank für die ganzen Antworten. Es hat sich bei meinen Fragen nicht um Hausaufgaben gehandelt. Ich bin noch total unwissend was OO programmieren angeht.

Ich war mehr an allgemeinen Aussagen interessiert, ich hatte nicht vor einen Sortieralgorithmus zu implementieren. Ich habe es aber schon ein paar mal gemacht, zum Spaß, aber nicht OO... Es ist einfach lustig sich solche Sachen auszudenken.

Mir ging es auch darum, wie man solche Sachen am besten macht. Z.B. also die Datenmenge gedanklich als Objekt und der Algo als Methode, richtig? Wie gesagt, nur aus Interesse.


Also grüße,
Manuel

 

[oopexpert]

Angenommen man würde einen Zoo haben. Also z.B. 20 unterschiedliche Klassen von Tieren. Diese Tiere haben so unterschiedliche Fähigkeiten, dass es keinen Sinn macht alle Tiere mit einer Klasse zu erschlagen. Aber alle Tiere können sich bewegen und diese Methode wäre für alle gleich. Müsste man diese Bewegungsmethode in alle 20 Klassen kopieren? In einer prozeduralen Sprache könnte man eine Subroutine schreiben und leicht wiederberwenden, wie ist das in JAVA? Würde man hier viel redundaten Code erzeugen oder gibt es eine elegantere Möglichkeit?

Da Java mit Objekten arbeitet, muss man Tätigkeiten/Aktionen (also Methoden) vielleicht immer mehrfach implementieren falls die in verschiedenen Objekten vorkommen?

Ja und Nein oder umgekehrt.

Grundsätzlich ist OO-angewandtes JAVA gesprächiger. Es kann vorkommen, dass Du in JAVA gezwungen wirst sogenannten Boiler-Code zu schreiben. Dies ist bezogen auf Vererbung maßgeblich. JAVA erlaubt nämlich keine Mehrfachvererbung. Mehrfachvererbung wird mit Hilfe von Delegation realisiert, was dann doppelten Code produzieren kann. ABER: es sind nur Einzeiler, die die Delegation realisieren. UND: Wenn Mehrfachvererbung braucht, dann hat man mit sehr hoher Wahrscheinlichkeit ein Design-Problem, womit ich nicht ausschließen möchte, dass es Situationen gibt, in denen man Mehrfachvererbung benötigt.

Bei einfacher Vererbung kann man eine Default-Implementierung einer Methode in der Oberklasse festlegen, und nur in den Spezialfällen diese überschreiben. Damit hält man Redundanzen auch gering. In deinem Beispiel mit dem "Bewegen" reicht eine Default-Implemetierung in der Oberklasse.

Sollten bei 20 abgeleiteten Klassen, 5 die Default-Implementierung nutzen, 5 völlig andersartige Abläufe in einer Methode haben, 10 den gleichen Ablauf innerhalb einer Methode haben, prüfen, ob da nicht noch eine Abstraktionsschicht zwischen muss.

Eins noch zu aufgeblähten Vererbungshierarchien:
Hier sollte nochmal in sich gegangen werden, ob man da nicht besser Metamodellierung vornimmt. Es ist zwar etwas komplizierter, aber man reduziert die Anzahl abgeleiteter Klassen und man braucht keine neue Ableitung, wenn eine neue Tierart hinzukommt.

Etwas Allgemeines:

JAVA ist wesentlich imperative Programmierung. Imperative Programmierung ? Wikipedia
Der Gegenpol von imperativer Programmierung (WIE wird die Lösung berechnet?) ist deklarative Programmierung (WAS wird zur Lösung berechnet?).
Damit hat man beide Extreme zusammen und ALLE Programmiersprachen bewegen sich irgendwo zwischen den beiden Extremen, wobei die Polarisierung meistens klar zu erkennen ist.

JAVA hat auch deklarative Elemente. Bestes Beispiel: Interfaces. Das Problem, was gelöst werden soll, ist die Implementation der deklarierten Methoden im Interface. Es sagt nur, WAS der Compiler sicherstellen soll, aber nicht WIE.

 

[The_S]

Mir ging es auch darum, wie man solche Sachen am besten macht. Z.B. also die Datenmenge gedanklich als Objekt und der Algo als Methode, richtig? Wie gesagt, nur aus Interesse.

Du musst die zu sortierende Daten ja irgendwo abspeichern. Ganz klassisch hast du also ein Array oder eine Liste in denen die zu sortierenden Objekte/primitive Datentypen liegen. Diese Datenstruktur schickst du in eine Methode, die dann mit einem Algo die Sortierung übernimmt. Bspw. Mergesort oder Quicksort.

So muss es aber nicht sein. Sollten die zu sortierenden Daten nach und nach in dein Programm fließen (bspw. Benutzereingaben) kannst du auch schon beim Einfügen der Daten in die Datenstruktur sortieren. Beispiele sind eine sortierte Liste, ein binärer Suchbaum, ein AVL-Baum oder ein SortedSet (Standardjava). Aus diesen Datenstrukturen kannst du dann mit relativ einfachen mitteln eine sortierte Reihenfolge deiner Daten erhalten (sortierte Liste und SortedSet durch einen einfachen Durchlauf, bei den Bäumen mit Hilfe einer sehr einfachen Tiefensuche). Hier ist das Einfügen (und Löschen) in die Datenstruktur etwas (je nach Effizienz der Datenstruktur) langsamer, dafür kannst du in solchen Strukturen deutlich schneller suchen und sortieren. Der komplexe Algorithmus ist hier also das Einfügen und nicht das eigentliche Sortieren.

Ansonsten gibt es bspw. noch einen Heap. Ein Heap ist ebenfalls eine Datenstruktur an dessen Spitze immer das größte oder kleinste Element steht. Auch hier ist das Einfügen von neuen Elementen etwas teurer, dafür kannst du aber auch sofort sehen, welches das aktuell größte/kleinste Element ist. Beim Sortieren wird dann das größte/kleinste Element vom Heap entfernt und durch einen effizienten Algorithmus die spezielle Struktur eines Heaps wiederhergestellt. Hier besteht also die Sortierung zum einen aus einem entsprechenden Einfügealgorithmus, aber auch aus einem "Sortieralgorithmus", der die Struktur des Heaps nach entfernen des größten/kleinsten Elements wiederherstellt. Der Sortieralgorithmus "Heapsort" baut bspw. aus einem gegebenen Array/Liste relativ effizient einen Heap und sortiert dann durch "entnehmen und neu strukturieren"-Operationen.

Du siehst, es gibt sehr viele Möglichkeiten eine Datenmenge sortiert zu bekommen - und das war noch lange nicht alles .

 

[Empire Phoenix]

Nicht zu vergessen CountingSort, wenn der anwendbar ist, ist er meistens auch das beste was geht.
Countingsort ? Wikipedia

 

[Manuel_H]

Danke für die vielen Antworten. Ich habe jetzt schon eine ziemlich genaue Vortsellung davon.

Gruß,
Manuel

 

[Dow Jones]

Und weil's so schön ist: Hier noch ein Link, unter dem Animationen der Arbeitsweisen von verschiedenen Sortieralgorithmen zu sehen sind. Samt Quellcodes in Java.
Sorting Algorithms Demo