codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <stdbool.h> #include <stdio.h> #include <stdint.h> #include <stdlib.h> #include "random.h" #include "xtimer.h" #define ARRAY_SIZE (8192) static uint8_t* alloc_random_array(size_t len) { uint8_t* a = malloc(len); for (size_t i = 0; i < len; ++i) a[i] = (random_uint32() & 0x7F); return a; } static bool search_naive(uint8_t key, uint8_t* array, size_t len) { for (uint8_t* end = array + len; array != end; ++array) { if (*array == key) return true; } return false; } static bool search_knuth(uint8_t key, uint8_t* array, size_t len) { array[len] = key; uint8_t* end; for (end = array + len; *array != key; ++array); return array != end; } static void do_benchmark(bool (*search)(uint8_t, uint8_t*, size_t), uint8_t key, uint8_t* array, size_t len, int iterations) { unsigned long total_time = 0; for (int i = 0; i < iterations; ++i) { bool found; xtimer_ticks32_t t[2]; t[0] = xtimer_now(); found = search(key, array, len); t[1] = xtimer_now(); total_time += t[1].ticks32 - t[0].ticks32; printf("found: %d, took %ld ticks\n", found, t[1].ticks32 - t[0].ticks32); } printf("average: %ld ticks\n", total_time / iterations); } int main(void) { uint8_t* array_a = alloc_random_array(ARRAY_SIZE); uint8_t* array_b = alloc_random_array(ARRAY_SIZE + 1); puts("naive search"); do_benchmark(search_naive, 0xFF, array_a, ARRAY_SIZE, 10); puts("knuth search"); do_benchmark(search_knuth, 0xFF, array_b, ARRAY_SIZE, 10); return 0; }
Private
[
?
]
Run code
Submit