rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12801
|
Dakuan schrieb: D.h. Du kannst es gar nicht mit einem Standardsortieralgorithmus sortieren, ...
Ja, leider. Ich benutze eine abgewandelte Version von Heapsort aus "Algorithmen in C" (von R. Sedgewick). Das brauchte ich mal in eine C Anwendung, wo die Daten schon teilweise vorsortiert waren. Da qsort() weniger optimal.
OK, das ändert die Lange natürlich dramatisch. Habe ich das überlesen oder hast Du das wirklich nicht erwähnt?
Viel Erfolg!
Danke. Ich habe da schonmal ein halbes Jahr auf einen Bugfix warten müssen. Ein feature request wird da wohl als noch weniger dringlich angesehen.
Oft kann man ja so etwas selbst als Patch beisteuern. 😉
|
snafu1
Anmeldungsdatum: 5. September 2007
Beiträge: 2123
Wohnort: Gelsenkirchen
|
Es wäre mit fiesen Tricks schon möglich, auch an private Member zu kommen. Ist halt nur nicht vorgesehen und mit den entsprechenden Gefahren verbunden, sprich: es sollte vermieden werden. Ein Beispiel findest du hier: https://stackoverflow.com/a/8282638
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12801
|
snafu1 schrieb: Es wäre mit fiesen Tricks schon möglich, auch an private Member zu kommen. Ist halt nur nicht vorgesehen und mit den entsprechenden Gefahren verbunden, sprich: es sollte vermieden werden.
Halte ich für eine sehr schlechte Idee nicht nur, weil es gegen die Prinzipien (encapsulation und information hiding) verstößt, sondern ganz praktische Probleme verursacht.
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Habe ich das überlesen oder hast Du das wirklich nicht erwähnt?
Hatte ich noch nicht erwähnt.
Oft kann man ja so etwas selbst als Patch beisteuern. 😉
Hatte ich schonmal gemacht. Der wurde dann noch zweimal abgeändert, weil der Entwickler noch einige Dinge bereinigen wollte. Das dufte ich dann auch testen. Hier traue ich mir das aber nicht zu, weil die zugrunde liegende Klasse Fl_Group Grundlage für etliche andere Klassen ist. Ich kann nicht abschätzen ob das, was ich da mache, ohne Nebenwirkung bleibt.
Es wäre mit fiesen Tricks schon möglich, auch an private Member zu kommen.
Das sieht wirklich tricky aus! Ich könnte natürlich auch so eine fake Klasse basteln, die nur wenige Daten enthält. Viel müsste ich da nicht kopieren:
| class FL_EXPORT Fl_Group : public Fl_Widget {
Fl_Widget** array_;
Fl_Widget* savedfocus_;
Fl_Widget* resizable_;
int children_;
...
|
Wie man sieht ist array_ hier auch ganz am Anfang. Aber wenn in der nächsten FLTK Version die Daten anders sortiert werden, kracht es. Wer soll später so einen Fehler finden? Den einfachen Weg hatte ich gestern schon probiert. Aber da lässt sich g++ nicht überzeugen:
ThumbView.cpp: In member function ‘void ThumbView::downheap(int, int)’:
ThumbView.cpp:1382:61: error: reinterpret_cast from type ‘Fl_Widget* const*’ to type ‘Fl_Widget**’ casts away qualifiers
Fl_Widget ** ar = reinterpret_cast<Fl_Widget **>(array());
^ Ich glaube ich lasse erstmal die Finger davon. Bei nur 1000 Dateien ist beim Sortien noch keine Verzögerung spürbar. Und ich schaue mir ja nicht täglich die Thumbnail Verzeichnisse an. Da macht sich wohl bemerkbar, das die benötigte Zeit stärker als linear anwächst.
|
Neral
Anmeldungsdatum: 3. Oktober 2007
Beiträge: 229
|
Ganz am Anfang: Das, was die FLTK-Leute da machen, finde ich extrem gruselig. Sowohl von der API als auch von der Implementierung. Wenn ich das Problem richtig verstanden habe, wäre auch folgende Lösung möglich:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | // Alle `children` aus der `FL_Group` entfernen (rückwärts, damit O(n)):
auto const length = group.children();
auto widgets = std::vector<FL_Widget*>{};
widgets.reserve(length);
for (int i = 0; i < length; ++i) {
auto const index = length - i - 1;
widgets.push(group.child(index));
group.remove(index);
}
// Sortieren
std::sort(begin(widgets), end(widgets), some_comparator);
// Positionen updaten
for (size_t i = 0; i < size(widgets); ++i) {
widgets[i].position = calculate_position_from_index(i);
}
// Wieder in die `FL_Group` einfügen
for (size_t i = 0; i < size(widgets); ++i) {
group.add(widgets[i]);
}
|
Das vermeidet die O(n² log(n)) Operationen, die man durch wiederholtes Einfügen und Löschen hat. Und jedes Widget wird nur ein Mal geändert anstatt O(n log(n)) Mal (kann wichtig sein, wenn jede Veränderung noch Signale wirft oder ein Redraw auslöst oder so).
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Neral schrieb: Ganz am Anfang: Das, was die FLTK-Leute da machen, finde ich extrem gruselig.
Vielleicht bessert sich das mit der Version 3 (2 wurde eingestellt). Deine Lösung gefällt mir! Da wäre aber zu überlegen, ob man das grundsätzlich so macht, oder erst ab einem bestimmten Schwellwert. Außerdem ist dabei zu berücksichtigen, das ein Fl_Scroll (von Gl_Group abgeleitet) immer 2 children hat, nämlich die beiden Scrollbalken. Die dürfen nicht mit sortiert werden. In diesem Beispiel ist in den Kommentaren zu sehen, dass der Autor damit auch schon seine Probleme hatte. Daher habe ich die Scrollbalken im Konstruktor meiner Klasse einfach mit
| this->child(0)->user_data( (void*)-1 );
|
als unantastbar markiert. Wenn man da alle Elemente sortiert, müssten die Vergleichsfunktionen das berücksichtigen oder sie müssen separat gespeichert weden.
|
Neral
Anmeldungsdatum: 3. Oktober 2007
Beiträge: 229
|
Dakuan schrieb: immer 2 children hat, nämlich die beiden Scrollbalken. Die dürfen nicht mit sortiert werden.
Man könnte die an den Anfang packen und dann die ersten zwei Elemente beim Entfernen auslassen.
|
Neral
Anmeldungsdatum: 3. Oktober 2007
Beiträge: 229
|
Ich hatte Langeweile und hab das von Dakuan verlinkte Beispiel ein wenig angepasst: 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215 | #include <cstddef>
#include <cstdio>
#include <algorithm>
#include <array>
#include <chrono>
#include <functional>
#include <iomanip>
#include <iostream>
#include <ranges>
#include <sstream>
#include <string>
#include <vector>
#include <FL/Fl.H>
#include <FL/Fl_Widget.H>
#include <FL/Fl_Double_Window.H>
#include <FL/Fl_Scroll.H>
#include <FL/Fl_Box.H>
#include <FL/Fl_Pixmap.H>
//
// Demonstrate simple scrollable thumbnail browser
// erco@netcom.com 08/06/02 -- "Draggable Boxes on Scrollable Desk" demo
// erco@seriss.com 06/29/16 -- Rewritten as thumbnail viewer
//
constexpr static char const* cat_xpm[] = {
"50 34 4 1",
" c black",
"o c #ff9900",
"@ c #ffffff",
"# c None",
"##################################################",
"### ############################## ####",
"### ooooo ########################### ooooo ####",
"### oo oo ######################### oo oo ####",
"### oo oo ####################### oo oo ####",
"### oo oo ##################### oo oo ####",
"### oo oo ################### oo oo ####",
"### oo oo oo oo ####",
"### oo oo ooooooooooooooo oo oo ####",
"### oo ooooooooooooooooooooo oo ####",
"### oo ooooooooooooooooooooooooooo ooo ####",
"#### oo ooooooo ooooooooooooo ooooooo oo #####",
"#### oo oooooooo ooooooooooooo oooooooo oo #####",
"##### oo oooooooo ooooooooooooo oooooooo oo ######",
"##### o ooooooooooooooooooooooooooooooo o ######",
"###### ooooooooooooooooooooooooooooooooooo #######",
"##### ooooooooo ooooooooo ooooooooo ######",
"##### oooooooo @@@ ooooooo @@@ oooooooo ######",
"##### oooooooo @ @@ ooooooo @ @@ oooooooo ######",
"##### oooooooo @@ @@ ooooooo @@ @@ oooooooo ######",
"##### oooooooo @@@ ooooooo @@@ oooooooo ######",
"##### ooooooooo ooooooooo ooooooooo ######",
"###### oooooooooooooo oooooooooooooo #######",
"###### oooooooo@@@@@@@ @@@@@@@oooooooo #######",
"###### ooooooo@@@@@@@@@ @@@@@@@@@ooooooo #######",
"####### ooooo@@@@@@@@@@@ @@@@@@@@@@@ooooo ########",
"######### oo@@@@@@@@@@@@ @@@@@@@@@@@@oo ##########",
"########## o@@@@@@ @@@@@ @@@@@ @@@@@@o ###########",
"########### @@@@@@@ @ @@@@@@@ ############",
"############ @@@@@@@@@@@@@@@@@@@@@ #############",
"############## @@@@@@@@@@@@@@@@@ ###############",
"################ @@@@@@@@@ #################",
"#################### #####################",
"##################################################",
};
static Fl_Pixmap cat{cat_xpm};
constexpr auto thumbnail_count = size_t{250'000};
struct Thumbnail final: public Fl_Box {
size_t value;
std::string other_value;
Thumbnail(
int X,
int Y,
int W,
int H,
size_t const value,
std::string other_value,
const char *L = nullptr
): Fl_Box(X, Y, W, H, L), value{value}, other_value{std::move(other_value)} {
this->image(cat);
this->box(FL_UP_BOX);
this->color(FL_GRAY);
}
auto handle(int event) -> int override;
};
struct ThumbnailViewer final: public Fl_Scroll {
using Fl_Scroll::Fl_Scroll;
auto autoarrange() -> void {
constexpr static auto calculate_x_from_index = [](int const i) {
return i % 4 * 100 + 50;
};
constexpr static auto const calculate_y_from_index = [](int const i) {
return i / 4 * 50 + 25;
};
auto const nchildren = this->children();
for (int i = 2; i < nchildren; ++i) {
this->child(i)->position(calculate_x_from_index(i - 2), calculate_y_from_index(i - 2));
}
}
auto sort(auto const compare) -> void {
auto const length = this->children();
auto widgets = std::vector<Thumbnail*>{};
widgets.reserve(length - 2);
for (auto i = 2; i < length; ++i) {
auto const index = length - i - 1;
// FIXME: Highly unsafe, here be dragons. Use `dynamic_cast` for additional safety.
widgets.push_back(static_cast<Thumbnail*>(this->child(index)));
this->remove(index);
}
std::ranges::sort(widgets, compare);
for (auto const widget: widgets) {
this->add(widget);
}
this->autoarrange();
this->damage(0xff);
this->draw();
}
};
auto Thumbnail::handle(int const event) -> int {
auto ret = 0;
switch (event) {
case FL_PUSH:
if (Fl::event_button() == 1) {
ret = 1;
}
break;
case FL_RELEASE:
if (Fl::event_button() == 1 and Fl::event_inside(x(), y(), w(), h())) {
ret = 1;
auto const start = std::chrono::steady_clock::now();
constexpr auto comparing = [](auto const member, auto const& compare) {
return [&compare, member](auto const l, auto const r) {
return compare(l->*member, r->*member);
};
};
switch (this->value % 4) {
case 0:
static_cast<ThumbnailViewer*>(this->parent())->sort(
comparing(&Thumbnail::value, std::greater{})
);
break;
case 1:
static_cast<ThumbnailViewer*>(this->parent())->sort(
comparing(&Thumbnail::value, std::less{})
);
break;
case 2:
static_cast<ThumbnailViewer*>(this->parent())->sort(
comparing(&Thumbnail::other_value, std::greater{})
);
break;
case 3:
static_cast<ThumbnailViewer*>(this->parent())->sort(
comparing(&Thumbnail::other_value, std::less{})
);
break;
}
// Auch möglich, wenn man die Rückgabewerte von `comparing` in eine
// `std::function<auto (Thumbnail*, Thumbnail*) -> bool>` castet:
// static auto const comparators = std::array{
// comparing(&Thumbnail::value, std::greater{}),
// comparing(&Thumbnail::value, std::less{}),
// comparing(&Thumbnail::other_value, std::greater{}),
// comparing(&Thumbnail::other_value, std::less{})
// };
// static_cast<ThumbnailViewer*>(this->parent())->sort(comparators[this->value % 4]);
auto const end = std::chrono::steady_clock::now();
auto const micros =
std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
std::cout << micros << '\n';
}
break;
}
return Fl_Box::handle(event) | ret;
}
auto main() -> int {
auto window = new Fl_Double_Window(600, 400);
auto thumbview = new ThumbnailViewer(10, 10, window->w() - 20, window->h() - 20);
thumbview->box(FL_FLAT_BOX);
thumbview->color(Fl_Color(46));
thumbview->begin();
{
for (auto i = size_t{0}; i < thumbnail_count; ++i) {
auto stream = std::stringstream{};
stream << std::setprecision(6) << i;
auto tn = new Thumbnail(0, 0, 80, 50, i, stream.str());
auto const s = std::to_string(i);
tn->copy_label(s.c_str());
}
}
thumbview->end();
thumbview->autoarrange();
window->end();
window->show();
return Fl::run();
}
|
Das sortiert 250k Thumbnails in ~50 ms (nach size_t sortiert) bzw. 120 ms (nach std::string sortiert).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | » g++ -std=c++20 -Wall -Wextra -pedantic $(fltk-config --cxxflags) -o main main.cpp $(fltk-config --ldflags) && ./main
139287
64613
122785
85424
172124
54677
166526
87383
47192
61534
52745
57246
116226
120013
52535
125212
52961
|
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
ich konnte das bisher nur überfliegen, aber "ein wenig angepasst" ist wohl etwas untertrieben. Mich würde da interessieren was der Autor dazu sagen würde 😉 Ich hatte heute Nachmittag keine Langeweile. War die ganze Zeit damit beschäftigt die Fehlermeldungen des Compilers zu bekämpfen. Jetzt bin ich so weit, dass die weg sind, bekomme aber Abstürze bei den Vergleichsfunktionen. Mit dem Debugger bin ich da noch nicht ran gekommen. Für Heute habe ich die Suche eingestellt. Merkwürdig ist allerdings, das der Absturz erst beim Vergleich N-1 auftritt (Speicherzugriffsfehler).
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Jetzt bin ich platt. Wenn ich meine Thumbboxen nach der Methode von Neral sortiere, geht das so schnell, dass ich bei 25553 Thumbs keine bemerkbare Verzögerung habe! Merkwürdig finde ich allerdings, das fehlerhafte Rückgabewerte einer Vergleichsfunktion zum Absturz führen können indem sort() bei nachfolgenden Vergleichen falsche Zeiger übergibt (0x41 ist bestimmt kein üblicher Wert). | int ThumbView::cmp_mtime_ascend( ThumbBox * t1, ThumbBox * t2 ) {
return t1->get_mtime() < t2->get_mtime();
}
|
Da wo jetzt das "<" war vorher ein Minus Zeichen. Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool.
|