Resultate für Übungsblatt 11 (Effizientes Merge Sort)

RZ-Kürzel

Zeit in ms

Prozessor / RAM

Sprache

Verwendete Techniken

pb1042

66.25 s

Intel i5-6300U CPU @ 2.4GHz / 8 GB

Python

Keine (baseline)

pb1042

15.8 s

Intel i5-6300U CPU @ 2.4GHz / 8 GB

Python

Spezialfälle, Einsparung von Kopien, Optimierung Schleife, Variablenumstellungen (Musterlösung)

rg168

3.25s

Intel i5-5350U CPU @ 1.8 Ghz / 8 GB RAM

C

code aus merge_sort.py übernommen / länge der Liste wird weitergegeben am Anfang.

am942

//

Intel i7‑106G7 CPU @ 1.3Ghz / 8 GB

C++

noch nicht

js1632

00.06 s

login.uni-freiburg.de

C++

move-semantik, rekursiv, in-place

os118

2.77 s

Intel Celeron N2930 @ 1.83 GHz / 8 GB

Java

Spezialbehandlung von Runde 1, Abbruch von merge, wenn eine der Listen durch ist

rd116

1.26 s

Intel i5‑10505 CPU @ 3.6Ghz / 16 GB

C++

Keine

ym58

1.408s

Intel i5-7500 CPU @ 3.40GHz × 4 / 16 GB

C++

C++

sh925

0.61s

Apple M1 Pro / 16 GB

C++

Keine

ld314

1.02s

Intel i5-12600K @ 3.70GHz / 16GB

Dart

Keine

sm754

2.12s

Intel i5-6200U CPU @ 2.30GHz / 8 GB

C++

Keine

sn212

28s

Intel i7-1165G7 CPU @ 2.80GHz / 16 GB

Python

Verbesserung der Conditions -> mehr while, Sonderbehandlung von liste länge 2 (vorher ca. 63s)

th357

18.31s

Intel(R) Core(TM) i7-1065G7 CPU @ 1.30GHz

Python

Umstellen von Conditions, Sonderbehandlung von Listen länge 2 und 4 (vorher 46.76s)

cd249

1340ms

AMD Ryzen 7 PRO 5850U / 42GB

C++

Keine

r172834g

0.17s

AMD Ryzen 7 6850U @ 4.70GHz / 16GB @ 6400MT/s

Rust

Nur eine Alloc

jb1454

infty

Apple M1 16 GB

C++

keine

ts593

0.41s

Intel i5-8350U CPU @ 1.70GHz / 8 GB

Rust

Rekursion, Wiederverwenden des temporären Speichers

aj218

50862ms

AMD Ryzen 5 2500u

Python

Verbesserung um überflüssige Schleifen wegzulassen

bd135

876ms

AMD Ryzen 3 4300U

C++

keine Techniken verwendet

rq3

1.8s

Intel Core i5 @ 2,3 GHz/ 8 GB

C++

Rekursion

me316

1.23s

Intel Core i7-4850HQ CPU @ 2.30GHz / 16 GB

C++

Sonderbehandlung der ersten Runde, Vereinfachung/ Umstellung des Codes

ro46

1424ms

Intel Core i7-7700K @ 4.2 GHz / 16 GB

C++

keine

ll407

3.380367s

Intel Core i5 @ 2,3 GHz / 16 GB

C++

Rekursion, weniger unnötige Arrays auf dem Heap

np151

1.088s

Intel Core i7-8565U @ 1.80GHz / 16 GB

Java

rekursion

lh693

4s

Intel(R) Core(TM) i5-10600 CPU @ 3.30GHz / 16 GB

C++

keine (davor 37 Sekunden)

tw282

0.909s

Intel Core I5-1135G7 @ 2.40GHz / 8 GB

C++

C++

aa444

3.38s

11th Gen Intel(R) Core(TM) i7-11700K @ 3.60GHz / 16 GB

C++

Zuvor: 20.59 mit Python, Veränderung: zusätzliche Funktion merge_sort_helper

