Entwickler-Ecke
Alle Sprachen - Alle Plattformen - Integer-Array in C++ initializieren, bestücken und verwenden
Delphi-Laie - Do 16.02.17 16:30
Titel: Integer-Array in C++ initializieren, bestücken und verwenden
Hallo Programmierfreunde!
Zur Zeit beschäftige ich mich damit,
eine C++-Version des Smoothsorts [
http://www.keithschwarz.com/interesting/code/smoothsort/Smoothsort.hh.html] zum Laufen zu bringen. Sofern ich das schaffen sollte, steht kaum noch etwas im Wege, das per Debugger-Unterstützung nach Pascal zu übersetzen.
Es war schon ein großer Erfolg für mich, in einem C++-Projekt in einem Microsoft-Visual-Studio-Projekt (MS VS 2008) den Quelltext, in eine Datei "Smoothsort.hh" geschrieben, per
Quelltext
1:
| #include "Smoothsort.hh" |
erfolgreich einzubinden, das compiliert fehlerfrei (Kontrolle: Den Quelltext verfälschen, und schon gibt es eine Fehlermeldung).
Doch wie diesen Algorithmus nun aufrufen? Ich fragte beim hilfsbereiten Autor Keith Schwarz nach und bekam folgende Antwort:
| Zitat: |
The code I wrote follows the C++ convention of delimiting ranges with iterators. You'd call the function by passing in iterators to the first element of the range to sort and one step past the end of the range to sort. For example:
std::vector<int> values = /* ... */
Smoothsort(values.begin(), values.end()); |
Also, nach Recherche den Code in meinem Projekt zu komplettieren versucht:
Quelltext
1:
2:
| std::vector<int> values = {3,2,1};
Smoothsort(values.begin(), values.end()); |
, aber das compiliert natürlich nicht. Der Kern der Fehlermeldung lautet:
| Zitat: |
error C2552: 'values': Initialisierung nicht zusammengesetzter Typen mit Initialisierungsliste ist nicht möglich
1> 'std::vector<_Ty>': Typen mit einer Basis sind nicht 'aggregate'
1> with
1> [
1> _Ty=int
1> ] |
Damit kann ich leider kaum etwas anfangen.
Kann mir jemand helfen, was da falsch ist, bitte?
Danke im voraus und Gruß
Delphi-Laie
hydemarie - Do 16.02.17 16:40
Was soll denn .hh für eine Endung sein? Hab' ich ja noch nie gesehen. - Aber das sind Stilfragen.
Dein Problem ist, dass du versuchst, ein C++11-Konstrukt mit einem Compiler zu verwenden, der mit C++11 noch nicht viel anfangen kann. Lösung: Nimm einen neueren Compiler.
Th69 - Do 16.02.17 16:58
Für älteres C++:
Quelltext
1:
2:
3:
| const int init_values[] = { 3, 2, 1 };
std::vector<int> values(init_values, init_values+3);
Smoothsort(values.begin(), values.end()); |
oder alternativ die einzelnen Werte per "push_back" hinzufügen:
Quelltext
1:
2:
3:
4:
5:
| std::vector<int> values;
values.push_back(3);
values.push_back(2);
values.push_back(1);
Smoothsort(values.begin(), values.end()); |
Für den Algorithmus selbst bräuchte man noch nicht einmal einen 'vector', da es auch ein Array tut (das ist das tolle an den Iteratoren ;- ):
Quelltext
1:
2:
| int values[] = { 3, 2, 1 };
Smoothsort(values, values+3); |
PS: Korrekter statt "values + 3" wäre in prof. Code "values + sizeof(values)/sizeof(values[0])", aber ich wollte dich damit nicht verwirren.
Delphi-Laie - Do 16.02.17 17:02
Liebe hydemarie, ich habe von C & Co. kaum Ahnung, kann deshalb auch kaum etwas dazu sagen. Ich kann nur sagen, daß es seit Jahr und Tag eine Qual für mich ist (dieses hier ist ein Paradebeispiel) und ich jedesmal heilfroh bin, das rettende Pascal-Ufer wieder erreicht zu haben. Vielen Dank!
Th69, auch Dir besten Dank! Ich werde mich versuchen.
Delphi-Laie - Do 16.02.17 20:01
Th69, speziell für Dich noch mein Zwischenstand: Den Vektor zu (be)füllen, scheinen alle Deine Varianten tauglich, es kompiliert jedenfalls anstandslos. Erst, wenn ich den Prozeduraufruf mit hinzunehme, scheitert das Compilieren mit unterschiedlichen Fehlermeldungen - jedenfalls in meinem VS 2008.
hydemaries Hindweis hat nun zur Folge, daß ich mir ein möglichst neues Visual Studio besorge. Da die Paketgrößen schneller als die Dowonloadgeschwindigkeiten wachsen, hat das eine stunden-/tagelange Download- und später Installationsorgie zur Folge.
Falls ich auch damit nicht weiterkomme, melde ich mich hier noch mal und / oder auch beim o.g. Autor.
Danke nochmals!
Ergänzung: Die "hh"-Dateiendung wurde längst auf "h" reduziert.
hydemarie - Do 16.02.17 20:02
Viel Glück!
Delphi-Laie - Do 16.02.17 20:55
Die Datei wird auch in VS 2008 compiliert, nur der Aufruf von Smoothsort scheitert (schrieb ich schon).
Wenn ich mit
Quelltext
1:
2:
3:
| const int init_values[] = { 3, 2, 1 };
std::vector<int> values(init_values, init_values+3);
Smoothsort(values.begin(), values.end()); |
aufrufe, kommt als Fehlermeldung:
| Zitat: |
c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2039: 'less': Ist kein Element von 'std'
1> .\src\main.cpp(97): Siehe Verweis auf die Instanziierung der gerade kompilierten Funktions-template "void Smoothsort<std::_Vector_iterator<_Ty,_Alloc>>(RandomIterator,RandomIterator)".
1> with
1> [
1> _Ty=int,
1> _Alloc=std::allocator<int>,
1> RandomIterator=std::_Vector_iterator<int,std::allocator<int>>
1> ]
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2065: 'less': nichtdeklarierter Bezeichner
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2275: 'std::iterator_traits<_Iter>::value_type': Ungültige Verwendung dieses Typs als Ausdruck
1> with
1> [
1> _Iter=std::_Vector_iterator<int,std::allocator<int>>
1> ]
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2059: Syntaxfehler: ')' |
.
mit
Quelltext
1:
2:
3:
4:
5:
| std::vector<int> values;
values.push_back(3);
values.push_back(2);
values.push_back(1);
Smoothsort(values.begin(), values.end()); |
kommt:
| Zitat: |
c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2039: 'less': Ist kein Element von 'std'
1> .\src\main.cpp(99): Siehe Verweis auf die Instanziierung der gerade kompilierten Funktions-template "void Smoothsort<std::_Vector_iterator<_Ty,_Alloc>>(RandomIterator,RandomIterator)".
1> with
1> [
1> _Ty=int,
1> _Alloc=std::allocator<int>,
1> RandomIterator=std::_Vector_iterator<int,std::allocator<int>>
1> ]
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2065: 'less': nichtdeklarierter Bezeichner
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2275: 'std::iterator_traits<_Iter>::value_type': Ungültige Verwendung dieses Typs als Ausdruck
1> with
1> [
1> _Iter=std::_Vector_iterator<int,std::allocator<int>>
1> ]
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2059: Syntaxfehler: ')' |
und zuletzt mit
Quelltext
1:
2:
| int values[] = { 3, 2, 1 };
Smoothsort(values, values+3); |
erscheint:
| Zitat: |
c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2039: 'less': Ist kein Element von 'std'
1> .\src\main.cpp(96): Siehe Verweis auf die Instanziierung der gerade kompilierten Funktions-template "void Smoothsort<int*>(RandomIterator,RandomIterator)".
1> with
1> [
1> RandomIterator=int *
1> ]
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2065: 'less': nichtdeklarierter Bezeichner
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2275: 'std::iterator_traits<_Iter>::value_type': Ungültige Verwendung dieses Typs als Ausdruck
1> with
1> [
1> _Iter=int *
1> ] |
Danke, Horst, das kenne ich beides schon. Das Smoothsort in meinem Sortierprogramm habe ich doch von dort. Mich reizt aber eine Variante davon, die ich gefunden zu haben glaube. Und "sound of sorting" hat im Original auch wieder etwas C-artiges, das ich übersetzen müßte. C & Co., wohin man im Internet schaut...
Delphi-Laie - Do 16.02.17 21:24
Du bist ein Schatz, tausenduneinen Dank! Schade, daß man als ein Forumsmitglied nur je ein Dankeschön an je einen Beitrag vergeben kann. Heureka, das war es! Zumindest compiliert es jetzt, den Rest werde ich hoffentlich allein schaffen. Ich habe ja schon einige Erfahrung damit, mich äußerst mühsam durch C-artige Quelltexte zu kämpfen, leider bin ich über das Kampfstadium nie hinausgekommen.
Das hätte ich allein, ohne Hilfe nie herausgefunden.
Postscriptum: Die Downloads der neueren Visual-Studios lasse ich mal besser weiter laufen. Man weiß ja nie...
C# - Fr 17.02.17 10:09
Kleine Anmerkung: man kann auch iterator von Arrays erstellen mit
C#-Quelltext
1:
2:
| int values[] = { 3, 2, 1 };
Smoothsort(std::begin(values), std::end(values)); |
Th69 - Fr 17.02.17 12:06
Aber dies auch nur mit C++11 und höher. ;-)
C# - Fr 17.02.17 12:20
ups hab die version nicht gecheckt :D
Delphi-Laie - Fr 17.02.17 15:45
 Th69 hat folgendes geschrieben  : |
