Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Exponententabelle (Felder)

Schreiben Sie ein Programm, das 10 000 000 zufällige Potenzierungen mit Basis und Exponent von je 1 bis 100 durchführt (z. B. 1514 oder 4189). Messen Sie die Zeit, die das Programm dafür benötigt.

Schreiben Sie ein zweites Programm, das zunächst eine quadratische Matrix mit allen Potenzresultaten von 1 bis 100 (als Basis und Exponent) füllt und danach 10 000 000 zufällige Potenzierungen mittels Nachschlagen in dieser Tabelle "löst".

Messen Sie die Zeit für das Füllen der Tabelle und das Nachschlagen und diskutieren Sie das Resultat.

Zusatzaufgabe: Ersetzen Sie schließlich die Potenzfunktion durch eine einfache Division und diskutieren Sie auch dieses Resultat.

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

5 Lösung(en)

import java.util.Random;

public class Exponentiationstabelle {
  public static void main(String[] args) {
    new Exponentiationstabelle().top(); }

  long startzeit;
  
  void top() {
      
    start();
    initTabelle(1, 100); // nicht in die Zeiterfassung aufnehmen, da vorab berechnet
    stopp("Inizialisieren");
    
    start();
    nachschlagen(1, 100, 10000000);
    stopp("Nachschlagen  "); 
    
    start();
    potenzieren(1, 100, 10000000);
    stopp("Exponeneten   ");
    
  }
 
  double [][] exponenten;
  void initTabelle(int min, int max) {
      exponenten = new double[max+1][max+1];
      for(int basis = min; basis <= max; basis++) {
          for(int exponent = min; exponent <= max; exponent++) {
              exponenten[basis][exponent] = Math.pow( basis, exponent); }
      }
  }

  void nachschlagen(int min, int max, int times) {
      while(times > 0) {
          int    basis     = zufall(min, max);
          int    exponent  = zufall(min, max);
          double resultat  = exponenten[basis][exponent];
          doSomething(resultat);
          times = times - 1;   }
  }


  void potenzieren(int min, int max, long times) {
    while(times > 0) {
       int    basis     = zufall(min, max);
       int    exponent  = zufall(min, max);
       double resultat  = Math.pow(basis, exponent);
       doSomething(resultat );
       times = times - 1;  }
  }


  public void doSomething(double resultat) {
    
  }


  Random r = new Random();

  int zufall(int min, int max) {
    return (int) (r.nextDouble() * (max - min + 1)) + min; }


  void stopp(String meldung) {
    long time = System.currentTimeMillis() - startzeit;
    System.out.println("Zeit in Millisekunden ("+meldung+"): " + time);  }

  void start() {
    startzeit = System.currentTimeMillis();  }

  
} // end of class Exponentiationstabelle
                
function randomExpon(a, b) {
  return Math.floor((Math.random() * 100) +1) ** Math.floor((Math.random() * 100) +1);
}

function createExponLibrary() {
  let lib = [];
  for (let a = 0; a <= 99; a++) {
    lib.push([]);
    for (let b = 0; b <= 99; b++) lib[a].push(a ** b);
  }
  return lib;
}

function exponLookUp() {
  return library[Math.floor(Math.random() * 99)][Math.floor(Math.random() * 99)];
}

function randomDivision() {
    return Math.floor((Math.random() * 100) +1) / Math.floor((Math.random() * 100) +1);
}

// messungen
let i;

console.time('10 Mio. zufällige Potenzierungen');
for (i = 1; i <= 1e7; i++) randomExpon();
console.timeEnd('10 Mio. zufällige Potenzierungen');

console.time('Tabelle erstellen und 10 Mio. zufällige Abfragen')

console.time('Tabelle erstellen');
let library = createExponLibrary();
console.timeEnd('Tabelle erstellen');

console.time('10 Mio. zufällige Abfragen');
for (i = 1; i <= 1e7; i++) exponLookUp();
console.timeEnd('10 Mio. zufällige Abfragen');

console.timeEnd('Tabelle erstellen und 10 Mio. zufällige Abfragen');

console.time('10 Mio. zufällige Divisionen');
for (i = 1; i <= 1e7; i++) randomDivision();
console.timeEnd('10 Mio. zufällige Divisionen');             // lissalanda@gmx.at

                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

# frozen_string_literal: false

require 'get_process_mem'

def direkte_berechnung
  GC.start
  GC.disable # Garbage collector deaktivieren
  t0 = Time.now
  mb0 = GetProcessMem.new.bytes

  (0..10_000_000).each do |i|
    j = (rand(1..100)**rand(1..100))
    # puts format('%d - %d', i, j)
  end

  t1 = Time.now
  mb1 = GetProcessMem.new.bytes

  puts format('- Einzelberechnungen: %f Sekunden', (t1 - t0))
  puts format('- Speicherbelastung: %d Bytes', (mb1 - mb0))
  GC.enable
end

