Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Welche Datenstruktur für sortierte Liste fester Größe?
Druckversion
Druckversion
Autor
Kein bestimmter Bereich J Welche Datenstruktur für sortierte Liste fester Größe?
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2434
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-08-24


Ich suche für ein Problem die $N$ besten Lösungen.
Diese werden in mehr oder weniger zufälliger Reihenfolge zusammen mit schlechteren Lösungen generiert.

Welche Datenstruktur kommt da in Frage?

$N$ beträgt eine Million und der Generator "freut" sich, wenn er einen möglichst guten Schätzer für die schlechteste akzeptable Lösung hat.

Ein Array dieser Größe tausende Male neu zu sortieren, um jeweils rund 100 Werte einzufügen, ist algorithmisch ineffizient.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 333
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-08-24


Hallo, wenn ich dein Anliegen richtig verstanden habe, würde ich eine Linked List mit insert-sort nutzen.

Dann sortierst du die neuen Werte einfach richtig ein und biegst die Pointer um.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2434
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-08-24


Einfügen in eine LinkedList liegt in O(n).
Das erscheint mir nicht besser als simples Mergen und nicht wesentlich besser als komplett neu zu sortieren.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1827
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-08-24


Kann man nicht einfach etwas Suchbaum-artiges nehmen, wie es etwa zum Implementieren von Haskells Data.Map verwendet wird?

Die Lösungen würde man also etwa in einem Data.Map Integer (Multiset L) aufsammeln, wobei L der Typ der Lösungen ist, und die Integer-Schlüssel die Bewertungen darstellen.
Ab und zu müsste man "die kleinere Hälfte" (oder so -- jedenfalls so, dass man N Lösungen behält, wenn man vorher mindestens N hatte) wegwerfen, aber soweit ich sehe, ist das nicht so aufwendig, wie ein Neuaufbauen des behaltenen Teilbaums, was in etwa einem Neusortieren entsprechen würde.

(Oder: ganz ähnlich, aber vermutlich simpler: man füllt ein Data.Set (Integer,L), und schmeißt daraus ab und zu etwas raus, etwa, wenn die Größe 2N ist, die untere Hälfte, oder vielleicht auch nach jedem Einfügen das kleinste Element, sobald die Größe mindestens N ist)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 333
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-08-25


Also du hast einen Algorithmus, der dir z. B. 500 Millionen Lösungen generiert. Von diesen 500 Millionen möchtest du nur die besten 1 Million Lösungen haben.

Was für eine Komplexität wünscht du dir denn? Wie stark unterscheiden sich die Ergebnisse der Vergleichsfunktion?

Du kannst die Suche wesentlich beschleunigen, wenn du beispielsweise alle Lösungen ignorierst, die 10% schlechter als die beste Lösung sind. Ich weiß nicht, ob das mit deinen Werten möglich ist. Und du läufst dann Gefahr, dass du nicht eine Million Lösungen bekommst.

Du kannst auch jedes mal eine sortierte Liste von 100.000 Elementen aufbauen und die dann in einem Durchgang in die Hauptliste einfügen.

Am einfachsten wäre es, wenn du den Wertebereich der besten Lösungen kennen würdest.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2434
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-08-25


Gefordert ist bei dem Problem die exakt 1-Million-ste Lösung.
Bekannt ist die beste Lösung.

Aus einer bekannten Lösung kann man schlechtere generieren.
Allerdings nicht notwendigerweise in der richtigen Reihenfolge.


Der Schlaf der Nacht ergab:

Für die Zeit der Iteration wird eine Priorityqueue (Arrayqueue) geführt.
Diese enthält immer die besten N bekannten Lösungen und den genauen Wert der N-ten bekannten Lösung als Schranke.

Sortiert wird (hier konkret unnötig) nur einmal am Ende.



Die Version mit PQ hat jetzt auch in akzeptabler Zeit das Ergebnis geliefert.


Wer selbst spielen will:
Die Aufgabenstellung war, die 1.000.000-ste natürliche Zahl (bzw. ihre Primfaktorzerlegung) mit mindestens 1.000.000 (nicht notwendigerweise unterschiedlichen) Primfaktoren zu finden.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1639
Aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-08-25


>Wer selbst spielen will:
Die Aufgabenstellung war, die 1.000.000-ste natürliche Zahl (bzw. ihre Primfaktorzerlegung) mit mindestens 1.000.000 (nicht notwendigerweise unterschiedlichen) Primfaktoren zu finden.

Mach mal ein Beispiel für 5.

Wirklich Primfaktoren oder auch deren Kombination ? 28=2*2*7, aber auch =2*14 etc

1 Mio Primfaktoren würde die kleinste ja 2^1000000 sein,oder ?


-----------------
Pech in der Liebe , Glück im Verlieren !!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2434
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-08-25


Das ist Problem 615 im Euler-Project.

"""
Consider the natural numbers having at least 5 prime factors, which don't have to be distinct.
Sorting these numbers by size gives a list which starts with:

32=2⋅2⋅2⋅2⋅2
48=2⋅2⋅2⋅2⋅3
64=2⋅2⋅2⋅2⋅2⋅2
72=2⋅2⋅2⋅3⋅3
80=2⋅2⋅2⋅2⋅5
96=2⋅2⋅2⋅2⋅2⋅3
  ...
So, for example, the fifth number with at least 5 prime factors is 80.

Find the millionth number with at least one million prime factors.
Give your answer modulo 123454321.
"""


(Bitte keine Lösungen oder komplette Skripte zur Lösung posten)


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1639
Aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-08-25


Euler-Project ... das dachte ich mir.

Viel Glück !




-----------------
Pech in der Liebe , Glück im Verlieren !!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige hat die Antworten auf ihre/seine Frage gesehen.
DerEinfaeltige hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]