| Aber dies auch nur mit C++11 und höher. ;-) |
Diese Vermutung war / ist richtig: Mein Visual Studio 2008 scheitert(e) diesmal an
Quelltext
1:
| Smoothsort(std::begin(values), std::end(values)); |
Edit: Vielleicht darf ich noch ergänzen, daß von den drei von Th69 genannten Möglichkeiten eine, nämlich die einfachste:
Quelltext
1:
2:
| int values[] = { 3, 2, 1 };
Smoothsort(values, values+3); |
auch schon vom Visual-Studio 2005 compiliert wird, währendhingegen die beiden anderen verweigert werden.
Also werde ich meine "Forschungen" jetzt mit der 2005er Version fortsetzen.
Horst_H - Fr 17.02.17 21:34
Hallo,
ich habe mal die Unit aus
https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Smoothsort#Delphi leicht modifiziert benutzt, um festzustellen, wie sich ein unterschiedlicher Grad an Unordnung auswirkt.
Ich hoffe, ich hatte ein gute Idee zur Erzeugung eines definierten Grades an Unordnung.
Ich habe die Feldindizes [0..n-1] einfach gemischt. Und dann die Feldelemente paarweise getauscht.
Wenn die Indizes also nach dem Mischen 1,23451,78686,123274... sind
werden also erst Feld[1] mit Feld[23451] getauscht, dann Feld[78686] mit Feld[123274] etc pp
Das ist zwar kein optimales Mischen, aber wenigtens tauscht es sehr wahrscheinlich auch bei wenigen Paaren über große Abstände und nicht nur in der Nähe.
Man sieht ja, das komplett gemischt und alle Paare tauschen, im Rahmen der Messgenauigkeit, gleich lang brauchen.
Wenn 409600 von den 1 Mio Paaren getauscht sind, oder andersherum 59,04 % aller Zahlen an ihrem richtigen Platz sind, ist die Laufzeit fast halbiert.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
| Anzahl der LongInt Elemente: 2 Mio
//Laufzeit fpc_64 Bit, fpc_32 Bit etwa 17% langsamer bei double,etwas schneller bei LongInt
Komplett gemischt| Laufzeit
2000000 810 ms
Getauschte Paare | Laufzeit
1000000 807 ms // alle Paare getauscht
800000 703 ms
640000 595 ms
512000 508 ms
409600 429 ms
327680 354 ms
262144 295 ms
209715 250 ms
167772 211 ms
134217 179 ms
107373 152 ms
85898 130 ms
68718 112 ms
54974 98 ms
43979 87 ms
35183 76 ms
28146 69 ms
22516 63 ms
18012 57 ms
14409 53 ms
11527 50 ms
9221 47 ms
7376 45 ms
5900 44 ms
4720 42 ms
3776 41 ms
3020 40 ms
2416 40 ms
1932 39 ms
1545 38 ms
0 36 ms} |
Ich hätte ein normales Heapsort zum Vergleichswert heranziehen sollen....
Gruß Horst
P.S.:
Weshalb der Versuch das C++ Programm nach Delphi zu wandeln.Wo unterschieden die sich denn?
Leonardo Zahlen sind in up und down drin.
EDIT: ich hatte statt double LongInt in dem Versuch, double ist wesentlich langsamer.
Delphi-Laie - Fr 17.02.17 23:36
Ach, da habe ich wohl "schlafende Hunde"..... oder einfach nur Horsts Interesse geweckt
| Horst_H hat folgendes geschrieben : |
Ich hoffe, ich hatte ein gute Idee zur Erzeugung eines definierten Grades an Unordnung.
Ich habe die Feldindizes [0..n-1] einfach gemischt. Und dann die Feldelemente paarweise getauscht.
Wenn die Indizes also nach dem Mischen 1,23451,78686,123274... sind
werden also erst Feld[1] mit Feld[23451] getauscht, dann Feld[78686] mit Feld[123274] etc pp |
Tut mir leid, aber das verstehe ich auch nach wiederholten Lesen nicht. Aber interessieren tut es mich durchaus. Die Erzeugung partieller Unordnung ist nämlich durchaus ein kreatives Betätigungsfeld - jenseits des Sortierens und Mischens, konkret zwischen beiden.
| Horst_H hat folgendes geschrieben : |
| Das ist zwar kein optimales Mischen, aber wenigtens tauscht es sehr wahrscheinlich auch bei wenigen Paaren über große Abstände und nicht nur in der Nähe. |
Das liest sich so, als seiest Du von einer Identpermutation ausgegangen (Feld[1]:=1,Feld[2]:=2 usw.), um dann "suboptimal" zu mischen. Warum nicht gleich das Feld mit Zufallszahlen bestücken?
| Horst_H hat folgendes geschrieben : |
| Ich hätte ein normales Heapsort zum Vergleichswert heranziehen sollen.... |
Bei völliger Unordnung hat Smoothsort keinen Vorteil gegenüber dem einfachen Heapsort. Smoothsort ist ein adaptives (bzw. "adaptiviertes") Heapsort. Meine Wahrnehmung: Je "(vor-)sortierter" eine Menge ist, also je höher das Ordnungsniveau der zu sortierenden Menge ist, desto mehr macht sich ein Geschwindigkeitsvorteil bemerkbar. Sortierte Mengen werden von Smoothsort in O(1) sortiert, d.h., (außer dem "Wahrnehmen" ihrer Sortiertheit durch "Abtastung") "in Ruhe gelassen", während Heapsort das nicht wahrnimmt und ersteinmal wieder alles bunt durcheinanderwürfelt.
| Horst_H hat folgendes geschrieben : |
Weshalb der Versuch das C++ Programm nach Delphi zu wandeln.Wo unterschieden die sich denn?
Leonardo Zahlen sind in up und down drin. |
Du meinst das i.S.v. implizit, nicht wahr? Explizit habe ich sie im genannten Algorithmus noch nicht wahrgenommen. Wie sie implizit wirken und werkeln, ist mir nicht so recht klar. Sie müßten aber durchaus relevant sein, denn diese Zahlenfolge ist ja Bestandteil auch der Urversion dieses Sortierverfahrens.
Damit wären wir schon beim ersten Unterschied, denn Keith Schwarz' Algorithmus verwendet die Leonardozahlen explizit. Er schreibt auch von einigen kleinen Optimierungen. Wenn ich die Übersetzung irgendwann hoffentlich einmal abgeschlossen und es in mein Sortierprogramm integriert / implementiert haben werde, werde ich schlauer sein. Im schlimmsten Falle habe ich einen Eintrag in der Algorithmenliste mehr, der keinerlei Unterschiede zum schon implementierten Smoothsort zeigt. Aber daran glaube ich nicht so recht. Neben der Visualisierung gibt es ja auch die Laufzeitmessung sowie Vergleichs- und Verschiebezähler.
Es ist eben mein Steckenpferd! ;-)
So, und jetzt übersetze ich weiter...
Ergänzung: An Deinen beiden Dateien versuchte ich mich, vergebens. Scheint mit einem Delphi XEx erstellt worden zu sein. Weiterhin überflog ich Deine "Vermischungsmethode", aber es ist wohl schon zu spät für mein (fehlendes) Aufnahmevermögen. Das eine sieht jedenfalls wie Fisher-Yates-Mischen aus, das andere sind wohl Nachbarsvertauschungen.
Horst_H - Sa 18.02.17 11:34
Guten morgen ;-) ,
Du hast schon recht, dieser definierte Grad an Unordnung interessierte mich.
Ich erzeuge ein Feld mit n Elementen, Daten[0..n-1] of tDaten, das schon sortiert ist, indem Daten[i] :=i ist.
Nun erzeuge eich ein Feld Indices[0..n-1] of integer, das auch Indices[i] :=i belegt ist, damit jeder Index auch genau einmal vorkommt.Deshalb fülle ich es nicht direkt mit Zufallszahlen, ala Indices[i] :=random( n ) , sondern mische die Indices.
Ich brauche doch immer die gleiche Ausgangslage für den Versuch, ob ich 10% oder 50% der Daten wegtausche.
Ich kann es nicht brauchen, das zufällig in einem Bereich der Indices immer nur gleiche Paare auftauchen
ala Indices = (....,1,1,2399,2399,5,5....) damit schaffe ich in dem Bereich keine weitere Unordnung und kann keine Aussage treffen.
Natürlich ist die Durchmischung nicht optimal, im Sinne von komplett zufällig.Auch ungemischt kann zufällig entstehen, oder genau 3 Elemente habe ihren Platz geändert.Ich tausche ja immer paarweise und dieses Paar wird nicht mehr verwendet.Dadurch habe ich die Gewissheit, das mit jedem Tausch die Unordnung wächst.
Ich habe mal eine Delphi7 Version daraus gemacht.Freepascal ist doch etwas effektiver, Dank inline von up / down.
Gruß Horst
Edit:
Bild ist ungünstig, bei mehreren Versuchen sind die beiden ersten Laufzeiten fast identisch und nicht 5% auseinander
Delphi-Laie - Sa 18.02.17 12:53
Jo, feines kleine Testprogramm, danke! Ich hätte nur noch den Button während der Laufzeit disabled. Mal schauen, ich werde mich später damit näher beschäftigen.
Allmählich verstehe ich es. Identische Ausgangssituationen kannst aber auch Du insofern nicht schaffen, als daß Du auch Zufallszahlen für die indexbasierten Elementetauschungen verwendest. Klar, die Laufzeit wird immer besser, je mehr sich das Ordnungsniveau der Sortieraufgabe erhöht. Das war ja gerade die geniale Verbesserung des Heapsorts. Herausgekommen ist allerdings leider ein Algorithmus, der auch für einen "gewöhnlichen Informatiker" eine Nummer zu groß sein dürfte, und außerdem die Kinderkrankheit der Instabilität des Heapsorts nicht ablegen konnte. Wenn Herr Dijkstra sie schon nicht beseitigen konnte, dann ist es wohl unmöglich.
Wenn ich mit der Übersetzung einmal fertig werden sollte - ich schätze grob, daß es mindestens noch mehrere Tage dauern wird - wird "meine" Alternativversion zu Deinem Programm hinzukommen, also in dieses integriert werden.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!