def tabellenberechnung
  GC.start
  GC.disable
  t0 = Time.now
  mb0 = GetProcessMem.new.bytes

  mat = Array.new(100) { |i| Array.new(100) { |j| i**j } }

  (0..mat.length- 1 ).each do |a|
    (0..mat[a].length - 1).each do |b|
      j = mat[a][b]
    end
  end


  t1 = Time.now

  (0..10_000_000).each do |i|
    j = (mat[rand(0..99)][rand(0..99)])
    # puts format('%d - %d', i, j)
  end

  t2 = Time.now
  mb2 = GetProcessMem.new.bytes

  puts format('- Matrix aufstellen: %f Sekunden', (t1 - t0))
  puts format('- Rechnungen nachschlagen: %f Sekunden', (t2 - t1))
  puts format('- gesamt: %f Sekunden', (t2 - t0))
  puts format('- Speicherbelastung: %d Bytes', (mb2 - mb0))
  GC.enable
end

puts 'direkte Berechnung: '
direkte_berechnung

puts 'Matrixberechung: '
tabellenberechnung

                

Lösung von: Ich Bins (tubs)

// NET 6.x | C# 10.x | VS-2022

using System.Diagnostics;
const int ITER = 10_000_000;
const int MIN = 1;
const int MAX = 100;
var rnd = new Random();

Test(ExpoList); // Aufgabe 1
Test(ExpoPeek); // Aufgabe 2
Test(DivList);  // Zusatzaufgabe

IEnumerable<int> ExpoList() {
    for (int i = 0; i < ITER; i++)
        yield return (int)Math.Pow(rnd.Next(MIN, MAX), rnd.Next(MIN, MAX));
}

IEnumerable<int> DivList() {
    for (int i = 0; i < ITER; i++)
        yield return rnd.Next(MIN, MAX) / rnd.Next(MIN, MAX);
}

int[,] ExpoMatrix() {
    var arr = new int[MAX, MAX];
    for (int i = 0; i < MAX - 1; i++)
        for (int k = 0; k < MAX - 1; k++)
            arr[i, k] = (int)Math.Pow(i, k);
    return arr;
}

IEnumerable<int> ExpoPeek() {
    var exp = ExpoMatrix();
    for (int i = 0; i < ITER; i++) {
        var x = exp[rnd.Next(MIN - 1, MAX - 1), rnd.Next(MIN - 1, MAX - 1)];
        var y = exp[rnd.Next(MIN - 1, MAX - 1), rnd.Next(MIN - 1, MAX - 1)];
        yield return (int)Math.Pow(x, y);
    }
}

void Test(Expo expo) {
    var sw = new Stopwatch();
    sw.Start();
    expo();
    sw.Stop();
    Console.WriteLine($"Zeit '{expo.Method.Name}': {sw.ElapsedTicks}");
}

public delegate IEnumerable<int> Expo();
                

Lösung von: Jens Kelm (@JKooP)

// C++ 14 | VS-2022
#include <iostream>
#include <vector>
#include <chrono>

const size_t ITER{ 10'000'000 };
const size_t MIN{ 1 };
const size_t MAX{ 100 };

struct Expo {
	std::vector<size_t>(*fp)();
};

std::vector<size_t> get_expo_list() {
    std::vector<size_t> tmp{};
	for (size_t i{ 0 }; i < ITER; i++)
		tmp.push_back((size_t)pow(rand() % 100 + 1, rand() % 100 + 1));
	return tmp;
}

std::vector<size_t> get_div_list() {
	std::vector<size_t> tmp{};
	for (size_t i{ 0 }; i < ITER; i++)
		tmp.push_back((rand() % 100 + 1) / (rand() % 100 + 1));
	return tmp;
}

std::vector<std::vector<size_t>> get_expo_matrix() {
	std::vector<std::vector<size_t>> tmp_x{};
	for (size_t i{ 0 }; i < MAX; i++) {
		std::vector<size_t> tmp_y{};
		for (size_t k{ 0 }; k < MAX; k++)
			tmp_y.push_back((size_t)pow(i, k));
		tmp_x.push_back(tmp_y);
	}
	return tmp_x;
}

std::vector<size_t> get_expo_peek() {
	const auto exp{ get_expo_matrix() };
	std::vector<size_t> tmp{};
	for (size_t i{ 0 }; i < ITER; i++) {
		const auto x{ exp[rand() % MAX][rand() % MAX] };
		const auto y{ exp[rand() % MAX][rand() % MAX] };
		tmp.push_back((size_t)pow(x, y));
	}
	return tmp;
}

void test(Expo expo) {
	const auto begin{ std::chrono::high_resolution_clock::now() };
	const auto e = &expo;
	const auto f = e->fp();
	const auto end{ std::chrono::high_resolution_clock::now() };
	std::cout << "Zeit: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << "ms\n";
}

int main() {
	srand((int)time(nullptr));
	const std::vector<Expo>v{ { &get_expo_list }, { &get_div_list }, { &get_expo_peek } };
	for (const auto& i : v) test(i);
}
                

Lösung von: Jens Kelm (@JKooP)

Verifikation/Checksumme:

Das Resultat ist stark davon abhängig, wie die Potenzfunktion optimiert ist. Eine Tabelle kann bis zu 5-fache Geschwindigkeit liefern: "Doppelter Speicher = doppelte Geschwindigkeit".

Wird anstelle einer Potenz eine einfache Multiplikation oder Addition verwendet, kann meist nichts eingespart werden - im Gegenteil: Solche Tabellen verlangsamen das Programm, da das Nachschlagen in Tabellen selbst Multiplikationen und Additionen verwendet.

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 1
Schwierigkeit: k.A.
Webcode: n2gz-2e3u
Autor: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen