[linux-l] [OT]: algorithmische Frage: Sort parallelisieren

[Volker Grabsch]

On Fri, Jan 05, 2007 at 08:24:05AM +0100, Oliver Bandel wrote:
> On Fri, Jan 05, 2007 at 02:14:53AM +0100, Volker Grabsch wrote:
> [...]
> > anrüchig, dass du nur die Algorithmen und nicht die Datenstrukturen
> > in Frage stellst.
> [...]
> 
> Ich finde anrüchig, daß Du Implementierungsdetails besprichst,
> die letztlich mit den selben Algorithemn bearbeitet werden.

Ich dachte, da gäbe es Klärungsbedarf. Und den gibt es wohl auch,
siehe andere Antwort, Stichpunkt Cache.

> Deswegen ging es mir um die Algorithmen. Welche Implementierung ich wähle,
> bzw. wählen würde, hängt von zu vielen Details ab, die noch unbekannt sind.

Ich hatte die Hoffnung, du wüsstest mehr darüber.

> BTW: Wieso betrachtest Du Dateien als Listen?

Schlechte Wortwahl. Ich meinte natürlich Stream, also
Nur-einmal-ablaufbare-Listen. Mehr braucht Merge-Sort ja nicht.

Dennoch kannst du Dateien auch als Listen auffassen. Das effizienteste
Lesen aus Dateien ist ja gerade das sequenzielle Auslesen, nicht der
Random-Access wie beim Arrays.

Kann natürlich sein, dass du meinen Begriff "Liste" für eine "einfach
verkettete Liste" gehalten hast. Das meinte ich natürlich nicht. Die
einfach verkettete Liste hat einige zusätzliche Eigenschaften, die
Arrays z.B. nicht haben.
(etwa das performante Abschneiden des Listenendes und Ransetzen an eine
andere Liste)

> Dateien als freezed Streams betrachtet sind eher als Listen zu betrachten,
> Dateien mit einer Länge und der Positionierbarkeit via File-Poitionierung
> (fsetpos() bzw. seek() und tell() usw.) lassen Dateien eher als Arrays
> betrachten.

Jedes Array lässt sich, in Hinblick auf Performance, als Liste auffassen.
Wobei ich mit Liste nur meine, dass ein sequentieller Zugriff möglich
ist, vorwärts und rückwärts. Betrachtet man nur eine Richtung, rede ich
vom Stream.

Aber "Liste" ist vielfach überladen, du hast dir wahrscheinlich etwas
konkreteres wie eine einfach verkettete Liste vorgestellt. Da haben
wir wohl aneinander vorbei geredet.


Viele Grüße,

    Volker

-- 
Volker Grabsch
---<<(())>>---
Administrator
NotJustHosting GbR