Sortierverfahren allgemein

Zitat von Necrowizzard

Im gleich am anfang wird von sortierverfahren gesprochen und dass diese ca 1/4 der "kommerziel benutzten rechenzeit" beanspruchen.

Sortieren ist nach wie vor sehr wichtig, aber das sollte man
schon dazu sagen: diese Studie ist, soweit ich mich erinnere,
schon etwas aelter.

Zitat von Necrowizzard

Wenn ich einen datensatz
...haben der laufend geändert wird, warum sollte ich diesen
sortieren? jedes neue element muss doch dann wieder an der
richtigen stelle eingefügt werden und das braucht doch wohl mehr
aufwand als ein benötigtes element über einen index zu suchen den
ich in einen unsortierten datensatz schreibe...
...dh wenn ich auf die daten um einiges öfters lese als
schreibe)...

Alles anzeigen

In den meisten Faellen wird deutlich oefter gelesen als
geschrieben, so 99:1. Nimm zum Beispiel dieses Forum hier und ueberleg
dir, welche daten da abgespeichert werden und wie das Verhaeltnis
schreiben <> lesen ist. Das ist meiner Erfahrung nach fast bei
den meisten Datensaetzen so.

Und was denn index betrifft: Ich weiss nicht wie du das gemeint hast "den
index in einen unsortierten datensatz schreiben"
Aber auch einen solchen index wirst Du wohl am ende durchsuchen muessen,
was dann wieder sortieren bedeutet.

Zitat von Necrowizzard

und dann noch eine frage zu java: ist es effektiver einen vector
oder ein array zu verwenden wenn ich ab und zu elemente aus dem
array entfernen muss (im moment verwende ich ein array und setze
einen typ-wert auf 0 wenn das element nicht betrachtet werden
soll - wäre es da besser gleich einen vector zu
benutzen?)

Alles anzeigen

zunaechst einmal: verwende statt eines vectors eine Liste, z.b
ArrayList. Da ist kein wirklich wichtiger Unterschied dabei, aber
vector == altes Ueberbleibsel aus der Javasteinzeit , ArrayList == neu.
Es gibt auch noch die LinkedList. Die Unterschiede zwischen den Beiden
macht ihr dann in Algodat gleich als naechstes nach dem Sortieren, wenn
ich mich recht erinnere.

Zu deiner eigentlichen Frage: Ich empfehle dir auf Arrays moeglichst ganz
zu verzichten und nur noch Listen zu verwenden, aus zwei Gruenden:

1. seit einigen Jahren werden die Collections in Java (Listen,
Maps usw.) derart gut von den Compilern optimiert, dass es
praktisch keinen nennenswerten Unterschied mehr macht, was du
verwendest.

2. Stelle niemals Performance ueber lesbaren Code, es sei denn du
hast handfeste Zahlen vor der Nase, die belegen, dass dein Programm
wegen genau diesem Stueck code nicht ausreichend performant ist.

Collections sind in Java meiner Meinung nach leichter zu benutzen
als Arrays: sie sind dynamisch und passen besser in die objektorientierte
Struktur von Java, waehrend Arrays eher haessliche Sonderfaelle sind.

Zitat von Necrowizzard

hm, naja ich weis nicht ob das jetzt
vielleicht etwas zu unwissend für das forum hier ist

Nein, ist es nicht. In gewisser Hinsicht ist Unwissen eine von
zwei moeglichen Voraussetzung dafuer, hier posten zu duerfen.

Zitat von Necrowizzard

aber bei einem array kann ich ohne
große probleme auf alle gespeicherten daten zugreifen (zb.:
testarray[i].pos < irgendwas - wenn testarray ein array von
instanzen einer klasse ist) bei einer list habe ich folgendes
problem: ich kann zwar objekte speichern aber tue mir gerade eben
schwer die einzelnen werte des objektes einzeln auszulesen

Das ist bei Listen nicht komplizierter als bei Arrays:

import java.awt.Point;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;




public class Test{
    public static void main(String[] args){

      //eine beispiel collection aus java.awt.Point
      List<Point> points = new ArrayList<Point>();


      for(int i=0;i<1000;i++){
        points.add(new Point(i, i+100));
      }


      //direkter Zugriff
      System.out.println(points.get(99).getX());


      //loop ueber alle Elemente
      for(Point point : points){
        System.out.println(point);
      }


    }
}

Zitat von Necrowizzard

(ist es in dem fall, dass ich einzelne werte aus den im array gespeicherten objekten auslesen und vergleichen will wirklich sinnvoller mit einer list zu arbeiten?)

Ja. Nicht das es mit arrays nicht auch gehen wuerde, aber
Collections sind vielseitiger. Du kannst z.B. von ihnen erben und
methoden überladen, oder Du kannst eigene Collection entwerfen
die sich dann nahtlos mit den anderen zusammen vertragen usw.
Arrays sind schon brauchbar, aber eben Sonderfälle, und da es
fuer diese Sonderfälle eigentlich keinen Nutzen mehr gibt, halte
ich es fuer klüger, ganz auf sie zu verzichten.

Zitat von Necrowizzard

PS: bezüglich index - im grunde habe
ich einen wert gemeint über den ich das objekt anspreche (vll ist
index da der falsche ausdruck), wir vll klarer wo ich stehe mit
der oben beschriebenen problemsituation

Diese Datenstruktur heisst Dictionary (in Java Map), und die
macht ihr auch in Algodat, gleich nach den Listen. Und du hast
voellig recht: Wenn Du viel schreibst und direkten Zugriff ueber
einen index brauchst, sind Maps sehr effizient (vor allem die
Hashtabellen, in Java java.util.HashMap). Es kommt auch immer auf
den jeweiligen Fall an. Wenn Du eine Liste von Daten hast an die
Du immer nur Elemente anhaengst, und oft darueber iterierst, ist
eine doppelt verlinkte Liste das effizienteste was es gibt.

Allerdings muss man aber am Ende trotzdem auch immer noch sehr
viel sortieren, weil eine sortierter Datensatz in vielen Faellen
einfach vorteilhaft ist. Zum Beispiel um Daten geordnet
anzuzeigen, oder schnell ein Minimum/Maximum berechnnen zu
koennen.

PS: Hier noch eine gute Einfuehrungin das java Collections Framework.

http://java.sun.com/docs/books/tut…ions/index.html