mp544

46599.51ms

2,3 GHz Dual-Core Intel Core i5 / 8 GB

Python

iterativ und kürzungen

sh887

1.13s

Intel Core i7-1260P @ 2.10 GHz / 16 GB

C++

Keine

pl175

2.54s

Apple M1 8 GB

C++

rekursiv, wenig Kopien

lk792

101ms

CPU Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz / 48 GB

GoLang

Keine

lb426

2.85s

Apple M1 16 GB

Dart

Keine

cs1327

15.25s

AMD Ryzen 5 5600X @ 3.7 GHz / 16 GB

Python

Vermeidung mehrfacher Berechnungen, Ersetzen von Schleifen, Umstrukturierung der Conditions

ll398

10.01s

Apple M1 / 8 GB

Python

komprimieren der for Schleife, Vermeidung unnötig doppelter Berechnungen, im merge eine zweite Liste benutzt und Veränderungen innerhalb der while Schleife

gg122

2603ms

AMD Ryzen 5 2500U

C++

rekursive Implementation

jb1319

952ms

(VM) AMD Ryzen 7 2700X @ 3.7GHz / 2.9 GB

C++

kein Neu-Erzeugen von Sublisten in merge

jw769

2.86 secs

AMD Ryzen 5 3600

C++

alles ist besser, bracht keine 1 1/2 Minuten mehr

ah823

26240 ms

Intel(R) Core(TM) i7-1065G7 CPU @ 1.30GHz 1.50 GHz

Python

Nutzung Hilfsliste, Vermeidung unnötiges mergen und Berechnen

bw133

1120 ms

(WSL) AMD Ryzen 5 5600X @ 3.7 GHz / 32 GB

C

Keine

ae282

47s

Intel(R) Core(TM)i5-10210U CPU @ 1.60GHz

Python

ersetzen der for Schleifen, Mehrfachzuweisung von Variablen, mehrfache Berechnungen vermieden

jt258

7537 ms

AMD Ryzen 7 6800U @2.7 GHz / 16 GB

C++

Keine

jj253

1535.26 ms

AMD Ryzen 5 4500U @ 3.5 Ghz / 8 GB

C

Code aus Vorlage übernommen, bei merge wird die Schleife wenn die erste Bedingung true ist direkt continued.

pb324

2.10s

Intel® Core™ i5-4300U CPU @ 1.90GHz × 4

C++

merge_3 aus Vorlesung 11 übernommen, merge_sort aus Vorlesung 1 übernommen mit simpleren while-Schleifen

fj84

27.91s

Intel Core i7-8550U CPU @ 1.80GHz / 16 GB

Python

merge aus musterlösung übernommen, Python sort für kleine teil arrays, temp array statt dauernder neuzuweisung von left_lst und right_lst und unnötige vergleiche beseitigt.

af465

12.89s

Quad-Core Intel Core i7 @ 3.1GHz / 16 GB

C++

Keine

dk426

2.96s

Intel Core i7 1165g7 @ 2.8GHz / 16 GB

python

merge_sort aus der Lösung von Blatt 01. Variablen einmal zuweisen for schleife ersetzen

ss942

12.18

(VM) Intel Core i7 1360P @ 2,2GHz / 4 GB

Rust

Keine

nw205

1,8 s

Intel Pentium CPU 4425Y @ 1.70GHz / 8 GB

C++

kein Schleifendurchlauf, wenn merge nur Listen der Länge 1 vergleicht.

jz203

30,15

Apple M1 / 8GB

Python

Keine

pt420

40.3 s

Apple M1 / 8 GB

Brainfuck

rekursiv gelöst

jz158

15.05 s

Apple M1 / 8GB

Python

Schleifen reduziert, kopieren vermieden

co112

11.01

Apple M1 / 16GB

Python

Keine, merge_sort from lecture 1

mh756

10.23

Intel(R) Core i5-1240P / 16 GB

C++

lief in einer VM