From 01c757e09afbc6ae401a56e9f588b21cea54b613 Mon Sep 17 00:00:00 2001
From: Alexandre Jesus <adbjesus@gmail.com>
Date: Mon, 6 Nov 2017 18:27:28 +0000
Subject: Add nem_ull with shuffle
---
src/common.c | 30 +++++++++++++++++++++++++++++
src/dfs.c | 4 ++--
src/main/nem_ull_shuffle.c | 43 ++++++++++++++++++++++++++++++++++++++++++
src/main/online.c | 2 ++
src/nem_ull.c | 47 ++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 124 insertions(+), 2 deletions(-)
create mode 100644 src/main/nem_ull_shuffle.c
(limited to 'src')
diff --git a/src/common.c b/src/common.c
index 7a8b316..5fc944e 100644
--- a/src/common.c
+++ b/src/common.c
@@ -111,3 +111,33 @@ int len_front(struct front_item * f){
for(N=0;f!=NULL;f=f->next,N++);
return N;
}
+
+/* Shuffle data items starting on a certain index, in place */
+void shuffle_items(struct data * d, int start) {
+ int i, ind;
+ struct item * new_items;
+
+ if (start < 0) return;
+ if (start >= d->N) return;
+
+ new_items = (struct item *)malloc(d->N * sizeof(struct item));
+
+ /* These stay the same */
+ for(i = 0; i < start; i++) {
+ new_items[i].p = d->items[i].p;
+ new_items[i].w = d->items[i].w;
+ }
+
+ /* Shuffle the rest */
+ for(i = start; i < d->N; i++) {
+ ind = rand() % (d->N - i);
+ new_items[i].p = d->items[i+ind].p;
+ new_items[i].w = d->items[i+ind].w;
+ d->items[i+ind].p = d->items[i].p;
+ d->items[i+ind].w = d->items[i].w;
+ }
+
+ /* Replace old array */
+ free(d->items);
+ d->items = new_items;
+}
diff --git a/src/dfs.c b/src/dfs.c
index 12f4ee2..172ac0b 100644
--- a/src/dfs.c
+++ b/src/dfs.c
@@ -88,6 +88,8 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s
* Free leaf;
* Continue;
*/
+ change++;
+
if(tree->depth == data->N) {
front_last->next = new_front_item(tree->values.p, tree->values.w, front_last, NULL);
front_last = front_last->next;
@@ -100,8 +102,6 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s
tree = tree->next;
free(old);
- change++;
-
continue;
}
diff --git a/src/main/nem_ull_shuffle.c b/src/main/nem_ull_shuffle.c
new file mode 100644
index 0000000..e0996ba
--- /dev/null
+++ b/src/main/nem_ull_shuffle.c
@@ -0,0 +1,43 @@
+#include <stdio.h>
+#include <time.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/time.h>
+#include "common.h"
+#include "structs.h"
+#include "nem_ull.h"
+
+int main(int argc, char * argv[]){
+ struct data * data;
+ struct front_item * front = NULL;
+
+ if(argc!=3){
+ printf("Wrong number of arguments!\n");
+ printf("Example usage: %s cut_point data_file\n", argv[0]);
+ return 0;
+ }
+
+ data = input(argv[2]);
+
+ struct timeval tv;
+ gettimeofday(&tv, NULL);
+ srand(tv.tv_sec + tv.tv_usec);
+
+ /* Sort data */
+ qsort(data->items, data->N, sizeof(struct item), cmp_items_ratio);
+
+ printf("%d\n", atoi(argv[1]));
+ clock_t t = clock();
+ front = nem_ull_online_shuffle(data, atoi(argv[1]));
+
+ /* Remove first item from front (only a placeholder) */
+ t = clock() - t;
+ printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(front));
+
+ print_front(front);
+
+ free_front(front);
+ free_data(data);
+
+ return 0;
+}
diff --git a/src/main/online.c b/src/main/online.c
index fbec660..7dec27c 100644
--- a/src/main/online.c
+++ b/src/main/online.c
@@ -13,6 +13,8 @@ int main(int argc, char * argv[]){
struct data * data;
struct front_item * front = NULL;
struct online_return ret;
+ ret.tree = NULL;
+ ret.front = NULL;
if(argc!=6){
printf("Wrong number of arguments!\n");
diff --git a/src/nem_ull.c b/src/nem_ull.c
index f08506b..6405fc2 100644
--- a/src/nem_ull.c
+++ b/src/nem_ull.c
@@ -1,4 +1,5 @@
#include <stdlib.h>
+#include <stdio.h>
#include "nem_ull.h"
#include "structs.h"
#include "common.h"
@@ -16,6 +17,52 @@ struct front_item * nem_ull(struct data * d){
return begin;
}
+struct front_item * nem_ull_online_shuffle(struct data * d, int rand_i){
+ struct front_item * front;
+ struct front_item * ret_front;
+ struct front_item * it;
+ struct front_item * tmp;
+ struct front_item * jt;
+ int i;
+
+ ret_front = new_front_item(0,0,NULL,NULL);
+ front = new_front_item(0,0,NULL,NULL);
+
+ for(i=0;i<d->N;++i){
+ if (i == rand_i) {
+ shuffle_items(d, i);
+ }
+ front = nem_ull_step(front,d,i);
+
+ it = ret_front;
+ jt = front;
+ while(it != NULL && jt != NULL) {
+ if(it->i.p == jt->i.p && it->i.w == jt->i.w) {
+ jt = jt->next;
+ if(it->next == NULL) break;
+ it = it->next;
+ } else if(it->i.p < jt->i.p || (it->i.p == jt->i.p && it->i.w < jt->i.w)) {
+ if(it->next == NULL) break;
+ it = it->next;
+ } else if(it->i.p > jt->i.p || (it->i.p == jt->i.p && it->i.w > jt->i.w)) {
+ tmp = new_front_item(jt->i.p, jt->i.w, it->prev, it);
+ tmp->time = jt->time;
+ tmp->prev->next = tmp;
+ tmp->next->prev = tmp;
+ jt = jt->next;
+ }
+ }
+
+ for(; jt != NULL; jt = jt->next) {
+ it->next = new_front_item(jt->i.p, jt->i.w, it, NULL);
+ it->next->time = jt->time;
+ it = it->next;
+ }
+ }
+
+ return ret_front;
+}
+
struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it){
unsigned long int i,l0t,l1t,n;
double pmax;
--
cgit v1.2.3