summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/main.c144
1 files changed, 138 insertions, 6 deletions
diff --git a/src/main.c b/src/main.c
index c4e74e4..94bc3d0 100644
--- a/src/main.c
+++ b/src/main.c
@@ -3,10 +3,57 @@
#include <stdint.h>
#include <okelib2/okelib2.h>
+int64_t piss516(int16_t *i,int32_t w);
int64_t piss5(int32_t *i,int32_t w);
int64_t piss4(int32_t *i,int32_t w);
+unsigned long long rfp416(unsigned short *bars, unsigned int n);
+unsigned long long rfp4(unsigned int *bars, unsigned int n);
unsigned long long rfp3(int *bars, int n);
+int64_t piss516(int16_t *i,int32_t w){
+ int64_t v;
+ int64_t q;
+ int16_t l;
+ int16_t m;
+ int32_t y;
+
+ v = 0;
+ l = 0;
+ q = 0;
+ y = 0;
+ int n = 0;
+
+ for(int32_t x = 0;x < w;x++){
+ int16_t c = i[x];
+
+ if(c >= l){
+ v += (int64_t)l*(int64_t)(x-y-1);
+ v -= q;
+ q = 0;
+ y = x;
+ l = c;
+ n++;
+ }else{
+ q += c;
+ }
+ }
+
+ m = l;
+ l = 0;
+
+ for(int32_t x = w-1;i[x] < m;x--){
+ int16_t c = i[x];
+
+ if(c >= l){
+ l = c;
+ }else{
+ v += l-c;
+ }
+ }
+
+ return v;
+}
+
int64_t piss5(int32_t *i,int32_t w){
int64_t v;
int64_t q;
@@ -18,6 +65,7 @@ int64_t piss5(int32_t *i,int32_t w){
l = 0;
q = 0;
y = 0;
+ int n = 0;
for(int32_t x = 0;x < w;x++){
int32_t c = i[x];
@@ -28,6 +76,7 @@ int64_t piss5(int32_t *i,int32_t w){
q = 0;
y = x;
l = c;
+ n++;
}else{
q += c;
}
@@ -88,6 +137,68 @@ int64_t piss4(int32_t *i,int32_t w){
return v;
}
+unsigned long long rfp416(unsigned short *bars, unsigned int n) {
+ unsigned long long bedrock_volume = bars[0];
+ unsigned long long volume = 0;
+ unsigned short highest = bars[0];
+ unsigned int start_i = 0;
+ unsigned int watershed_i = 0;
+
+ for (unsigned int i = 1; i < n; i++) {
+ bedrock_volume += bars[i];
+ if (bars[i] >= highest) {
+ volume += (i - start_i) * (unsigned long long)highest;
+ highest = bars[i];
+ start_i = i;
+ watershed_i = i;
+ }
+ }
+
+ volume += highest;
+
+ highest = bars[n-1];
+ start_i = n-1;
+ for (unsigned int i = n-2; i > watershed_i; i--) {
+ if (bars[i] > highest) {
+ volume += (start_i - i) * (unsigned long long)highest;
+ highest = bars[i];
+ start_i = i;
+ }
+ }
+ return volume + (start_i - watershed_i) * (unsigned long long)highest - bedrock_volume;
+}
+
+unsigned long long rfp4(unsigned int *bars, unsigned int n) {
+ unsigned long long bedrock_volume = bars[0];
+ unsigned long long volume = 0;
+ unsigned long long highest = bars[0];
+ unsigned int start_i = 0;
+ unsigned int watershed_i = 0;
+
+ for (unsigned int i = 1; i < n; i++) {
+ bedrock_volume += bars[i];
+ if (bars[i] >= highest) {
+ volume += (i - start_i) * highest;
+ highest = bars[i];
+ start_i = i;
+ watershed_i = i;
+ }
+ }
+
+ volume += highest;
+
+ highest = bars[n-1];
+ start_i = n-1;
+ for (unsigned int i = n-2; i > watershed_i; i--) {
+ if (bars[i] > highest) {
+ volume += (start_i - i) * highest;
+ highest = bars[i];
+ start_i = i;
+ }
+ }
+ return volume + (start_i - watershed_i) * highest - bedrock_volume;
+}
+
unsigned long long rfp3(int *bars, int n) {
unsigned long long volume = 0;
unsigned long long prev_volume = 0;
@@ -119,16 +230,21 @@ unsigned long long rfp3(int *bars, int n) {
}
int main(int argc,char **argv){
- int32_t *i;
+ uint32_t *i;
+ uint16_t *i16;
int32_t w;
ftimer_t t;
srand(20);
w = 100000000;
- i = malloc(sizeof(int32_t)*w);
+ i = malloc(sizeof(uint32_t)*w);
+ i16 = malloc(sizeof(uint16_t)*w);
if(!i) return 1;
+ if(!i16) return 1;
for(int32_t x = 0;x < w;x++){
- i[x] = (int32_t)rand() & 0xFFFF;
+ i16[x] = (uint16_t)rand() & 0xFFFF;
+ if(x > w/2 && i16[x]>0) i16[x] -= 1;
+ i[x] = i16[x];
}
/*
@@ -139,16 +255,32 @@ int main(int argc,char **argv){
ftimer_init(&t);
+ /*
+ ftimer_zero(&t);
+ printf("rfp3 %14lld ",rfp3(i,w));
+ print_ftimer(&t);
+ */
+
ftimer_zero(&t);
- printf("rfp3 %lld ",rfp3(i,w));
+ printf("rfp4 %14lld ",rfp4(i,w));
print_ftimer(&t);
ftimer_zero(&t);
- printf("piss4 %lld ",piss4(i,w));
+ printf("rfp416 %14lld ",rfp416(i16,w));
+ print_ftimer(&t);
+
+ /*
+ ftimer_zero(&t);
+ printf("piss4 %14lld ",piss4(i,w));
+ print_ftimer(&t);
+ */
+
+ ftimer_zero(&t);
+ printf("piss5 %14lld ",piss5(i,w));
print_ftimer(&t);
ftimer_zero(&t);
- printf("piss5 %lld ",piss5(i,w));
+ printf("piss516 %14lld ",piss516(i16,w));
print_ftimer(&t);
return 0;